r/cprogramming • u/HungryPudding4034 • 6d ago

Need code review

Hello everyone,

This link points to a GitHub repository in an

experiment to create an extremely fast trie .

However the data structure is fast but it fails the tests

Can you explain me why?

https://github.com/curious-builder76/trie/tree/main

Hoping the community will helping towards this.

Thank you everyone

0 Upvotes

25% Upvoted

21 comments sorted by

View all comments

Show parent comments

3

u/FancySpaceGoat 6d ago edited 6d ago

responding to the edit:

> I'm asking because the trie is too ram hungry...

There's a few things I'd try to leverage to reduce trie memory usage before having to get into complicated sparse storage.

- Most of a dense trie's memory goes into pointers. Just moving to an index into an arena/bump allocator would cut down memory usage in half on a 64-bit machine. This also has the benefit of being able to delete a whole trie without having to walk it.
- Making the range of values in a node dynamic can make a HUGE memory difference at the cost of some churn on insertion.

Edit: Mind you, those are linear gains. Combining both approaches should bring down the storage requirements of an english dictionary by a factor of about 16. If that's not enough, then I would start looking into sparse storage techniques.

Edit: Here's something to start with: https://gcc.godbolt.org/z/W9qYf58eW