Skip to content
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

Closed
p5pRT opened this issue Mar 2, 2016 · 7 comments
Closed

reduce number of calls to add_cp_to_invlist. #15210

p5pRT opened this issue Mar 2, 2016 · 7 comments

Comments

@p5pRT
Copy link

p5pRT commented Mar 2, 2016

Migrated from rt.perl.org#127641 (status was 'resolved')

Searchable as RT127641$

@p5pRT
Copy link
Author

p5pRT commented Mar 2, 2016

From @tonycoz

This is related to 127392.

Since seeing​:

| ->79.98% (659,203B) 0x4F7407​: S_invlist_trim (regcomp.c​:7784)
| | ->78.89% (650,281B) 0x4F80D1​: Perl__invlist_union_maybe_complement_2nd (regc
omp.c​:8271)
| | | ->77.80% (641,288B) 0x4F8B12​: Perl__add_range_to_invlist (regcomp.c​:8581)
| | | | ->77.80% (641,288B) 0x4F8BF4​: S_add_cp_to_invlist (regcomp.c​:8621)
| | | | | ->77.80% (641,288B) 0x4D4807​: S_get_ANYOF_cp_list_for_ssc (regcomp.c​:1
047)

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

@p5pRT
Copy link
Author

p5pRT commented Mar 2, 2016

From @tonycoz

0001-reduce-number-of-calls-to-add_cp_to_invlist.patch
From 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

@p5pRT
Copy link
Author

p5pRT commented Mar 2, 2016

@khwilliamson - Status changed from 'new' to 'open'

@p5pRT
Copy link
Author

p5pRT commented Mar 2, 2016

From @khwilliamson

Thanks, applied as 6f8848d
--
Karl Williamson

@p5pRT
Copy link
Author

p5pRT commented Mar 2, 2016

@khwilliamson - Status changed from 'open' to 'pending release'

@p5pRT
Copy link
Author

p5pRT commented May 13, 2016

From @khwilliamson

Thank you for submitting this report. You have helped make Perl better.
 
With the release of Perl 5.24.0 on May 9, 2016, this and 149 other issues have been resolved.

Perl 5.24.0 may be downloaded via https://metacpan.org/release/RJBS/perl-5.24.0

@p5pRT p5pRT closed this as completed May 13, 2016
@p5pRT
Copy link
Author

p5pRT commented May 13, 2016

@khwilliamson - Status changed from 'pending release' to 'resolved'

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant