Skip to content

RFC: Drop hash table for per-element attributes for more compact sorted vector#221

Merged
LoZack19 merged 1 commit intomasterfrom
sorted-vec-instead-of-hash-table
Dec 2, 2024
Merged

RFC: Drop hash table for per-element attributes for more compact sorted vector#221
LoZack19 merged 1 commit intomasterfrom
sorted-vec-instead-of-hash-table

Conversation

@adamreichold
Copy link
Member

@adamreichold adamreichold commented Dec 2, 2024

While looking at our indexmap dependency, I wondered whether a hash table per element is not too heavy weight for what we are doing. For looking up attributes by name, we can also use a sorted list to get O(log n) instead O(<1>) which considering the typical number of attributes on an element should be good enough. Similarly, adding attributes one-by-one after the fact should be rare, so shuffling them around should be rare as well. What this yields is a more compact representation and simpler machine code (even though the source code gets a bit messier).

@adamreichold adamreichold force-pushed the sorted-vec-instead-of-hash-table branch from f589f17 to 03e329b Compare December 2, 2024 07:38
@adamreichold
Copy link
Member Author

The branch is based off #220.

@adamreichold adamreichold force-pushed the sorted-vec-instead-of-hash-table branch from 03e329b to ee66ee8 Compare December 2, 2024 08:02
Copy link
Contributor

@LoZack19 LoZack19 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@LoZack19 LoZack19 merged commit 26f04ed into master Dec 2, 2024
@adamreichold adamreichold deleted the sorted-vec-instead-of-hash-table branch December 2, 2024 18:03
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants