oxc-project / oxc-project/backlog

Convert `Span` to a single `u64`?

Open
#178 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
No language data
Stars
7
Forks
0
PR merge metrics
No merged PRs in 30d

Description

Span is currently defined as:

#[repr(C)]
pub struct Span {
    pub start: u32,
    pub end: u32,
    _align: PointerAlign,
}

#[repr(transparent)]
struct PointerAlign([usize; 0]);

PointerAlign ensures that Span is aligned on 8 on 64-bit systems. Some methods make use of this property to perform faster operations on Spans e.g. PartialEq compares 2 Spans by converting them to u64s first, which is faster.

Background

I had been scratching my head about why https://github.com/oxc-project/oxc/pull/10933, which converted lexer's Token to a single u128 had such a large perf benefit. We'd also tried laying out the struct's fields so it was identical in memory to what that PR did, but that did not provide the same perf boost.

Now, after conversation on https://github.com/oxc-project/oxc/pull/13042#pullrequestreview-3119644072, I think I have a guess as to why. That PR converted Token to:

#[derive(Clone, Copy)]
#[repr(transparent)]
pub struct Token(u128);

The key to the perf boost might have been #[repr(transparent)]. Maybe that made Token able to be passed to functions in a register, whereas the multi-field struct couldn't.

How this applies to Span

I thought that aligning Span on 8 would make it able to passed to functions in a single register, rather than 2 registers for each field. But now I'm not so sure.

Maybe we could do the same trick as on Token, and convert Span to:

#[derive(Clone, Copy)]
#[repr(transparent)]
pub struct Span(u64);

impl Span {
    pub fn start(self) -> u32 {
        self.0 as u32
    }

    pub fn end(self) -> u32 {
        self.0 >> 32 as u32
    }
}

As Spans are commonly copied around, this might give a measurable benefit.

Battle plan

First of all, could test the theory that Token's good perf is due to #[repr(transparent)] by removing that attribute (or replacing it with #[repr(C)]) and seeing what effect is has on benchmarks.

If that does confirm the theory, then alter Span accordingly.

32-bit platforms

On 32-bit platforms e.g. WASM, it may be beneficial for Span to remain 2 x u32s. On the other hand, even though WASM is 32 bit, the underlying system is likely to be 64 bit, so representing Span as a u64 may still be beneficial in WASM.

Other 32-bit systems exist, and Oxc nominally supports them. But in practice I doubt we have any users running Oxc on old 32-bit computers, so WASM is the only real 32-bit target.

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

Start by examining the existing Token representation and benchmarks, then compare performance with and without its representation attribute. Next, inspect Span's current layout and methods, including behavior on 32-bit targets such as WASM. Done means the benchmark results establish whether the representation matters and provide a basis for deciding whether Span should use a single u64.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.