Vectorization

Modern processors offer lot of implicit parallelism by vector instruction. We can obtain similar level of paralellism by using ordinary aritmetic.

We are given a simple regular expression and we want to find all of its occurences as fast as possible. For typical matching of regular expression an engine spends most time finding possible start. Our framework allows find these starts quickly.

We first describe a domain specific language {\it llmatch} to 

We use a domain specific language called {\it llmatch} to generate c code. 
\begin{tabular}{l | l}
\verb$char(x)   $& match character
\verb$range(x,y)$& match character range
\verb${code}    $& semantic action
\verb$e1 e2     $& sequencing
\verb$e1|e2     $& choice
\verb$e1&e2 ~e1 $& lookaheads
\end{tabular}
We restrict sequencing for sake of implementation, a first expression must always end in same position.

Semantic actions are specified in \verb$C$ language. They can access variables s and p which are matched string and start of current match.

We can describe \verb$C$ string functions  as

\begin{verbatim}
	strlen    = char('\0') {return p-s;}

	strchr(n) = char(n[0]) {return p;}
						| char('\0') {return NULL;}

	strstr(n) = char(n[0]) char(n[1]) {if (!cmp(p+2,n+2)) return p;}
						| char('\0') {return NULL;}
\end{verbatim}

Compare with glibc handcrafted assembly on i7. 
As strstr must on unsuccessfull match find a trailing zero. lower bound on optimum. Degenerate cases, treated later.

Implementation vector instructions 
test_eq aritmetic

strstr