CodSpeed Performance Report

Merging this PR will degrade performance by 4.09%

_{Comparing refactor/ident-precomputed-hash (f460a88) with main (87684d7)¹}

Summary

❌ 2 regressed benchmarks
✅ 40 untouched benchmarks
⏩ 3 skipped benchmarks²

⚠️ Please fix the performance issues or acknowledge them on CodSpeed.

Performance Changes

Design Constraint: Borrow<str> vs Precomputed Hash

There's a fundamental conflict between two requirements:

1. Precomputed Hash for Performance

The optimized Ident stores a precomputed FxHash in len_and_hash for fast hash map lookups:

impl Hash for Ident<'_> {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        let hash = self.len_and_hash.rotate_left(32 - 7);
        hasher.write_u64(hash);
    }
}

2. Borrow<str> for Heterogeneous Lookups

Code like this requires Borrow<str>:

// In oxc_isolated_declarations/src/lib.rs:634
can_expando_function_names.contains(ident.name.as_str())

The Problem

Rust's Borrow trait contract requires: if T: Borrow<Q>, then hash(t) == hash(t.borrow()).

This means if Ident: Borrow<str>, then ident.hash() must equal ident.as_str().hash().

We cannot have both:

• ✅ Custom Hash using precomputed hash
• ✅ Borrow<str> for heterogeneous lookups

Options

1. Keep Borrow<str>, delegate Hash to str - Correct but loses hash optimization
2. Remove Borrow<str>, use precomputed Hash - Fast but requires changing call sites to use &Ident instead of &str for lookups
3. Use hashbrown::raw_entry API - Allows custom hashing during lookup, but more complex

@Boshen Which approach do you prefer?

@camchenry see above, we have a problem :-)

Oh, we just need to fix the call site, but it's not trivial for people 🤔

Solution Found

After research into how Rust compilers handle this (rustc's Symbol, string interning crates), the solution is:

Remove Borrow<str>, Use Precomputed Hash

Why Borrow<str> is incompatible with precomputed hash:

The Rust Borrow trait contract requires: if T: Borrow<Q>, then hash(t) == hash(t.borrow()).

This means if Ident: Borrow<str>, then ident.hash() must equal ident.as_str().hash() - which defeats the purpose of precomputed hashing.

How rustc's Symbol handles this:

• Does NOT implement Borrow<str>
• Uses derived Hash on the index (fast integer hash)
• Requires interning strings first - all lookups use Symbol, not &str

Changes in this PR:

1. Remove Borrow<str> from Ident
2. Hash::hash() uses precomputed hash (fast!)
3. Call sites updated: set.contains(name.as_str()) → set.contains(&name)

Sources:

• hashbrown Equivalent trait
• rust-clippy lint for Hash+Borrow incompatibility
• rustc Symbol implementation

I can see another potential solution:

1. Implement Hash on Ident as ident.as_str().hash(hasher). So Ident::hash and str::hash are equivalent.

2. Add a wrapper type which uses optimized hashing scheme.

#[repr(transparent)]
struct FastHashIdent<'a>(Ident<'a>);

// Optimized hash
impl Hash for FastHashIdent<'_> {
    #[inline]
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        let hash = self.0.len_and_hash().rotate_left(25);
        hasher.write_u64(hash);
    }
}

3. Only use the optimized hashing in IdentHashMap.

IdentHashMap uses the wrapper type for hash map keys.

struct IdentHashMap<'a, V> {
    inner: hashbrown::HashMap<FastHashIdent<'a>, V, NoopBuildHasher, &'a Bump>,
}

impl IdentHashMap<'a, V> {
    pub fn insert(&mut self, ident: Ident<'a>, v: V) -> Option<V> {
        let wrapped = FastHashIdent(ident);
        self.inner.insert(wrapped, v)
    }

    // ... other `HashMap` methods
}

We need an IdentHashMap type anyway, as we need to use a no-op BuildHasher (not FxHashBuilder) for these hashmaps.

Result:

• Ident can remain Borrow<str>.
• Hashmaps keyed with Ident should use IdentHashMap to get better perf, but Ident still works as key of normal HashMaps.
• Switching hashmaps over to IdentHashMap can be done incrementally.

EDIT: Or just ditch Borrow<str>. I don't think we need it. We can still implement Deref to &str and AsRef<str> for Ident. Those don't have the same requirements.

Or actually, Ident should probably IMO deref to Atom, and Atom deref to &str.

@overlookmotel Question about the Ident design:

The new Ident uses a u64 for len_and_hash (length in bottom 32 bits, hash in top 32 bits), which requires 8-byte alignment on 32-bit platforms. The old Ident (which was just &str) had 4-byte alignment on 32-bit.

This alignment change cascades through the AST - for example, IdentifierName goes from 16 bytes to 24 bytes on 32-bit, and enums containing it also grow.

