1 | \section{Running-time Comparison with DFA and NFA |
---|
2 | Implementations}\label{sec:analysis} |
---|
3 | |
---|
4 | Our experimental results indicate that regular expression matching using |
---|
5 | bitstreams can outperform current implementations of NFA- and DFA-based |
---|
6 | matching. |
---|
7 | It is worth exploring why this is so, and under what conditions one might |
---|
8 | expect bitstreams to perform better than NFA- or DFA-based matchers, and |
---|
9 | vice-versa. |
---|
10 | |
---|
11 | The bitstream method starts with a preprocessing step: the compilation |
---|
12 | of the |
---|
13 | regular expression using the parabix toolchain. |
---|
14 | Compilation is an offline process whose time is not counted in our |
---|
15 | performance |
---|
16 | measures, as parabix is a experimental research compiler that is not |
---|
17 | optimized. |
---|
18 | This leads to a bias in our results, as our timings for nrgrep and grep |
---|
19 | include the time taken for preprocessing. |
---|
20 | We have attempted to minimize the bias by performing our tests with large |
---|
21 | inputs, so that the text-scanning costs dominate the preprocessing costs. |
---|
22 | We furthermore believe that, if a special-purpose optimized compiler for |
---|
23 | regular expressions were built, that its inclusion in bitstream grep |
---|
24 | would not |
---|
25 | substantially increase the running time, particularly for large input |
---|
26 | texts--the compilation involved is straightforward. |
---|
27 | |
---|
28 | For simplicity, we will first assume that the input regular expressions |
---|
29 | are restricted to having Kleene closures only of single characters or |
---|
30 | alternations of single characters. |
---|
31 | This is a broad class of regular expressions, covering the majority of |
---|
32 | common uses of grep. |
---|
33 | |
---|
34 | Let $\Sigma$ be our input alphabet and $\sigma = | \Sigma |$. |
---|
35 | As we are comparing techniques in practice, we assume that $\Sigma$ is a |
---|
36 | standard input alphabet, such as ASCII ($\sigma = 128$), UTF-8 ($\sigma = 256$), |
---|
37 | UTF-16 ($\sigma = 65536$ ), or UTF-32 ($\sigma \approx 4.3 \times 10^9$). |
---|
38 | This assumption allows us to equate the number of bits in the encoding of a |
---|
39 | character (a parameter for the bitstream method) with $\log \sigma$. |
---|
40 | |
---|
41 | |
---|
42 | The bitstream method compiles a regular expression of size $m$ into |
---|
43 | bitstream code that is $O(m \log \sigma)$ statements long (with one operation |
---|
44 | per statement; it is essentially three-address code). |
---|
45 | This is translated to machine code and placed inside a |
---|
46 | loop\footnote{Technically, it is inside two loops: an inner one that |
---|
47 | executes once per $w$ characters in a large buffer, and an outer one |
---|
48 | that successively fetches |
---|
49 | buffers until the input is exhausted.} that |
---|
50 | executes once per $w$ characters, where $w$ is the width of the processor's |
---|
51 | word. |
---|
52 | Also inside this loop is the transposition step that converts character-encoded |
---|
53 | files into their bitstream representation; |
---|
54 | this transposition takes $O(\log w)$ work per loop iteration. |
---|
55 | |
---|
56 | In total, this is $O(m \log \sigma + \log w)$ work per iteration. |
---|
57 | In current practice, we have $\log w$ around 8 (for 256-bit architectures), |
---|
58 | and $\log \sigma$ at least 7. |
---|
59 | Thus, $m \log \sigma$ will dominate $\log w$ |
---|
60 | with current and forseeable technology--we do not expect to see $\log w$ |
---|
61 | skyrocket. |
---|
62 | So we can absorb the $\log w$ term and state the work as $O(m \log \sigma)$ per |
---|
63 | iteration. |
---|
64 | We multiply this by $O(\frac{n}{w})$ iterations to give |
---|
65 | $O(\frac{n m \log \sigma}{w})$ work. |
---|
66 | |
---|
67 | We further note that all of the work in the loop is |
---|
68 | done by superscalar instructions, with the exception of the additions, |
---|
69 | which require carry propagation. |
---|
70 | There will be at most $C$ of these additions in the loop, where $C$ is the |
---|
71 | number of concatenation and Kleene star operations in the regular |
---|
72 | expression; $C < m$. |
---|
73 | |
---|
74 | Almost all intermediate bitstreams in the loop body can be kept in |
---|
75 | registers, |
---|
76 | requiring no storage in memory. |
---|
77 | Good register allocation--and limited live ranges for bitstream |
---|
78 | variables--keeps register spillage to a minimum. |
---|
79 | For those bitstreams that do require storage in memory, |
---|
80 | long buffers are allocated, allowing the successive iterations of the |
---|
81 | loop to access successive memory locations. |
---|
82 | That is, for the few streams requiring it, |
---|
83 | memory is accessed in a sequential fashion. |
---|
84 | As this is the best case for |
---|
85 | hardware prefetching, |
---|
86 | we expect few cache misses with bitstream method. |
---|
87 | |
---|
88 | Compare this with NFA methods. |
---|
89 | In the base NFA method, a state set of approximately $m$ states is kept |
---|
90 | as a bit |
---|
91 | set in $\frac{m}{w}$ machine words (or $\frac{m}{8}$ bytes). |
---|
92 | For each character $c$ of the input, |
---|
93 | a precomputed transition table, indexed by the $c$ and the current state |
---|
94 | set, |
---|
95 | is accessed. |
---|
96 | Since there are $2^{\Theta(m)}$ state sets, the transition table will have |
---|
97 | $\sigma 2^{\Theta(m)}$ entries. |
---|
98 | %%, where $\sigma$ is the size of the input alphabet. |
---|
99 | Each entry is a new state set, which requires $\frac{m}{8}$ bytes. |
---|
100 | Thus, the transition table is of size $\sigma m 2^{\Theta(m)}$, which is |
---|
101 | quite |
---|
102 | large: it can become expensive to precompute, and it consumes a lot of |
---|
103 | memory. |
---|
104 | For even fairly small $m$ a table of this size will probably not fit in |
---|
105 | cache |
---|
106 | memory. |
---|
107 | Thus, we would expect many cache misses with this base method. |
---|
108 | |
---|
109 | To improve the table size, several authors have separated the transition |
---|
110 | table |
---|
111 | into several tables, each indexed by a subset of the bits in the bit set |
---|
112 | representing the current state. |
---|
113 | Suppose one uses $k$ bits of the state set to index each table. |
---|
114 | Ignoring ceilings, this requires $\frac{m}{k}$ tables, |
---|
115 | each with $\sigma 2^k$ |
---|
116 | entries of $\frac{m}{8}$ bytes apiece. |
---|
117 | Each table therefore takes up $ m 2^{k-3} \sigma$ bytes, |
---|
118 | and so the collection of them takes up $\frac{m^2 2^{k-3}\sigma}{k}$ bytes. |
---|
119 | At each character, the NFA algorithm does one lookup in each table, |
---|
120 | combining the results with $\frac{m}{k}-1$ boolean OR operations. |
---|
121 | |
---|
122 | The original NFA method of Thompson uses $k=1$, |
---|
123 | which gives a $m$ tables of $\frac{m \sigma}{4}$ bytes each, |
---|
124 | along with |
---|
125 | $m$ lookups and $m-1$ boolean OR operations to |
---|
126 | combine the lookups, per character. |
---|
127 | |
---|
128 | Navarro and Raffinot use $k= \frac{m}{2}$, |
---|
129 | giving $2$ tables of $2^{\frac{m}{2}-3} m \sigma$ bytes each, |
---|
130 | two lookups per character, and 1 boolean OR operation per character to |
---|
131 | combine the lookups. |
---|
132 | |
---|
133 | In Table \ref{tab:ascii}, we summarize the theoretical analysis of these NFA |
---|
134 | methods, listing the number of table lookups per input character and the size of the |
---|
135 | tables for various values of $m$, the number of states. |
---|
136 | We assume the ASCII character set ($\sigma = 128$); any of the |
---|
137 | UTF character sets would yield larger tables. |
---|
138 | |
---|
139 | \begin{table} |
---|
140 | \small{ |
---|
141 | \begin{tabular}{rrrrrrr} |
---|
142 | %% & & Thompson & \ & NavRaff & NFA \\ |
---|
143 | $k$ & & $1$ & $4$ & $8$ & $\frac{m}{2}$ & $m$\\ |
---|
144 | %%\hline |
---|
145 | lookups & & $m$ & $\frac{m}{4}$ & $\frac{m}{8}$ & 2 & 1\\ |
---|
146 | \hline |
---|
147 | & $m$ & & & & \\ |
---|
148 | \multirow{4}{1.35cm}{memory (KiB)} |
---|
149 | & 5 & 0.8 & 1.6 & 12.5 & 1.3 & 2.5\\ |
---|
150 | & 10 & 3.1 & 6.2 & 50.0 & 10.0 & 160.0\\ |
---|
151 | & 15 & 7.0 & 14.1 & 112.5 & 120.0 & 7680.0\\ |
---|
152 | & 20 & 12.5 & 25.0 & 200.0 & 640.0 & 327680.0\\ |
---|
153 | & 25 & 19.5 & 39.1 & 312.5 & 6400.0 & 13107200.0\\ |
---|
154 | \end{tabular} |
---|
155 | } |
---|
156 | \caption{lookups per character and memory consumed by tables in NFA methods |
---|
157 | (in kibibytes)} |
---|
158 | \label{tab:ascii} |
---|
159 | \end{table} |
---|
160 | |
---|
161 | Of particular importance to the speed of NFA methods is whether the |
---|
162 | table lookups result in cache hits or not. |
---|
163 | If the tables are small enough, then they will fit into cache and |
---|
164 | lookups will all be cache hits, taking minimal time. |
---|
165 | In this case, the time per input character will be a small constant times the |
---|
166 | number of lookups. |
---|
167 | |
---|
168 | If the tables are not small enough to fit into cache, some proportion |
---|
169 | of the lookups will generate cache misses. |
---|
170 | This will stall the processor and these stalls will come to dominate the |
---|
171 | computation time. |
---|
172 | In this case, the time per input character will be some large constant |
---|
173 | (a cache miss can take about two orders of magnitude longer than a cache hit) |
---|
174 | times the number of lookups. |
---|
175 | |
---|
176 | Using 256KiB as an estimate of the size of a current standard data cache, |
---|
177 | we can consider those entries of Table \ref{tab:ascii} above 256 to be |
---|
178 | relatively slow. |
---|
179 | We can summarize these theoretical predictions by saying that the NFA methods |
---|
180 | with small $k$ scale well with an increase in NFA states, but with large $k$ the method is |
---|
181 | limited to a small number of states. |
---|
182 | |
---|
183 | We can now directly (but roughly) compare the NFA methods with bitstream |
---|
184 | methods. |
---|
185 | Consider small-$k$ (say, $k <= 4$) NFA methods. |
---|
186 | For the reasonable range of $m$, the tables fit into cache. |
---|
187 | The running time is predicted to be a small constant times the |
---|
188 | $\frac{m}{k} >= \frac{m}{4}$ lookups. |
---|
189 | The small constant, which we will underapproximate with 4 cycles, is for the |
---|
190 | table addressing computation, combining the lookups with boolean OR, and final state |
---|
191 | detection and handling. |
---|
192 | Thus, the running time per input character may be lower-bounded by |
---|
193 | $4*\frac{m}{4}$, or simply $m$, cycles. |
---|
194 | |
---|
195 | Our method, on the other hand, takes time $O(\frac{m \log \sigma}{w})$ per |
---|
196 | input character, where the constant inside the big-Oh is approximately 2. |
---|
197 | Furthermore, we expect no cache misses due to the regular stride of our memory |
---|
198 | accesses. |
---|
199 | For ASCII, this time becomes at most $2 \frac{7m}{w} = \frac{14m}{w}$ cycles |
---|
200 | per character. |
---|
201 | This is faster than the small-$k$ NFA methods by a factor of $w/14$. |
---|
202 | For processors with a 128-bit word, this is about one order of magnitude. |
---|
203 | |
---|
204 | |
---|
205 | |
---|
206 | |
---|
207 | |
---|