fork of https://github.com/sourcegraph/zoekt
1// Copyright 2019 Google Inc. All rights reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package index
16
17import (
18 "fmt"
19 "math/rand"
20 "reflect"
21 "testing"
22 "testing/quick"
23
24 "slices"
25
26 "github.com/google/go-cmp/cmp"
27
28 "github.com/sourcegraph/zoekt"
29)
30
31func TestCompressedPostingIterator_limit(t *testing.T) {
32 f := func(nums, limits []uint32) bool {
33 if len(nums) == 0 || len(limits) == 0 {
34 return true
35 }
36
37 nums = sortedUnique(nums)
38 slices.Sort(limits)
39
40 want := doHitIterator(&inMemoryIterator{postings: nums}, limits)
41
42 it := newCompressedPostingIterator(toDeltas(nums), stringToNGram("abc"))
43 got := doHitIterator(it, limits)
44 if !reflect.DeepEqual(want, got) {
45 t.Log(cmp.Diff(want, got))
46 return false
47 }
48 return true
49 }
50 if err := quick.Check(f, nil); err != nil {
51 t.Error(err)
52 }
53}
54
55func doHitIterator(it hitIterator, limits []uint32) []uint32 {
56 var nums []uint32
57 for _, limit := range limits {
58 it.next(limit)
59 nums = append(nums, it.first())
60 }
61 return nums
62}
63
64func BenchmarkCompressedPostingIterator(b *testing.B) {
65 cases := []struct{ size, limitSize int }{
66 {100, 50},
67 {10000, 100},
68 {10000, 1000},
69 {10000, 10000},
70 {100000, 100},
71 {100000, 1000},
72 {100000, 10000},
73 {100000, 100000},
74 }
75 for _, tt := range cases {
76 b.Run(fmt.Sprintf("%d_%d", tt.size, tt.limitSize), func(b *testing.B) {
77 benchmarkCompressedPostingIterator(b, tt.size, tt.limitSize)
78 })
79 }
80}
81
82func benchmarkCompressedPostingIterator(b *testing.B, size, limitsSize int) {
83 nums := genUints32(size)
84 limits := genUints32(limitsSize)
85
86 nums = sortedUnique(nums)
87 slices.Sort(limits)
88
89 ng := stringToNGram("abc")
90 deltas := toDeltas(nums)
91
92 b.ResetTimer()
93
94 for n := 0; n < b.N; n++ {
95 it := newCompressedPostingIterator(deltas, ng)
96 for _, limit := range limits {
97 it.next(limit)
98 _ = it.first()
99 }
100 var s zoekt.Stats
101 it.updateStats(&s)
102 b.SetBytes(s.IndexBytesLoaded)
103 }
104}
105
106func genUints32(size int) []uint32 {
107 // Deterministic for benchmarks
108 r := rand.New(rand.NewSource(int64(size)))
109 nums := make([]uint32, size)
110 for i := range nums {
111 nums[i] = r.Uint32()
112 }
113 return nums
114}