Bucket-based API for HashTable

[orlp]

I want to propose the following API for HashTable. On OccupiedEntry I would like to add

/// Return in which bucket this entry is located.
///
/// Note: this index is not stable if the hash table is rehashed.
pub fn get_bucket(&self) -> usize;

On HashTable itself I would like to add the following four functions:

/// Returns the bucket index an entry in the hash table is located at, or `None` otherwise.
///
/// Note: this index is not stable if the hash table is rehashed.
pub fn find_bucket(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<usize>;

/// Return a reference to the value located at `bucket_idx`, or `None` otherwise.
pub fn at_bucket(&self, bucket_idx: usize) -> Option<&T>;

/// Return an `OccupiedEntry` for the entry located at `bucket_idx`, or `None` otherwise.
pub fn at_bucket_mut(&mut self, bucket_idx: usize) -> Option<OccupiedEntry<T>>;

/// Returns the total number of buckets in this `HashTable`.
pub fn num_buckets(&self) -> usize;

There are multiple reasons why I'd like this.

1. It allows incredibly flexible iteration over the hash table. I am aware that this iteration would be suboptimal compared to a SIMD-based iteration which checks the tags of 16 elements in one go, but the flexibility it provides is well worth it. For example: it makes parallel iteration over the hash table trivial, in whatever permutation you'd like.

2. It allows intrusive data structures to interweave with the hash table, so long as you are careful to avoid rehashing. An example I ran into recently was the writing of a fixed-capacity LRU cache. When the LRU cache wants to evict the least recently used key it has to do a lookup for that key. It could instead simply store the bucket index and use that to directly remove the key, as the hash table never rehashes in this example. (This example did not in fact avoid rehashing, churn leads to rehashing, even with the same capacity.)

3. It allows additional algorithms to run safely and soundly (e.g. no pointers into the hash table which requires unsafe code and which may or may not get invalidated with the latest flavor of stacked/tree borrows) while referring into the hash table. For example: sorting the keys of a hash table while not cloning the keys or taking them out of the table.

[cuviper]

I think this would help indexmap's OccupiedEntry as well, since a bucket index doesn't hold a lifetime. I could store a simpler (&mut IndexMapCore, usize) instead of needing separate references for my other fields. It would also remove the need for the awkward hash_table::AbsentEntry, because I could just map find_entry to an index (i.e. find_bucket) to avoid the NLL limitations.

[moulins]

2. It allows intrusive data structures to interweave with the hash table, so long as you are careful to avoid rehashing. An example I ran into recently was the writing of a fixed-capacity LRU cache. When the LRU cache wants to evict the least recently used key it has to do a lookup for that key. It could instead simply store the bucket index and use that to directly remove the key, as the hash table never rehashes in this example.

This assumes that deleting an element doesn't displace other elements, which is currently true but not technically guaranteed, as far as I can tell?

[orlp]

This assumes that deleting an element doesn't displace other elements, which is currently true but not technically guaranteed, as far as I can tell?

I think that's correct.

[cuviper]

In theory, insertions could displace existing items as well.

The standard library definitely shouldn't make any guarantees about this, but would it be so bad if hashbrown did?

[cuviper]

@Amanieu, any thoughts on this proposal?

[cuviper]

/// Return an `OccupiedEntry` for the entry located at `bucket_idx`, or `None` otherwise.
pub fn at_bucket_mut(&mut self, bucket_idx: usize) -> Option<OccupiedEntry<T>>;

This will also need a hash to create an OccupiedEntry.
(which only needs that for remove() -> VacantEntry AFAICS)

Maybe this should just return Option<&mut T>, and a direct remove_bucket might be better for your LRU eviction?

[orlp]

@cuviper I no longer think this is applicable for LRU eviction. Any purpose where there is key churn will eventually result in rehashing, invalidating bucket indexes.

The iteration usecases are still valid though.

[cuviper]

In indexmap's case, I would also want a way to remove by bucket, but I do have the hash at hand too if needed.

[Amanieu]

My main concern with exposing such an API is that it forces additional constraints on the shape of the underlying data structure. Specifically:

• We would need to specify the conditions under which bucket indices are invalidated. If these are too narrow then it limits the hash table implementation, and if they are too broad then the bucket API becomes much less useful.
• Even exposing buckets as usize forces the table layout to be an open addressing table and excludes closed addressing tables based on linked-list. While I don't expect this to change, it is still a limitation on the table layout.

In the end, the entire point of the hashbrown 0.15 release was to avoid exposing internal details so that we could modify the table internal more easily. This feels like a step backwards.

[orlp]

Even the strictest policy that states any insertion/deletion may invalidate bucket indices would already be sufficient for custom iteration. Regarding the open addressing vs. closed addressing, I don't think that would ever change in the lifetime of hashbrown, and even if it did I don't think it would be a problem to do a breaking release for it.

[cuviper]

Even the strictest policy that states any insertion/deletion may invalidate bucket indices

That would also be fine for indexmap's potential use.

[pervognsen]

Accessing slots by index would also allow an optimization I've used in the past in other contexts. An example: a handle is represented by a key and a speculative slot index. To look up the handle in the table you first try to probe the slot at the speculative index. If the probe fails, you do a normal lookup using the handle's key; afterwards you atomically replace the handle's slot index with wherever you found the key in the table. In addition to the more obvious benefits of avoiding the probe sequence most of the time, it lets you inline the speculative probe check while outlining the fallback lookup code. Also, SIMD-based hash tables generally sacrifice hole-in-one access latency, and this lets you use a lower latency scalar code path for the speculative probe check.

(I'm not saying Hashbrown should implement anything like this, but it's something user code can implement if you allow access by slot index. Invalidating slot indices on every insert/delete is not a correctness problem for this use case, but it would obviously degrade the performance of the speculation to the point where it wouldn't be worth it.)

[Amanieu]

I've since changed my opinion and think that this API is most likely the best way forward since it also addresses a lot of a existing issues such as #420 and #382. I would be in favor of adding this API to HashTable.

[cuviper]

/// Return an `OccupiedEntry` for the entry located at `bucket_idx`, or `None` otherwise.
pub fn at_bucket_mut(&mut self, bucket_idx: usize) -> Option<OccupiedEntry<T>>;

Note that this one would also require a hash value, only because OccupiedEntry needs that for remove() -> VacantEntry. So it might still make sense to have a method that only returns &mut T, no hash necessary.

(edit: and scrolling back, I see I already mentioned that, sorry!)