parallel-hashmap VS bitcoin-cash-node

Standard library maps/unordered_maps are themselves notoriously slow anyway. A sparse_hash_map from abseil or parallel-hashmaps[1] would be better.

[1] https://github.com/greg7mdp/parallel-hashmap

Cool! Looking forward to you trying my phmap - and please let me know if you have any question.

I do this as well in my phmap and gtl implementations. It makes the tables look worse in benchmarks like the above, but prevents really bad surprises occasionally.

Thanks a lot for the great benchmark, Martin. Glad you used different hash functions, because I do sacrifice some speed to make sure that the performance of my hash maps doesn't degrade drastically with poor hash functions. Happy to see that my phmap and gtl (the C++20 version) performed well.

I use https://github.com/greg7mdp/parallel-hashmap when I need better performance of maps and sets.

Then they should really try https://github.com/greg7mdp/parallel-hashmap, the current state of the art.

Unordered hash map shootout CMAP = https://github.com/tylov/STC KMAP = https://github.com/attractivechaos/klib PMAP = https://github.com/greg7mdp/parallel-hashmap FMAP = https://github.com/skarupke/flat_hash_map RMAP = https://github.com/martinus/robin-hood-hashing HMAP = https://github.com/Tessil/hopscotch-map TMAP = https://github.com/Tessil/robin-map UMAP = std::unordered_map Usage: shootout [n-million=40 key-bits=25] Random keys are in range [0, 2^25). Seed = 1656617916: T1: Insert/update random keys: KMAP: time: 1.949, size: 15064129, buckets: 33554432, sum: 165525449561381 CMAP: time: 1.649, size: 15064129, buckets: 22145833, sum: 165525449561381 PMAP: time: 2.434, size: 15064129, buckets: 33554431, sum: 165525449561381 FMAP: time: 2.112, size: 15064129, buckets: 33554432, sum: 165525449561381 RMAP: time: 1.708, size: 15064129, buckets: 33554431, sum: 165525449561381 HMAP: time: 2.054, size: 15064129, buckets: 33554432, sum: 165525449561381 TMAP: time: 1.645, size: 15064129, buckets: 33554432, sum: 165525449561381 UMAP: time: 6.313, size: 15064129, buckets: 31160981, sum: 165525449561381 T2: Insert sequential keys, then remove them in same order: KMAP: time: 1.173, size: 0, buckets: 33554432, erased 20000000 CMAP: time: 1.651, size: 0, buckets: 33218751, erased 20000000 PMAP: time: 3.840, size: 0, buckets: 33554431, erased 20000000 FMAP: time: 1.722, size: 0, buckets: 33554432, erased 20000000 RMAP: time: 2.359, size: 0, buckets: 33554431, erased 20000000 HMAP: time: 0.849, size: 0, buckets: 33554432, erased 20000000 TMAP: time: 0.660, size: 0, buckets: 33554432, erased 20000000 UMAP: time: 2.138, size: 0, buckets: 31160981, erased 20000000 T3: Remove random keys: KMAP: time: 1.973, size: 0, buckets: 33554432, erased 23367671 CMAP: time: 2.020, size: 0, buckets: 33218751, erased 23367671 PMAP: time: 2.940, size: 0, buckets: 33554431, erased 23367671 FMAP: time: 1.147, size: 0, buckets: 33554432, erased 23367671 RMAP: time: 1.941, size: 0, buckets: 33554431, erased 23367671 HMAP: time: 1.135, size: 0, buckets: 33554432, erased 23367671 TMAP: time: 1.064, size: 0, buckets: 33554432, erased 23367671 UMAP: time: 5.632, size: 0, buckets: 31160981, erased 23367671 T4: Iterate random keys: KMAP: time: 0.748, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 CMAP: time: 0.627, size: 23367671, buckets: 33218751, repeats: 8, sum: 4465059465719680 PMAP: time: 0.680, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 FMAP: time: 0.735, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 RMAP: time: 0.464, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 HMAP: time: 0.719, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 TMAP: time: 0.662, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 UMAP: time: 6.168, size: 23367671, buckets: 31160981, repeats: 8, sum: 4465059465719680 T5: Lookup random keys: KMAP: time: 0.943, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 CMAP: time: 0.863, size: 23367671, buckets: 33218751, lookups: 34235332, found: 29040438 PMAP: time: 1.635, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 FMAP: time: 0.969, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 RMAP: time: 1.705, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 HMAP: time: 0.712, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 TMAP: time: 0.584, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 UMAP: time: 1.974, size: 23367671, buckets: 31160981, lookups: 34235332, found: 29040438

