package ksuid import ( "testing" "time" ) func TestCompressedSet(t *testing.T) { tests := []struct { scenario string function func(*testing.T) }{ { scenario: "String", function: testCompressedSetString, }, { scenario: "GoString", function: testCompressedSetGoString, }, { scenario: "sparse", function: testCompressedSetSparse, }, { scenario: "packed", function: testCompressedSetPacked, }, { scenario: "mixed", function: testCompressedSetMixed, }, { scenario: "iterating over a nil compressed set returns no ids", function: testCompressedSetNil, }, { scenario: "concatenating multiple compressed sets is supported", function: testCompressedSetConcat, }, { scenario: "duplicate ids are appear only once in the compressed set", function: testCompressedSetDuplicates, }, { scenario: "building a compressed set with a single id repeated multiple times produces the id only once", function: testCompressedSetSingle, }, { scenario: "iterating over a compressed sequence returns the full sequence", function: testCompressedSetSequence, }, } for _, test := range tests { t.Run(test.scenario, test.function) } } func testCompressedSetString(t *testing.T) { id1, _ := Parse("0uHjRkQoL2JKAQIULPdqqb5fOkk") id2, _ := Parse("0uHjRvkOG5CbtoXW5oCEp3L2xBu") id3, _ := Parse("0uHjSJ4Pe5606kT2XWixK6dirlo") set := Compress(id1, id2, id3) if s := set.String(); s != `["0uHjRkQoL2JKAQIULPdqqb5fOkk", "0uHjRvkOG5CbtoXW5oCEp3L2xBu", "0uHjSJ4Pe5606kT2XWixK6dirlo"]` { t.Error(s) } } func testCompressedSetGoString(t *testing.T) { id1, _ := Parse("0uHjRkQoL2JKAQIULPdqqb5fOkk") id2, _ := Parse("0uHjRvkOG5CbtoXW5oCEp3L2xBu") id3, _ := Parse("0uHjSJ4Pe5606kT2XWixK6dirlo") set := Compress(id1, id2, id3) if s := set.GoString(); s != `ksuid.CompressedSet{"0uHjRkQoL2JKAQIULPdqqb5fOkk", "0uHjRvkOG5CbtoXW5oCEp3L2xBu", "0uHjSJ4Pe5606kT2XWixK6dirlo"}` { t.Error(s) } } func testCompressedSetSparse(t *testing.T) { now := time.Now() times := [100]time.Time{} for i := range times { times[i] = now.Add(time.Duration(i) * 2 * time.Second) } ksuids := [1000]KSUID{} for i := range ksuids { ksuids[i], _ = NewRandomWithTime(times[i%len(times)]) } set := Compress(ksuids[:]...) for i, it := 0, set.Iter(); it.Next(); { if i >= len(ksuids) { t.Error("too many KSUIDs were produced by the set iterator") break } if ksuids[i] != it.KSUID { t.Errorf("bad KSUID at index %d: expected %s but found %s", i, ksuids[i], it.KSUID) } i++ } reportCompressionRatio(t, ksuids[:], set) } func testCompressedSetPacked(t *testing.T) { sequences := [10]Sequence{} for i := range sequences { sequences[i] = Sequence{Seed: New()} } ksuids := [1000]KSUID{} for i := range ksuids { ksuids[i], _ = sequences[i%len(sequences)].Next() } set := Compress(ksuids[:]...) for i, it := 0, set.Iter(); it.Next(); { if i >= len(ksuids) { t.Error("too many KSUIDs were produced by the set iterator") break } if ksuids[i] != it.KSUID { t.Errorf("bad KSUID at index %d: expected %s but found %s", i, ksuids[i], it.KSUID) } i++ } reportCompressionRatio(t, ksuids[:], set) } func testCompressedSetMixed(t *testing.T) { now := time.Now() times := [20]time.Time{} for i := range times { times[i] = now.Add(time.Duration(i) * 2 * time.Second) } sequences := [200]Sequence{} for i := range sequences { seed, _ := NewRandomWithTime(times[i%len(times)]) sequences[i] = Sequence{Seed: seed} } ksuids := [1000]KSUID{} for i := range ksuids { ksuids[i], _ = sequences[i%len(sequences)].Next() } set := Compress(ksuids[:]...) for i, it := 0, set.Iter(); it.Next(); { if i >= len(ksuids) { t.Error("too many KSUIDs were produced by the set iterator") break } if ksuids[i] != it.KSUID { t.Errorf("bad KSUID at index %d: expected %s but found %s", i, ksuids[i], it.KSUID) } i++ } reportCompressionRatio(t, ksuids[:], set) } func testCompressedSetDuplicates(t *testing.T) { sequence := Sequence{Seed: New()} ksuids := [1000]KSUID{} for i := range ksuids[:10] { ksuids[i], _ = sequence.Next() // exercise dedupe on the id range code path } for i := range ksuids[10:] { ksuids[i+10] = New() } for i := 1; i < len(ksuids); i += 4 { ksuids[i] = ksuids[i-1] // generate many dupes } miss := make(map[KSUID]struct{}) uniq := make(map[KSUID]struct{}) for _, id := range ksuids { miss[id] = struct{}{} } set := Compress(ksuids[:]...) for it := set.Iter(); it.Next(); { if _, dupe := uniq[it.KSUID]; dupe { t.Errorf("duplicate id found in compressed set: %s", it.KSUID) } uniq[it.KSUID] = struct{}{} delete(miss, it.KSUID) } if len(miss) != 0 { t.Error("some ids were not found in the compressed set:") for id := range miss { t.Log(id) } } } func testCompressedSetSingle(t *testing.T) { id := New() set := Compress( id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, id, ) n := 0 for it := set.Iter(); it.Next(); { if n != 0 { t.Errorf("too many ids found in the compressed set: %s", it.KSUID) } else if id != it.KSUID { t.Errorf("invalid id found in the compressed set: %s != %s", it.KSUID, id) } n++ } if n == 0 { t.Error("no ids were produced by the compressed set") } } func testCompressedSetSequence(t *testing.T) { seq := Sequence{Seed: New()} ids := make([]KSUID, 5) for i := 0; i < 5; i++ { ids[i], _ = seq.Next() } iter := Compress(ids...).Iter() index := 0 for iter.Next() { if iter.KSUID != ids[index] { t.Errorf("mismatched id at index %d: %s != %s", index, iter.KSUID, ids[index]) } index++ } if index != 5 { t.Errorf("Expected 5 ids, got %d", index) } } func testCompressedSetNil(t *testing.T) { set := CompressedSet(nil) for it := set.Iter(); it.Next(); { t.Errorf("too many ids returned by the iterator of a nil compressed set: %s", it.KSUID) } } func testCompressedSetConcat(t *testing.T) { ksuids := [100]KSUID{} for i := range ksuids { ksuids[i] = New() } set := CompressedSet(nil) set = AppendCompressed(set, ksuids[:42]...) set = AppendCompressed(set, ksuids[42:64]...) set = AppendCompressed(set, ksuids[64:]...) for i, it := 0, set.Iter(); it.Next(); i++ { if ksuids[i] != it.KSUID { t.Errorf("invalid ID at index %d: %s != %s", i, ksuids[i], it.KSUID) } } } func reportCompressionRatio(t *testing.T, ksuids []KSUID, set CompressedSet) { len1 := byteLength * len(ksuids) len2 := len(set) t.Logf("original %d B, compressed %d B (%.4g%%)", len1, len2, 100*(1-(float64(len2)/float64(len1)))) } func BenchmarkCompressedSet(b *testing.B) { ksuids1 := [1000]KSUID{} ksuids2 := [1000]KSUID{} for i := range ksuids1 { ksuids1[i] = New() } ksuids2 = ksuids1 buf := make([]byte, 0, 1024) set := Compress(ksuids2[:]...) b.Run("write", func(b *testing.B) { n := 0 for i := 0; i != b.N; i++ { ksuids2 = ksuids1 buf = AppendCompressed(buf[:0], ksuids2[:]...) n = len(buf) } b.SetBytes(int64(n + len(ksuids2))) }) b.Run("read", func(b *testing.B) { n := 0 for i := 0; i != b.N; i++ { n = 0 for it := set.Iter(); true; { if !it.Next() { n++ break } } } b.SetBytes(int64((n * byteLength) + len(set))) }) }