rust-lang / rust-lang/hashbrown

Allow to prefetch buckets

Open
#677 13 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
3k
Forks
358
Avg merge
11h 57m
Merged PRs (30d)
2

Description

In Apache DataFusion we are using hashbrown extensively and I noticed in hash aggregation when the hash table (we use the raw API there) become very large we are memory bound so a natural solution would be to have some kind of prefetching (FYI we are using stable Rust), but there is no way to do that currently

We have something like this (simplified):

for (row, &target_hash) in batch_hashes.iter().enumerate() {
    let entry = self.map.entry(
        target_hash,
        // eq
        |(exist_hash, group_idx)| target_hash == *exist_hash && group_rows.row(row) == group_values.row(*group_idx),
        // hasher
        |(hash, _)|  *hash);

    let group_idx = match entry {
        // Existing group_index for this group value
        Entry::Occupied(o) => {
            let (_hash, group_idx) = o.get();  
            
            *group_idx
        }
        // Need to create new entry for the group
        Entry::Vacant(v) => {
            // Add new entry to aggr_state and save newly created index
            let group_idx = group_values.num_rows();
            group_values.push(group_rows.row(row));
            v.insert((target_hash, group_idx));

            group_idx
        }
    };
    groups.push(group_idx);
}

Allowing to prefetch from the map can help performance for our case.

Because we insert to the table on missing we would have to reserve the x amount of items beforehand for the prefetching to be valuable

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Begin with hashbrown's raw API and the simplified entry loop in the issue, focusing on how prefetching would interact with missing-key insertion and reserving capacity. Check the stable Rust constraint while determining the API and behavior; done means the map can prefetch useful buckets before lookup without undermining insertion performance.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.