Changeset 3665 for docs/Working/re/analysis.tex

Ignore:
Timestamp:
Mar 4, 2014, 4:34:49 PM (5 years ago)
Message:

Minor edits, spelling, grammar, consistency.

File:
1 edited

Legend:

Unmodified
 r3641 The bitstream method starts with a preprocessing step: the compilation of the regular expression using the parabix toolchain. regular expression using the Parabix toolchain. Compilation is an offline process whose time is not counted in our performance measures, as parabix is a experimental research compiler that is not measures, as Parabix is a experimental research compiler that is not optimized. This leads to a bias in our results, as our timings for nrgrep and grep inputs, so that the text-scanning costs dominate the preprocessing costs. We furthermore believe that, if a special-purpose optimized compiler for regular expressions were built, that its inclusion in bitstream grep regular expressions were built, that its inclusion in bitstreams grep would not substantially increase the running time, particularly for large input and $\log \sigma$ at least 7. Thus, $m \log \sigma$ will dominate $\log w$ with current and forseeable technology--we do not expect to see $\log w$ with current and foreseeable technology--we do not expect to see $\log w$ skyrocket. So we can absorb the $\log w$ term and state the work as $O(m \log \sigma)$ per The running time is predicted to be a small constant times the $\frac{m}{k} >= \frac{m}{4}$ lookups. The small constant, which we will underapproximate with 4 cycles, is for the The small constant, which we will under approximate with 4 cycles, is for the table addressing computation, combining the lookups with boolean OR, and final state detection and handling.