New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
reduce number of calls to add_cp_to_invlist. #15210
Comments
From @tonycozThis is related to 127392. Since seeing: | ->79.98% (659,203B) 0x4F7407: S_invlist_trim (regcomp.c:7784) from that ticket, it's struck me that the loops involved was inefficient in that _add_range_to_invlist() is called for every code point, rather than looking for ranges, which I expect to be fairly common in the built-in character classes like \w. The attached patch attempts to reduce the number of calls to add_cp_to_invlist() where it's simple to do so. Tony |
From @tonycoz0001-reduce-number-of-calls-to-add_cp_to_invlist.patchFrom 79cb62ac4a1f17481215013731ee46d683c4680e Mon Sep 17 00:00:00 2001
From: Tony Cook <tony@develop-help.com>
Date: Wed, 2 Mar 2016 16:19:43 +1100
Subject: reduce number of calls to add_cp_to_invlist()
Both S_get_ANYOF_cp_list_for_ssc() and S_put_charclass_bitmap_innards()
have tight loops that iterate over a bitmap and calls add_cp_to_invlist()
for each bit set.
add_cp_to_invlist() is a fairly wrapper around _add_range_to_invlist()
which create a new invlist to hold the range and then calls
_invlist_union() to perform the add. This is moderately expensive.
Instead of indirectly calling _add_range_to_invlist(), where it's
simple to do so, instead look for ranges of bits set in the bitmaps
and call _add_range_to_invlist() directly.
This changed the cachegrind output from running:
./perl -e 'qr/_?[\W_]/;'
from:
==23406== I refs: 1,752,149
==23406== I1 misses: 5,405
==23406== LLi misses: 3,588
==23406== I1 miss rate: 0.30%
==23406== LLi miss rate: 0.20%
==23406==
==23406== D refs: 683,242 (414,061 rd + 269,181 wr)
==23406== D1 misses: 13,370 ( 7,646 rd + 5,724 wr)
==23406== LLd misses: 7,025 ( 3,417 rd + 3,608 wr)
==23406== D1 miss rate: 1.9% ( 1.8% + 2.1% )
==23406== LLd miss rate: 1.0% ( 0.8% + 1.3% )
==23406==
==23406== LL refs: 18,775 ( 13,051 rd + 5,724 wr)
==23406== LL misses: 10,613 ( 7,005 rd + 3,608 wr)
==23406== LL miss rate: 0.4% ( 0.3% + 1.3% )
to:
==25041== I refs: 1,189,412
==25041== I1 misses: 5,218
==25041== LLi misses: 3,598
==25041== I1 miss rate: 0.43%
==25041== LLi miss rate: 0.30%
==25041==
==25041== D refs: 440,339 (283,047 rd + 157,292 wr)
==25041== D1 misses: 11,872 ( 7,257 rd + 4,615 wr)
==25041== LLd misses: 7,024 ( 3,417 rd + 3,607 wr)
==25041== D1 miss rate: 2.6% ( 2.5% + 2.9% )
==25041== LLd miss rate: 1.5% ( 1.2% + 2.2% )
==25041==
==25041== LL refs: 17,090 ( 12,475 rd + 4,615 wr)
==25041== LL misses: 10,622 ( 7,015 rd + 3,607 wr)
==25041== LL miss rate: 0.6% ( 0.4% + 2.2% )
ie. from 1.75 million instructions to 1.19 million instructions.
---
regcomp.c | 13 +++++++++++--
1 file changed, 11 insertions(+), 2 deletions(-)
diff --git a/regcomp.c b/regcomp.c
index d66a4c7..1307829 100644
--- a/regcomp.c
+++ b/regcomp.c
@@ -1423,7 +1423,12 @@ S_get_ANYOF_cp_list_for_ssc(pTHX_ const RExC_state_t *pRExC_state,
/* Add in the points from the bit map */
for (i = 0; i < NUM_ANYOF_CODE_POINTS; i++) {
if (ANYOF_BITMAP_TEST(node, i)) {
- invlist = add_cp_to_invlist(invlist, i);
+ unsigned int start = i++;
+
+ for (; i < NUM_ANYOF_CODE_POINTS && ANYOF_BITMAP_TEST(node, i); ++i) {
+ /* empty */
+ }
+ invlist = _add_range_to_invlist(invlist, start, i-1);
new_node_has_latin1 = TRUE;
}
}
@@ -19957,7 +19962,11 @@ S_put_charclass_bitmap_innards(pTHX_ SV *sv,
/* Accumulate the bit map into the unconditional match list */
for (i = 0; i < NUM_ANYOF_CODE_POINTS; i++) {
if (BITMAP_TEST(bitmap, i)) {
- invlist = add_cp_to_invlist(invlist, i);
+ int start = i++;
+ for (; i < NUM_ANYOF_CODE_POINTS && BITMAP_TEST(bitmap, i); i++) {
+ /* empty */
+ }
+ invlist = _add_range_to_invlist(invlist, start, i-1);
}
}
--
2.1.4
|
@khwilliamson - Status changed from 'new' to 'open' |
From @khwilliamsonThanks, applied as 6f8848d |
@khwilliamson - Status changed from 'open' to 'pending release' |
From @khwilliamsonThank you for submitting this report. You have helped make Perl better. Perl 5.24.0 may be downloaded via https://metacpan.org/release/RJBS/perl-5.24.0 |
@khwilliamson - Status changed from 'pending release' to 'resolved' |
Migrated from rt.perl.org#127641 (status was 'resolved')
Searchable as RT127641$
The text was updated successfully, but these errors were encountered: