regex direct support for sse4 intrinsics

Dmitry Olshansky dmitry.olsh at gmail.com
Mon Mar 26 12:10:44 PDT 2012


On 26.03.2012 22:14, Jay Norwood wrote:
> The sse4 capabilities include a range mode of string matching,
> that lets you match characters in a 16 byte string based on a 16
> byte set of start and stop character ranges. See the
> _SIDD_CMP_RANGES mode in the table.
>
>
> For example, the pattern in some of our examples for finding the
> start of a word is a-zA-Z, and for other characters in the word
> a-zA-Z0-9. Either of these patterns could be tested for match on
> a 16 byte input in a single operation in the sse4 engine.
>
> http://msdn.microsoft.com/en-us/library/bb531465.aspx

Nice idea.
Though I can assure you that the biggest problem is not in comparing 
things at all. The most time is spent accessing various lookup tables, 
saving/loading state, updating match location and so on. Especially so 
because of Unicode. Also add an overhead of UTF decoding into the mix 
(that I plan to avoid).
To put it bluntly: R-T version spends around 20% of time doing actual 
matching at best (averaged, depends on pattern), half of this could be 
avoided by optimizing "framework" code.
C-T version spends around 35% on on matching, but still the main
inefficiency in the "framework" part of code. C-T matcher admittedly has 
very simple framework.

Speaking more of run-time version of regex, it is essentially running a 
VM that executes instructions that do various kinds of match-this, 
match-that. The VM dispatch code is quite slow, the optimal _threaded_ 
code requires either doing it in _assembly_ or _computed_ goto in the 
language. The VM _dispatch_ takes up to 30% of time in the default matcher.

>
> Looking at the msft intrinsics, it seems like the D ones could be
> more efficient and elegant looking using D slices, since they are
> passing the string and length of string as separate parameters.
>
> It would be good if the D regex processing could detect simple
> range match patterns and use the sse4 extensions when available.
>
> There is also an article from intel where they demo use of these
> instructions for xml parsing.
>
> http://software.intel.com/en-us/articles/xml-parsing-accelerator-with-intel-streaming-simd-extensions-4-intel-sse4/
>

Worth looking into.


-- 
Dmitry Olshansky


More information about the Digitalmars-d mailing list