9 ms·

A Critique of Rust's `std::collections`

85 points by pimeys 10y ago

zerosign 10y ago
I think std means standard collections, not custom ("special" case) collection library. People may look for this kind of specialization in outside std or create their own library. Or you could start be the first one who create this extended collection std.. CMIIW
jeffdavis 10y ago
I appreciate reading thoughtful, constructive criticisms like this. But ultimately, I didn't find any of his points paricularly compelling. Maybe the author can point to a language that really gets this right? I haven't written much rust, though.
paulddraper 10y ago
He says BinaryHeap is superfluous, but then complains there's not a priority queue. Huh? 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 https://docs.python.org/3.5/library/heapq.html Critique that next, please.
- desdiv 10y ago
  Yeah, he made an embarrassing mistake. I googled "rust binary heap" and the second link[0] is a priority queue example using the std binary heap. [0] https://doc.rust-lang.org/std/collections/binary_heap/ https://doc.rust-lang.org/std/collections/binary_heap/
  - paulddraper 10y ago
    The weird thing is...after having that brought to his attention, he reasserts his error.
programmer_man 10y ago
Typo: "alternatives and way(s) to improve it"
grayrest 10y ago
This showed up on r/rust last night and there's a lot of discussion there: https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcollections_is_absolutely_horrible/ https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcolle...
chowells 10y ago
Yes, you really do need collision attack resistance in your standard hash table implementation. You know why? Because we've known for a long time that insecure defaults are broken. I'm glad rust makes the correct choice here.
- AstralStorm 10y ago
  No, cryptographic hash has an additional property. It is one way. So, given a hash it is hard to derive original input. 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.
  - koverstreet 10y ago
    Uh, what? Siphash isn't a cryptographic hash function. It's a keyed hash function designed not to leak the key.
  - valarauca1 10y ago
    >It is one way. So, given a hash it is hard to derive original input. 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.
    - luchs 10y ago
      >This is the definition of a Hash Function. Not a cryptographic Hash Function. 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.
bluejekyll 10y ago
I'm not entirely sure I get all of these arguments. It sounds like someone complaining about the language being young, and the early implementations aren't perfect. 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!
- hyperpape 10y ago
  It's true that Java took a long time to develop (good) concurrent collections, but I will suggest that they're more important in 2016 than they were in 1995. Core counts are increasing, and the competition from other languages is better. 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).
  - bluejekyll 10y ago
    I didn't mean to imply that a ten year wait was acceptable. That being said, expecting stable concurrent libraries just one year after the language stabilized isn't reasonable. Futures just landed, and those seem like a good first step toward a good concurrency model.
- Manishearth 10y ago
  I strongly believe that concurrent datastructures should be kept out of the stdlib. There are just way too many tradeoffs to worry about here, and these tradeoffs are far more important in the concurrent case. 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.
petters 10y ago
> And, ignoring that point for a moment, The idea that your code is ‘secure by default’ is a dangerous one and promotes ignorance about security. You code is not secure by default Bah. This argument can be used to show anything. I could argue that C++ is better than Rust with the same argument.
loeg 10y ago
> The other popular self-balancing trees are good candidates as well (AVL and LLRB/Red-black). While they do essentially the same, they can have very different performance characteristics, and switching can influence the program’s performance vastly. 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).
- wahern 10y ago
  In C and C++ code it's common to use a red-black tree implementation where the node is part of the object. For example, using the standard BSD library #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 In such implementations the RB tree will be faster. The reason to prefer a B-tree is to minimize the number of cache misses incurred when loading objects _through_ separately allocated nodes. But if the node is part of the object, you've already eliminated that cost entirely and so a B-tree is strictly inferior. <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.
jsnell 10y ago
A lot of this article might be a matter of opinion, but the discussion on HashMaps seems to be outright false. The author has set up some kind of a double hashing strawman, when the actual implementation uses linear probing (which is the only kind of Robin Hood hash table anyone would implement today).
agentgt 10y ago
In all fairness I have yet to see a language with an awesome builtin collections library that meets everyones needs (and I use JDK collections all the time.... it took a long time to get where it is and still is sort of ok). If you know of a language that does please chime in. 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.
thenewwazoo 10y ago
This particular quote rang very true to me: > 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.
- steveklabnik 10y ago
  I am interested in improving this. It's tough because as an experienced Rust programmer, I feel like it's obvious, but have a hard time figuring out how to put it into words. It should be something that can be intuitive, rather than needing explicit docs, though those can help too.
