4 ms·

I’ve never actually seen a length passed to make() when creating a map - does it work? Edit: yep - https://go.dev/ref/spec#Making_slices_maps_and_channels http

I’ve never actually seen a length passed to make() when creating a map - does it work? Edit: yep - https://go.dev/ref/spec#Making_slices_maps_and_channels https://go.dev/ref/spec#Making_slices_maps_and_channels

tialaramex 3y ago
[From that link] > map of type T with initial space for approximately n elements That "approximately" isn't great there. Nobody wants "approximately". If "exactly" is difficult - which it might be in many conceivable designs for this data structure - then what you want to offer is "at least". If I'm a programmer and I know I want to put all 623 of these Doodads in the data structure, offering me a way to get a data structure with space for exactly 623 is great. One with space for at least 623 is fine, whereas approximately 623 is barely useful. Should I try asking for 624 in case that helps ? Do I need to dig into the detailed implementation to figure out, OK, 700 will definitely ensure 623 will fit ?
- foldr 3y ago
  I’m guessing the amount of space occupied by N elements will vary depending on how the hashing plays out for the given keys (and probably key insertion order too). So ‘approximately’ is probably the best you can do without making enormous pessimal overallocations.
  - tialaramex 3y ago
    Blergh, I spent a while digging and you're right which is pretty sad. Go's map appears to end up as an array of buckets where each bucket is eight items but can form a linked list of overflow buckets as needed. So if we tell Go we want to store 623 Doodads in the map, Go will try to guess how many buckets (of up to 8 Doodads) it should use for the map, and I think it'll try 128 here? Although maybe 96. 128 buckets means when we actually put our 623 Doodads in the map, on average the buckets are just over half full, but there's a fair chance that by accident one of our buckets fills completely, requiring an overflow, which allocates even though we told the map we had 623 Doodads. There are a lot of design choices in Go that I don't sympathise with and this is one of them.
    - foldr 3y ago
      That's just how hashtables work, isn't it? Do you know of any hash table implementations that allow this kind of 'at least' allocation?
      - tialaramex 3y ago
        Most modern hash map designs don't do this weird shuffle with buckets and linked lists because pointer chasing is super expensive. https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.with_capacity https://doc.rust-lang.org/std/collections/struct.HashMap.htm... Because it's documenting the actual API in the standard library this even spells out that the result has "at least the specified capacity" https://github.com/facebook/folly/blob/main/folly/container/F14.md https://github.com/facebook/folly/blob/main/folly/container/... F14 is a linear map but I couldn't immediately find actual API documentation, however it should have the same property where if you ask for an F14 with specific capacity or you reserve enough capacity, that's an "at least" promise not an approximate one.
        foldr 3y ago
        I believe Rust uses hashbrown as the underlying implementation now. This just calculates the number of buckets based on the number of items requested: https://github.com/rust-lang/hashbrown/blob/009969a86029084938f3966f92f446cdcfa1eb1f/src/raw/mod.rs#L202 https://github.com/rust-lang/hashbrown/blob/009969a860290849... In the worst case all the items you insert will go in one bucket, and you'll have to rehash, which requires allocation. I'm not sure this is any different from Go in that respect. I suspect that the inherently probabilistic nature of a hashtable makes it impossible to guarantee capacity without allocating way more space than would be required in typical cases. If there is a clever way to avoid this it would certainly be interesting to read about it. Edit: Also, Go's hashtable implementation does not use linked lists (though it is a chaining implementation).
        tialaramex 3y ago
        Your initial observation is correct, Rust's HashMap is these days a HashBrown, which is an implementation of Google's Swiss Tables: But the use of the "Bucket" nomenclature in that file has probably misled you, the buckets it is talking about are for putting exactly one item in and they're just stored as one huge growable array (like a Vec). Suppose we do as I mentioned before: let mut doodads: HashMap<Doodad> = HashMap::with_capacity(623); The calculation will do 623 * (8/7) which is 712, and then it'll round up to the next power of two [ultimately because shifts are cheaper elsewhere in the arithmetic] which is 1024. So it allocates 1024 buckets sized to store one Doodad each. The Swiss Tables algorithm would work up until 1023 Doodads are in the table (one must be empty, but it doesn't matter which one) however performance trade offs mean you should resize before that, HashBrown does so after 1024 * (7/8) = 896 items, which you'll observe is indeed "at least" 623 items. > In the worst case all the items you insert will go in one bucket, and you'll have to rehash In the worst case - which is incredibly unlikely with a good hash, and you'll notice Rust supplies a good hash by default - we'll insert 623 items which have the same hash, and so they'll prefer to ideally be in the same bucket, but they're instead taking up 623 contiguous buckets and all our searches are now linear, so our performance is poor with average probe length 312. But we don't in fact grow, even if you could argue we should grow, this is so unlikely that it's not catered for, you won't find any code to detect this scenario let alone do anything about it. > If there is a clever way to avoid this it would certainly be interesting to read about it. All the modern Open Addressed hash tables avoid this, by just not caring about the incredibly unlikely "But what if all my data hashes to the same value?" case. This means if you did hit that case their performance is abysmal, but you won't so who cares. They just degrade gracefully as we get progressively unluckier, whereas Go's approach is forced to allocate as soon as we get unlucky enough. It might seem like Go's approach is great if we've got plenty of memory and don't mind allocations, since at least we don't degrade performance when we're unlucky. Unfortunately that non-degraded performance isn't very good. Go would choose 128 buckets with space for 8 Doodads in each bucket, but this means most of our buckets have 4 or 5 Doodads in them, and we always try them in order, so look-up actually probes considerably more Doodads than with Open Addressing normally. The Swiss Tables have to get pretty unlucky before they are that bad, and whenever they're not unlucky they're doing much better...

tialaramex 3y ago

[From that link] > map of type T with initial space for approximately n elements That "approximately" isn't great there. Nobody wants "approximately". If "exactly" is difficult - which it might be in many conceivable designs for this data structure - then what you want to offer is "at least". If I'm a programmer and I know I want to put all 623 of these Doodads in the data structure, offering me a way to get a data structure with space for exactly 623 is great. One with space for at least 623 is fine, whereas approximately 623 is barely useful. Should I try asking for 624 in case that helps ? Do I need to dig into the detailed implementation to figure out, OK, 700 will definitely ensure 623 will fit ?

foldr 3y ago
I’m guessing the amount of space occupied by N elements will vary depending on how the hashing plays out for the given keys (and probably key insertion order too). So ‘approximately’ is probably the best you can do without making enormous pessimal overallocations.
- tialaramex 3y ago
  Blergh, I spent a while digging and you're right which is pretty sad. Go's map appears to end up as an array of buckets where each bucket is eight items but can form a linked list of overflow buckets as needed. So if we tell Go we want to store 623 Doodads in the map, Go will try to guess how many buckets (of up to 8 Doodads) it should use for the map, and I think it'll try 128 here? Although maybe 96. 128 buckets means when we actually put our 623 Doodads in the map, on average the buckets are just over half full, but there's a fair chance that by accident one of our buckets fills completely, requiring an overflow, which allocates even though we told the map we had 623 Doodads. There are a lot of design choices in Go that I don't sympathise with and this is one of them.
  - foldr 3y ago
    That's just how hashtables work, isn't it? Do you know of any hash table implementations that allow this kind of 'at least' allocation?
    - tialaramex 3y ago
      Most modern hash map designs don't do this weird shuffle with buckets and linked lists because pointer chasing is super expensive. https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.with_capacity https://doc.rust-lang.org/std/collections/struct.HashMap.htm... Because it's documenting the actual API in the standard library this even spells out that the result has "at least the specified capacity" https://github.com/facebook/folly/blob/main/folly/container/F14.md https://github.com/facebook/folly/blob/main/folly/container/... F14 is a linear map but I couldn't immediately find actual API documentation, however it should have the same property where if you ask for an F14 with specific capacity or you reserve enough capacity, that's an "at least" promise not an approximate one.
      - foldr 3y ago
        I believe Rust uses hashbrown as the underlying implementation now. This just calculates the number of buckets based on the number of items requested: https://github.com/rust-lang/hashbrown/blob/009969a86029084938f3966f92f446cdcfa1eb1f/src/raw/mod.rs#L202 https://github.com/rust-lang/hashbrown/blob/009969a860290849... In the worst case all the items you insert will go in one bucket, and you'll have to rehash, which requires allocation. I'm not sure this is any different from Go in that respect. I suspect that the inherently probabilistic nature of a hashtable makes it impossible to guarantee capacity without allocating way more space than would be required in typical cases. If there is a clever way to avoid this it would certainly be interesting to read about it. Edit: Also, Go's hashtable implementation does not use linked lists (though it is a chaining implementation).
        tialaramex 3y ago
        Your initial observation is correct, Rust's HashMap is these days a HashBrown, which is an implementation of Google's Swiss Tables: But the use of the "Bucket" nomenclature in that file has probably misled you, the buckets it is talking about are for putting exactly one item in and they're just stored as one huge growable array (like a Vec). Suppose we do as I mentioned before: let mut doodads: HashMap<Doodad> = HashMap::with_capacity(623); The calculation will do 623 * (8/7) which is 712, and then it'll round up to the next power of two [ultimately because shifts are cheaper elsewhere in the arithmetic] which is 1024. So it allocates 1024 buckets sized to store one Doodad each. The Swiss Tables algorithm would work up until 1023 Doodads are in the table (one must be empty, but it doesn't matter which one) however performance trade offs mean you should resize before that, HashBrown does so after 1024 * (7/8) = 896 items, which you'll observe is indeed "at least" 623 items. > In the worst case all the items you insert will go in one bucket, and you'll have to rehash In the worst case - which is incredibly unlikely with a good hash, and you'll notice Rust supplies a good hash by default - we'll insert 623 items which have the same hash, and so they'll prefer to ideally be in the same bucket, but they're instead taking up 623 contiguous buckets and all our searches are now linear, so our performance is poor with average probe length 312. But we don't in fact grow, even if you could argue we should grow, this is so unlikely that it's not catered for, you won't find any code to detect this scenario let alone do anything about it. > If there is a clever way to avoid this it would certainly be interesting to read about it. All the modern Open Addressed hash tables avoid this, by just not caring about the incredibly unlikely "But what if all my data hashes to the same value?" case. This means if you did hit that case their performance is abysmal, but you won't so who cares. They just degrade gracefully as we get progressively unluckier, whereas Go's approach is forced to allocate as soon as we get unlucky enough. It might seem like Go's approach is great if we've got plenty of memory and don't mind allocations, since at least we don't degrade performance when we're unlucky. Unfortunately that non-degraded performance isn't very good. Go would choose 128 buckets with space for 8 Doodads in each bucket, but this means most of our buckets have 4 or 5 Doodads in them, and we always try them in order, so look-up actually probes considerably more Doodads than with Open Addressing normally. The Swiss Tables have to get pretty unlucky before they are that bad, and whenever they're not unlucky they're doing much better...