Skip to content

Optimizations of the trie implementation #199

@abizjak

Description

@abizjak

Task description

There are several opportunities for optimizations of the trie implementation, both space and time wise.

At least the following ones should be considered. Any changes should be accompanied by meaningful benchmarks or arguments why memory use is reduced.

Sub-tasks

  • The Stem and MutStem types contain a "stem", a list of bytes. In the vast majority of cases, for non-malicious use, these will be very short, very rarely above 40 bytes. Thus a small-scale optimization where we would use something like tinyvec/smallvec for storing the key inline if it is small could be very beneficial to both performance, and reducing memory pressure and fragmentation.
  • When serializing (and in store_update) the node's children we now waste a full byte for the child tag. This is wasteful since we could just use the top 4 bits of the Reference, still leaving 60 bits to address, which is more than will ever be needed.

Metadata

Metadata

Assignees

No one assigned

    Labels

    [Prio] LowShould be fixed if time permits but can be postponed.[Size] Medium[Type] TaskAn additional feature or improvement.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions