github/arbo
1
1
Fork 0
mirror of https://github.com/vocdoni/arbo.git synced 2026-01-09 13:57:54 -05:00
Code Issues Packages Projects Releases Wiki Activity
86 Commits 26 Branches 0 Tags
feature/dump-writer-reader
Commit Graph

23 Commits

Author SHA1 Message Date
arnaucube
e8094038ee Complete upFromSubRoots cases & add test 2021-11-23 13:33:40 +01:00
arnaucube
6cf1e58d9f Implement addBatchInDisk for big trees 
Implement addBatchInDisk for big trees, which does not puts the tree in
memory, and works directly over the db data, parallelizing for each CPU.
 2021-10-25 14:55:42 +02:00
arnaucube
7c6316dcbd Update AddBatch to return invalids index + error 2021-10-06 19:19:16 +02:00
arnaucube
30d8b42fd3 Add checks that len(key)<=maxKeyLen 
Add checks that the key is not bigger than maximum key length for the tree
maxLevels size, where maximum key len = ceil(maxLevels/8).

This is because if the key bits length is bigger than the maxLevels of the
tree, two different keys that their difference is at the end, will collision in
the same leaf of the tree (at the max depth).
 2021-10-04 14:33:49 +02:00
arnaucube
0921cac304 Update keyPath to be ceil(maxLevels/8) 2021-10-01 10:57:50 +02:00
arnaucube
ed0cf70d57 Update VT goroutines errs & Update Pack&UnpackSibl 
- Update VT goroutines errs to avoid race condition
- Update pack & unpack siblings to use 2-byte for full length & bitmap
bytes length
- Add check in UnpackSiblings to avoid panic
 2021-09-21 17:37:11 +02:00
arnaucube
dff11f4a7f Fix level when going down & in computeHashes 
Fix level when going down & in computeHashes, this affected the methods
Get, GenProof & AddBatch.
 2021-08-31 11:59:38 +02:00
arnaucube
1638860da0 Fix VirtualTree.addBatch bucket levels 2021-08-29 23:38:41 +02:00
arnaucube
2514b3188f Update db usage to new dvote.db interface version 2021-08-06 18:41:13 +02:00
arnaucube
01ec075b35 Update missing errors management 2021-07-21 11:57:18 +02:00
arnaucube
df896f6e96 Add option to input empty values at AddBatch 
Add option to input empty values at AddBatch & different number of keys
& values.
 2021-07-02 19:08:46 +02:00
arnaucube
2c62f31446 Update upFromNodes function for unbalanced tree 
- Update upFromNodes function for unbalanced tree case
- Add AddBatchTestVector2 & 3 with some edge cases
- Add checkRoots test method, which stores the Dump of the tree to file for after-debug
 2021-06-03 18:27:46 +02:00
arnaucube
467f063129 Update check of already existing key on add 
- Update check of already existing key on add
- Update docs of methods
 2021-06-02 10:26:40 +02:00
arnaucube
0b2c3b07ed Update public methods signatures 
- Update public methods signatures
- Remove 'lastAccess' param
- Add option to pass root for tree.Dump, Iterate, IterateWithStop,
Graphviz (and related)
- Move error messages to const defined error messages for external usage
 2021-05-26 17:01:09 +02:00
arnaucube
f24fb28266 Small update addbatch_test.go org 2021-05-26 09:30:57 +02:00
arnaucube
d16ebd0c80 Rm functions related to Old AddBatch 2021-05-24 22:26:50 +02:00
arnaucube
f31ed1d2d1 AddBatch implement using VirtualTree.AddBatch 
Reduces the num of hashes, dbGet and dbPut on cases D & E.

