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 "github.com/sourcegraph/zoekt"
28)
29
30func TestCompressedPostingIterator_limit(t *testing.T) {
31 f := func(nums, limits []uint32) bool {
32 if len(nums) == 0 || len(limits) == 0 {
33 return true
34 }
35
36 nums = sortedUnique(nums)
37 slices.Sort(limits)
38
39 want := doHitIterator(&inMemoryIterator{postings: nums}, limits)
40
41 it := newCompressedPostingIterator(toDeltas(nums), stringToNGram("abc"))
42 got := doHitIterator(it, limits)
43 if !reflect.DeepEqual(want, got) {
44 t.Log(cmp.Diff(want, got))
45 return false
46 }
47 return true
48 }
49 if err := quick.Check(f, nil); err != nil {
50 t.Error(err)
51 }
52}
53
54func doHitIterator(it hitIterator, limits []uint32) []uint32 {
55 var nums []uint32
56 for _, limit := range limits {
57 it.next(limit)
58 nums = append(nums, it.first())
59 }
60 return nums
61}
62
63func BenchmarkCompressedPostingIterator(b *testing.B) {
64 cases := []struct{ size, limitSize int }{
65 {100, 50},
66 {10000, 100},
67 {10000, 1000},
68 {10000, 10000},
69 {100000, 100},
70 {100000, 1000},
71 {100000, 10000},
72 {100000, 100000},
73 }
74 for _, tt := range cases {
75 b.Run(fmt.Sprintf("%d_%d", tt.size, tt.limitSize), func(b *testing.B) {
76 benchmarkCompressedPostingIterator(b, tt.size, tt.limitSize)
77 })
78 }
79}
80
81func benchmarkCompressedPostingIterator(b *testing.B, size, limitsSize int) {
82 nums := genUints32(size)
83 limits := genUints32(limitsSize)
84
85 nums = sortedUnique(nums)
86 slices.Sort(limits)
87
88 ng := stringToNGram("abc")
89 deltas := toDeltas(nums)
90
91 b.ResetTimer()
92
93 for n := 0; n < b.N; n++ {
94 it := newCompressedPostingIterator(deltas, ng)
95 for _, limit := range limits {
96 it.next(limit)
97 _ = it.first()
98 }
99 var s zoekt.Stats
100 it.updateStats(&s)
101 b.SetBytes(s.IndexBytesLoaded)
102 }
103}
104
105func genUints32(size int) []uint32 {
106 // Deterministic for benchmarks
107 r := rand.New(rand.NewSource(int64(size)))
108 nums := make([]uint32, size)
109 for i := range nums {
110 nums[i] = r.Uint32()
111 }
112 return nums
113}