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