1
// @(#) $Revision: 4.1 $ $Source: /judy/test/manual/SLcompare.c $
2
//=======================================================================
3
// Author Douglas L. Baskins, June 2002.
4
// Permission to use this code is freely granted, provided that this
5
// statement is retained.
6
// email - doug@sourcejudy.com
7
//=======================================================================
9
// Compile for choice of algorithm:
11
// cc -static -O -o Judy -DJUDYMETHOD SLcompare.c -lJudy
12
// cc -static -O -o Hash -DHASHMETHOD SLcompare.c
13
// cc -static -O -o Splay -DSPLAYMETHOD SLcompare.c
14
// cc -static -O -o Redblack -DREDBLACKMETHOD SLcompare.c
16
// Note: -static will generally get better performance because string
17
// routines are slower with shared librarys.
24
// Redblack <textfile>
27
This program will give you a chance to measure the speed/space
28
performance of 4 different string store/lookup algorithms on your data
29
set. All are very fast and generally can scale to very large data sets.
30
The memory efficiency is usually best with the Judy algorithm because it
31
uses the opportunity to compress data in a digital tree. The Hashing is
32
generally the fastest algorithm, however it looses its advantage when
33
the number of stored exceeds about 5X the size of the hash table.
34
Many thanks to J. Zobel for supplying the code for Hash, Splay and
37
I will be including more algorithms as people donate code for testing.
39
The Judy code is available at: <http://sourceforge.net/projects/judy>
42
This is the output of this program when run on a 750Mhz P3 laptop.
44
This output is using a file available from www.google.com. It looks
45
like 'http' web pages and was one of the files used in a March 2002
46
contest by www.google.com
48
wc google/data/repos.00
49
3440314 14613027 162822437 google/data/repos.00
51
lines avg_linelen getline stored RAMused/line store/ln lookup/ln ADT
52
2807737 58.0 byts 0.856 uS 1455201 104.0 byts 4.859 uS 4.566 uS SPLAY
53
2807737 58.0 byts 0.862 uS 1455201 96.0 byts 2.523 uS 2.101 uS HASH
54
2807737 58.0 byts 0.856 uS 1455201 104.0 byts 4.601 uS 4.001 uS REDBLK
55
2807737 58.0 byts 0.875 uS 1455201 78.7 byts 3.898 uS 2.687 uS JUDY
57
With = 1.46 million lines stored and 2.81 million non-blank lines,
58
all the algorithms seem to keep their performance. The hash table is a
59
perfect size for this data set. I suspect only the HASH algorithm will
60
slow down with larger data sets unless the hash table is increased larger
61
than 2**20 million entrys. I have now tried a data set with about 10
62
million unique lines on a 64 bit machine (google/data/repos.*).
63
The speeds are about the same. Lookup times are in the 2-4 uSec range
64
and this is probably insignificant compared to the application needing
65
the data. I think all four methods are fine for speed, and Judy is a
66
standout for its memory efficiency -- frequently using less memory than
69
I plan on tuning JudySL in the near future. This should improve the
70
performance of JudySL with short (a text word) strings. I have a data
71
base of all (28.8 million) domain names on the internet as a test case.
74
28826508 28826508 488227095 /data/domnames.txt
76
For the curious, JudySL (I.E JSLI/G macros in this program) is simply an
77
application subroutine that uses JudyL to the work. JudyL is a very
78
scaleable word to word (or pointer) mapper. JudySL is implemented as a
79
digital tree using JudyL arrays as 2^32 (or 2^64 in 64 bit machines)
80
wide (virtual) nodes. Each level in the digital tree decodes the next 4
81
(or 8) bytes of the line/string until only one entry would be in the
82
node. Then the remaining undecoded portion of the line is stored as a
83
string from the parent node. A digital tree does not need rotation or
84
balancing. In practice, digital trees are rarely use because of their
85
poor memory efficiency in the nodes and a tendency to have large depths.
86
These problems are solved in the Judy algorithm. For more details see
87
application notes on: www.sourcejudy.com. And for the really curious,
88
a technical paper is available in the application section. If you would
89
like to be a reviewer, contact Doug Baskins at <doug@sourcejudy.com>
95
#include <stdio.h> // printf
98
#include <errno.h> // errno
99
#include <sys/mman.h> // mmap()
100
#include <sys/stat.h> // stat()
101
#include <sys/time.h> // gettimeofday()
103
// remove all uses of this in production code.
104
int gDupCnt = 0; // counter for duplicate strings
106
//=======================================================================
107
// T I M I N G M A C R O S
108
//=======================================================================
109
// if your machine is one of the supported types in the following header
110
// file then uncomment this corresponding to what the header file says.
111
// This will give very high timing resolution.
113
// #define JU_xxxxxxx 1 // read timeit.h
114
// #define JU_LINUX_IA32 1 // I.E. IA32 Linux
117
// optional for high resolution times and compile with timeit.c
118
// cc -static -O -o Judy -DJUDYMETHOD SLcompare.c timeit.c -lJudy
120
//#include "timeit.h"
122
double DeltaUSec; // Global for remembering delta times
126
// Note: I have found some Linux systems (2.4.18-6mdk) to have bugs in the
127
// gettimeofday() routine. Sometimes it returns a negative ~2840 microseconds
128
// instead of 0 or 1. If you use the above #include "timeit.h" and compile with
129
// timeit.c and use -DJU_LINUX_IA32, that problem will be eliminated. This is
130
// because for delta times less than .1 sec, the hardware free running timer
131
// is used instead of gettimeofday(). I have found the negative time problem
132
// appears about 40-50 times per second with consecutive gettimeofday() calls.
134
#define TIMER_vars(T) struct timeval __TVBeg_##T, __TVEnd_##T
136
#define STARTTm(T) gettimeofday(&__TVBeg_##T, NULL)
140
gettimeofday(&__TVEnd_##T, NULL); \
141
(D) = (double)(__TVEnd_##T.tv_sec - __TVBeg_##T.tv_sec) * 1E6 + \
142
((double)(__TVEnd_##T.tv_usec - __TVBeg_##T.tv_usec)); \
147
//=======================================================================
148
// M E M O R Y S I Z E M A C R O S
149
//=======================================================================
150
// Most mallocs have mallinfo()
152
// define this if your malloc does not have mallinfo();
155
double DeltaMem; // for remembering
159
#include <malloc.h> // mallinfo()
161
struct mallinfo malStart;
163
#define STARTmem malStart = mallinfo() /* works with some mallocs */
166
struct mallinfo malEnd = mallinfo(); \
167
/* strange little dance from signed to unsigned to double */ \
168
unsigned int _un_int = malEnd.arena - malStart.arena; \
169
DeltaMem = _un_int; /* to double */ \
174
// this usually works for machines with less than 1-2Gb RAM.
175
// (it does not include memory ACQUIRED by mmap())
179
#define STARTmem (malStart = (char *)sbrk(0))
182
char *malEnd = (char *)sbrk(0); \
183
DeltaMem = malEnd - malStart; \
189
//=======================================================================
190
// G E T S T R I N G F R O M mmap() F I L E M A C R O
191
//=======================================================================
193
// From memory map POINTER store next '\n' terminated string to BUFFER
194
// Delete spaces, tabs, returns and resulting blank lines.
196
// POINTER must be check to be within memory mapped file range
198
// NOTE: This code will core-dump if a corrupt text file because
199
// POINTER is not checked to exceed end of file.
201
#define MAXLINE 10000 // max length line
203
#define GETLINE(BUFFER,POINTER) \
207
for (;;) /* forever */ \
209
switch (_chr = *POINTER++) \
211
case ' ': /* eat spaces */ \
212
case '\t': /* eat tabs */ \
213
case '\r': /* eat returns */ \
215
case '\n': /* eat blank lines */ \
216
if (_count == 0) continue; \
217
case '\0': /* Done */ \
218
BUFFER[_count++] = '\0'; \
220
default: /* copy char */ \
221
if (_count == (MAXLINE - 1)) \
222
{ /* cut into 2 lines */ \
223
BUFFER[_count++] = '\0'; \
227
BUFFER[_count++] = _chr; \
235
//=======================================================================
236
// J U D Y M E T H O D
237
//=======================================================================
240
#define ADTMETHOD "JUDY"
244
#define MEMOVD 0 /* no overhead in Judy */
245
#define INITARRAY Pvoid_t JudyArray = NULL
247
// store string into array
248
#define STORESTRING(STRING) \
251
JSLI(_PValue, JudyArray, STRING); /* insert string */ \
252
if (++(*_PValue) != 1) gDupCnt++; /* count dup strings */ \
255
// get pointer to Value associated with string
257
#define GETSTRING(STRING) \
260
JSLG(_PValue, JudyArray, STRING); \
261
if (_PValue == NULL) /* not found -- bug */ \
263
printf("GETSTRING failed(Judy) -- BUG!\n\n"); \
270
// Note: this optimization by J. Zobel should not be necessary
271
// with the -static compile option (linux). (dlb)
275
scmp(char *s1, char *s2)
277
while (*s1 != '\0' && *s1 == *s2)
284
#else // ! SLOW_STRCMP
288
#endif // ! SLOW_STRCMP
290
//=======================================================================
291
// H A S H M E T H O D
292
//=======================================================================
295
#define ADTMETHOD "HASH"
297
#define MEMOVD (sizeof(ht)) /* the hash table is overhead */
299
#define STORESTRING(STRING) hashinsert(ht, STRING)
301
#define GETSTRING(STRING) \
304
_return = hashsearch(ht, STRING); \
305
if (_return == NULL) /* not found -- bug */ \
307
printf("GETSTRING(hash) failed -- BUG!\n\n"); \
312
/* Author J. Zobel, April 2001.
313
Permission to use this code is freely granted, provided that this
314
statement is retained. */
316
#define TSIZE (1LU << 20) /* many processors need this to be a pwr of 2 */
318
#define HASHFN bitwisehash
320
#define INITARRAY static HASHREC *ht[TSIZE]
321
#define SIZEOFINIT sizeof(ht[TSIZE])
323
typedef struct hashrec
326
struct hashrec *next;
330
/* Bitwise hash function. Note that tsize does not have to be prime. */
332
bitwisehash(char *word, int tsize, unsigned int seed)
338
for (; (c = *word) != '\0'; word++)
340
h ^= ((h << 5) + c + (h >> 2));
342
return ((unsigned int)((h & 0x7fffffff) % tsize));
345
#ifdef notdef // not needed if a static definition used in UNIX
346
/* Create hash table, initialise ptrs to NULL */
353
ht = (HASHREC **) malloc(sizeof(HASHREC *) * TSIZE);
355
for (i = 0; i < TSIZE; i++)
356
ht[i] = (HASHREC *) NULL;
362
/* Search hash table for given string, return record if found, else NULL */
364
hashsearch(HASHREC ** ht, char *w)
366
HASHREC *htmp, *hprv;
367
unsigned int hval = HASHFN(w, TSIZE, SEED);
369
for (hprv = NULL, htmp = ht[hval];
370
htmp != NULL && scmp(htmp->word, w) != 0;
371
hprv = htmp, htmp = htmp->next)
376
if (hprv != NULL && htmp != NULL) /* move to front on access */
378
hprv->next = htmp->next;
379
htmp->next = ht[hval];
386
/* Search hash table for given string, insert if not found */
388
hashinsert(HASHREC ** ht, char *w)
390
HASHREC *htmp, *hprv;
391
unsigned int hval = HASHFN(w, TSIZE, SEED);
393
for (hprv = NULL, htmp = ht[hval];
394
htmp != NULL && scmp(htmp->word, w) != 0;
395
hprv = htmp, htmp = htmp->next)
402
htmp = (HASHREC *) malloc(sizeof(HASHREC));
403
htmp->word = (char *)malloc(strlen(w) + 1);
404
strcpy(htmp->word, w);
411
/* new records are not moved to front */
415
if (hprv != NULL) /* move to front on access */
417
hprv->next = htmp->next;
418
htmp->next = ht[hval];
421
gDupCnt++; /* count duplicate strings */
429
//=======================================================================
430
// S P L A Y M E T H O D
431
//=======================================================================
434
#define ADTMETHOD "SPLAY"
436
#define MEMOVD 0 /* not enough overhead to count */
438
/* Author J. Zobel, April 2001.
439
Permission to use this code is freely granted, provided that this
440
statement is retained. */
444
typedef struct wordrec
447
struct wordrec *left, *right;
452
typedef struct ansrec
454
struct wordrec *root;
459
#define ONELEVEL(PAR,CURR,DIR,RID) \
461
PAR->DIR = CURR->RID; \
463
PAR->DIR->PAR = PAR; \
469
#define ZIGZIG(GPAR,PAR,CURR,DIR,RID) \
471
CURR->PAR = GPAR->PAR; \
472
if (CURR->PAR != NULL) \
474
if (CURR->PAR->DIR == GPAR) \
475
CURR->PAR->DIR = CURR; \
477
CURR->PAR->RID = CURR; \
479
GPAR->DIR = PAR->RID; \
480
if (GPAR->DIR != NULL) \
481
GPAR->DIR->PAR = GPAR; \
482
PAR->DIR = CURR->RID; \
483
if (CURR->RID != NULL) \
484
CURR->RID->PAR = PAR; \
491
#define ZIGZAG(GPAR,PAR,CURR,DIR,RID) \
493
CURR->PAR = GPAR->PAR; \
494
if (CURR->PAR != NULL) \
496
if (CURR->PAR->DIR == GPAR) \
497
CURR->PAR->DIR = CURR; \
499
CURR->PAR->RID = CURR; \
501
PAR->RID = CURR->DIR; \
502
if (PAR->RID != NULL) \
503
PAR->RID->PAR = PAR; \
504
GPAR->DIR = CURR->RID; \
505
if (GPAR->DIR != NULL) \
506
GPAR->DIR->PAR = GPAR; \
513
int scount = ROTATEFAC;
515
/* Search for word in a splay tree. If word is found, bring it to
516
root, possibly intermittently. Structure ans is used to pass
517
in the root, and to pass back both the new root (which may or
518
may not be changed) and the looked-for record. */
520
splaysearch(ANSREC * ans, char *word)
522
TREEREC *curr = ans->root, *par, *gpar;
527
if (ans->root == NULL)
532
while (curr != NULL && (val = scmp(word, curr->word)) != 0)
542
if (curr == ans->root)
547
if (scount <= 0 && curr != NULL) /* Move node towards root */
551
while ((par = curr->par) != NULL)
553
if (par->left == curr)
555
if ((gpar = par->par) == NULL)
557
ONELEVEL(par, curr, left, right);
559
else if (gpar->left == par)
561
ZIGZIG(gpar, par, curr, left, right);
565
ZIGZAG(gpar, par, curr, right, left);
570
if ((gpar = par->par) == NULL)
572
ONELEVEL(par, curr, right, left);
574
else if (gpar->left == par)
576
ZIGZAG(gpar, par, curr, left, right);
580
ZIGZIG(gpar, par, curr, right, left);
590
/* Insert word into a splay tree. If word is already present, bring it to
591
root, possibly intermittently. Structure ans is used to pass
592
in the root, and to pass back both the new root (which may or
593
may not be changed) and the looked-for record. */
596
splayinsert(ANSREC * ans, char *word)
598
TREEREC *curr = ans->root, *par, *gpar, *prev = NULL, *wcreate();
603
if (ans->root == NULL)
605
ans->ans = ans->root = wcreate(word, NULL);
609
while (curr != NULL && (val = scmp(word, curr->word)) != 0)
621
curr = prev->right = wcreate(word, prev);
623
curr = prev->left = wcreate(word, prev);
626
gDupCnt++; /* count duplicate strings */
630
if (scount <= 0) /* Move node towards root */
634
while ((par = curr->par) != NULL)
636
if (par->left == curr)
638
if ((gpar = par->par) == NULL)
640
ONELEVEL(par, curr, left, right);
642
else if (gpar->left == par)
644
ZIGZIG(gpar, par, curr, left, right);
648
ZIGZAG(gpar, par, curr, right, left);
653
if ((gpar = par->par) == NULL)
655
ONELEVEL(par, curr, right, left);
657
else if (gpar->left == par)
659
ZIGZAG(gpar, par, curr, left, right);
663
ZIGZIG(gpar, par, curr, right, left);
672
/* Create a node to hold a word */
674
wcreate(char *word, TREEREC * par)
678
tmp = (TREEREC *) malloc(sizeof(TREEREC));
679
tmp->word = (char *)malloc(strlen(word) + 1);
680
strcpy(tmp->word, word);
681
tmp->left = tmp->right = NULL;
688
#define INITARRAY ANSREC ans = {0}
690
#define STORESTRING(STRING) splayinsert(&ans, STRING)
692
#define GETSTRING(STRING) splaysearch(&ans, STRING)
694
#endif // SPLAYMETHOD
696
//=======================================================================
697
// R E D B L A C K M E T H O D
698
//=======================================================================
700
#ifdef REDBLACKMETHOD
701
#define ADTMETHOD "REDBLACK"
703
#define MEMOVD 0 /* not enough overhead to count */
705
/* Author J. Zobel, April 2001.
706
Permission to use this code is freely granted, provided that this
707
statement is retained. */
709
typedef struct wordrec
712
struct wordrec *left, *right;
718
typedef struct ansrec
720
struct wordrec *root;
728
/* Find word in a redblack tree */
731
redblacksearch(ANSREC * ans, char *word)
733
TREEREC *curr = ans->root;
736
if (ans->root != NULL)
738
while (curr != NULL && (val = scmp(word, curr->word)) != 0)
752
/* Rotate the right child of par upwards */
753
/* Could be written as a macro, but not really necessary
754
as it is only called on insertion */
757
leftrotate(ANSREC * ans, TREEREC * par)
759
TREEREC *curr, *gpar;
761
if ((curr = par->right) != NULL)
763
par->right = curr->left;
764
if (curr->left != NULL)
765
curr->left->par = par;
766
curr->par = par->par;
767
if ((gpar = par->par) == NULL)
771
if (par == gpar->left)
781
/* Rotate the left child of par upwards */
783
rightrotate(ANSREC * ans, TREEREC * par)
785
TREEREC *curr, *gpar;
787
if ((curr = par->left) != NULL)
789
par->left = curr->right;
790
if (curr->right != NULL)
791
curr->right->par = par;
792
curr->par = par->par;
793
if ((gpar = par->par) == NULL)
797
if (par == gpar->left)
807
/* Insert word into a redblack tree */
809
redblackinsert(ANSREC * ans, char *word)
811
TREEREC *curr = ans->root, *par, *gpar, *prev = NULL, *wcreate();
814
if (ans->root == NULL)
816
ans->ans = ans->root = wcreate(word, NULL);
819
while (curr != NULL && (val = scmp(word, curr->word)) != 0)
831
/* Insert a new node, rotate up if necessary */
834
curr = prev->right = wcreate(word, prev);
836
curr = prev->left = wcreate(word, prev);
839
while ((par = curr->par) != NULL
840
&& (gpar = par->par) != NULL && curr->par->colour == RED)
842
if (par == gpar->left)
844
if (gpar->right != NULL && gpar->right->colour == RED)
847
gpar->right->colour = BLACK;
853
if (curr == par->right)
856
leftrotate(ans, curr);
860
if ((gpar = par->par) != NULL)
863
rightrotate(ans, gpar);
869
if (gpar->left != NULL && gpar->left->colour == RED)
872
gpar->left->colour = BLACK;
878
if (curr == par->left)
881
rightrotate(ans, curr);
885
if ((gpar = par->par) != NULL)
888
leftrotate(ans, gpar);
893
if (curr->par == NULL)
895
ans->root->colour = BLACK;
898
gDupCnt++; /* count duplicate strings */
903
/* Create a node to hold a word */
905
wcreate(char *word, TREEREC * par)
909
tmp = (TREEREC *) malloc(sizeof(TREEREC));
910
tmp->word = (char *)malloc(strlen(word) + 1);
911
strcpy(tmp->word, word);
912
tmp->left = tmp->right = NULL;
919
#define INITARRAY ANSREC ans = {0}
921
#define STORESTRING(STRING) redblackinsert(&ans, STRING)
923
#define GETSTRING(STRING) redblacksearch(&ans, STRING)
925
#endif // REDBLACKMETHOD
927
//=======================================================================
928
// M A I N P R O G R A M -by- Doug Baskins
929
//=======================================================================
931
// error routine for system routines for accessing file
935
printf("%s: Cannot open file \"%s\": %s " \
936
"(errno = %d)\n", argv[0], argv[1], strerror(errno), \
938
fprintf(stderr, "%s: Cannot open file \"%s\": %s " \
939
"(errno = %d)\n", argv[0], argv[1], strerror(errno), \
945
//=======================================================================
946
// M E A S U R E A D T S P E E D and M E M O R Y U S A G E
947
//=======================================================================
950
main(int argc, char *argv[])
952
TIMER_vars(tm); // declare timer variables
953
int fd; // to read file.
954
struct stat statbuf; // to get size of file
955
char *Pfile; // ram address of file
956
size_t fsize; // file size in bytes
957
char *FSmap; // start address of mapped file
958
char *FEmap; // end address+1 of mapped file
959
char String[MAXLINE]; // input buffer
960
int StrCnt; // line counter
965
// CHECK FOR REQUIRED INPUT FILE PARAMETER:
969
printf("Usage: %s <text file>\n", argv[0]);
975
if (stat(argv[1], &statbuf) == -1)
978
fsize = statbuf.st_size;
982
if ((fd = open(argv[1], O_RDONLY)) == -1)
988
(char *)mmap(NULL, fsize, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
989
if (Pfile == (char *)-1)
992
FEmap = Pfile + fsize; // set end+1 address
994
// print command name + run arguments
997
for (ii = 0; ii < argc; ii++)
998
printf("%s ", argv[ii]);
1002
// file is in RAM, read again to measure time
1004
STARTTm(tm); // start timer
1006
for (StrCnt = 0, FSmap = Pfile; FSmap < FEmap; )
1008
GETLINE(String, FSmap); // 'read' next string
1012
ENDTm(DeltaUSec, tm); // end timer
1014
// print header - 6 fields
1016
printf("# lines avg_linelen getline stored");
1017
printf(" RAMused/line store/ln lookup/ln ADT\n");
1019
// print numb lines filesize/line
1021
printf("%8u", StrCnt); // Number of lines
1022
printf(" %6.1f byts", (double)fsize / (double)StrCnt); // filesize/line
1025
// print time to read a line
1027
printf(" %5.3f uS", DeltaUSec / (double)StrCnt);
1030
// INPUT/STORE LOOP:
1032
// read each input line into String and store into ADT
1034
STARTmem; // current malloc() mem usage
1035
STARTTm(tm); // start timer
1037
for (FSmap = Pfile; FSmap < FEmap; )
1039
GETLINE(String, FSmap); // 'read' next string
1041
STORESTRING(String);
1043
ENDTm(DeltaUSec, tm); // end timer
1044
ENDmem; // current malloc() mem usage
1046
// print number of non-duplicate lines
1048
printf(" %8u", StrCnt - gDupCnt); // duplicate lines
1050
// print RAM used by malloc() by ADT to store data
1052
printf(" %7.1f byts", (double)(DeltaMem + MEMOVD) /
1053
(double)(StrCnt - gDupCnt));
1055
// print time per line to store the data
1057
printf(" %6.3f uS", DeltaUSec / (double)StrCnt);
1062
STARTTm(tm); // start timer
1064
for (FSmap = Pfile; FSmap < FEmap; )
1066
GETLINE(String, FSmap); // 'read' next string
1070
ENDTm(DeltaUSec, tm); // end timer
1072
// print time per line to lookup the data from the ADT
1074
printf(" %6.3f uS", DeltaUSec / (double)StrCnt); // store time/line
1075
printf(" %s\n", ADTMETHOD);