1// Copyright (c) 2016-2017 The btcsuite developers
2// Copyright (c) 2016-2017 The Lightning Network Developers
3// Use of this source code is governed by an ISC
4// license that can be found in the LICENSE file.
5
6package gcs_test
7
8import (
9	"encoding/binary"
10	"math/rand"
11	"testing"
12
13	"github.com/btcsuite/btcutil/gcs"
14)
15
16func genRandFilterElements(numElements uint) ([][]byte, error) {
17	testContents := make([][]byte, numElements)
18	for i := range testContents {
19		randElem := make([]byte, 32)
20		if _, err := rand.Read(randElem); err != nil {
21			return nil, err
22		}
23		testContents[i] = randElem
24	}
25
26	return testContents, nil
27}
28
29var (
30	generatedFilter *gcs.Filter
31	filterErr       error
32)
33
34// BenchmarkGCSFilterBuild benchmarks building a filter.
35func BenchmarkGCSFilterBuild50000(b *testing.B) {
36	var testKey [gcs.KeySize]byte
37	for i := 0; i < gcs.KeySize; i += 4 {
38		binary.BigEndian.PutUint32(testKey[i:], rand.Uint32())
39	}
40
41	randFilterElems, genErr := genRandFilterElements(50000)
42	if err != nil {
43		b.Fatalf("unable to generate random item: %v", genErr)
44	}
45
46	b.ReportAllocs()
47	b.ResetTimer()
48
49	var localFilter *gcs.Filter
50	for i := 0; i < b.N; i++ {
51		localFilter, err = gcs.BuildGCSFilter(
52			P, M, key, randFilterElems,
53		)
54		if err != nil {
55			b.Fatalf("unable to generate filter: %v", err)
56		}
57	}
58	generatedFilter = localFilter
59}
60
61// BenchmarkGCSFilterBuild benchmarks building a filter.
62func BenchmarkGCSFilterBuild100000(b *testing.B) {
63	var testKey [gcs.KeySize]byte
64	for i := 0; i < gcs.KeySize; i += 4 {
65		binary.BigEndian.PutUint32(testKey[i:], rand.Uint32())
66	}
67
68	randFilterElems, genErr := genRandFilterElements(100000)
69	if err != nil {
70		b.Fatalf("unable to generate random item: %v", genErr)
71	}
72
73	b.ReportAllocs()
74	b.ResetTimer()
75
76	var localFilter *gcs.Filter
77	for i := 0; i < b.N; i++ {
78		localFilter, err = gcs.BuildGCSFilter(
79			P, M, key, randFilterElems,
80		)
81		if err != nil {
82			b.Fatalf("unable to generate filter: %v", err)
83		}
84	}
85	generatedFilter = localFilter
86}
87
88var (
89	match bool
90)
91
92// BenchmarkGCSFilterMatch benchmarks querying a filter for a single value.
93func BenchmarkGCSFilterMatch(b *testing.B) {
94	filter, err := gcs.BuildGCSFilter(P, M, key, contents)
95	if err != nil {
96		b.Fatalf("Failed to build filter")
97	}
98
99	b.ReportAllocs()
100	b.ResetTimer()
101
102	var localMatch bool
103	for i := 0; i < b.N; i++ {
104		localMatch, err = filter.Match(key, []byte("Nate"))
105		if err != nil {
106			b.Fatalf("unable to match filter: %v", err)
107		}
108
109		localMatch, err = filter.Match(key, []byte("Nates"))
110		if err != nil {
111			b.Fatalf("unable to match filter: %v", err)
112		}
113	}
114	match = localMatch
115}
116
117var (
118	randElems1, _        = genRandFilterElements(1)
119	randElems10, _       = genRandFilterElements(10)
120	randElems100, _      = genRandFilterElements(100)
121	randElems1000, _     = genRandFilterElements(1000)
122	randElems10000, _    = genRandFilterElements(10000)
123	randElems100000, _   = genRandFilterElements(100000)
124	randElems1000000, _  = genRandFilterElements(1000000)
125	randElems10000000, _ = genRandFilterElements(10000000)
126
127	filterElems1000, _  = genRandFilterElements(1000)
128	filter1000, _       = gcs.BuildGCSFilter(P, M, key, filterElems1000)
129	filterElems5000, _  = genRandFilterElements(5000)
130	filter5000, _       = gcs.BuildGCSFilter(P, M, key, filterElems5000)
131	filterElems10000, _ = genRandFilterElements(10000)
132	filter10000, _      = gcs.BuildGCSFilter(P, M, key, filterElems10000)
133)
134
135// matchAnyBenchmarks contains combinations of random filters and queries used
136// to measure performance of various MatchAny implementations.
137var matchAnyBenchmarks = []struct {
138	name   string
139	query  [][]byte
140	filter *gcs.Filter
141}{
142	{"q100-f1K", randElems100, filter1000},
143	{"q1K-f1K", randElems1000, filter1000},
144	{"q10K-f1K", randElems10000, filter1000},
145	{"q100K-f1K", randElems100000, filter1000},
146	{"q1M-f1K", randElems1000000, filter1000},
147	{"q10M-f1K", randElems10000000, filter1000},
148
149	{"q100-f5K", randElems100, filter5000},
150	{"q1K-f5K", randElems1000, filter5000},
151	{"q10K-f5K", randElems10000, filter5000},
152	{"q100K-f5K", randElems100000, filter5000},
153	{"q1M-f5K", randElems1000000, filter5000},
154	{"q10M-f5K", randElems10000000, filter5000},
155
156	{"q100-f10K", randElems100, filter10000},
157	{"q1K-f10K", randElems1000, filter10000},
158	{"q10K-f10K", randElems10000, filter10000},
159	{"q100K-f10K", randElems100000, filter10000},
160	{"q1M-f10K", randElems1000000, filter10000},
161	{"q10M-f10K", randElems10000000, filter10000},
162}
163
164// BenchmarkGCSFilterMatchAny benchmarks the sort-and-zip MatchAny impl.
165func BenchmarkGCSFilterZipMatchAny(b *testing.B) {
166	for _, test := range matchAnyBenchmarks {
167		b.Run(test.name, func(b *testing.B) {
168			b.ReportAllocs()
169
170			var (
171				localMatch bool
172				err        error
173			)
174
175			for i := 0; i < b.N; i++ {
176				localMatch, err = test.filter.ZipMatchAny(
177					key, test.query,
178				)
179				if err != nil {
180					b.Fatalf("unable to match filter: %v", err)
181				}
182			}
183			match = localMatch
184		})
185	}
186}
187
188// BenchmarkGCSFilterMatchAny benchmarks the hash-join MatchAny impl.
189func BenchmarkGCSFilterHashMatchAny(b *testing.B) {
190	for _, test := range matchAnyBenchmarks {
191		b.Run(test.name, func(b *testing.B) {
192			b.ReportAllocs()
193
194			var (
195				localMatch bool
196				err        error
197			)
198
199			for i := 0; i < b.N; i++ {
200				localMatch, err = test.filter.HashMatchAny(
201					key, test.query,
202				)
203				if err != nil {
204					b.Fatalf("unable to match filter: %v", err)
205				}
206			}
207			match = localMatch
208		})
209	}
210}
211
212// BenchmarkGCSFilterMatchAny benchmarks the hybrid MatchAny impl.
213func BenchmarkGCSFilterMatchAny(b *testing.B) {
214	for _, test := range matchAnyBenchmarks {
215		b.Run(test.name, func(b *testing.B) {
216			b.ReportAllocs()
217
218			var (
219				localMatch bool
220				err        error
221			)
222
223			for i := 0; i < b.N; i++ {
224				localMatch, err = test.filter.MatchAny(
225					key, test.query,
226				)
227				if err != nil {
228					b.Fatalf("unable to match filter: %v", err)
229				}
230			}
231			match = localMatch
232		})
233	}
234}
235