Does using Option<im::HashMap<K, V>> ever make sense?

#1

Does an empty im::HashMap allocate any object on the heap?
I am trying to figure out if it makes sense to use Option<im::HashMap<K, V>> or if HashMap<K, V> already automatically does said optimization when empty.

im::HashMap::new() points to im::HashMap::default(), at https://docs.rs/im/15.0.0/src/im/hash/map.rs.html#126-128 , which appears to be doing some type of allocation from the pool, but I am not sure.

EDIT: link for default: https://docs.rs/im/15.0.0/src/im/hash/map.rs.html#1642

#2

I can’t speak to the internals of im, but note that there can be a semantic difference between a missing map and an empty one. For example, you might want None to mean the map hasn’t been calculated/loaded yet and an empty map to mean the calculation produced no results.

Unless I’m dealing with particularly performance-sensitive code, this is the only case where I’d wrap any kind of HashMap in an Option: A single heap allocation (if that) for an empty map isn’t going to make much difference for most code.

7 Likes
#3

Philosophically, I agree with you.

Practically, I still want to understand if the empty case is optimized. :slight_smile:

1 Like
#5

Looking at the source code, it seems like if you don’t use the "pool" feature, the hashmap contains a zero-sized "fake pool" that can be ignored, and also an Arc or Rc (depending on threadsafe feature) to a Node which contains a sized_chunks::sparse_chunk::SparseChunk. So this one is actually allocated, and decently sized, consisting of (I think) 32 Entryies (though they’re behind MaybeUninit, so at least the initialization is not too bad performance-wise). And finally, there’s also an Arc or Rc to a (build-)hasher, by default a RandomState, so that’s another allocation for a 2×u64 sized type.

Conclusion: There’s no optimization for the empty case.

3 Likes