Changeset 3647


Ignore:
Timestamp:
Feb 24, 2014, 2:28:29 PM (5 years ago)
Author:
cameron
Message:

Integreate gre2p

Location:
docs/Working/re
Files:
2 edited

Legend:

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

    r3642 r3647  
    7575file {data/avxinstructions3.dat};
    7676
    77 \legend{Bitstreams,NRGrep,Gre2p,Annot}
     77\legend{bitstreams,nrgrep,gre2p,Annot}
    7878\end{axis}
    7979\end{tikzpicture}
     
    126126file {data/avxcycles3.dat};
    127127
    128 \legend{Bitstreams,NRGrep,Gre2p,Annot}
     128\legend{bitstreams,nrgrep,gre2p,Annot}
    129129\end{axis}
    130130\end{tikzpicture}
  • docs/Working/re/sse2.tex

    r3644 r3647  
    5050report data for them. 
    5151GNU grep is a popular open-source implementation that is claimed to be
    52 primarily DFA-based with
    53 heuristics for important special cases.   
     52primarily DFA-based with heuristics for important special cases.   
    5453The agrep implementation does not support
    5554some of the common regular expression syntax feature and is limited to
     
    9998file {data/cycles3.dat};
    10099 
    101 \legend{Bitstreams,NRGrep,Gre2p,Annot}
     100\legend{bitstreams,nrgrep,gre2p,Annot}
    102101\end{axis}
    103102\end{tikzpicture}
     
    106105\end{figure}
    107106
    108 Figure \ref{fig:SSECyclesPerByte} shows CPU cycles per input byte for each expression on each implementation.
    109 For the three most complicated expressions, the bitstreams implementation had the lowest cycle count, while grep
    110 was an order of magnitude slower.
    111 
    112 For the @ expression, GNU grep had very slightly better performance than the bitstreams implementation.  The bitstreams implementation has a fixed overhead
    113 for transposition that hurts relative performance for very simple expressions.
    114 
    115 For the Date expression, nrgrep is able to skip large portions of the input file since every time it encounters a character that can't appear in a date, it can skip past six characters.  For the more compicated expressions, it loses this advantage.
    116 
    117 The bitstreams implementation has fairly consistent performance.  As the regular expression complexity increases, the cycle count increases slowly.  The largest difference in cycles per byte for the bitstreams implementation is a ratio of 2 to 1.  The same cannot be said of grep or nrgrep.  The
    118 latter uses more than 10 times the cycles per byte for Xquote than for Date.  The number of cycles per byte that gGrep uses for URIOrEmail is almost 900 times as many as it uses for @.
     107Figure \ref{fig:SSECyclesPerByte} shows CPU cycles per input byte for
     108each expression on each implementation.
     109Both the bitstreams and the nrgrep implementation performed
     110much better than the DFA-based gre2p, with the bitstreams
     111implementation
     112consistently an order of magnitude faster.
     113
     114For the Date expression, nrgrep outperforms our bitstreams
     115implementation here.  In this case, nrgrep takes advantage of skipping:
     116every time it encounters a character that can't appear in a date, it
     117can skip past six characters. 
     118For the more compicated expressions, it loses this advantage.
     119
     120The bitstreams implementation has fairly consistent performance.  As
     121the regular expression complexity increases, the cycle count increases
     122slowly.  The largest difference in cycles per byte for the bitstreams
     123implementation is a ratio of 2 to 1.  The same cannot be said of gre2p
     124or nrgrep, with gre2p exhibiting a 4 to 1 range over these expressions
     125and
     126nrgrep exhibiting a 10 to 1 range.
    119127
    120128\begin{figure}
     
    131139legend style={at={(0.5,-0.15)},
    132140anchor=north,legend columns=-1},
    133 ymax=0.5,
     141ymax=110,
    134142ybar,
    135143bar width=7pt,
     
    142150file {data/instructions3.dat};
    143151 
    144 \legend{Bitstreams,NRGrep,Gre2p,Annot}
     152\legend{bitstreams,nrgrep,gre2p,Annot}
    145153\end{axis}
    146154\end{tikzpicture}
     
    153161implementation continues to show consistent performance.  This is
    154162especially noticeable in Figure \ref{fig:SSEInstructionsPerCycle},
    155 which shows instructions per cycle.  The bitstreams implementation has
    156 almost no variation in the instructions per cycle.  Both grep and
    157 nrGrep have considerably more variation based on the input regular
    158 expression.   
     163which shows instructions per cycle.  Both the bitstreams and
     164gre2p implementations show relatively stable IPC characteristics,
     165while nrgrep exhibits considerably more variation.
    159166 
    160167
     
    182189file {data/ipc3.dat};
    183190
    184 \legend{Bitstreams,NRGrep,Gre2p,Annot}
     191\legend{bitstreams,nrgrep,gre2p,Annot}
    185192\end{axis}
    186193\end{tikzpicture}
     
    212219file {data/branch-misses3.dat};
    213220
    214 \legend{Bitstreams,NRGrep,Gre2p,Annot}
     221\legend{bitstreams,nrgrep,gre2p,Annot}
    215222\end{axis}
    216223\end{tikzpicture}
     
    218225\caption{Branch Misses per Instruction}\label{fig:SSEBranchMisses}
    219226\end{figure}
    220 Figure \ref{fig:SSEBranchMisses} shows the branch misses per kilobyte.  The bitstreams implementation remains consistent here.  Each of nrgrep and grep have branch miss rates that vary significantly with different regular expressions. 
    221 
    222 Overall, our performance is considerably better than both nrgrep and grep for the more complicated expressions that were tested.  Also, our performance scales smoothly with regular expression complexity so it can be expected to remain better for complicated expressions in general.
    223 
    224 
     227Figure \ref{fig:SSEBranchMisses} shows the branch misses per kilobyte.
     228The bitstreams and gre2p implementations remains consistent here.
     229Significant variation is seen with nrgrep.
     230
     231Overall, our performance is considerably better than both nrgrep and gre2p for the more complicated expressions that were tested.  Also, our performance scales smoothly with regular expression complexity so it can be expected to remain better for complicated expressions in general.
     232
     233
Note: See TracChangeset for help on using the changeset viewer.