Trie Memory and Performance Experiments

./gradlew customFatJar
java -cp build\libs\all-in-one-jar-1.0-SNAPSHOT.jar -Xms4g com.ajlopez.blockchain.TrieMemoryPerformance 1048576 32 20
No values: 1048576
Key size: 32
Value size: 20
MB before: 40.96002960205078
MB after: 488.32274627685547
MB after GC: 182.94497680664062
Creation time (ms): 19027
Hash time (ms): 13839
Trie size (nodes): 1414795

Generating 1 mega of values

These are the megabytes used in memory (after creating the trie, and do garbage collector):

Megabytes used by the trie nodes depending on the value size
Times (in millisecond) to create trie and calculate its root hash, depending on the value size (in bytes)

Generating from 1 to 10 megas of values

In this experiment series I vary the number of nodes, keeping the key size fixed to 20 bytes.

Trie memory usage
Trie memory usage after executing garbage collector
Number of nodes vs number of values inserted

Conclusions

These are only experiments, and the results are informal. They are too dependent of the execution machine. But I could write some preliminary conclusions:

  • There are many relations that are linear
  • At least with the experimental values used and 4 gigas of minimum size heap, Java garbage collector don’t alter the execution time (at least, not a lot)
  • Root hash calculation time is not small, it have the same order of magnitude than creation time
  • Apparently, the non-leaf nodes occupy more memory, relative to leaf nodes memory, as expected having arity 16. So many results with many key values are less dependent on value size.

These are only experiments

Yes, the main production case is: block execution. My trie implementation is prepared to have a good performance: when using an store, during the execution process, the used nodes are loaded in memory, and kept in it, so the more used nodes are easily queried. Practically, there is no production use case to have a 10 million key values trie in memory. But these experiments could give us a first glimpse about the trie memory usage and process performance.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store