This is an implementation of a trie, that I will be using on a code editor to parse keywords from a given programming language. I decided to use a trie when I asked this question, and the implementation seems to perform pretty well and without errors from valgrind/memcheck.
I want to make sure I'm squeezing every bit of performance out of this thing, though. So I want to know if there's anything more I can do to improve performance (I guess that makes this a performance-related review). Are there any performance tips?
While I'm not specifically looking for a review of the coding style, if I'm doing anything weird please point it out.
Implementation:
Header:
// trie.h
#include <stdlib.h>
#define TRIE_SIZE 256 // would be different for unicode
struct trie_node {
int class; /* acts as a class or id of the word
* and used for checking for a match
*/
struct trie_node * nodes[TRIE_SIZE];
};
struct trie {
struct trie_node head, * current;
};
int trie_init (struct trie * t);
int trie_adds (struct trie_node * head, char * str, int class);
int trie_freenode (struct trie_node * node);
int trie_free (struct trie * t);
int trie_pass (struct trie * t, unsigned char c);
int trie_reset (struct trie * t);
Implementation:
#include "trie.h"
#include <stdlib.h>
int trie_init (struct trie * t){
t->current = &t->head;
for (int i = 0; i < TRIE_SIZE; i++){
t->head.nodes[i] = 0;
}
t->head.class = 0;
return 0;
}
int trie_adds (struct trie_node * head, char * str, int class){
if (str[0]){
int num = str[0];
if (!head->nodes[num]){ // create new node
head->nodes[num] = calloc (1, sizeof (struct trie_node));
if (!head->nodes[num]) return -1;
}
if (str[1]) return trie_adds (head->nodes[num], &str[1], class);
else head->nodes[num]->class = class;
}
return 0;
}
// used in trie_free
static int trie_freenode (struct trie_node * node){
if (!node || !node->nodes){
return -1;
}
for (int i = 0; i < TRIE_SIZE; i++){
if (node->nodes[i]){
trie_freenode (node->nodes[i]);
free (node->nodes[i]);
}
}
return 0;
}
int trie_free (struct trie * t){
for (int i = 0; i < TRIE_SIZE; i++){
if (t->head.nodes[i]){
trie_freenode (t->head.nodes[i]);
free (t->head.nodes[i]);
t->head.nodes[i] = 0;
}
}
t->current = &t->head;
return 0;
}
int trie_pass (struct trie * t, unsigned char c){
t->current = t->current ? t->current->nodes[c]) : 0;
return t->current ? t->current->state : 0;
}
int trie_reset (struct trie * t){
t->current = &t->head;
return 0;
}
Comparative test program (no trie):
#include <stdio.h>
#include <stdlib.h>
char * gettestfile (char * filename);
int strcmp2 (char * str1, char * str2);
#define isqualifier(c)\
(((c >= 'a') && (c <= 'z')) || ((c >= 'A') && (c <= 'Z')))
int main (int argc, char * argv[]){
if (argc < 3){
printf ("usage %s filename [words]\n", argv[0]);
return -1;
}
char * buffer = gettestfile (argv[1]);
if (!buffer){
return -1;
}
int nmatches = 0;
for (int i = 0; buffer[i];){
while (buffer[i] && !isqualifier (buffer[i])) i++;
if (!buffer[i]) break;
int i2 = 0;
for (int j = 2; j < argc; j++){
i2 = strcmp2 (&buffer[i], argv[j]);
if (i2 > 0) break;
}
if (i2 > 0){
i += i2;
nmatches++;
} else while (buffer[i] && isqualifier (buffer[i])) i++;
}
printf ("found %d matches\n", nmatches);
free (buffer);
return 0;
}
int strcmp2 (char * str1, char * str2){
int i = 0;
for (; str1[i] && str2[i]; i++){
if (str1[i] != str2[i]){
break;
}
}
return (str2[i] || isqualifier (str1[i])) ? 0 : i;
}
char * gettestfile (char * filename){
char * buffer = 0;
int len = 0;
FILE * file = fopen (filename, "r");
if (!file){
return 0;
}
fseek(file, 0L, SEEK_END);
len = ftell(file);
fseek(file, 0L, SEEK_SET);
buffer = calloc (len + 1, 1);
if (!buffer){
fclose (file);
return 0;
}
fread (buffer, 1, len, file);
fclose (file);
return buffer;
}
Comparative test program (with trie):
#include <stdio.h>
#include <stdlib.h>
#include "trie.h"
#define isqualifier(c)\
(((c >= 'a') && (c <= 'z')) || ((c >= 'A') && (c <= 'Z')))
char * gettestfile (char *);
int main (int argc, char * argv[]){
char * buffer = 0;
struct trie t;
if (argc < 3){
printf ("usage: %s filename [words]\n", argv[0]);
return -1;
}
trie_init (&t);
for (int i = 2; i < argc; i++){
trie_adds (&t.head, argv[i], 1);
}
buffer = gettestfile (argv[1]);
int nmatches = 0;
if (buffer){
for (int i = 0; buffer[i]; i++){
char c = buffer[i];
if (isqualifier (c)){
trie_pass (&t, buffer[i]);
} else {
if (t.current && t.current->class){
nmatches++;
}
trie_reset (&t);
}
}
free (buffer);
}
printf ("found %d matches\n", nmatches);
trie_free (&t);
return 0;
}
char * gettestfile (char * filename){
char * buffer = 0;
int len = 0;
FILE * file = fopen (filename, "r");
if (!file){
return 0;
}
fseek(file, 0L, SEEK_END);
len = ftell(file);
fseek(file, 0L, SEEK_SET);
buffer = calloc (len + 1, 1);
if (!buffer){
fclose (file);
return 0;
}
fread (buffer, 1, len, file);
fclose (file);
return buffer;
}
Notes about implementation:
isqualifier
is used to check if a character is a qualifying unit of a word. In this case, it is the alphabet (it may also be contain numbers and '_' if it is parsing code). The use of this macro is to eliminate matches like the
within the word there
. If there is a qualifier before or after a two sequences of characters, it is not considered a match.
Performance testing:
I've already timed both of these with a large text file. Here's some of the results:
Test 1:
root@nodeTwo:/usr/local/src/trie# time ./std-test big.txt one
found 3091 matches
real 0m0.058s
user 0m0.052s
sys 0m0.004s
root@nodeTwo:/usr/local/src/trie# time ./trie-test big.txt one
found 3091 matches
real 0m0.068s
user 0m0.064s
sys 0m0.000s
Test 2:
root@nodeTwo:/usr/local/src/trie# time ./std-test big.txt one the here that now next hello for while this
found 100085 matches
real 0m0.137s
user 0m0.132s
sys 0m0.004s
root@nodeTwo:/usr/local/src/trie# time ./trie-test big.txt one the here that now next hello for while this
found 100085 matches
real 0m0.077s
user 0m0.072s
sys 0m0.004s
Test 3:
root@nodeTwo:/usr/local/src/trie# time ./std-test big.txt one the here that now next hello for while this when do something crazy let me know
found 107419 matches
real 0m0.188s
user 0m0.184s
sys 0m0.004s
root@nodeTwo:/usr/local/src/trie# time ./trie-test big.txt one the here that now next hello for while this when do something crazy let me know
found 107419 matches
real 0m0.077s
user 0m0.072s
sys 0m0.004s
Notes about testing:
To perform this test, I downloaded this text file (warning: it's 6.5MB of text) and used it with both programs. If you would like to download the text file and build the source for this review, you can use that link and this link to the GitHub page.
Solutions:
The only way I can think of that may increase performance is by allocating the entire list into continuous virtual memory (would that help get it into CPU Cache?), instead of broken up chunks, and mapping the list to that. I don't know how much to expect this to help, so I'm not sure if I should bother with it or not.