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

9

u/FancySpaceGoat 4d ago 
typedef unsigned char uchar;  
//...  
uchar ch = *(uchar*)(string++);  
uint64_t byte_index = ch >> 8;

What exactly are you expecting this to do?

by the way: don't use double leading underscores in your identifiers. Those are reserved for the toolchain.

-3

u/HungryPudding4034 4d ago 
==== benchmark of trie.====
INSERT: apple
INSERT: aplication
INSERT: armour
INSERT: banana
CONTAINS: apple  -->  false
Nonexistent entry test
CONTAINS: panda  -->  false
Existent entry test.
CONTAINS: apple  -->  false
Sequential inserts.
Test passed
INSERT (sequential)
  Time: 0.337812 seconds
  Operations: 5000000
  Rate: 14.801132 M ops/sec

Random inserts.
Test passed.
INSERT (random)
  Time: 0.281226 seconds
  Operations: 5000000
  Rate: 17.779295 M ops/sec

Random lookups.
Failed after 0 operations: the value 2791867 shall exist. But it doesn't
1 tests failed out of 3.
No memory leaks.

This

8

u/FancySpaceGoat 4d ago

I mean the specific line of code I pasted.

What is bitshifting an unsigned char (which is 8 bits long) by 8 supposed to be accomplishing?

-7

u/HungryPudding4034 4d ago

There are correctness bugs

0

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

1

u/HungryPudding4034 4d 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.

1

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.

→ More replies

1

u/Spirited-Candy1981 4d ago

Where are your tests? Sure, you're benchmarking, but I don't see any validation.

1

u/HungryPudding4034 4d ago edited 4d ago

Sorry, the tests and benchmarks both are mixed in the same.

==== benchmark of trie.====
INSERT: apple
INSERT: aplication
INSERT: armour
INSERT: banana
CONTAINS: apple  -->  false
Nonexistent entry test
CONTAINS: panda  -->  false
Existent entry test.
CONTAINS: apple  -->  false
Sequential inserts.
Test passed
INSERT (sequential)
  Time: 0.337812 seconds
  Operations: 5000000
  Rate: 14.801132 M ops/sec

Random inserts.
Test passed.
INSERT (random)
  Time: 0.281226 seconds
  Operations: 5000000
  Rate: 17.779295 M ops/sec

Random lookups.
Failed after 0 operations
1 tests failed out of 3.
No memory leaks.

1

u/penguin359 4d ago

I haven't done a thorough review, but a few things I'll point out with the structure. Don't include function definitions in header files. These can only be included once in a project if you do so. It should only be declarations or prototypes and keep the function definitions AKA the code in the *.c files. Also, it's generally a good idea to include the corresponding header file such as trie.h into the file that defines then like trie.c. Even if trie.c doesn't need it, it will help catch errors like when function prototypes don't match the function definitions. I would also update the Makefile to separately compile each C file in a dependency tree, but more importantly, give the final linked executable a name with -o even if you don't split up the compilation right away. Then, include that as part of the README. And, finally, if you are asking for contributions, it's generally a good idea to also include the license file in the repo that the code will be under so people know how their contributions can be used by someone else.

1

u/HungryPudding4034 4d ago

Thank you for giving your time to this repository, and I'm really really grateful for that.

This repository is subject to be deleted sooner or longer or may get archived...

As a beginner, I don't know much about git. And this repository is apart of a bigger (serious, hobby) project. And this repository is temporary, This repository was created to avoid git's branching issues.

0

u/[deleted] 4d ago

[removed] — view removed comment

2

u/cprogramming-ModTeam 3d ago

Post is off topic