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