source: docs/Working/icGrep/evaluation.tex @ 4466

Last change on this file since 4466 was 4466, checked in by cameron, 4 years ago

Evaluation of optimization; diagram tweaks

File size: 3.1 KB
Line 
1\section{Evaluation}\label{sec:evaluation}
2
3In this section, we report on the evaluation of ICgrep performance, looking
4at three aspects.   First we consider a performance studies in a series
5of Unicode regular expression search problems in comparison to the
6contemporary competitors, including pcre2grep released in January 2015
7and ugrep of the ICU 54.1 software distribution.  Then we move on to
8investigate some performance aspects of ICgrep internal methods, looking
9at the impact of optimizations and multithreading.
10
11\subsection{ICgrep vs. Contemporary Competitors}
12
13\subsection{Optimizations of Bitwise Methods}
14
15In order to support evaluation of bitwise methods, as well as to support
16the teaching of those methods and ongoing research, icGrep has an array
17of command-line options.   This makes it relatively straightforward
18to report on certain performance aspects of ICgrep, while others require
19special builds. 
20
21For example, the command-line switch {\tt -disable-matchstar} can be used
22to eliminate the use of the MatchStar operation for handling
23Kleene-* repetition of character classes.   In this case, icGrep substitutes
24a while loop that iteratively extends match results.   
25Surprisingly, this
26does not change performance much in many practical cases.   
27In each block,
28the maximum iteration count is the maximum length run encountered; the
29overall performance is based on the average of these maximums throughout the
30file.   But when search for XML tags using the regular expression
31\verb:<[^!?][^>]*>:, a slowdown of more than 2X may be found in files
32with many long tags. 
33
34The {\tt -disable-log2-bounded-repetition} flag allows these
35effectiveness of the special techniques for bounded repetition of
36byte classes to be assessed.   A slowdown of 30\% was observed
37with the searches using the regular expression
38\verb:(^|[ ])[a-zA-Z]{11,33}([.!? ]|$):, for example.
39
40To assess the effectiveness of inserting if-statements, the
41number of non-nullable pattern elements between the if-tests
42can be set with the {\tt -if-insertion-gap=} option.   The
43default value in icGrep is 3, setting the gap to 100 effectively
44turns of if-insertion.   Eliminating if-insertion sometimes improves
45performance by avoiding the extra if tests and branch mispredications.
46For patterns with long strings, however, there can be a substantial
47slowdown; searching for a pattern of length 40 slows down by more
48than 50\% without the if-statement short-circuiting.
49
50ICgrep also provides options that allow
51various internal representations to be printed out.   These
52can aid in understanding and/or debugging performance issues.
53For example, the option
54{\tt -print-REs} show the parsed regular expression as it goes
55through various transformations.   The internal Pablo code generated
56may be displayed with {\tt -print-pablo}.  This can be quite useful in
57helping understand the match process.   It also possible to print out the
58generated LLVM IR code ({\tt -dump-generated-IR}), but this may be
59less useful as it includes many
60details of low-level carry-handling that obscures the core logic.
61
62\subsection{Single vs. Multithreaded Performance}
Note: See TracBrowser for help on using the repository browser.