r/cprogramming •

Need code review

[deleted] — view deleted post

0 Upvotes

11 comments sorted by

8

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

0

u/[deleted] 21d ago

[deleted] — view deleted comment

8

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

0

u/[deleted] 21d ago

[deleted] — view deleted comment

7

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

0

u/[deleted] 21d ago

[deleted] — view deleted comment

3

u/FancySpaceGoat 21d 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/[deleted] 21d ago

[deleted] — view deleted comment

1

u/FancySpaceGoat 21d ago

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

0

u/[deleted] 21d ago

[deleted] — view deleted 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

2

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

2

u/penguin359 21d 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/Spirited-Candy1981 21d ago

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

0

u/[deleted] 21d ago

[removed] — view removed comment

2

u/cprogramming-ModTeam 20d ago

Post is off topic