-
Notifications
You must be signed in to change notification settings - Fork 6
/
README.txt
executable file
·209 lines (147 loc) · 10.2 KB
/
README.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
Refereed Cache-Conscious String Data Structures for Strings
This is the complete readme file for my memory-resident string
data structures, as detailed in my PhD Thesis. Depending on your download,
you may only have a selection of these data structures.
Author: Dr. Nikolas Askitis.
Email: [email protected]
PUBLICATIONS
--------------------------------------------------------------------------------------------------------------------
These data structures are available from the following refereed publications:
1. B-tries for Disk-based String Management, VLDB Journal, Volume 18, Issue 1, Pages 157 - 179, 2009. ISSN:1066-8888
2. Engineering scalable, cache and space efficient tries for strings, VLDB Journal, Published Online, 2010. DOI: 10.1007/s00778-010-0183-9 ISSN: 1066-8888
3. HAT-Trie: A Cache-Conscious Trie-Based Data Structure For Strings, The 30th International Australasian Computer Science Conference (ACSC), Volume 62, pages 97 - 105, 2007. ISSN: 1445-1336
4. Cache-conscious collision resolution in string hash tables, The 12th International String Processing and Information Retrieval Conference (SPIRE), LNCS 3772, pages 91 - 102, 2005. ISSN: 0302-9743
5. Fast and compact hash tables for integer keys, The 32nd International Australasian Computer Science Conference (ACSC), Volume 91, pages 101 - 110, 2009. ISSN: 1445-1336
6. Redesigning the string hash table, burst trie, and BST to exploit cache, ACM JEA Vol. 15, No. 1, Article 1.7 2011
GENERAL GUIDELINES:
--------------------------------------------------------------------------------------------------------------------
A file to insert or search is first buffered entirely in main-memory to factor-out the cost of fetching
individual strings from disk. Hence, it is important to keep the file size small,
relative to the amount of memory your system has and the size of the data structure.
Otherwise, the file buffer will occupy most of main memory, forcing the data structure
to use virtual memory.
If you want to use a large file, then simply break it up into smaller pieces and
list the pieces on the command-line, as shown below.
*** You must provide the correct parameters (command-line format) to these data structures,
as shown below.
For accurate results, be sure to run these data structures when your operating system is
under light load. That is, don't run any other unnecessary software and drop down to
console mode if possible (temporarily stop your graphical user interface like KDE).
Also, please disable power-saving features such as Intel SpeedStep or AMD Cool 'n' Quiet technology. This is to
ensure that your processor(s) are operating at full speed before running the software.
You can find out what speed your processor (cores) are running at using the following command in Linux: less /proc/cpuinfo
DATA STRUCTURES
--------------------------------------------------------------------------------------------------------------------
1. array BST
2. standard BST
3. array hash table (3 variants)
4. standard hash table
5. array burst-trie (2 variants)
6. standard burst-trie
7. standard redblack
8. standard splay
9. HAT-trie
10. B-trie
11. B-tree
SOFTWARE VARIANTS
--------------------------------------------------------------------------------------------------------------------
a) Hash tables:
array-hash-exact = array hash table where slots are resized by as many bytes as needed (i.e exact-fit)
array-hash-page = array hash table where slots are resized in 64-byte blocks.
array-hash-exact-mtf = array hash table with exact-fit and move-to-front on access.
array-hash-32bit-int = array hash table designed for 32-bit integer (binary) keys (with 32-bit integer payload).
b) Burst tries:
The array burst trie also has the same variants, namely the:
array-burst-trie-exact
array-burst-trie-page
PC ARCHITECTURE (AMD 64-bit or Intel 64-bit Processor)
----------------------------------------------------------------------------------------------------------------------
Developed for x86_64 Linux Platforms on an AMD or Intel based processor.
We used Kubuntu 10.04 to compile and prepare the software.
Currently, my data structures are designed for 64-bit architectures (hence,
they assume that pointers are 8-bytes long). Please note, in my papers, I (mostly)
used the 32-bit versions, since back then, my primary machine was a 32-bit P4. Check out
paper number 2, listed above, for reference of performance on a more modern 64-bit processor.
DATA SETS
---------------------------------------------------------------------------------------------------------------------
These (string dictionary) data structures support plain-text ASCII-7 datasets (printable-range).
Strings can be of variable-length and are null-terminated, one string per line.
For example:
HTML
test
apple
automobile
aeroplane
space
b
a
genome sequence analysis
testing the source
ozsort
test
...
The 32-bit integer (dictionary) data structures support 4-byte integer datasets (in binary format, that is,
non-human readable). They must appear all in one line.
EXPERIMENTS
---------------------------------------------------------------------------------------------------------------------
./quick_compare.bsh [optional: user-specified file]
This script will run a "quick-and-dirty" benchmark experiment, comparing all these data structures using a user-specified file.
You will need a x86_64 Intel/AMD Linux PC with at least 4GB of RAM to run these experiments. 8GB of RAM is recommended.
Eg:
bunzip2 sampleData.bz2;
./quick_compare.bsh sampleData;
TO RUN:
----------------------------------------------------------------------------------------------------------------------
All data structures share the same command-line interface, as follows:
<data-structure> [Number of slots or the container size] [[ output file name ]] <number of datasets to insert> <datasets to insert (separated by white space)> <number of datasets to search> <datasets to search (separated by white space)>
Parameters within <> brackets are mandatory, whereas those in [] brackets are only required by the hash table(s) and burst trie(s).
Parameters in [[ ]] brackets are only required by the B-tree and B-trie.
1) Container size: the number of strings a container must store before it is burst.
2) Number of slots: the number of slots allocated by the hash table (power of 2).
**************************************************************************************
IMPORTANT:
Slot numbers of be of a power of 2 e.g: 65536, 8388608, etc.
Slot numbers and container sizes must be set to no less than 16.
**************************************************************************************
EXAMPLES:
-----------------------------------------------------------------------------------------------------------------------
./nikolas_askitis_array_bst 1 /mnt/in/data/file1 2 /mnt/in/data/file1 /tmp/other
./standard-bst 1 /mnt/in/data/file1 2 /mnt/in/data/file1 /tmp/other
./nikolas_askitis_array_burst_trie_exact 256 3 file1 file2 file3 1 file2
./nikolas_askitis_hat_trie 32768 3500000 1 dataset 1 dataset
./nikolas_askitis_array_hash 65536 1 skew1.in 1 skew1.in
./nikolas_askitis_btrie output_file 1 file1 1 file2
./nikolas_askitis_btree output_file 1 file1 1 file2
OUTPUT:
------------------------------------------------------------------------------------------------------------------------
The output of all data structures are as follows (in order, from left-to-right):
1) The data structure used:
2) Total memory (virtual memory): This is the total memory used by the running process, as reported by the operating system.
This is a true measure of memory consumption, capturing space lost due to fragmentation
and other overheads. This measure does not include the space taken to buffer the
dataset. If you use the 'top' Linux command, for example, this will capture the same
information, but with the space occupied by the dataset buffer, which can make it
difficult to see how must space is eaten by the program itself, and not its file buffer.
3) Estimated memory usage: The total memory, in megabytes, required by the data structure --- the measure
includes the estimated 8-byte allocation overhead imposed by every call to malloc. It
may be slightly less than or more than the virtual memory usage reported (in step 2).
For the B-tree and B-trie, this represents the total disk space used.
4) Total insertion time: The total or elapsed time, in seconds, required by the data structure
to insert the files that were specified on the command line.
5) Total search time: The total or elapsed time, in seconds, required by the data structure to
search the files that were specified on the command line.
6) Number of strings inserted: Returns the total number of strings stored by the data structure.
IMPORTANT: the data structure does not maintain duplicates, hence, only
unique strings are inserted.
7) Number of strings searched: Returns the total number of strings that were found during a search.
8) Number of slots allocated or
container threshold: The number of slots allocated by the hash table or the container threshold (the
number of strings a container can store prior to bursting) of a burst trie. For
the B-tree and B-trie, this is the bucket size used for leaf nodes, which is
set to 8192 bytes in this release.
9) Additional (optional) info: Extra information may be displayed, such as growth policy used and whether
move-to-front is enabled.
An example (we map the output to the numbers above):
linux@: ./array-bst 1 28772169 1 28772169
Array-BST 774.09 764.92 456.12 423.41 28772169 28772169
(1) (2) (3) (4) (5) (6) (7)