In perl.git, the branch smoke-me/davem/fbm has been created
<http://perl5.git.perl.org/perl.git/commitdiff/2119163cf9aaa352780f851b9f0b14473ec55a41?hp=0000000000000000000000000000000000000000>
at 2119163cf9aaa352780f851b9f0b14473ec55a41 (commit)
- Log -----------------------------------------------------------------
commit 2119163cf9aaa352780f851b9f0b14473ec55a41
Author: David Mitchell <[email protected]>
Date: Sat Sep 26 13:12:40 2015 +0100
make /fixed-substr/ much faster.
TL;DR: on platforms with a libc memchr() implementation which makes good
use of underlying hardware support, patterns which include fixed
substrings will now often be much faster; for example with glibc on on a
recent x86_64 CPU, this:
$s = "a" x 1000 . "wxyz";
$s =~ /wxyz/ for 1..30000
is now about 7 times faster. On systems with slow memchr(), e.g. 32-bit
ARM Raspberry Pi, there will be a small or little speedup. Conversely,
some pathological cases, such as "ab" x 1000 =~ /aa/ will be slower now;
up to 3 times slower on the rPi, 1.5x slower on x86_64.
In detail:
The perl core includes a Boyer-Moore substring matcher, Perl_fbm_instr(),
which is used to quickly find a fixed substring within a longer string,
where a table of lookups is pre-computed from the substring. As well as
being used in index() where the substring is a constant, its main use
is in patterns. When the regex engine compiles a pattern, it typically
takes note of the two longest fixed substrings within the pattern; for
example in
/[01]abc\w+de\d+fghij+/
the two longest are "abc" and "fghij". The engine uses Perl_fbm_instr() to
scan for these two strings before running the full NFA. This often allows
the string to be quickly rejected, or to find a suitable minimum starting
point to run the NFA.
However, Perl_fbm_instr() was written about 16 years ago and has been
virtually untouched since, so it could with some love.
It currently special-cases strings of length 1 and 2, using roll-your-own
loops along the lines of
while (s < end) { if (*s = c1) ... }
while strings of length 3+ use the Boyer-Moore algorithm. The big
advantage of BM is that in a best-case, where none of the characters from
the substring are found in this region of the string, it only has to test
every N'th char, where N is length of the substring. For example when
searching for wxyz in abcdefghikl..., it just reads and tests d,h,l,..
However these days some platforms have decent memchr() implementations.
For example, glibc has assembly-level implementations for i386, x86_64,
sparc32/64, powerpc32/64, s390-32/64, arm, m68k and ia64 by the looks of
it. These can often be substantially faster than a C-level implementation.
This commit makes Perl_fbm_instr() use memchr() where possible.
For the length == 1 special case, it just calls memchr() directly rather
than using a loop as previously.
For the length == 2 special case, it continues to distinguish the cases
where the two chars of the substring are the same or differ. For the
former it calls memchr() after an initial direct failure, i.e.
if (*s != c) { s++; s = memchr(....); ... }
For the latter case it does a similar direct test first (to avoid the
costly overhead of a call to memchr() when the next char is the one we
seek anyway), but in addition, on each failure to find the second char
following a found first char, it swaps which char it's searching for.
This means that in something like "aaaaaaa..." =~ /ab/, it wont keep
hopping 1 char position with memchar(s,'a'); after the first hop it
will do memchr(s,'b') and skip lots of chars in one go. This helps reduce
the number of pathological cases.
For the length >= 3 cases (normal BM), it keeps using BM, but after each
iteration where the pointer has been incremented by the skip determined by
the BM algorithm, it now does an additional
if (*s != c) { s++; s = memchr(....); ... }
step before running the next iteration of BM.
M t/perf/benchmarks
M util.c
commit e57a4087250d7ec97166209c42bdb30a1bef510a
Author: David Mitchell <[email protected]>
Date: Fri Sep 25 16:02:53 2015 +0100
fbm_instr(): tweak docs and formatting
Expand the commentary at the start of this function; add more blank lines
to separate chunks of code, and document what SVpbm_TAIL is for.
M sv.h
M util.c
-----------------------------------------------------------------------
--
Perl5 Master Repository
