1package tsm1
2
3import (
4	"fmt"
5	"math/rand"
6	"reflect"
7	"testing"
8	"testing/quick"
9	"time"
10)
11
12func Test_TimeEncoder(t *testing.T) {
13	enc := NewTimeEncoder(1)
14
15	x := []int64{}
16	now := time.Unix(0, 0)
17	x = append(x, now.UnixNano())
18	enc.Write(now.UnixNano())
19	for i := 1; i < 4; i++ {
20		x = append(x, now.Add(time.Duration(i)*time.Second).UnixNano())
21		enc.Write(x[i])
22	}
23
24	b, err := enc.Bytes()
25	if err != nil {
26		t.Fatalf("unexpected error: %v", err)
27	}
28
29	if got := b[0] >> 4; got != timeCompressedRLE {
30		t.Fatalf("Wrong encoding used: expected rle, got %v", got)
31	}
32
33	var dec TimeDecoder
34	dec.Init(b)
35	for i, v := range x {
36		if !dec.Next() {
37			t.Fatalf("Next == false, expected true")
38		}
39
40		if v != dec.Read() {
41			t.Fatalf("Item %d mismatch, got %v, exp %v", i, dec.Read(), v)
42		}
43	}
44}
45
46func Test_TimeEncoder_NoValues(t *testing.T) {
47	enc := NewTimeEncoder(0)
48	b, err := enc.Bytes()
49	if err != nil {
50		t.Fatalf("unexpected error: %v", err)
51	}
52
53	var dec TimeDecoder
54	dec.Init(b)
55	if dec.Next() {
56		t.Fatalf("unexpected next value: got true, exp false")
57	}
58}
59
60func Test_TimeEncoder_One(t *testing.T) {
61	enc := NewTimeEncoder(1)
62	var tm int64
63
64	enc.Write(tm)
65	b, err := enc.Bytes()
66	if err != nil {
67		t.Fatalf("unexpected error: %v", err)
68	}
69
70	if got := b[0] >> 4; got != timeCompressedPackedSimple {
71		t.Fatalf("Wrong encoding used: expected uncompressed, got %v", got)
72	}
73
74	var dec TimeDecoder
75	dec.Init(b)
76	if !dec.Next() {
77		t.Fatalf("unexpected next value: got true, exp false")
78	}
79
80	if tm != dec.Read() {
81		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), tm)
82	}
83}
84
85func Test_TimeEncoder_Two(t *testing.T) {
86	enc := NewTimeEncoder(2)
87	t1 := int64(0)
88	t2 := int64(1)
89	enc.Write(t1)
90	enc.Write(t2)
91
92	b, err := enc.Bytes()
93	if err != nil {
94		t.Fatalf("unexpected error: %v", err)
95	}
96
97	if got := b[0] >> 4; got != timeCompressedRLE {
98		t.Fatalf("Wrong encoding used: expected rle, got %v", got)
99	}
100
101	var dec TimeDecoder
102	dec.Init(b)
103	if !dec.Next() {
104		t.Fatalf("unexpected next value: got true, exp false")
105	}
106
107	if t1 != dec.Read() {
108		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t1)
109	}
110
111	if !dec.Next() {
112		t.Fatalf("unexpected next value: got true, exp false")
113	}
114
115	if t2 != dec.Read() {
116		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t2)
117	}
118}
119
120func Test_TimeEncoder_Three(t *testing.T) {
121	enc := NewTimeEncoder(3)
122	t1 := int64(0)
123	t2 := int64(1)
124	t3 := int64(3)
125
126	enc.Write(t1)
127	enc.Write(t2)
128	enc.Write(t3)
129
130	b, err := enc.Bytes()
131	if err != nil {
132		t.Fatalf("unexpected error: %v", err)
133	}
134
135	if got := b[0] >> 4; got != timeCompressedPackedSimple {
136		t.Fatalf("Wrong encoding used: expected rle, got %v", got)
137	}
138
139	var dec TimeDecoder
140	dec.Init(b)
141	if !dec.Next() {
142		t.Fatalf("unexpected next value: got true, exp false")
143	}
144
145	if t1 != dec.Read() {
146		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t1)
147	}
148
149	if !dec.Next() {
150		t.Fatalf("unexpected next value: got true, exp false")
151	}
152
153	if t2 != dec.Read() {
154		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t2)
155	}
156
157	if !dec.Next() {
158		t.Fatalf("unexpected next value: got true, exp false")
159	}
160
161	if t3 != dec.Read() {
162		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t3)
163	}
164}
165
166func Test_TimeEncoder_Large_Range(t *testing.T) {
167	enc := NewTimeEncoder(2)
168	t1 := int64(1442369134000000000)
169	t2 := int64(1442369135000000000)
170	enc.Write(t1)
171	enc.Write(t2)
172	b, err := enc.Bytes()
173	if err != nil {
174		t.Fatalf("unexpected error: %v", err)
175	}
176
177	if got := b[0] >> 4; got != timeCompressedRLE {
178		t.Fatalf("Wrong encoding used: expected rle, got %v", got)
179	}
180
181	var dec TimeDecoder
182	dec.Init(b)
183	if !dec.Next() {
184		t.Fatalf("unexpected next value: got true, exp false")
185	}
186
187	if t1 != dec.Read() {
188		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t1)
189	}
190
191	if !dec.Next() {
192		t.Fatalf("unexpected next value: got true, exp false")
193	}
194
195	if t2 != dec.Read() {
196		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t2)
197	}
198}
199
200func Test_TimeEncoder_Uncompressed(t *testing.T) {
201	enc := NewTimeEncoder(3)
202	t1 := time.Unix(0, 0).UnixNano()
203	t2 := time.Unix(1, 0).UnixNano()
204
205	// about 36.5yrs in NS resolution is max range for compressed format
206	// This should cause the encoding to fallback to raw points
207	t3 := time.Unix(2, (2 << 59)).UnixNano()
208	enc.Write(t1)
209	enc.Write(t2)
210	enc.Write(t3)
211
212	b, err := enc.Bytes()
213	if err != nil {
214		t.Fatalf("expected error: %v", err)
215	}
216
217	if exp := 25; len(b) != exp {
218		t.Fatalf("length mismatch: got %v, exp %v", len(b), exp)
219	}
220
221	if got := b[0] >> 4; got != timeUncompressed {
222		t.Fatalf("Wrong encoding used: expected uncompressed, got %v", got)
223	}
224
225	var dec TimeDecoder
226	dec.Init(b)
227	if !dec.Next() {
228		t.Fatalf("unexpected next value: got true, exp false")
229	}
230
231	if t1 != dec.Read() {
232		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t1)
233	}
234
235	if !dec.Next() {
236		t.Fatalf("unexpected next value: got true, exp false")
237	}
238
239	if t2 != dec.Read() {
240		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t2)
241	}
242
243	if !dec.Next() {
244		t.Fatalf("unexpected next value: got true, exp false")
245	}
246
247	if t3 != dec.Read() {
248		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), t3)
249	}
250}
251
252func Test_TimeEncoder_RLE(t *testing.T) {
253	enc := NewTimeEncoder(512)
254	var ts []int64
255	for i := 0; i < 500; i++ {
256		ts = append(ts, int64(i))
257	}
258
259	for _, v := range ts {
260		enc.Write(v)
261	}
262
263	b, err := enc.Bytes()
264	if exp := 12; len(b) != exp {
265		t.Fatalf("length mismatch: got %v, exp %v", len(b), exp)
266	}
267
268	if got := b[0] >> 4; got != timeCompressedRLE {
269		t.Fatalf("Wrong encoding used: expected uncompressed, got %v", got)
270	}
271
272	if err != nil {
273		t.Fatalf("unexpected error: %v", err)
274	}
275
276	var dec TimeDecoder
277	dec.Init(b)
278	for i, v := range ts {
279		if !dec.Next() {
280			t.Fatalf("Next == false, expected true")
281		}
282
283		if v != dec.Read() {
284			t.Fatalf("Item %d mismatch, got %v, exp %v", i, dec.Read(), v)
285		}
286	}
287
288	if dec.Next() {
289		t.Fatalf("unexpected extra values")
290	}
291}
292
293func Test_TimeEncoder_Reverse(t *testing.T) {
294	enc := NewTimeEncoder(3)
295	ts := []int64{
296		int64(3),
297		int64(2),
298		int64(0),
299	}
300
301	for _, v := range ts {
302		enc.Write(v)
303	}
304
305	b, err := enc.Bytes()
306	if err != nil {
307		t.Fatalf("unexpected error: %v", err)
308	}
309
310	if got := b[0] >> 4; got != timeUncompressed {
311		t.Fatalf("Wrong encoding used: expected uncompressed, got %v", got)
312	}
313
314	var dec TimeDecoder
315	dec.Init(b)
316	i := 0
317	for dec.Next() {
318		if ts[i] != dec.Read() {
319			t.Fatalf("read value %d mismatch: got %v, exp %v", i, dec.Read(), ts[i])
320		}
321		i++
322	}
323}
324
325func Test_TimeEncoder_220SecondDelta(t *testing.T) {
326	enc := NewTimeEncoder(256)
327	var ts []int64
328	now := time.Now()
329	for i := 0; i < 220; i++ {
330		ts = append(ts, now.Add(time.Duration(i*60)*time.Second).UnixNano())
331	}
332
333	for _, v := range ts {
334		enc.Write(v)
335	}
336
337	b, err := enc.Bytes()
338	if err != nil {
339		t.Fatalf("unexpected error: %v", err)
340	}
341
342	// Using RLE, should get 12 bytes
343	if exp := 12; len(b) != exp {
344		t.Fatalf("unexpected length: got %v, exp %v", len(b), exp)
345	}
346
347	if got := b[0] >> 4; got != timeCompressedRLE {
348		t.Fatalf("Wrong encoding used: expected uncompressed, got %v", got)
349	}
350
351	var dec TimeDecoder
352	dec.Init(b)
353	i := 0
354	for dec.Next() {
355		if ts[i] != dec.Read() {
356			t.Fatalf("read value %d mismatch: got %v, exp %v", i, dec.Read(), ts[i])
357		}
358		i++
359	}
360
361	if i != len(ts) {
362		t.Fatalf("Read too few values: exp %d, got %d", len(ts), i)
363	}
364
365	if dec.Next() {
366		t.Fatalf("expecte Next() = false, got true")
367	}
368}
369
370func Test_TimeEncoder_Quick(t *testing.T) {
371	quick.Check(func(values []int64) bool {
372		// Write values to encoder.
373		enc := NewTimeEncoder(1024)
374		exp := make([]int64, len(values))
375		for i, v := range values {
376			exp[i] = int64(v)
377			enc.Write(exp[i])
378		}
379
380		// Retrieve encoded bytes from encoder.
381		buf, err := enc.Bytes()
382		if err != nil {
383			t.Fatal(err)
384		}
385
386		// Read values out of decoder.
387		got := make([]int64, 0, len(values))
388		var dec TimeDecoder
389		dec.Init(buf)
390		for dec.Next() {
391			if err := dec.Error(); err != nil {
392				t.Fatal(err)
393			}
394			got = append(got, dec.Read())
395		}
396
397		// Verify that input and output values match.
398		if !reflect.DeepEqual(exp, got) {
399			t.Fatalf("mismatch:\n\nexp=%+v\n\ngot=%+v\n\n", exp, got)
400		}
401
402		return true
403	}, nil)
404}
405
406func Test_TimeEncoder_RLESeconds(t *testing.T) {
407	enc := NewTimeEncoder(6)
408	ts := make([]int64, 6)
409
410	ts[0] = int64(1444448158000000000)
411	ts[1] = int64(1444448168000000000)
412	ts[2] = int64(1444448178000000000)
413	ts[3] = int64(1444448188000000000)
414	ts[4] = int64(1444448198000000000)
415	ts[5] = int64(1444448208000000000)
416
417	for _, v := range ts {
418		enc.Write(v)
419	}
420
421	b, err := enc.Bytes()
422	if got := b[0] >> 4; got != timeCompressedRLE {
423		t.Fatalf("Wrong encoding used: expected rle, got %v", got)
424	}
425
426	if err != nil {
427		t.Fatalf("unexpected error: %v", err)
428	}
429
430	var dec TimeDecoder
431	dec.Init(b)
432	for i, v := range ts {
433		if !dec.Next() {
434			t.Fatalf("Next == false, expected true")
435		}
436
437		if v != dec.Read() {
438			t.Fatalf("Item %d mismatch, got %v, exp %v", i, dec.Read(), v)
439		}
440	}
441
442	if dec.Next() {
443		t.Fatalf("unexpected extra values")
444	}
445}
446
447func TestTimeEncoder_Count_Uncompressed(t *testing.T) {
448	enc := NewTimeEncoder(2)
449	t1 := time.Unix(0, 0).UnixNano()
450	t2 := time.Unix(1, 0).UnixNano()
451
452	// about 36.5yrs in NS resolution is max range for compressed format
453	// This should cause the encoding to fallback to raw points
454	t3 := time.Unix(2, (2 << 59)).UnixNano()
455	enc.Write(t1)
456	enc.Write(t2)
457	enc.Write(t3)
458
459	b, err := enc.Bytes()
460	if got := b[0] >> 4; got != timeUncompressed {
461		t.Fatalf("Wrong encoding used: expected rle, got %v", got)
462	}
463
464	if err != nil {
465		t.Fatalf("unexpected error: %v", err)
466	}
467
468	if got, exp := CountTimestamps(b), 3; got != exp {
469		t.Fatalf("count mismatch: got %v, exp %v", got, exp)
470	}
471}
472
473func TestTimeEncoder_Count_RLE(t *testing.T) {
474	enc := NewTimeEncoder(5)
475	ts := make([]int64, 6)
476
477	ts[0] = int64(1444448158000000000)
478	ts[1] = int64(1444448168000000000)
479	ts[2] = int64(1444448178000000000)
480	ts[3] = int64(1444448188000000000)
481	ts[4] = int64(1444448198000000000)
482	ts[5] = int64(1444448208000000000)
483
484	for _, v := range ts {
485		enc.Write(v)
486	}
487
488	b, err := enc.Bytes()
489	if got := b[0] >> 4; got != timeCompressedRLE {
490		t.Fatalf("Wrong encoding used: expected rle, got %v", got)
491	}
492
493	if err != nil {
494		t.Fatalf("unexpected error: %v", err)
495	}
496
497	if got, exp := CountTimestamps(b), len(ts); got != exp {
498		t.Fatalf("count mismatch: got %v, exp %v", got, exp)
499	}
500}
501
502func TestTimeEncoder_Count_Simple8(t *testing.T) {
503	enc := NewTimeEncoder(3)
504	t1 := int64(0)
505	t2 := int64(1)
506	t3 := int64(3)
507
508	enc.Write(t1)
509	enc.Write(t2)
510	enc.Write(t3)
511
512	b, err := enc.Bytes()
513	if err != nil {
514		t.Fatalf("unexpected error: %v", err)
515	}
516
517	if got := b[0] >> 4; got != timeCompressedPackedSimple {
518		t.Fatalf("Wrong encoding used: expected rle, got %v", got)
519	}
520
521	if err != nil {
522		t.Fatalf("unexpected error: %v", err)
523	}
524
525	if got, exp := CountTimestamps(b), 3; got != exp {
526		t.Fatalf("count mismatch: got %v, exp %v", got, exp)
527	}
528}
529
530func TestTimeDecoder_Corrupt(t *testing.T) {
531	cases := []string{
532		"",                 // Empty
533		"\x10\x14",         // Packed: not enough data
534		"\x20\x00",         // RLE: not enough data for starting timestamp
535		"\x2012345678\x90", // RLE: initial timestamp but invalid uvarint encoding
536		"\x2012345678\x7f", // RLE: timestamp, RLE but invalid repeat
537		"\x00123",          // Raw: data length not multiple of 8
538	}
539
540	for _, c := range cases {
541		var dec TimeDecoder
542		dec.Init([]byte(c))
543		if dec.Next() {
544			t.Fatalf("exp next == false, got true")
545		}
546	}
547}
548
549func BenchmarkTimeEncoder(b *testing.B) {
550	enc := NewTimeEncoder(1024)
551	x := make([]int64, 1024)
552	for i := 0; i < len(x); i++ {
553		x[i] = time.Now().UnixNano()
554		enc.Write(x[i])
555	}
556
557	b.ResetTimer()
558	for i := 0; i < b.N; i++ {
559		enc.Bytes()
560		enc.Reset()
561		for i := 0; i < len(x); i++ {
562			enc.Write(x[i])
563		}
564	}
565}
566
567func BenchmarkTimeDecoder_Packed(b *testing.B) {
568	x := make([]int64, 1024)
569	enc := NewTimeEncoder(1024)
570	for i := 0; i < len(x); i++ {
571		x[i] = time.Now().UnixNano()
572		enc.Write(x[i])
573	}
574	bytes, _ := enc.Bytes()
575
576	b.ResetTimer()
577
578	var dec TimeDecoder
579	for i := 0; i < b.N; i++ {
580		dec.Init(bytes)
581		for dec.Next() {
582		}
583	}
584}
585
586func BenchmarkTimeDecoder_RLE(b *testing.B) {
587	x := make([]int64, 1024)
588	enc := NewTimeEncoder(1024)
589	for i := 0; i < len(x); i++ {
590		x[i] = int64(i * 10)
591		enc.Write(x[i])
592	}
593	bytes, _ := enc.Bytes()
594
595	b.ResetTimer()
596
597	b.StopTimer()
598	var dec TimeDecoder
599	b.StartTimer()
600
601	for i := 0; i < b.N; i++ {
602		dec.Init(bytes)
603		for dec.Next() {
604		}
605	}
606}
607
608func BenchmarkTimeBatch_DecodeAllUncompressed(b *testing.B) {
609	benchmarks := []int{
610		5,
611		55,
612		555,
613		1000,
614	}
615
616	values := []int64{
617		-2352281900722994752, 1438442655375607923, -4110452567888190110,
618		-1221292455668011702, -1941700286034261841, -2836753127140407751,
619		1432686216250034552, 3663244026151507025, -3068113732684750258,
620		-1949953187327444488, 3713374280993588804, 3226153669854871355,
621		-2093273755080502606, 1006087192578600616, -2272122301622271655,
622		2533238229511593671, -4450454445568858273, 2647789901083530435,
623		2761419461769776844, -1324397441074946198, -680758138988210958,
624		94468846694902125, -2394093124890745254, -2682139311758778198,
625	}
626
627	for _, size := range benchmarks {
628		rand.Seed(int64(size * 1e3))
629
630		enc := NewTimeEncoder(size)
631		for i := 0; i < size; i++ {
632			enc.Write(values[rand.Int()%len(values)])
633		}
634		bytes, _ := enc.Bytes()
635
636		b.Run(fmt.Sprintf("%d", size), func(b *testing.B) {
637			b.SetBytes(int64(len(bytes)))
638			b.ReportAllocs()
639
640			dst := make([]int64, size)
641			for i := 0; i < b.N; i++ {
642				var dec TimeDecoder
643				dec.Init(bytes)
644				var n int
645				for dec.Next() {
646					dst[n] = dec.Read()
647					n++
648				}
649			}
650		})
651	}
652}
653
654func BenchmarkTimeBatch_DecodeAllPackedSimple(b *testing.B) {
655	benchmarks := []struct {
656		n int
657	}{
658		{5},
659		{55},
660		{555},
661		{1000},
662	}
663	for _, bm := range benchmarks {
664		rand.Seed(int64(bm.n * 1e3))
665
666		enc := NewTimeEncoder(bm.n)
667		for i := 0; i < bm.n; i++ {
668			// Small amount of randomness prevents RLE from being used
669			enc.Write(int64(i*1000) + int64(rand.Intn(10)))
670		}
671		bytes, _ := enc.Bytes()
672
673		b.Run(fmt.Sprintf("%d", bm.n), func(b *testing.B) {
674			b.SetBytes(int64(len(bytes)))
675			b.ReportAllocs()
676
677			dst := make([]int64, bm.n)
678			for i := 0; i < b.N; i++ {
679				var dec TimeDecoder
680				dec.Init(bytes)
681				var n int
682				for dec.Next() {
683					dst[n] = dec.Read()
684					n++
685				}
686			}
687		})
688	}
689}
690
691func BenchmarkTimeBatch_DecodeAllRLE(b *testing.B) {
692	benchmarks := []struct {
693		n     int
694		delta int64
695	}{
696		{5, 10},
697		{55, 10},
698		{555, 10},
699		{1000, 10},
700	}
701	for _, bm := range benchmarks {
702		enc := NewTimeEncoder(bm.n)
703		acc := int64(0)
704		for i := 0; i < bm.n; i++ {
705			enc.Write(acc)
706			acc += bm.delta
707		}
708		bytes, _ := enc.Bytes()
709
710		b.Run(fmt.Sprintf("%d_delta_%d", bm.n, bm.delta), func(b *testing.B) {
711			b.SetBytes(int64(len(bytes)))
712			b.ReportAllocs()
713
714			dst := make([]int64, bm.n)
715			for i := 0; i < b.N; i++ {
716				var dec TimeDecoder
717				dec.Init(bytes)
718				var n int
719				for dec.Next() {
720					dst[n] = dec.Read()
721					n++
722				}
723			}
724		})
725	}
726}
727