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

Minor edits, spelling, grammar, consistency.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/re/analysis.tex

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