Current benchmarks:
```
CASE A, AddBatch was 9.101855 times faster than without AddBatch
	nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory
	dbgStats(hash: 2.047k, dbGet: 1, dbPut: 2.049k)
CASE B, AddBatch was 8.244078 times faster than without AddBatch
	nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory
	dbgStats(hash: 2.047k, dbGet: 198, dbPut: 2.049k)
CASE C, AddBatch was 8.511131 times faster than without AddBatch
	nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory
	dbgStats(hash: 2.047k, dbGet: 202, dbPut: 2.049k)
CASE D, AddBatch was 8.565696 times faster than without AddBatch
	nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory
	dbgStats(hash: 8.191k, dbGet: 1.800k, dbPut: 8.193k)
CASE E, AddBatch was 8.970056 times faster than without AddBatch
	nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory
	dbgStats(hash: 10.409k, dbGet: 2.668k, dbPut: 10.861k)
TestAddBatchBench: nCPU: 4, nLeafs: 50000, hash: Blake2b, db: leveldb
	Add loop:	10.616145533s
		dbgStats(hash: 824.884k, dbGet: 788.975k, dbPut: 924.884k)
	AddBatch:	942.34815ms
		dbgStats(hash: 122.051k, dbGet: 1, dbPut: 122.053k)
TestDbgStats
	add in loop    dbgStats(hash: 141.911k, dbGet: 134.650k, dbPut: 161.911k)
	addbatch caseA dbgStats(hash: 24.522k, dbGet: 1, dbPut: 24.524k)
	addbatch caseD dbgStats(hash: 26.985k, dbGet: 2.465k, dbPut: 26.989k)
```
 2021-05-24 17:05:03 +02:00
arnaucube
d09bd605bb Implement VirtualTree.addBatch with cpu parallelization 2021-05-23 21:31:33 +02:00
arnaucube
4167583b8d Add dbgStats metrics 
Add dbgStats metrics to analyze number of Hashes, db Gets, and db Puts.

Current benchmarks:
```
CASE A, AddBatch was 8.841700 times faster than without AddBatch
	nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory
	dbgStats(hash: 2.044k, dbGet: 1, dbPut: 2.049k)
CASE B, AddBatch was 7.678766 times faster than without AddBatch
	nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory
	dbgStats(hash: 2.044k, dbGet: 199, dbPut: 2.049k)
CASE C, AddBatch was 8.401087 times faster than without AddBatch
	nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory
	dbgStats(hash: 2.044k, dbGet: 207, dbPut: 2.049k)
CASE D, AddBatch was 2.466346 times faster than without AddBatch
	nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory
	dbgStats(hash: 33.884k, dbGet: 30.697k, dbPut: 33.889k)
CASE E, AddBatch was 1.958160 times faster than without AddBatch
	nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory
	dbgStats(hash: 41.419k, dbGet: 37.558k, dbPut: 41.874k)
TestAddBatchBench: nCPU: 4, nLeafs: 50000, hash: Blake2b, db: leveldb
	Add loop:	10.089858449s
		dbgStats(hash: 825.285k, dbGet: 788.869k, dbPut: 925.285k)
	AddBatch:	904.647829ms
		dbgStats(hash: 122.458k, dbGet: 1, dbPut: 122.463k)
TestDbgStats
	add in loop    dbgStats(hash: 141.915k, dbGet: 134.602k, dbPut: 161.915k)
	addbatch caseA dbgStats(hash: 24.528k, dbGet: 1, dbPut: 24.533k)
	addbatch caseD dbgStats(hash: 115.506k, dbGet: 97.482k, dbPut: 115.516k)
```
 2021-05-23 16:19:04 +02:00
arnaucube
03bb9f7447 AddBatch use Virtual Tree for empty trees/subtrees 
- AddBatch use Virtual Tree for cases A,B,C
- ImportDump use AddBatch instead of adding one by one
- Reorg & add more virtual tree tests
 2021-05-18 10:57:06 +02:00
arnaucube
66f6ae14bb Add computeHashes at virtual tree 2021-05-17 22:16:08 +02:00
arnaucube
e13b09215e Add virtual tree graphviz printing methods 2021-05-17 21:33:12 +02:00
arnaucube
8a8ec8c49e Implement Virtual Tree construction 
VirtualTree (vt) computes a tree without computing any hash. With the
idea of once all the leafs are placed in their positions, the hashes can
be computed, avoiding computing a node hash more than one time.
 2021-05-17 19:32:15 +02:00