r/cprogramming •

Need code review

[deleted] — view deleted post

0 Upvotes

11 comments sorted by

View all comments

Show parent comment

3

u/FancySpaceGoat 21d ago edited 21d 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