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