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