Trie Implementation: using Int vs Char

Question

I'm currently trying to implement a trie in C in order in order to make a speller check (dictionary is taken from a text file loaded into the trie structure).

Here is my current struct for nodes (taken from https://www.cs.bu.edu/teaching/c/tree/trie/):

typedef struct trieNodeTag 
{
    char key;
    struct trieNodeTag *next, *children;
} trieNodeT;

key being the letter of each word to load in memory.

My question is the following: does that make a difference in memory / speed to use a type int for key ? Is a char treated directly as an int ?

Thank you !

What platform is the implementation done for? I would guess the difference would be hardly noticeable for moderately sized words stored in the trie. — Codor, Jan 23 '17 at 19:32
It makes no difference on most machines. The pointers will need to be aligned so there is padding after the `key` if it is a `char`, and there is less, possibly zero, padding if it is an `int`. — Jonathan Leffler, Jan 23 '17 at 19:33
Re-ordering and having the pointers first, then the `key`, may make more performance difference than `char/int` (Place the field that gets used most as the first field.) . IAC, "try" different approaches and rate them, — chux - Reinstate Monica, Jan 23 '17 at 19:37
The best way to answer your question is to code it and run it through iterations while profiling it. Honestly, changing one datatype is hardly difficult to test this definitively. — David Hoelzer, Jan 23 '17 at 19:55

score 2 · Answer 1 · edited May 23 '17 at 12:01

Since char is followed by two pointers, the struct will get padded to give next and children a proper alignment. Assuming that the size of an int is less than or equal to the size of a pointer on your system, declaring key an int will not change memory requirements of your struct.

As far as the speed is concerned, good chances are that you wouldn't see much difference either way. A good practical approach is to pick the type that fits the logic of your program best, and change it to a different type only if profiling suggests that it would make a large difference.

score 1 · Answer 2 · answered Jan 23 '17 at 19:32

1

Whether int behaves differently from char would also depend on the platform. The type int would probably be the machine word, which is easier to address; however, char might be smaller in memory size.

answered Jan 23 '17 at 19:32

Codor

17,447
9
29
56

score 1 · Accepted Answer · answered Jan 23 '17 at 19:43

My question is the following: does that make a difference in memory / speed to use a type int for key ?

It is likely -- but not certain -- that the size of struct trieNodeTag would remain the same if you modified the type of its key member from char to int, because it is likely that the compiler lays out that struct so that the offset of pointer next from the beginning of the structure is a multiple of four bytes. If you want to know for sure, then apply the sizeof() operator to each version of the struct, and compare the results. The outcome will depend to some extent on the C implementation you use.

Is a char treated directly as an int ?

In the evaluation of most expressions, an operand of type char is promoted to int before it is operated upon. This is cheap, and it might even be free, but no, a char is not treated directly as an int.

Overall, then, if the code is equally correct with the key typed as either int or char, then you should see little or no performance difference between the two.

I think you're posing the wrong question, however. It is likely that one of the types int and char is a more natural fit to the intended use of member key. I'd guess that's char, but whichever it is, that's the one to use. Strive to write code that makes sense and works correctly. Use appropriate algorithms for the task, but don't sweat fine performance details until and unless you measure your performance and find it lacking.

Trie Implementation: using Int vs Char

3 Answers3