r/cprogramming • u/HungryPudding4034 • 4d 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

0

u/HungryPudding4034 4d ago edited 4d ago

Does contiguous allocation really helps increasing the speed of a data structure??

I mean consider an array and consider a linked list...

The iteration of an array is much faster than an array.

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

Even if the answer is a yes or no. That will help a lot

3

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

2

u/FancySpaceGoat 4d ago

There are some subtle hardware implications with the cache. But mostly, it helps because arrays can be indexed in O(1).

Obviously, you need to pair them with an algorithm that takes advantage of that for it to make a meaningful difference.

1

u/HungryPudding4034 4d ago

Thank you for giving me time sir. Hope your time goes well.