A Critique of Rust's `std::collections`
ticki.github.io
ticki.github.io
Collision resistance is a separate property which can be fulfilled without one way property.
Maybe you want hash numbers that are not predictable by an attacker, but sip hash is not salted either. Plus salting does not require a cryptographic hash either.
Siphash isn't a cryptographic hash function. It's a keyed hash function designed not to leak the key.
This is the definition of a Hash Function. Not a cryptographic Hash Function.
Cryptographic Hashes should NEVER collide, on any inputs, ever, period. The moment it is found too, the algorithm is considered depreciated. This is why MD5 shouldn't be used anymore, there is a generalized algorithm for producing collisions.
Cryptographic hashes are overkill for HashTables/HashMaps because you can't use 128/256/512bit address spaces unless your attempt to store all the information in the galaxy or observable universe. And modern computers just aren't there yet. Also they are very slow.
So when your masking a 512bit output, down to 16bits of your HashTable you just lose the will never collide guarantee. Then something that operates at 10GB/s, and can collide sounds better then something that runs at 150MB/s and will still collide anyways.
No, a hash function is just any function which can be used to put values into a hash map. If your inputs are numbers, modulo will work fine as a hash function, but is obviously not one-way.
>Cryptographic Hashes should NEVER collide, on any inputs, ever, period.
This is obviously not possible, as the output of the cryptographic hash function is of fixed-length while the input is variable-length. Finding collision just needs to be hard, not impossible.
modulo will work fine as a hash function, but is obviously not one-way.
Proof via arrogance:
X % 100 = 50
Solve for X
Solution X = F(n) where F(n) = 100*n+50 (for all n > 1)
Cryptographic Hashes should NEVER collide, on any inputs, ever, period.
>This is obviously not possible
Obviously yes all cryptographic hashes aren't unique for every input. As they maybe N bytes long. And simply a logic will tell you there is more information in N bytes of data vs 64 bytes (512bits).
The real issue is, prove it. Testing even the 512bit address space will take you longer then the heat death of the universe, so good luck!
https://en.wikipedia.org/wiki/Trapdoor_function
Note that the definition is about a pre-image, not necessarily the input used to create it in the first place.
Second, that definition is absolutely not correct. "Never" would require that the size of the output of the hash function be equivalent to the size of the universe of possible inputs, which it obviously isn't. There's a very important difference between "never be observed in practice" and "never, period." You're not using the language precisely, and that's very dangerous when talking about hashing and cryptography.
None of those properties is needed for indexing into hash table. Good collision resistance is all that is required and salting for more paranoid cases.
> you just lose the will never collide guarantee
There is no such guarantee, in fact, the opposite is guaranteed.
It's just very unlikely that you get a collision - that's a desirable property of any hash function -, and it should be hard to create a collision because the function is hard to reverse - that's a desirable property of any cryptographic hash function, as the OP laid out.
No it doesn't. These are independent properties. That is, collision resistance does not imply onewayness, and onewayness does not imply collision resistance.
Collision Resistance: it is hard to find x != x' such that h(x) = h(x')
One Wayness: Given y, an n-bit string randomly chosen from the output space of h(), it is hard to find any x such that h(x) = y.
Proof that CR does not imply OW: Suppose g() is collision resistant and outputs n bits. Define h(x) to be 0x if x is n bits long, otherwise 1x. Collisions are hard to find: if y starts with 1 there are no collisions, and if it starts with 0 then you'd need to find a collision in g(), which is collision resistant. h() is not one way: given a random y in the output space, with probability 1/2 it is trivial to find an x such that h(x) = y.
Proof that OW does not imply CR: Suppose that g() is one-way. Define h(x) = g(x) with the last bit truncated. h() is one-way because you cannot invert h without inverting g(). h() is not collision resistant because for any x, h(x0) = h(x1)
It's not the fastest general purpose hash --- but it's not supposed to be. It's supposed to be performant enough to be used as a default, and in being a default, it's supposed to take a pretty common attack off the table.
It's the right default. In the rare situations where container hashing winds up high on the profile, the faster hash should be the optional hash.
[edit]
Also, as a slight additional nitpick to the article, the term "cryptographic hash," when used in isolation, typically implies collision resistance, and SipHash is specifically not collision resistant due to its small output size.
I studied SipHash a while ago and implemented a SIMD version but that performed slower (needs 4x64 bit int vectors and doesn't allow any instruction level parallelism). I'm sure that you could make a faster hash function with 4x32 bit vectors using similar ARX (add-rotate-xor) networks but I'm not smart enough to do the cryptanalysis.
There's a new hash function called HighwayHash which was about 11GB/s but the implementation is very tied to Intel CPUs (SSE4.1 or AVX512) and uses 4x64 bit vectors. And no cryptanalysis on that either, although it looks like it has similar characteristics to SipHash.
Hash table keys are typically quite short, so going crazy with SIMD to push the throughput might not be a great idea.
SipHash is the only hash function that has credible cryptanalysis against key recovery and collisions.
E.g. FNV1 is trivially simple to generate collisions against.
Yes, it's non-reversable, and it doesn't allow easy seed-independent multi collisions as with other hash functions. But one hash function used in a hash table can never be secure. The collision resolution adds the security part. (or/plus some other schemes which are obviously over your head).
https://internals.rust-lang.org/t/collection-traits-take-2/1...
https://internals.rust-lang.org/t/traits-that-should-be-in-s...
For comparison, here are Java's core collection interfaces: Collection, Set, SortedSet, List, Queue, Deque, Map, and SortedMap.
http://docs.oracle.com/javase/tutorial/collections/interface...
https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcolle...
Bah. This argument can be used to show anything. I could argue that C++ is better than Rust with the same argument.
For not being perfect, it's amazing how awesome the std lib is!
Also, the concurrent collections didn't show up in Java until 1.5, I believe. I think that was ten years into the life of the language, which was after the 1.3/4 releases which actually made the JVM substantially more performant.
Rust is young, concurrent data models are hard, but it is being worked on, and you can lend a hand! There are good points in this article, and some of them are being discussed on the Rust forums. This is a great time to be involved in helping shape a language and its libraries!
I'm not saying we should be disgusted if there aren't immediately awesome concurrent data structures, but you can't be satisfied with waiting until 2024 (the equivalent of Java 1.5, I believe).
Futures just landed, and those seem like a good first step toward a good concurrency model.
Take a concurrent hashmap for example. Do you want a "vec of lock free lists" kind which is lock free and infinite-capacity (no need to copy-reallocate), or do you want a probing one which has fine-grained locks and needs to reallocate (but has better cache behavior)? Or something in between? If it matters enough that `Mutex<HashMap<K,V>>` isn't good enough, then these tradeoffs matter too. Rust could have a rogues' gallery of concurrent hashmaps, but that feels like bloat.
Some already exist in the ecosystem, though, and you can always use those. But I'd love to see more work here!
Having a semi-official/nursery library containing a lot of concurrent datastructures would be nice, though. crossbeam provides better primitives for writing such things, but not the actual datastructures.
There are tradeoffs in non-concurrent data structures too. Do you want a boolean vector that aligns to word size, or one that conserves memory and fits in cache? Pushed to the limit, nearly ever non-primitive part of the library has compromises.
Don't let great be the enemy of good. Concurrent collections are a common need. Include some reasonable implementations with compromises. No, you won't answer every use case, but you can be better than `Mutex<HashMap<K,V>>` and still provide something solid.
Need a concurrent hashmap? Use Mutex<HashMap>. Think that's not good enough for your use case? Then what the stdlib would have offered will probably not fit for you either.
Remember, I'm not saying that we shouldn't have these things in a library somewhere (even an official library), I'm saying they shouldn't be in the stdlib, because there's an additional burden to that, and stability guarantees mean that it's harder to evolve.
> If the allocation is hidden to the programmer, she might not realize the expensive operations behind the scenes.
I am a green Rust programmer, and I currently have little insight into the allocation costs of the various things I'm doing, and I haven't yet found a strategy for gaining it. I feel like the actual mechanisms for memory management are so deeply buried that it would take lots and lots of spelunking to get an idea of what's going on behind the scenes. Even something as simple as a "This function allocates <x> memory" tag with stdlib functions would help me immensely.
EDIT: And of course, I do encourage you to check out the documentation that we have in the std::collections module that goes into at least a little detail about each of the standard collections, along with tips for choosing when to use each: https://doc.rust-lang.org/std/collections/#when-should-you-u...
Mostly, I think my problem is that I don't know what I don't know. Like I said, I'm green. :)
A binary heap is a priority queue. (Specifically, a binary heap is an implementation of a priority queue, just as a linked list is an implementation of a list.)
Even after the "they're fundamentally very different" update, he's still wrong.
Wanna know what the (non-synchronized) priority queue is called in Python? heapq https://docs.python.org/3.5/library/heapq.html Critique that next, please.
The article suggests using quadratic probing instead, but that has two weaknesses. Cache locality is worse than linear probing. But the deal breaker is that the hash table must have a prime number size for correctness. This makes the hash table grow quite quickly once the size reaches tens of thousands. And finding primes is another issue.
The big thing I missed in my limited playing around with Rust is more types of queues. This is in large part because I was attacking Rust in a similar way to Java. Because of its lack of other concurrency models other than threads I was resorting to queues (I'm sure there are more "reactive-like" libraries now).
Overall I can't decide if a better approach might be to let library writers work on adding more structures instead of a batteries included approach. Maybe just have the traits included and thats it.
In what scenario would you prefer an RB-tree (or AVL tree) to a B-tree?
My understanding is that the performance characteristics of RB/AVL trees can mostly be described as "worse." Maybe insert speed? But in that case, you'd really prefer an LSM tree.
The author is also very confused about how hash table DoS attacks are protected. And what a cryptographic hash is. There are very fast non-cryptographic hash functions like xxHash (in fact, I thought siphash was much faster than 1GB/s, but I could be misremembering).
Heck, for large inputs, python's random hash isn't much faster than hmacmd5, but for 8 byte inputs python's random hash is faster than siphash24.
The better measurement is X hashes per second at N key size, and then perform that at a few key sizes.
[edit]
I finally found a comparison that does this and includes siphash:
http://cglab.ca/~abeinges/blah/hash-rs/
Note that siphash is competitive with everything except FNV for small inputs, but FNV blows it away up to about 60 bytes.
> but for 8 byte inputs python's random hash is faster
> than siphash24.
(I need to get clearance to post updated results)
I think not looking at both the bare hash performance and the map performance is a bad idea because there are a lot more variables involved testing against a Map, but poor distribution (which ought not be an issue with anything except FNV on that graph) could make a fast hash not useful.
#include <sys/tree.h>
struct foo {
RB_ENTRY(foo) rbe; // tree node
};
RB_HEAD(foo_tree, foo);
RB_GENERATE(foo_tree, foo, rbe, foo_cmp);
...
struct foo_tree rbt = { 0 };
struct foo *foo;
...
RB_INSERT(foo_tree, &rbt, foo); // no memory allocation
<sys/tree.h> is written in the same vein as <sys/queue.h>, a collection of list implementations originally included with BSD and even provided by glibc. The tree and especially list routines are used for most of the data structures in *BSD kernels and utilities, and the Linux kernel and other systems often use very similar libraries.
The downside to using predefined, preallocated nodes is that you can't mix-and-match types in the same collection. And an object can only be inserted into a single collection unless you define multiple nodes.
In practice this isn't a concern. Especially in systems programming it's uncommon to need or even want to stash random objects in a collection, or for objects to exist in many multiple trees or lists simultaneously.
And it's a very useful property to be able to rely on the fact that insertion can _never_ fail (always for lists; qualified never for trees). That dramatically simplifies code dealing with complex data structures and that must remain robust in the face of resource exhaustion. It means that once you've allocated a new object, you can guarantee insertion into any number of collections. That also simplifies backing out of a transaction because you can make guarantees about consistency--i.e. that an object is definitely a member of this list or that tree. This benefit is often overlooked in Rust and elsewhere because idiomatic Rust code is expected to exit on memory exhaustion anyhow.
I can't remember the last time I actually used a hash table in C that wasn't specialized (e.g. perfect hash function). The fact that a dynamic hash table may need to be resized introduces an undesirable failure mode; it may happen only once in a million insertions, but that's significantly more often than never. For general use I default to a red-black tree, which usefully can serve as a sorted container, too (e.g. for priority queues). When performance matters (i.e. a proven bottleneck) I'll invariably use a more specialized data structure and implementation suited to the particular problem, perhaps also refactoring other aspects of the code as appropriate.
IMHO, all this concern about the fastest general purpose algorithm and implementation seems like bike shedding. When performance _truly_, _manifestly_ matters, a general purpose implementation is unlikely to suffice.
I haven't written much rust, though.