search

aionnetwork / aion

Aion Network - Java Implementation
https://theoan.com/
MIT License
337 stars 112 forks source link

DAT (double array trie) POC #130

Open aion-jin opened 6 years ago

aion-jin commented 6 years ago

DAT detail:

https://linux.thai.net/~thep/datrie/datrie.html

C :

https://github.com/omeid/libdatrie Java:

https://github.com/digitalstain/DoubleArrayTrie JS:

https://github.com/bramstein/datrie

compare with BTC merkle tree: https://bitcoin.org/en/developer-guide#term-merkle-tree

Eth patricia-tree: https://github.com/ethereum/wiki/wiki/Patricia-Tree

benchmark:

Insert | update | fetch | construct

Thanks for Robert, we find 3rd candidate here the hat-trie http://crpit.com/confpapers/CRPITV62Askitis.pdf

aion-jin commented 6 years ago

I just post the benchmark from Robert and Sergiu here:

TrieImpl (default) implementation:

Insert duration: 9667ms Update duration: 10050ms Read duration: 761ms Delete duration: 7612ms

DAT implementation:

Insert duration: 6111ms Update duration: 1862ms Read duration: 555ms Delete duration: 1547ms*