diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-05 18:07:13 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-05 18:07:13 +0000 |
| commit | 636c7dc17286d93d788c741d15fd756aeda066d5 (patch) | |
| tree | e7ae158cc54f591041a061b9865bcae51854f15c /triehash/README.md | |
| parent | Initial commit. (diff) | |
| download | apt-upstream/1.8.2.3.tar.xz apt-upstream/1.8.2.3.zip | |
Adding upstream version 1.8.2.3.upstream/1.8.2.3upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'triehash/README.md')
| -rw-r--r-- | triehash/README.md | 58 |
1 files changed, 58 insertions, 0 deletions
diff --git a/triehash/README.md b/triehash/README.md new file mode 100644 index 0000000..d6f6e7f --- /dev/null +++ b/triehash/README.md @@ -0,0 +1,58 @@ +# Order-preserving minimal perfect hash function generator + +Build order-preserving minimal perfect hash functions. + +[](https://codecov.io/gh/julian-klode/triehash) +[](https://travis-ci.org/julian-klode/triehash) + +## Performance + +Performance was evaluated against other hash functions. As an input set, the +fields of Debian Packages and Sources files was used, and each hash function +was run 1,000,000 times for each word. The byte count of the words were then +summed up and divided by the total number of nanoseconds each function ran, so +all speeds below are given in bytes per nanosecond, AKA gigabyte per second. + +arch/function|jak-x230 (amd64)|backup (amd64)|asachi.d.o (arm64)|asachi.d.o (armel)|asachi.d.o (armhf)|plummer.d.o (ppc64el)|eller.d.o (mipsel) +-------------|----------------|--------------|------------------|------------------|------------------|---------------------|------------------ +Trie | 2.4 | 1.9 | 1.2 | 0.9 | 0.8 | 2.0 | 0.2 +Trie (*) | 2.2 | 1.7 | 0.8 | 0.7 | 0.7 | 1.8 | 0.2 +re2c | 1.7 | 1.3 | 0.9 | 0.9 | 0.7 | 1.6 | 0.2 +re2c (*) | 1.2 | 0.9 | 0.6 | 0.6 | 0.5 | 1.1 | 0.1 +gperf (*) | 0.7 | 0.5 | 0.2 | 0.2 | 0.2 | 0.5 | 0.1 +gperf | 1.3 | 0.9 | 0.3 | 0.3 | 0.2 | 0.4 | 0.1 +djb (*) | 0.7 | 0.5 | 0.3 | 0.3 | 0.3 | 0.5 | 0.1 +djb (**) | 1.0 | 0.7 | 0.4 | 0.5 | 0.5 | 0.6 | 0.2 +djb | 0.9 | 0.7 | 0.5 | 0.5 | 0.5 | 0.7 | 0.2 +apt (*) | 1.2 | 0.9 | 0.7 | 0.7 | 0.7 | 1.1 | 0.2 +apt (**) | 2.3 | 1.7 | 0.7 | 0.9 | 0.8 | 1.9 | 0.2 + +And transposed: + +function/arch |Trie |Trie (*) |re2c |re2c (*) |gperf (*)|gperf |djb (*) |djb (**) |djb |apt (*) |apt (**) +---------------------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|--------- +jak-x230 (amd64) | 2.4| 2.2| 1.7| 1.2| 0.7| 1.3| 0.7| 1.0| 0.9| 1.2| 2.3 +backup (amd64) | 1.9| 1.7| 1.3| 0.9| 0.5| 0.9| 0.5| 0.7| 0.7| 0.9| 1.7 +asachi.d.o (arm64) | 1.2| 0.8| 0.9| 0.6| 0.2| 0.3| 0.3| 0.4| 0.5| 0.7| 0.7 +asachi.d.o (armel) | 0.9| 0.7| 0.9| 0.6| 0.2| 0.3| 0.3| 0.5| 0.5| 0.7| 0.9 +asachi.d.o (armhf) | 0.8| 0.7| 0.7| 0.5| 0.2| 0.2| 0.3| 0.5| 0.5| 0.7| 0.8 +plummer.d.o (ppc64el)| 2.0| 1.8| 1.6| 1.1| 0.5| 0.4| 0.5| 0.6| 0.7| 1.1| 1.9 +eller.d.o (mipsel) | 0.2| 0.2| 0.2| 0.1| 0.1| 0.1| 0.1| 0.2| 0.2| 0.2| 0.2 + + +Legend: + +* The (*) variants are case-insensitive, (**) are more optimised versions + of the (*) versions. +* DJB (*) is a DJB Hash with naive lowercase conversion, DJB (**) just ORs one + bit into each value to get alphabetical characters to be lowercase +* APT (*) is the AlphaHash function from APT which hashes the last 8 bytes in a + word in a case-insensitive manner. APT (**) is the same function unrolled. +* All hosts except the x230 are Debian porterboxes. The x230 has a Core i5-3320M, + barriere has an Opteron 23xx. + +Notes: + +* The overhead is larger than needed on some platforms due to gcc inserting + unneeded zero extend instructions, see: + https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77729 |