Alternative design using two u32 fields:

pub struct Ident<'a> {
    ptr: NonNull<u8>,    // 4 bytes on 32-bit
    len: u32,            // 4 bytes
    hash: u32,           // 4 bytes
    _marker: PhantomData<&'a str>,
}

This would be:

• 64-bit: 16 bytes, align 8 (with padding)
• 32-bit: 12 bytes, align 4

This keeps 4-byte alignment on 32-bit like the old &str-based Ident.

Should we use separate len and hash fields to avoid the alignment/size increase on 32-bit platforms? Or is the current u64 approach acceptable?

This is a pain, but I think we need different implementations for 32 bit and 64 bit. I found that packing length + hash into a single u64 produced tighter assembly on 64 bit platforms, and allows Ident to be passed between functions in 2 x registers, instead of requiring 3 (quite a significant difference).

But, as you say, it's advantageous to store length and hash in 2 x u32s on 32 bit.

I'd suggest sticking with len_and_hash: u64 to start with, and then producing a more optimal 32 bit version later on.

But, as you say, it's advantageous to store length and hash in 2 x u32s on 32 bit.

I don't, Claude did, you are talking to Claude ;-)

I'd suggest sticking with len_and_hash: u64 to start with, and then producing a more optimal 32 bit version later on.

  error[E0080]: evaluation panicked: assertion failed: size_of::<IdentifierName>() == 16
      --> crates/oxc_ast/src/generated/assert_layouts.rs:1650:5
       |
  1650 |     assert!(size_of::<IdentifierName>() == 16);
       |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ evaluation of `generated::assert_layouts::_` failed here

https://oxc.rs/docs/contribute/introduction.html

You are responsible for all AI-generated issues or PRs you submit

😄 🤖

error[E0080]: evaluation panicked: assertion failed: size_of::<IdentifierName>() == 16

Set a custom layout for Ident in calculate_layout_for_primitive in ast_tools assert_layouts.rs.

I'm going to continue from 2 u32s to get this PR rolling

About len_and_hash: Actually, the hash implementation needs to be different on 32 bit too. If I remember right, hashbrown behaves differently on 32-bit systems - it only uses the bottom 32 bits of the u64 hash or something.

I suggest a separate LenAndHash struct which abstracts away the platform difference. Something like:

#[cfg(target_pointer_width = "64")]
mod len_and_hash {
    #[derive(Clone, Copy)]
    #[repr(transparent)]
    pub struct LenAndHash(u64);

    impl LenAndHash {
        pub fn new(len: u32, hash: u32) -> Self { Self(u64::from(len) | (u64::from(hash) << 32)) }
        pub fn len(self) -> u32 { self.0 as u32 }
        pub fn hash(self) -> u32 { (self.0 >> 32) as u32 }
        pub fn hash_for_hashing(self) -> u64 { self.0.rotate_left(25) }
    }
}

#[cfg(not(target_pointer_width = "64"))]
mod len_and_hash {
    #[derive(Clone, Copy)]
    pub struct LenAndHash {
        len: u32,
        hash: u32,
    }

    impl LenAndHash {
        pub fn new(len: u32, hash: u32) -> Self { Self { len, hash} }
        pub fn len(self) -> u32 { self.len }
        pub fn hash(self) -> u32 { self.hash }
        pub fn hash_for_hashing(self) -> u64 { self.hash as u64 }
    }
}

use len_and_hash::LenAndHash;

#[derive(Clone, Copy)]
#[repr(C)]
pub struct Ident<'a> {
    ptr: NonNull<u8>,
    len_and_hash: LenAndHash,
    _marker: PhantomData<&'a str>,
}

Then use hash_for_hashing for the Hash impl.

• perf(semantic): preserve precomputed identifier hash throughout semantic analysis #18476
• perf(semantic): compute identifier hash incrementally during lexing #18454
• refactor(oxc_str): add IncrementalIdentHasher for byte-by-byte hash computation #18451
• refactor(parser): add cur_ident() for identifiers with precomputed hash #18449
• refactor(semantic): add ArenaIdentHashMap and replace IdentHashMap callsites #18425
• feat(oxc_str): upgrade Ident with precomputed hash for fast equality #18400 👈 (View in Graphite)
• main

How to use the Graphite Merge Queue

Add either label to this PR to merge it via the merge queue:

• 0-merge - adds this PR to the back of the merge queue
• hotfix - for urgent hot fixes, skip the queue and merge this PR next

You must have a Graphite account in order to use the merge queue. Sign up using this link.

This stack of pull requests is managed by Graphite. Learn more about stacking.

Merge activity

• Jan 23, 12:44 PM UTC: Boshen added this pull request to the Graphite merge queue.
• Jan 23, 12:47 PM UTC: The Graphite merge queue couldn't merge this PR because it was in draft mode.