Branch: refs/heads/smoke-me/khw-regexec
Home: https://github.com/Perl/perl5
Commit: 4e20bf9a5f5a826094b9d4a85d8db7c18df77061
https://github.com/Perl/perl5/commit/4e20bf9a5f5a826094b9d4a85d8db7c18df77061
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M cpan/Test-Harness/lib/App/Prove.pm
M cpan/Test-Harness/lib/App/Prove/State.pm
M cpan/Test-Harness/lib/App/Prove/State/Result.pm
M cpan/Test-Harness/lib/App/Prove/State/Result/Test.pm
M cpan/Test-Harness/lib/TAP/Base.pm
M cpan/Test-Harness/lib/TAP/Formatter/Base.pm
M cpan/Test-Harness/lib/TAP/Formatter/Color.pm
M cpan/Test-Harness/lib/TAP/Formatter/Console.pm
M cpan/Test-Harness/lib/TAP/Formatter/Console/ParallelSession.pm
M cpan/Test-Harness/lib/TAP/Formatter/Console/Session.pm
M cpan/Test-Harness/lib/TAP/Formatter/File.pm
M cpan/Test-Harness/lib/TAP/Formatter/File/Session.pm
M cpan/Test-Harness/lib/TAP/Formatter/Session.pm
M cpan/Test-Harness/lib/TAP/Harness.pm
M cpan/Test-Harness/lib/TAP/Harness/Env.pm
M cpan/Test-Harness/lib/TAP/Object.pm
M cpan/Test-Harness/lib/TAP/Parser.pm
M cpan/Test-Harness/lib/TAP/Parser/Aggregator.pm
M cpan/Test-Harness/lib/TAP/Parser/Grammar.pm
M cpan/Test-Harness/lib/TAP/Parser/Iterator.pm
M cpan/Test-Harness/lib/TAP/Parser/Iterator/Array.pm
M cpan/Test-Harness/lib/TAP/Parser/Iterator/Process.pm
M cpan/Test-Harness/lib/TAP/Parser/Iterator/Stream.pm
M cpan/Test-Harness/lib/TAP/Parser/IteratorFactory.pm
M cpan/Test-Harness/lib/TAP/Parser/Multiplexer.pm
M cpan/Test-Harness/lib/TAP/Parser/Result.pm
M cpan/Test-Harness/lib/TAP/Parser/Result/Bailout.pm
M cpan/Test-Harness/lib/TAP/Parser/Result/Comment.pm
M cpan/Test-Harness/lib/TAP/Parser/Result/Plan.pm
M cpan/Test-Harness/lib/TAP/Parser/Result/Pragma.pm
M cpan/Test-Harness/lib/TAP/Parser/Result/Test.pm
M cpan/Test-Harness/lib/TAP/Parser/Result/Unknown.pm
M cpan/Test-Harness/lib/TAP/Parser/Result/Version.pm
M cpan/Test-Harness/lib/TAP/Parser/Result/YAML.pm
M cpan/Test-Harness/lib/TAP/Parser/ResultFactory.pm
M cpan/Test-Harness/lib/TAP/Parser/Scheduler.pm
M cpan/Test-Harness/lib/TAP/Parser/Scheduler/Job.pm
M cpan/Test-Harness/lib/TAP/Parser/Scheduler/Spinner.pm
M cpan/Test-Harness/lib/TAP/Parser/Source.pm
M cpan/Test-Harness/lib/TAP/Parser/SourceHandler.pm
M cpan/Test-Harness/lib/TAP/Parser/SourceHandler/Executable.pm
M cpan/Test-Harness/lib/TAP/Parser/SourceHandler/File.pm
M cpan/Test-Harness/lib/TAP/Parser/SourceHandler/Handle.pm
M cpan/Test-Harness/lib/TAP/Parser/SourceHandler/Perl.pm
M cpan/Test-Harness/lib/TAP/Parser/SourceHandler/RawTAP.pm
M cpan/Test-Harness/lib/TAP/Parser/YAMLish/Reader.pm
M cpan/Test-Harness/lib/TAP/Parser/YAMLish/Writer.pm
M cpan/Test-Harness/lib/Test/Harness.pm
Log Message:
-----------
TAP::Harness: Move timer initialization
Prior to this commit, the timers for counting elapsed time and CPU usage
were begun when a job's first output appears. This yields inaccurate
results. These results are saved in t/test_state for future runs so
that they can start the longest-running tests first, which leads to
using the available cores more efficiently. (If you start a long running
test after everything else is nearly done, you have to wait for it to
finish before the suite as a whole is; if you start the long ones first,
and the shortest last, you don't have to wait very long for any
stragglers to complete.) Inaccurate results here lead to this
situation, which we were often seeing in the podcheck.t test.
The worst case is if there is heavy computation at the beginning of the
test being run. podcheck, for example, examines all the pods in the
directory structure to find which links to other pods do or do not have
corresponding anchors. Output doesn't happen until the analysis is
complete. On my system, this takes over 30 seconds, but prior to this
commit, what was noted was just the time required to do the output,
about 200 milliseconds. The result was that podcheck was viewed as
being one of the shortest tests run, so was started late in the process,
and generally held up the completion of it.
This commit by itself doesn't improve the test completion very much,
because, test tests are run a whole directory at a time, and the
directory podcheck is in, for example, is run last. The next commit
addresses that.
Commit: f76107759997d6454373de8982b4de816b993c0f
https://github.com/Perl/perl5/commit/f76107759997d6454373de8982b4de816b993c0f
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M t/harness
Log Message:
-----------
XXX env name: t/harness: Add option for faster test suite execution
This commit adds an environment variable, XXX, which if set to non-zero
increases the parallelism in the execution of the test suite, speeding
it up on systems with multiple cores.
Normally, there are two main test sections, one for core and the second
for non-core tests, and the testing of the non-core one doesn't begin
until the first is complete. Within each section, there are a number of
test categories, like 're' for regular expressions, and 'JSON::PP' for
the pure perl implementation of JSON.
Within each category, there are various single .t test files. Some
categories can have those be tested in parallel; some require them to be
done in a particular order, say because an earlier .t does setup for
subsequent ones. We already have this capability.
Completion of all the tests in a category is not needed before those of
another category can be started. This is how it already works.
However, the core section categories are ordered so that they begin in a
logical order for someone trying to get perl to work. First to start
are the basic sanity tests, then by roughly decreasing order of
widespread use in perl programs in the wild, with the final two
categories, porting and perf, being mainly of use to perl5 porters.
These two categories aren't started until all the tests in the earlier
categories are started. We have some long running tests in those two
categories, and generally they delay the start of the entire second section.
If those long running tests could be started sooner, shorter tests in
the first section could be run in parallel with them, increasing the
average CPU utilization, and the second section could begin (and hence
end) earlier, shortening the total elapsed execution time of the entire
suite.
The second section has some very long running tests. JSON-PP is one of
them. If it could run in parallel with tests from the first section,
that would also speed up the completion of the suite.
The environment variable added by this commit does both things. The
basic sanity test categories in the first section continue to be started
before anything else. But then all other tests are run in decreasing
order of elapsed time they take to run, removing the boundaries between
some categories, and between the two sections.
The gain from this increases as the number of jobs run in parallel does;
slower high core platforms have the highest increase. On the old
dromedary with 24 cores, the gain is 20%, almost 2 minutes. On my more
modern box with 12 cores, it is 8%.
Commit: 3fed5a8cf741fb83e0f929187c43048c26f216e3
https://github.com/Perl/perl5/commit/3fed5a8cf741fb83e0f929187c43048c26f216e3
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M regcharclass.h
M regen/regcharclass.pl
Log Message:
-----------
regen/regcharclass.pl: Rmv special case
This avoided checking for optimizations. Whatever its original use, it
doesn't do any good, and the optimizations are actually useful.
Commit: dce8749b1f147a90d7294f16568f34bad867dc63
https://github.com/Perl/perl5/commit/dce8749b1f147a90d7294f16568f34bad867dc63
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M regcharclass.h
M regen/regcharclass.pl
M regen/regcharclass_multi_char_folds.pl
Log Message:
-----------
regcharclass.pl: Get code point folding to a seq
Previously regcharclass.pl could tell if an input string was a
multi-character fold of some Unicode code point. This commit adds the
ability to return what that code point is. This capability will be used
in a later commit.
Commit: fd014442793db7eb0b4c4fc8e6ca17fc70bd0a67
https://github.com/Perl/perl5/commit/fd014442793db7eb0b4c4fc8e6ca17fc70bd0a67
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c: Trim trailing blanks
Commit: 49852d44ccf5a3b59a2129360421d127dc251081
https://github.com/Perl/perl5/commit/49852d44ccf5a3b59a2129360421d127dc251081
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c: Change name of static function
The new name reflects its new functionality coming in future commits
Commit: 713c909299690c065e477896e5bee27b980d5ac5
https://github.com/Perl/perl5/commit/713c909299690c065e477896e5bee27b980d5ac5
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M t/re/fold_grind.pl
Log Message:
-----------
re/fold_grind.pl: Test a couple more code points
These add tests for checking that the revised folding in a future commit
works in some edge cases that previously weren't an issue.
Commit: 431a3b453528840d3425c656d05bd2d6b4e99e17
https://github.com/Perl/perl5/commit/431a3b453528840d3425c656d05bd2d6b4e99e17
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M handy.h
Log Message:
-----------
Make API some C99 typedef work-arounds
I added these some releases ago, but kept them private. No untoward
things have happened, so I'm now making them API.
Commit: 302c1df9a6b41eef89612b641ab892c5a127d861
https://github.com/Perl/perl5/commit/302c1df9a6b41eef89612b641ab892c5a127d861
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M regexec.c
M regexp.h
Log Message:
-----------
regexec.c: Revamp looping end conditions
Consider the pattern /A*B/ where A and B are arbitrary. The pattern
matching code tries to make a tight loop to match the span of A's. The
logic of this was not really updated when UTF-8 was added. A function
was called that essentially punted when UTF-8 was involved. I did
revamp the function some releases ago to fix some bugs and to at least
consider UTF-8 to some extent.
This commit revamps the whole mechanism so that now UTF-8 is a first
class citizen, and improves the loop exit criteria for non-UTF-8 as
well. The old code returned FALSE if there was no possiblility of
anything matching (such as the match requiring UTF-8 to represent and
the target isn't UTF-8 encoded). If there was a match possibility it
returned TRUE and 1 or 2 code points that could be the first things
in B if A is something like '.*'. Or in the case of A being a single
repeating character, those 1 or 2 code points could be what 'A' matched
under /i, the thing(s) being spanned. For other situations it gave up
and returned 0 code points. In this case, the caller had to check for
every eventuality, and in the case of /i had to re-fold each backtrack.
Like the old one, the new function introduced here returns FALSE if
there is no possibility of a match succeeding, but unlike the old one it
never gives up. If the return is TRUE, It also always returns:
1) A string and a mask to quickly rule out non-matches
2) A count of initial bytes that are exact matches, and a count of
initial definitive matches
3) The first character of all possible matches
The caller does a bitwise 'and' of the target string with the returned
mask. If that doesn't match the returned string, then the caller can
immediately rule out this match. If the mask is all one bits, then
there are no false positives. This will always be the case if the
function is called on an exact match, one without /i. Likewise, if just
a single 0 bit is in the mask, there are just two possible matches, and
the match is definitive for these, with no false positives. The more 0
bits in the mask, the more false positives there are, but it still
quickly rules out the remaining ones. This is graceful degradation,
unlike the mechanism it replaces.
When the counts of initial exact and definitive match bytes are non-zero
(a likely scenario), the caller can use this to cut down the number of
brute force tests it must do.
Finally, having the exact strings of what can possibly match means no
need to refold when backtracking.
Here are some examples. In an EXACT node, the mask returned will be all
one bits, and the returned string will be the first character of the
node. The caller will AND the mask with the target string and see if it
matches the returned string. This is not very different from before,
except that the caller doesn't have to check each time if 0, 1, or 2
characters were returned from the function, and then behave accordingly.
Only if the match succeeds, does it need to check if this was a
definitive match or not.
More complex is
qr/.*\N{U+100}/i
Only U+100 and U+101 match. The old way knew this and returned those
code points and the two UTF-8 strings that represent them: \xC4\x80 and
\xC4\x81. There were a bunch of conditionals in the old way to
determine to use the UTF-8 strings, and to compare each one separately.
The mask and string returned in the new way uses a single compare and
mask, dispensing with the code point returns completely.
The old way was optimized for ASCII characters, and the new way doesn't
improve that for the ones whose only matches are their upper and lowercase
versions. But for those with matches outside of ASCII, the old one gave
up and the caller had to resort to brute force matching each time,
whereas the new one always returns something that can quickly rule out
many possibilities. An example is
qr/.*\N{LATIN SMALL LETTER K}/i
'K', 'k', and the KELVIN SIGN all match. Here is a detailed analysis of
this case to show the complexities involved.
This pattern is too complicated for the code prior to this commit to
deal with. The new code returns the mask 0x56, and a string 0x42.
There are 4 zero bits in this mask. That means that the code can
immediately reject all but 16 of the possible bytes that could follow
it. The ones it accepts are:
0x82 83 8A 8B
A2 A3 AA AB
C2 C3 CA CB
E2 E3 EA EB
If the target string isn't UTF-8 encoded, this excludes 240 of 256
bytes, all non-ASCII and 4 of which are extremely rare control
characters, a false positive rate of 94% or 97%, depending on if you
count those controls. If you're dealing with just ASCII inputs, it's a
0% false positive rate.
If the target string is UTF-8 encoded, the first 8 bytes in the list
above are illegal start bytes. The 4 Cx bytes are the beginning of
2-byte representations, each of which has 64 possible continuation
bytes, so any of 256 characters could match, out of the possible 1792
legal 2-UTF-8-byte characters, a 14% false positive rate
The 4 Ex bytes are the beginning of 3-byte representations, each of
which has 64-squared possible continuation bytes, so any of 16384
characters could match, out the possible 63488 legal 3-UTF-8-byte
characters, a 26% false positive rate.
All 4-byte, 5-byte, etc., representations are excluded, so the total
false positive rate approaches 0% if we include all possible UTF-8
sequences. If we confine the input domain to just the million legal
Unicode code points, the false positive rate is 1%, but, except for
emoji, most characters in any sort of common use are represented by 3 or
fewer bytes, and the false positive rate is about 25%, but only the
characters common to multiple scripts or Latin ones in that domain
are likely to occur in text with 'k' and 'K'. There are 4758 of these
in the current version of the Unicode standard, of which this could
potentially match 3500, or 76%, if all were equally likely to occur
immediately after one of these 'K'-characters. One could do further
restrictions, such as using only modern, non-technical characters to get
wildly differing false positive rates.
But whatever the false positive rate, it is better than the brute force
method required prior to this commit.
Finally, perhaps the worst case fold in Unicode is that of
\N{GREEK SMALL LETTER IOTA WITH DIALYTIKA AND OXIA}. There are 6
characters that match this under /i. As a result, the mask and returned
string have lots of false positives. But they still rule out all
characters that aren't represented by 2 or 3 bytes, and any 2 byte
characters that begin with D0-DF.
Commit: 7e10ee52346f802b2b233cc55bc83483f20497a2
https://github.com/Perl/perl5/commit/7e10ee52346f802b2b233cc55bc83483f20497a2
Author: Karl Williamson <[email protected]>
Date: 2020-11-14 (Sat, 14 Nov 2020)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c: White-space, comments only
Mostly indent because the prior commit created a new block
Compare: https://github.com/Perl/perl5/compare/0ee435a6a41e...7e10ee52346f