- kibwen 10y ago
  I agree that we should add some more documentation in this area (though we always have to be careful that we don't document things so thoroughly that we de-facto stabilize the internals and make it impossible for us to improve them in the future). But in the meantime, if you're just learning the language, I would recommend not being overly concerned with the performance details of collections until you start seeing them at the top of your performance profiles. 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-use-which-collection https://doc.rust-lang.org/std/collections/#when-should-you-u...
  - thenewwazoo 10y ago
    Well, it's not so much about performance of existing code as it is about being able to take a high-level view of the design of a program. To pick a bad example, if I know one function will allocate memory according to a certain pattern (e.g. 2n*sizeof(obj)) and another will just shift an internal pointer around, I predict it'll get easier to reason about the behavior of the code. The semantics of ?alloc+free are exceptionally easy to understand, but I have no idea how or when Rust allocates memory, except for a vague notion of heap vs stack. I suspect there's an elegant relationship between how Rust does its (hidden) memory management and the behavior of the borrow checker, but I haven't come across anything yet linking the two concepts. Mostly, I think my problem is that I don't know what I don't know. Like I said, I'm green. :)
exDM69 10y ago
The variant of Robin Hood hash table isn't a double hashing scheme like the original research paper. This is more like linear probing with a collision resolution trick to reduce worst case in lookups. 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.
cpeterso 10y ago
Does Rust define collection traits for abstract interfaces like Set, Map, and Queue like Java's Collections interfaces? I don't see any in the std::collections documentation. Standardizing those APIs in the std lib seems as (or more!) important than providing concrete implementations like BTreeMap. I see some 2015 discussion about missing collections traits: https://internals.rust-lang.org/t/collection-traits-take-2/1272 https://internals.rust-lang.org/t/collection-traits-take-2/1... https://internals.rust-lang.org/t/traits-that-should-be-in-std-but-arent/3002 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/interfaces/index.html http://docs.oracle.com/javase/tutorial/collections/interface...
- steveklabnik 10y ago
  IIRC, we need higher kinded types before we can create a truly great set of generic collections traits.
  - mafribe 10y ago
    Are higher-kinded types scheduled for inclusion? If so when?
    - steveklabnik 10y ago
      They're at the "nobody has yet to come up with a serious proposal" stage. Some are skeptical that they can ever fit in. We'll see.
      - mafribe 10y ago
        Thanks. Do you know who is working on this? I'd like to talk with them.
        steveklabnik 10y ago
        I'm not aware of anyone seriously pursuing it yet.

85 points by pimeys 10y ago

I think std means standard collections, not custom ("special" case) collection library. People may look for this kind of specialization in outside std or create their own library. Or you could start be the first one who create this extended collection std.. CMIIW

jeffdavis 10y ago

I appreciate reading thoughtful, constructive criticisms like this. But ultimately, I didn't find any of his points paricularly compelling. Maybe the author can point to a language that really gets this right? I haven't written much rust, though.

paulddraper 10y ago

He says BinaryHeap is superfluous, but then complains there's not a priority queue. Huh? 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 https://docs.python.org/3.5/library/heapq.html Critique that next, please.

desdiv 10y ago
Yeah, he made an embarrassing mistake. I googled "rust binary heap" and the second link[0] is a priority queue example using the std binary heap. [0] https://doc.rust-lang.org/std/collections/binary_heap/ https://doc.rust-lang.org/std/collections/binary_heap/
- paulddraper 10y ago
  The weird thing is...after having that brought to his attention, he reasserts his error.

programmer_man 10y ago

Typo: "alternatives and way(s) to improve it"

grayrest 10y ago

This showed up on r/rust last night and there's a lot of discussion there: https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcollections_is_absolutely_horrible/ https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcolle...

chowells 10y ago

Yes, you really do need collision attack resistance in your standard hash table implementation. You know why? Because we've known for a long time that insecure defaults are broken. I'm glad rust makes the correct choice here.

AstralStorm 10y ago
No, cryptographic hash has an additional property. It is one way. So, given a hash it is hard to derive original input. 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.
- koverstreet 10y ago
  Uh, what? Siphash isn't a cryptographic hash function. It's a keyed hash function designed not to leak the key.
- valarauca1 10y ago
  >It is one way. So, given a hash it is hard to derive original input. 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.
  - luchs 10y ago
    >This is the definition of a Hash Function. Not a cryptographic Hash Function. 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.

bluejekyll 10y ago

I'm not entirely sure I get all of these arguments. It sounds like someone complaining about the language being young, and the early implementations aren't perfect. 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!

hyperpape 10y ago
It's true that Java took a long time to develop (good) concurrent collections, but I will suggest that they're more important in 2016 than they were in 1995. Core counts are increasing, and the competition from other languages is better. 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).
- bluejekyll 10y ago
  I didn't mean to imply that a ten year wait was acceptable. That being said, expecting stable concurrent libraries just one year after the language stabilized isn't reasonable. Futures just landed, and those seem like a good first step toward a good concurrency model.
