4 ms·

That's not quite it: with heapless, memory is fully static, the size of hash map is a compile-time parameter, which is a part of HashMap's type. In Zig, the ma

That's not quite it: with heapless, memory is fully static, the size of hash map is a compile-time parameter, which is a part of HashMap's type. In Zig, the map could be initialized and sized at runtime, but you still can enforce, statically, that it doesn't do any allocations after that. In both nightly Rust and Zig, heapless version can be expressed by passing a fixed-buffer-backed allocator to the standard hash map.

menaerus 3y ago
I don't quite understand how do you change the size of a zig hashmap in runtime by, for example, inserting 1M items at some point but at the same time being able to enforce in compile-time that such operation will not result with dynamic allocation?
- 8n4vidtmkvmk 3y ago
  I don't know, but you could avoid resizing the hashmap and allow the collisions but then your buckets would still need resizing
- matklad 3y ago
  Compare these two methods: https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3cbe0ad1a18bc0dd55/lib/std/hash_map.zig#L1196 https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c... https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3cbe0ad1a18bc0dd55/lib/std/hash_map.zig#L1014 https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c... One of them requires passing an allocator (and can allocate), the other doesn’t have an allocator argument (and thus can’t allocate). If you only pass allocator to `init` method of your application, and don’t store it anywhere, only init will be able to call allocating methods, the rest of the app will be allocation free, by construction.
  - menaerus 3y ago
    If the second one can't allocate then how does it handle the case where you don't have enough capacity to insert the new (k,v) pair? I can see that the difference between the two is in self.growIfNeeded() call, https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3cbe0ad1a18bc0dd55/lib/std/hash_map.zig#L1288 https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c..., which the one that doesn't allocate really doesn't have. Does it assume that the predefined capacity will not be reached?
    - e4m2 3y ago
      > Does it assume that the predefined capacity will not be reached? Yes, the function name says exactly that as well, though admittedly what this actually means and what consequences it might have if the assumption is false are probably fairly opaque to a novice user. > how does it handle the case where you don't have enough capacity to insert the new (k,v) pair? Breaking the invariant results in safety-checked undefined behavior, that's what the "asserts" in the doc comment signifies[0]. Basically, if something goes awry at runtime you'll get a crash along with a nice error trace in Debug/ReleaseSafe mode or with the appropriate @setRuntimeSafety call. If instead you'd like to have errors that you can handle, you could use your real allocator where you expect to actually use it and pass a failing allocator[1] everywhere else (but that's sort of abusing the API IMO, I don't know if I'd actually recommend you do this). [0] https://ziglang.org/documentation/master/#Doc-Comment-Guidance https://ziglang.org/documentation/master/#Doc-Comment-Guidan... [1] https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3cbe0ad1a18bc0dd55/lib/std/mem.zig#L130-L146 https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c...
      - menaerus 3y ago
        Right, that's what I thought is happening under the hood. Thanks for confirming. This also means that there is nothing novel about this approach that cannot be achieved in other programming languages as one of the parent comments claimed. This is simply a hashmap with pre-allocated pool of memory.

menaerus 3y ago

I don't quite understand how do you change the size of a zig hashmap in runtime by, for example, inserting 1M items at some point but at the same time being able to enforce in compile-time that such operation will not result with dynamic allocation?

8n4vidtmkvmk 3y ago
I don't know, but you could avoid resizing the hashmap and allow the collisions but then your buckets would still need resizing
matklad 3y ago
Compare these two methods: https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3cbe0ad1a18bc0dd55/lib/std/hash_map.zig#L1196 https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c... https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3cbe0ad1a18bc0dd55/lib/std/hash_map.zig#L1014 https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c... One of them requires passing an allocator (and can allocate), the other doesn’t have an allocator argument (and thus can’t allocate). If you only pass allocator to `init` method of your application, and don’t store it anywhere, only init will be able to call allocating methods, the rest of the app will be allocation free, by construction.
- menaerus 3y ago
  If the second one can't allocate then how does it handle the case where you don't have enough capacity to insert the new (k,v) pair? I can see that the difference between the two is in self.growIfNeeded() call, https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3cbe0ad1a18bc0dd55/lib/std/hash_map.zig#L1288 https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c..., which the one that doesn't allocate really doesn't have. Does it assume that the predefined capacity will not be reached?
  - e4m2 3y ago
    > Does it assume that the predefined capacity will not be reached? Yes, the function name says exactly that as well, though admittedly what this actually means and what consequences it might have if the assumption is false are probably fairly opaque to a novice user. > how does it handle the case where you don't have enough capacity to insert the new (k,v) pair? Breaking the invariant results in safety-checked undefined behavior, that's what the "asserts" in the doc comment signifies[0]. Basically, if something goes awry at runtime you'll get a crash along with a nice error trace in Debug/ReleaseSafe mode or with the appropriate @setRuntimeSafety call. If instead you'd like to have errors that you can handle, you could use your real allocator where you expect to actually use it and pass a failing allocator[1] everywhere else (but that's sort of abusing the API IMO, I don't know if I'd actually recommend you do this). [0] https://ziglang.org/documentation/master/#Doc-Comment-Guidance https://ziglang.org/documentation/master/#Doc-Comment-Guidan... [1] https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3cbe0ad1a18bc0dd55/lib/std/mem.zig#L130-L146 https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c...
    - menaerus 3y ago
      Right, that's what I thought is happening under the hood. Thanks for confirming. This also means that there is nothing novel about this approach that cannot be achieved in other programming languages as one of the parent comments claimed. This is simply a hashmap with pre-allocated pool of memory.