cucapra / cucapra/pollen

Switch span representation from start/end to start/length

Open
#233 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
45
Forks
3
PR merge metrics
No merged PRs in 30d

Description

FlatGFA's core machinery for flat data storage is in [the `pool` module][pool]. That module comes with two ["newtype"-esque structs][newtype] for representing references to stuff stored in the arenas: `Id` and `Span`. Respectively, these are references to a single item and a contiguous range of items.

This issue is about the representation of `Span`. Currently, it uses a "start/end" representation, so that's two `u32`s for 8 total bytes. We should consider instead a "start/length" representation, which could probably use a `u32` for the start and `u16` for the length for a total of 6 bytes. Let's try that! Here's a to-do list:

* make the change
* fix any client code that was relying on the internal representation of `Span`, hopefully making it better and more readable in the process
* measure the impact on file size
* measure the impact on performance (maybe this comes at the small cost of needing to compute the end index more often? Not sure if this will be significant)

I hope that this is a clean win without much downside, and we can apply it everywhere. We could just merge the change and not look back. Importantly, I see this change as orthogonal to the sequence-specific representation work in #214. Beyond this work, #234 describes an even more aggressive representation for `Span` that we could try.

[newtype]: https://doc.rust-lang.org/rust-by-example/generics/new_types.html
[pool]: https://github.com/cucapra/pollen/blob/main/flatgfa/src/pool.rs

Contributor guide

No contributing guide indexed for this repository

Research direction

Start in flatgfa/src/pool.rs, focusing on the Span definition and its documented start/end representation. Search for client code that relies on Span's internal fields, then measure file size and performance before and after the change. Done means the representation and affected clients are updated, with the size and performance impact recorded.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.