Manishearth 10y ago
I strongly believe that concurrent datastructures should be kept out of the stdlib. There are just way too many tradeoffs to worry about here, and these tradeoffs are far more important in the concurrent case. 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.

petters 10y ago

> And, ignoring that point for a moment, The idea that your code is ‘secure by default’ is a dangerous one and promotes ignorance about security. You code is not secure by default Bah. This argument can be used to show anything. I could argue that C++ is better than Rust with the same argument.

loeg 10y ago

> The other popular self-balancing trees are good candidates as well (AVL and LLRB/Red-black). While they do essentially the same, they can have very different performance characteristics, and switching can influence the program’s performance vastly. 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).

wahern 10y ago
In C and C++ code it's common to use a red-black tree implementation where the node is part of the object. For example, using the standard BSD library #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 In such implementations the RB tree will be faster. The reason to prefer a B-tree is to minimize the number of cache misses incurred when loading objects _through_ separately allocated nodes. But if the node is part of the object, you've already eliminated that cost entirely and so a B-tree is strictly inferior. <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.

jsnell 10y ago

A lot of this article might be a matter of opinion, but the discussion on HashMaps seems to be outright false. The author has set up some kind of a double hashing strawman, when the actual implementation uses linear probing (which is the only kind of Robin Hood hash table anyone would implement today).

agentgt 10y ago

In all fairness I have yet to see a language with an awesome builtin collections library that meets everyones needs (and I use JDK collections all the time.... it took a long time to get where it is and still is sort of ok). If you know of a language that does please chime in. 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.

thenewwazoo 10y ago

This particular quote rang very true to me: > 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.

steveklabnik 10y ago
I am interested in improving this. It's tough because as an experienced Rust programmer, I feel like it's obvious, but have a hard time figuring out how to put it into words. It should be something that can be intuitive, rather than needing explicit docs, though those can help too.
kibwen 10y ago
I agree that we should add some more documentation in this area (though we always have to be careful that we don't document things so thoroughly that we de-facto stabilize the internals and make it impossible for us to improve them in the future). But in the meantime, if you're just learning the language, I would recommend not being overly concerned with the performance details of collections until you start seeing them at the top of your performance profiles. 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-use-which-collection https://doc.rust-lang.org/std/collections/#when-should-you-u...
- thenewwazoo 10y ago
  Well, it's not so much about performance of existing code as it is about being able to take a high-level view of the design of a program. To pick a bad example, if I know one function will allocate memory according to a certain pattern (e.g. 2n*sizeof(obj)) and another will just shift an internal pointer around, I predict it'll get easier to reason about the behavior of the code. The semantics of ?alloc+free are exceptionally easy to understand, but I have no idea how or when Rust allocates memory, except for a vague notion of heap vs stack. I suspect there's an elegant relationship between how Rust does its (hidden) memory management and the behavior of the borrow checker, but I haven't come across anything yet linking the two concepts. Mostly, I think my problem is that I don't know what I don't know. Like I said, I'm green. :)

exDM69 10y ago

The variant of Robin Hood hash table isn't a double hashing scheme like the original research paper. This is more like linear probing with a collision resolution trick to reduce worst case in lookups. 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.

cpeterso 10y ago

Does Rust define collection traits for abstract interfaces like Set, Map, and Queue like Java's Collections interfaces? I don't see any in the std::collections documentation. Standardizing those APIs in the std lib seems as (or more!) important than providing concrete implementations like BTreeMap. I see some 2015 discussion about missing collections traits: https://internals.rust-lang.org/t/collection-traits-take-2/1272 https://internals.rust-lang.org/t/collection-traits-take-2/1... https://internals.rust-lang.org/t/traits-that-should-be-in-std-but-arent/3002 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/interfaces/index.html http://docs.oracle.com/javase/tutorial/collections/interface...

steveklabnik 10y ago
IIRC, we need higher kinded types before we can create a truly great set of generic collections traits.
- mafribe 10y ago
  Are higher-kinded types scheduled for inclusion? If so when?
  - steveklabnik 10y ago
    They're at the "nobody has yet to come up with a serious proposal" stage. Some are skeptical that they can ever fit in. We'll see.
    - mafribe 10y ago
      Thanks. Do you know who is working on this? I'd like to talk with them.
      - steveklabnik 10y ago
        I'm not aware of anyone seriously pursuing it yet.