arbo/addbatch_test.go
addbatch_test.goRaw
1package arbo
2
3import (
4 "crypto/rand"
5 "encoding/hex"
6 "fmt"
7 "math/big"
8 "runtime"
9 "sort"
10 "testing"
11 "time"
12
13 qt "github.com/frankban/quicktest"
14 "github.com/iden3/go-merkletree/db/leveldb"
15 "github.com/iden3/go-merkletree/db/memory"
16)
17
18var debug = true
19
20func printTestContext(prefix string, nLeafs int, hashName, dbName string) {
21 if debug {
22 fmt.Printf("%snCPU: %d, nLeafs: %d, hash: %s, db: %s\n",
23 prefix, runtime.NumCPU(), nLeafs, hashName, dbName)
24 }
25}
26
27func printRes(name string, duration time.Duration) {
28 if debug {
29 fmt.Printf("%s: %s \n", name, duration)
30 }
31}
32
33func debugTime(descr string, time1, time2 time.Duration) {
34 if debug {
35 fmt.Printf("%s was %.02fx times faster than without AddBatch\n",
36 descr, float64(time1)/float64(time2))
37 }
38}
39
40func testInit(c *qt.C, n int) (*Tree, *Tree) {
41 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
42 c.Assert(err, qt.IsNil)
43 defer tree1.db.Close()
44
45 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
46 c.Assert(err, qt.IsNil)
47 defer tree2.db.Close()
48
49 // add the initial leafs to fill a bit the trees before calling the
50 // AddBatch method
51 for i := 0; i < n; i++ {
52 k := BigIntToBytes(big.NewInt(int64(i)))
53 v := BigIntToBytes(big.NewInt(int64(i * 2)))
54 if err := tree1.Add(k, v); err != nil {
55 c.Fatal(err)
56 }
57 if err := tree2.Add(k, v); err != nil {
58 c.Fatal(err)
59 }
60 }
61 return tree1, tree2
62}
63
64func TestAddBatchCaseA(t *testing.T) {
65 c := qt.New(t)
66
67 nLeafs := 1024
68
69 tree, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
70 c.Assert(err, qt.IsNil)
71 defer tree.db.Close()
72
73 start := time.Now()
74 for i := 0; i < nLeafs; i++ {
75 k := BigIntToBytes(big.NewInt(int64(i)))
76 v := BigIntToBytes(big.NewInt(int64(i * 2)))
77 if err := tree.Add(k, v); err != nil {
78 t.Fatal(err)
79 }
80 }
81 time1 := time.Since(start)
82
83 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
84 c.Assert(err, qt.IsNil)
85 defer tree2.db.Close()
86 tree2.dbgInit()
87
88 var keys, values [][]byte
89 for i := 0; i < nLeafs; i++ {
90 k := BigIntToBytes(big.NewInt(int64(i)))
91 v := BigIntToBytes(big.NewInt(int64(i * 2)))
92 keys = append(keys, k)
93 values = append(values, v)
94 }
95 start = time.Now()
96 indexes, err := tree2.AddBatch(keys, values)
97 c.Assert(err, qt.IsNil)
98 time2 := time.Since(start)
99 if debug {
100 debugTime("CASE A, AddBatch", time1, time2)
101 printTestContext(" ", nLeafs, "Poseidon", "memory")
102 tree2.dbg.print(" ")
103 }
104 c.Check(len(indexes), qt.Equals, 0)
105
106 // check that both trees roots are equal
107 c.Check(tree2.Root(), qt.DeepEquals, tree.Root())
108}
109
110func TestAddBatchCaseANotPowerOf2(t *testing.T) {
111 c := qt.New(t)
112
113 nLeafs := 1027
114
115 tree, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
116 c.Assert(err, qt.IsNil)
117 defer tree.db.Close()
118
119 for i := 0; i < nLeafs; i++ {
120 k := BigIntToBytes(big.NewInt(int64(i)))
121 v := BigIntToBytes(big.NewInt(int64(i * 2)))
122 if err := tree.Add(k, v); err != nil {
123 t.Fatal(err)
124 }
125 }
126
127 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
128 c.Assert(err, qt.IsNil)
129 defer tree2.db.Close()
130
131 var keys, values [][]byte
132 for i := 0; i < nLeafs; i++ {
133 k := BigIntToBytes(big.NewInt(int64(i)))
134 v := BigIntToBytes(big.NewInt(int64(i * 2)))
135 keys = append(keys, k)
136 values = append(values, v)
137 }
138 indexes, err := tree2.AddBatch(keys, values)
139 c.Assert(err, qt.IsNil)
140 c.Check(len(indexes), qt.Equals, 0)
141
142 // check that both trees roots are equal
143 c.Check(tree2.Root(), qt.DeepEquals, tree.Root())
144}
145
146func randomBytes(n int) []byte {
147 b := make([]byte, n)
148 _, err := rand.Read(b)
149 if err != nil {
150 panic(err)
151 }
152 return b
153}
154
155func TestAddBatchCaseATestVector(t *testing.T) {
156 c := qt.New(t)
157 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
158 c.Assert(err, qt.IsNil)
159 defer tree1.db.Close()
160
161 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
162 c.Assert(err, qt.IsNil)
163 defer tree2.db.Close()
164
165 // leafs in 2nd level subtrees: [ 6, 0, 1, 1]
166 testvectorKeys := []string{
167 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
168 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
169 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
170 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
171 }
172 var keys, values [][]byte
173 for i := 0; i < len(testvectorKeys); i++ {
174 key, err := hex.DecodeString(testvectorKeys[i])
175 c.Assert(err, qt.IsNil)
176 keys = append(keys, key)
177 values = append(values, []byte{0})
178 }
179
180 for i := 0; i < len(keys); i++ {
181 if err := tree1.Add(keys[i], values[i]); err != nil {
182 t.Fatal(err)
183 }
184 }
185
186 indexes, err := tree2.AddBatch(keys, values)
187 c.Assert(err, qt.IsNil)
188 c.Check(len(indexes), qt.Equals, 0)
189 // check that both trees roots are equal
190 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
191
192 // 2nd test vectors
193 tree1, err = NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
194 c.Assert(err, qt.IsNil)
195 defer tree1.db.Close()
196
197 tree2, err = NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
198 c.Assert(err, qt.IsNil)
199 defer tree2.db.Close()
200
201 testvectorKeys = []string{
202 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
203 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
204 "9cb87ec67e875c61390edcd1ab517f443591047709a4d4e45b0f9ed980857b8e",
205 "9b4e9e92e974a589f426ceeb4cb291dc24893513fecf8e8460992dcf52621d4d",
206 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
207 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
208 "3cd55dbfb8f975f20a0925dfbdabe79fa2d51dd0268afbb8ba6b01de9dfcdd3c",
209 "5d0a9d6d9f197c091bf054fac9cb60e11ec723d6610ed8578e617b4d46cb43d5",
210 }
211 keys = [][]byte{}
212 values = [][]byte{}
213 for i := 0; i < len(testvectorKeys); i++ {
214 key, err := hex.DecodeString(testvectorKeys[i])
215 c.Assert(err, qt.IsNil)
216 keys = append(keys, key)
217 values = append(values, []byte{0})
218 }
219
220 for i := 0; i < len(keys); i++ {
221 if err := tree1.Add(keys[i], values[i]); err != nil {
222 t.Fatal(err)
223 }
224 }
225
226 indexes, err = tree2.AddBatch(keys, values)
227 c.Assert(err, qt.IsNil)
228 c.Check(len(indexes), qt.Equals, 0)
229 // check that both trees roots are equal
230 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
231}
232
233func TestAddBatchCaseARandomKeys(t *testing.T) {
234 c := qt.New(t)
235
236 nLeafs := 8
237
238 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
239 c.Assert(err, qt.IsNil)
240 defer tree1.db.Close()
241
242 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
243 c.Assert(err, qt.IsNil)
244 defer tree2.db.Close()
245
246 var keys, values [][]byte
247 for i := 0; i < nLeafs; i++ {
248 keys = append(keys, randomBytes(32))
249 // values = append(values, randomBytes(32))
250 values = append(values, []byte{0})
251 // fmt.Println("K", hex.EncodeToString(keys[i]))
252 }
253
254 // TODO delete
255 keys[0], _ = hex.DecodeString("1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642")
256 keys[1], _ = hex.DecodeString("2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf")
257 keys[2], _ = hex.DecodeString("9cb87ec67e875c61390edcd1ab517f443591047709a4d4e45b0f9ed980857b8e")
258 keys[3], _ = hex.DecodeString("9b4e9e92e974a589f426ceeb4cb291dc24893513fecf8e8460992dcf52621d4d")
259 keys[4], _ = hex.DecodeString("1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5")
260 keys[5], _ = hex.DecodeString("d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7")
261 keys[6], _ = hex.DecodeString("3cd55dbfb8f975f20a0925dfbdabe79fa2d51dd0268afbb8ba6b01de9dfcdd3c")
262 keys[7], _ = hex.DecodeString("5d0a9d6d9f197c091bf054fac9cb60e11ec723d6610ed8578e617b4d46cb43d5")
263
264 for i := 0; i < len(keys); i++ {
265 if err := tree1.Add(keys[i], values[i]); err != nil {
266 t.Fatal(err)
267 }
268 }
269
270 indexes, err := tree2.AddBatch(keys, values)
271 c.Assert(err, qt.IsNil)
272 // tree1.PrintGraphviz(nil)
273 // tree2.PrintGraphviz(nil)
274
275 c.Check(len(indexes), qt.Equals, 0)
276
277 // check that both trees roots are equal
278 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
279}
280
281func TestAddBatchCaseB(t *testing.T) {
282 c := qt.New(t)
283
284 nLeafs := 1024
285 initialNLeafs := 99 // TMP TODO use const minLeafsThreshold-1 once ready
286
287 tree1, tree2 := testInit(c, initialNLeafs)
288 tree2.dbgInit()
289
290 start := time.Now()
291 for i := initialNLeafs; i < nLeafs; i++ {
292 k := BigIntToBytes(big.NewInt(int64(i)))
293 v := BigIntToBytes(big.NewInt(int64(i * 2)))
294 if err := tree1.Add(k, v); err != nil {
295 t.Fatal(err)
296 }
297 }
298 time1 := time.Since(start)
299
300 // prepare the key-values to be added
301 var keys, values [][]byte
302 for i := initialNLeafs; i < nLeafs; i++ {
303 k := BigIntToBytes(big.NewInt(int64(i)))
304 v := BigIntToBytes(big.NewInt(int64(i * 2)))
305 keys = append(keys, k)
306 values = append(values, v)
307 }
308 start = time.Now()
309 indexes, err := tree2.AddBatch(keys, values)
310 c.Assert(err, qt.IsNil)
311 time2 := time.Since(start)
312 if debug {
313 debugTime("CASE B, AddBatch", time1, time2)
314 printTestContext(" ", nLeafs, "Poseidon", "memory")
315 tree2.dbg.print(" ")
316 }
317 c.Check(len(indexes), qt.Equals, 0)
318
319 // check that both trees roots are equal
320 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
321}
322
323func TestAddBatchCaseBRepeatedLeafs(t *testing.T) {
324 c := qt.New(t)
325
326 nLeafs := 1024
327 initialNLeafs := 99 // TMP TODO use const minLeafsThreshold-1 once ready
328
329 tree1, tree2 := testInit(c, initialNLeafs)
330
331 for i := initialNLeafs; i < nLeafs; i++ {
332 k := BigIntToBytes(big.NewInt(int64(i)))
333 v := BigIntToBytes(big.NewInt(int64(i * 2)))
334 if err := tree1.Add(k, v); err != nil {
335 t.Fatal(err)
336 }
337 }
338
339 // prepare the key-values to be added, including already existing keys
340 var keys, values [][]byte
341 for i := 0; i < nLeafs; i++ {
342 k := BigIntToBytes(big.NewInt(int64(i)))
343 v := BigIntToBytes(big.NewInt(int64(i * 2)))
344 keys = append(keys, k)
345 values = append(values, v)
346 }
347 indexes, err := tree2.AddBatch(keys, values)
348 c.Assert(err, qt.IsNil)
349 c.Check(len(indexes), qt.Equals, initialNLeafs)
350
351 // check that both trees roots are equal
352 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
353}
354
355func TestSplitInBuckets(t *testing.T) {
356 c := qt.New(t)
357
358 nLeafs := 16
359 kvs := make([]kv, nLeafs)
360 for i := 0; i < nLeafs; i++ {
361 k := BigIntToBytes(big.NewInt(int64(i)))
362 v := BigIntToBytes(big.NewInt(int64(i * 2)))
363 keyPath := make([]byte, 32)
364 copy(keyPath[:], k)
365 kvs[i].pos = i
366 kvs[i].keyPath = k
367 kvs[i].k = k
368 kvs[i].v = v
369 }
370
371 // check keyToBucket results for 4 buckets & 8 keys
372 c.Assert(keyToBucket(kvs[0].k, 4), qt.Equals, 0)
373 c.Assert(keyToBucket(kvs[1].k, 4), qt.Equals, 2)
374 c.Assert(keyToBucket(kvs[2].k, 4), qt.Equals, 1)
375 c.Assert(keyToBucket(kvs[3].k, 4), qt.Equals, 3)
376 c.Assert(keyToBucket(kvs[4].k, 4), qt.Equals, 0)
377 c.Assert(keyToBucket(kvs[5].k, 4), qt.Equals, 2)
378 c.Assert(keyToBucket(kvs[6].k, 4), qt.Equals, 1)
379 c.Assert(keyToBucket(kvs[7].k, 4), qt.Equals, 3)
380
381 // check keyToBucket results for 8 buckets & 8 keys
382 c.Assert(keyToBucket(kvs[0].k, 8), qt.Equals, 0)
383 c.Assert(keyToBucket(kvs[1].k, 8), qt.Equals, 4)
384 c.Assert(keyToBucket(kvs[2].k, 8), qt.Equals, 2)
385 c.Assert(keyToBucket(kvs[3].k, 8), qt.Equals, 6)
386 c.Assert(keyToBucket(kvs[4].k, 8), qt.Equals, 1)
387 c.Assert(keyToBucket(kvs[5].k, 8), qt.Equals, 5)
388 c.Assert(keyToBucket(kvs[6].k, 8), qt.Equals, 3)
389 c.Assert(keyToBucket(kvs[7].k, 8), qt.Equals, 7)
390
391 buckets := splitInBuckets(kvs, 4)
392
393 expected := [][]string{
394 {
395 "00000000", // bucket 0
396 "08000000",
397 "04000000",
398 "0c000000",
399 },
400 {
401 "02000000", // bucket 1
402 "0a000000",
403 "06000000",
404 "0e000000",
405 },
406 {
407 "01000000", // bucket 2
408 "09000000",
409 "05000000",
410 "0d000000",
411 },
412 {
413 "03000000", // bucket 3
414 "0b000000",
415 "07000000",
416 "0f000000",
417 },
418 }
419
420 for i := 0; i < len(buckets); i++ {
421 sortKvs(buckets[i])
422 c.Assert(len(buckets[i]), qt.Equals, len(expected[i]))
423 for j := 0; j < len(buckets[i]); j++ {
424 c.Check(hex.EncodeToString(buckets[i][j].k[:4]),
425 qt.Equals, expected[i][j])
426 }
427 }
428}
429
430// compareBytes compares byte slices where the bytes are compared from left to
431// right and each byte is compared by bit from right to left
432func compareBytes(a, b []byte) bool {
433 // WIP
434 for i := 0; i < len(a); i++ {
435 for j := 0; j < 8; j++ {
436 aBit := a[i] & (1 << j)
437 bBit := b[i] & (1 << j)
438 if aBit > bBit {
439 return false
440 } else if aBit < bBit {
441 return true
442 }
443 }
444 }
445 return false
446}
447
448// sortKvs sorts the kv by path
449func sortKvs(kvs []kv) {
450 sort.Slice(kvs, func(i, j int) bool {
451 return compareBytes(kvs[i].keyPath, kvs[j].keyPath)
452 })
453}
454
455func TestAddBatchCaseC(t *testing.T) {
456 c := qt.New(t)
457
458 nLeafs := 1024
459 initialNLeafs := 101 // TMP TODO use const minLeafsThreshold+1 once ready
460
461 tree1, tree2 := testInit(c, initialNLeafs)
462 tree2.dbgInit()
463
464 start := time.Now()
465 for i := initialNLeafs; i < nLeafs; i++ {
466 k := BigIntToBytes(big.NewInt(int64(i)))
467 v := BigIntToBytes(big.NewInt(int64(i * 2)))
468 if err := tree1.Add(k, v); err != nil {
469 t.Fatal(err)
470 }
471 }
472 time1 := time.Since(start)
473
474 // prepare the key-values to be added
475 var keys, values [][]byte
476 for i := initialNLeafs; i < nLeafs; i++ {
477 k := BigIntToBytes(big.NewInt(int64(i)))
478 v := BigIntToBytes(big.NewInt(int64(i * 2)))
479 keys = append(keys, k)
480 values = append(values, v)
481 }
482 start = time.Now()
483 indexes, err := tree2.AddBatch(keys, values)
484 c.Assert(err, qt.IsNil)
485 time2 := time.Since(start)
486 if debug {
487 debugTime("CASE C, AddBatch", time1, time2)
488 printTestContext(" ", nLeafs, "Poseidon", "memory")
489 tree2.dbg.print(" ")
490 }
491 c.Check(len(indexes), qt.Equals, 0)
492
493 // check that both trees roots are equal
494 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
495}
496
497func TestAddBatchCaseD(t *testing.T) {
498 c := qt.New(t)
499
500 nLeafs := 4096
501 initialNLeafs := 900
502
503 tree1, tree2 := testInit(c, initialNLeafs)
504 tree2.dbgInit()
505
506 start := time.Now()
507 for i := initialNLeafs; i < nLeafs; i++ {
508 k := BigIntToBytes(big.NewInt(int64(i)))
509 v := BigIntToBytes(big.NewInt(int64(i * 2)))
510 if err := tree1.Add(k, v); err != nil {
511 t.Fatal(err)
512 }
513 }
514 time1 := time.Since(start)
515
516 // prepare the key-values to be added
517 var keys, values [][]byte
518 for i := initialNLeafs; i < nLeafs; i++ {
519 k := BigIntToBytes(big.NewInt(int64(i)))
520 v := BigIntToBytes(big.NewInt(int64(i * 2)))
521 keys = append(keys, k)
522 values = append(values, v)
523 }
524 start = time.Now()
525 indexes, err := tree2.AddBatch(keys, values)
526 c.Assert(err, qt.IsNil)
527 time2 := time.Since(start)
528 if debug {
529 debugTime("CASE D, AddBatch", time1, time2)
530 printTestContext(" ", nLeafs, "Poseidon", "memory")
531 tree2.dbg.print(" ")
532 }
533 c.Check(len(indexes), qt.Equals, 0)
534
535 // check that both trees roots are equal
536 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
537}
538
539func TestAddBatchCaseE(t *testing.T) {
540 c := qt.New(t)
541
542 nLeafs := 4096
543 initialNLeafs := 900
544
545 tree1, _ := testInit(c, initialNLeafs)
546
547 start := time.Now()
548 for i := initialNLeafs; i < nLeafs; i++ {
549 k := BigIntToBytes(big.NewInt(int64(i)))
550 v := BigIntToBytes(big.NewInt(int64(i * 2)))
551 if err := tree1.Add(k, v); err != nil {
552 t.Fatal(err)
553 }
554 }
555 time1 := time.Since(start)
556
557 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
558 c.Assert(err, qt.IsNil)
559 defer tree2.db.Close()
560 tree2.dbgInit()
561
562 var keys, values [][]byte
563 // add the initial leafs to fill a bit the tree before calling the
564 // AddBatch method
565 for i := 0; i < initialNLeafs; i++ {
566 k := BigIntToBytes(big.NewInt(int64(i)))
567 v := BigIntToBytes(big.NewInt(int64(i * 2)))
568 // use only the keys of one bucket, store the not used ones for
569 // later
570 if i%4 != 0 {
571 keys = append(keys, k)
572 values = append(values, v)
573 continue
574 }
575 if err := tree2.Add(k, v); err != nil {
576 t.Fatal(err)
577 }
578 }
579
580 for i := initialNLeafs; i < nLeafs; i++ {
581 k := BigIntToBytes(big.NewInt(int64(i)))
582 v := BigIntToBytes(big.NewInt(int64(i * 2)))
583 keys = append(keys, k)
584 values = append(values, v)
585 }
586 start = time.Now()
587 indexes, err := tree2.AddBatch(keys, values)
588 c.Assert(err, qt.IsNil)
589 time2 := time.Since(start)
590 if debug {
591 debugTime("CASE E, AddBatch", time1, time2)
592 printTestContext(" ", nLeafs, "Poseidon", "memory")
593 tree2.dbg.print(" ")
594 }
595 c.Check(len(indexes), qt.Equals, 0)
596
597 // check that both trees roots are equal
598 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
599}
600
601func TestFlp2(t *testing.T) {
602 c := qt.New(t)
603 c.Assert(flp2(31), qt.Equals, 16)
604 c.Assert(flp2(32), qt.Equals, 32)
605 c.Assert(flp2(33), qt.Equals, 32)
606 c.Assert(flp2(63), qt.Equals, 32)
607 c.Assert(flp2(64), qt.Equals, 64)
608 c.Assert(flp2(9000), qt.Equals, 8192)
609}
610
611func TestAddBatchBench(t *testing.T) {
612 nLeafs := 50_000
613 printTestContext("TestAddBatchBench: ", nLeafs, "Blake2b", "leveldb")
614
615 // prepare inputs
616 var ks, vs [][]byte
617 for i := 0; i < nLeafs; i++ {
618 k := randomBytes(32)
619 v := randomBytes(32)
620 ks = append(ks, k)
621 vs = append(vs, v)
622 }
623
624 benchAdd(t, ks, vs)
625
626 benchAddBatch(t, ks, vs)
627}
628
629func benchAdd(t *testing.T, ks, vs [][]byte) {
630 c := qt.New(t)
631
632 dbDir := t.TempDir()
633 storage, err := leveldb.NewLevelDbStorage(dbDir, false)
634 c.Assert(err, qt.IsNil)
635 tree, err := NewTree(storage, 140, HashFunctionBlake2b)
636 c.Assert(err, qt.IsNil)
637
638 if debug {
639 tree.dbgInit()
640 }
641 start := time.Now()
642 for i := 0; i < len(ks); i++ {
643 err = tree.Add(ks[i], vs[i])
644 c.Assert(err, qt.IsNil)
645 }
646 printRes(" Add loop", time.Since(start))
647 tree.dbg.print(" ")
648}
649
650func benchAddBatch(t *testing.T, ks, vs [][]byte) {
651 c := qt.New(t)
652
653 dbDir := t.TempDir()
654 storage, err := leveldb.NewLevelDbStorage(dbDir, false)
655 c.Assert(err, qt.IsNil)
656 tree, err := NewTree(storage, 140, HashFunctionBlake2b)
657 c.Assert(err, qt.IsNil)
658
659 if debug {
660 tree.dbgInit()
661 }
662 start := time.Now()
663 invalids, err := tree.AddBatch(ks, vs)
664 printRes(" AddBatch", time.Since(start))
665 c.Assert(err, qt.IsNil)
666 c.Assert(len(invalids), qt.Equals, 0)
667 tree.dbg.print(" ")
668}
669
670func TestDbgStats(t *testing.T) {
671 c := qt.New(t)
672
673 nLeafs := 10_000
674
675 // prepare inputs
676 var ks, vs [][]byte
677 for i := 0; i < nLeafs; i++ {
678 k := randomBytes(32)
679 v := randomBytes(32)
680 ks = append(ks, k)
681 vs = append(vs, v)
682 }
683
684 // 1
685 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
686 c.Assert(err, qt.IsNil)
687 defer tree1.db.Close()
688
689 tree1.dbgInit()
690
691 for i := 0; i < len(ks); i++ {
692 err = tree1.Add(ks[i], vs[i])
693 c.Assert(err, qt.IsNil)
694 }
695
696 // 2
697 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
698 c.Assert(err, qt.IsNil)
699 defer tree2.db.Close()
700
701 tree2.dbgInit()
702
703 invalids, err := tree2.AddBatch(ks, vs)
704 c.Assert(err, qt.IsNil)
705 c.Assert(len(invalids), qt.Equals, 0)
706
707 // 3
708 tree3, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
709 c.Assert(err, qt.IsNil)
710 defer tree3.db.Close()
711
712 tree3.dbgInit()
713
714 // add few key-values
715 // invalids, err = tree3.AddBatch(ks[:], vs[:])
716 invalids, err = tree3.AddBatch(ks[:1000], vs[:1000])
717 c.Assert(err, qt.IsNil)
718 c.Assert(len(invalids), qt.Equals, 0)
719
720 // add the rest of key-values
721 invalids, err = tree3.AddBatch(ks[1000:], vs[1000:])
722 c.Assert(err, qt.IsNil)
723 c.Assert(len(invalids), qt.Equals, 0)
724
725 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
726 c.Check(tree3.Root(), qt.DeepEquals, tree1.Root())
727
728 if debug {
729 fmt.Println("TestDbgStats")
730 tree1.dbg.print(" add in loop ")
731 tree2.dbg.print(" addbatch caseA ")
732 tree3.dbg.print(" addbatch caseD ")
733 }
734}
735
736func TestLoadVT(t *testing.T) {
737 c := qt.New(t)
738
739 nLeafs := 1024
740
741 tree, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
742 c.Assert(err, qt.IsNil)
743 defer tree.db.Close()
744
745 var keys, values [][]byte
746 for i := 0; i < nLeafs; i++ {
747 k := randomBytes(31)
748 v := randomBytes(31)
749 keys = append(keys, k)
750 values = append(values, v)
751 }
752 indexes, err := tree.AddBatch(keys, values)
753 c.Assert(err, qt.IsNil)
754 c.Check(len(indexes), qt.Equals, 0)
755
756 vt, err := tree.loadVT()
757 c.Assert(err, qt.IsNil)
758 _, err = vt.computeHashes()
759 c.Assert(err, qt.IsNil)
760
761 // check that tree & vt roots are equal
762 c.Check(tree.Root(), qt.DeepEquals, vt.root.h)
763}
764
765// TODO test adding batch with repeated keys in the batch
766// TODO test adding batch with multiple invalid keys