std::unordered_map is notorious for being slow. Use a better implementation (I like the flat naps from here, which are the same as abseil’s). The question that needs to be asked too is if you need to use a map.

A comparison against phmap would also be nice.

std::unordered_map is perfectly fine. You can do better with external libraries, like parallel hashmap, but these tend to be drop-in replacements

Thinking maybe this: https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node/-/tree/master

Yep, just a suggestion/comment in the config file here which showed me 'this was useful for me, let me share it' kind of vibes. I also checked their history there. Seem to be helping review things too (i have no idea about the back story here, just going on what I'm seeing before me)

They're already implemented and running on testnet4, using node software built from this MR: https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node/-/merge_requests/1600

Either build the test branch yourself (https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node/-/merge_requests/1600) or use Calin's build here (https://www.c3-soft.com/downloads/BitcoinCash/testing/mr-1600)

At first I was disappointed by the results following official build instructions for BCHN (here) & Bitcoin Core (here), but eventually I realized they were missing the strip * command. BCHN gave a strange warning when running it, but that issue is apparently resolved with the -DCLIENT_VERSION_IS_RELEASE flag. Without stripping, the bitcoin-qt.exe can be 415 MiB instead of under 31 MiB.

#!/bin/bash sudo apt-get update sudo apt-get upgrade -y sudo apt-get install -y build-essential cmake git git-lfs libboost-chrono-dev libboost-filesystem-dev libboost-test-dev libboost-thread-dev libevent-dev libminiupnpc-dev libssl-dev libzmq3-dev ninja-build python3 help2man unzip sudo apt-get install -y build-essential libtool autotools-dev automake pkg-config libssl-dev libevent-dev bsdmainutils libboost-system-dev libboost-filesystem-dev libboost-chrono-dev libboost-program-options-dev libboost-test-dev libboost-thread-dev sudo apt-get install -y libdb-dev libdb++-dev liblmdb++-dev sudo apt-get install -y htop git config --global user.email "[email protected]" git config --global user.name "Your Name" #git clone https://github.com/mtrycz/txunami.git #cd txunami #git submodule update --init --recursive #cd BitcoinUnlimited #git checkout dev #./autogen.sh #./configure --with-gui=no --enable-shared --enable-wallet --with-incompatible-bdb #make -j9 #./src/bitcoind -scalenet -blockmaxsize=256000000 -maxmempool=2048 -daemon -rpcworkqueue=32 #cd .. #make git clone https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node.git cd bitcoin-cash-node/ git checkout 24.1.0 #git clone https://gitlab.com/matricz/bitcoin-cash-node.git #cd bitcoin-cash-node/ #git checkout phmap mkdir build cd build cmake -GNinja .. -DBUILD_BITCOIN_QT=OFF -DCMAKE_BUILD_TYPE:STRING=Release ninja #cd #wget https://mtrycz-test.s3.eu-central-1.amazonaws.com/prunedscalenet.zip #unzip prunedscalenet.zip mkdir /dev/shm/.bitcoin cd # ./bitcoin-cash-node/build/src/bitcoind -daemon -debug=bench -debug=coindb -checkpoints=0 -assumevalid=0 -datadir=/dev/shm/.bitcoin -scalenet # tail -f /dev/shm/.bitcoin/scalenet/debug.log | grep -E --color "Flush:|"

BCH runs by a diverse set of node implementations that have slightly different implementations (and docs), although following the same consensus rules. I would recommend starting with BCHN's list of consensus changes since the hard fork in 2017: https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node/-/blob/master/doc/bch-upgrades.md

A draft implementation is coming to testnets for BCH via Bitcoin Cash Node hopefully soon.