README.md (zeek-4.0.2) | : | README.md (zeek-4.0.3) | ||
---|---|---|---|---|

skipping to change at line 304 | skipping to change at line 304 | |||

list or tree. | list or tree. | |||

Our first proposal (suggested by Github user funny-falcon) avoids this overhead | Our first proposal (suggested by Github user funny-falcon) avoids this overhead | |||

by always storing one tree per bin. It may also be worthwhile to store the first | by always storing one tree per bin. It may also be worthwhile to store the first | |||

entry directly in the bin, which avoids allocating any tree nodes in the common | entry directly in the bin, which avoids allocating any tree nodes in the common | |||

case where bins are sparsely populated. What kind of tree should be used? | case where bins are sparsely populated. What kind of tree should be used? | |||

Given SipHash and HighwayHash provide high quality randomness, depending on | Given SipHash and HighwayHash provide high quality randomness, depending on | |||

expecting attack surface simple non-balancing binary search tree could perform | expecting attack surface simple non-balancing binary search tree could perform | |||

reasonably well. [Wikipedia says](https://en.wikipedia.org/wiki/Binary_search_tr ee#Definition) | reasonably well. [Wikipedia says](https://en.wikipedia.org/wiki/Binary_search_tr ee#Definition) | |||

> After a long intermixed sequence of random insertion and deletion, the expecte | > After a long intermixed sequence of random insertion and deletion, the | |||

d | > expected height of the tree approaches square root of the number of keys, √n, | |||

> height of the tree approaches square root of the number of keys, √n, which gro | > which grows much faster than log n. | |||

ws | ||||

> much faster than log n. | ||||

While `O(√n)` is much larger than `O(log n)`, it is still much smaller than `O(n )`. | While `O(√n)` is much larger than `O(log n)`, it is still much smaller than `O(n )`. | |||

And it will certainly complicate the timing attack, since the time of operation | And it will certainly complicate the timing attack, since the time of operation | |||

on collisioned bin will grow slower. | on collisioned bin will grow slower. | |||

If stronger safety guarantees are needed, then a balanced tree should be used. | If stronger safety guarantees are needed, then a balanced tree should be used. | |||

Scapegoat and splay trees only offer amortized complexity guarantees, whereas | Scapegoat and splay trees only offer amortized complexity guarantees, whereas | |||

treaps require an entropy source and have higher constant factors in practice. | treaps require an entropy source and have higher constant factors in practice. | |||

Self-balancing structures such as 2-3 or red-black trees require additional | Self-balancing structures such as 2-3 or red-black trees require additional | |||

bookkeeping information. We can hope to reduce rebalancing cost by realizing | bookkeeping information. We can hope to reduce rebalancing cost by realizing | |||

skipping to change at line 358 | skipping to change at line 358 | |||

## Third-party implementations / bindings | ## Third-party implementations / bindings | |||

Thanks to Damian Gryski and Frank Wessels for making us aware of these | Thanks to Damian Gryski and Frank Wessels for making us aware of these | |||

third-party implementations or bindings. Please feel free to get in touch or | third-party implementations or bindings. Please feel free to get in touch or | |||

raise an issue and we'll add yours as well. | raise an issue and we'll add yours as well. | |||

By | Language | URL | By | Language | URL | |||

--- | --- | --- | --- | --- | --- | |||

Damian Gryski | Go and x64 assembly | https://github.com/dgryski/go-highway/ | Damian Gryski | Go and x64 assembly | https://github.com/dgryski/go-highway/ | |||

Lovell Fuller | node.js bindings | https://github.com/lovell/highwayhash | Lovell Fuller | node.js bindings | https://github.com/lovell/highwayhash | |||

Nick Babcock | Rust port | https://github.com/nickbabcock/highway-rs | ||||

Vinzent Steinberg | Rust bindings | https://github.com/vks/highwayhash-rs | Vinzent Steinberg | Rust bindings | https://github.com/vks/highwayhash-rs | |||

Frank Wessels & Andreas Auernhammer | Go and ARM assembly | https://github.com/m inio/highwayhash | Frank Wessels & Andreas Auernhammer | Go and ARM assembly | https://github.com/m inio/highwayhash | |||

Phil Demetriou | Python 3 bindings | https://github.com/kpdemetriou/highwayhash- cffi | Phil Demetriou | Python 3 bindings | https://github.com/kpdemetriou/highwayhash- cffi | |||

Jonathan Beard | C++20 constexpr | https://gist.github.com/jonathan-beard/632017 faa1d9d1936eb5948ac9186657 | ||||

## Modules | ## Modules | |||

### Hashes | ### Hashes | |||

* c_bindings.h declares C-callable versions of SipHash/HighwayHash. | * c_bindings.h declares C-callable versions of SipHash/HighwayHash. | |||

* sip_hash.cc is the compatible implementation of SipHash, and also provides | * sip_hash.cc is the compatible implementation of SipHash, and also provides | |||

the final reduction for sip_tree_hash. | the final reduction for sip_tree_hash. | |||

* sip_tree_hash.cc is the faster but incompatible SIMD j-lanes tree hash. | * sip_tree_hash.cc is the faster but incompatible SIMD j-lanes tree hash. | |||

* scalar_sip_tree_hash.cc is a non-SIMD version. | * scalar_sip_tree_hash.cc is a non-SIMD version. | |||

End of changes. 3 change blocks. | ||||

5 lines changed or deleted | | 5 lines changed or added |