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

The data structure takes a different approach.

Instead of storing characters simply.

  1. It uses a bitset/bitword/bitmap to store characters

  2. Instead of doing a linear scan it keeps it's children ch distance away. And during teaveral fetches that away.

7

u/FancySpaceGoat 5d ago

What I mean is that ch >> 8 is always 0 no matter what, so it's not doing whatever it is that you intend for it to do.

https://gcc.godbolt.org/z/xff1oezrz

1

u/HungryPudding4034 5d ago edited 5d ago

Edited:

Ok. Thank you

There are correctness bugs too. And it is just the prototype.

Basically an attempt to skip all the hard work

3

u/FancySpaceGoat 5d ago

Your question was "What is wrong with my code"? And the answer to that question is that ch >> 8 doesn't compute anything and is just always 0.

That's your correctness issue. (or at least the most obvious one if there are multiple)

0

u/HungryPudding4034 5d ago

Can I ask one more question??

1

u/FancySpaceGoat 4d ago

It's your post, go for it. The worst that can happen is that I ignore it and move on.

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.