4 ms·

creating the map with an appropriate capacity would probably speed up its implementation significantly having to rehash several times is nasty

bayindirh 4y ago
If it also causes re-allocations when the capacity is set to too low a la C++, the speedup will be more than significant.
- masklinn 4y ago
  It necessarily does. That is also the case where it might cause a rehash, however that’s less certain as many hashmaps will trade memory for storing the hashes to avoid recomputing them over and over. I’d assume they can use these hashes directly when reallocating, though they still need to perform collision resolution. Either way properly sizing the hashmap is a good idea. Though load factor needs to be take in account, and I’m not sure whether the average hashmap multiplies the capacity by the maximum load factor in order to ensure there’s actually space for the number of items intended. I’d hope so, but…
avg_dev 4y ago
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 4y 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 4y 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 4y 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 4y 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 4y 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.

bayindirh 4y ago

If it also causes re-allocations when the capacity is set to too low a la C++, the speedup will be more than significant.

masklinn 4y ago
It necessarily does. That is also the case where it might cause a rehash, however that’s less certain as many hashmaps will trade memory for storing the hashes to avoid recomputing them over and over. I’d assume they can use these hashes directly when reallocating, though they still need to perform collision resolution. Either way properly sizing the hashmap is a good idea. Though load factor needs to be take in account, and I’m not sure whether the average hashmap multiplies the capacity by the maximum load factor in order to ensure there’s actually space for the number of items intended. I’d hope so, but…

avg_dev 4y ago

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 4y 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 4y 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 4y 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 4y 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 4y 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.