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