This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Add ANYOFM regnode
authorKarl Williamson <khw@cpan.org>
Tue, 30 Jan 2018 03:47:56 +0000 (20:47 -0700)
committerKarl Williamson <khw@cpan.org>
Tue, 30 Jan 2018 18:39:16 +0000 (11:39 -0700)
This is a specialized ANYOF node for use when the code points in it
have characteristics that allow them to be matched with a mask instead
of a bit map.  When this happens, the speed up is pretty spectacular:

Key:
    Ir   Instruction read
    Dr   Data read
    Dw   Data write
    COND conditional branches
    IND  indirect branches

The numbers represent raw counts per loop iteration.

Results of ('b' x 10000) . 'a' =~ /[Aa]/

          blead    mask Ratio %
       -------- ------- -------
    Ir 153132.0 25636.0   597.3
    Dr  40909.0  2155.0  1898.3
    Dw  20593.0   593.0  3472.7
  COND  20529.0  3028.0   678.0
   IND     22.0    22.0   100.0

See the comments in regcomp.c or
http://nntp.perl.org/group/perl.perl5.porters/249001 for a description
of the cases that this new technique can handle.  But several common
ones include the C0 controls (on ASCII platforms), [01], [0-7], [Aa] and
any other ASCII case pair.

The set of ASCII characters also could be done with this node instead of
having the special ASCII regnode, reducing code size and complexity.
I haven't investigated the speed loss of doing so.

A NANYOFM node could be created for matching the complements this one
matches.

A pattern like /A/i is not affected by this commit, but the regex
optimizer could be changed to take advantage of this commit.  What would
need to be done is for it to look at the first byte of an EXACTFish node
and if its one of the case pairs this handles, to generate a synthetic
start class for it.  This would automatically invoke the sped up code.

embed.fnc
embed.h
proto.h
regcomp.c
regexec.c
t/re/anyof.t

index fa68d95..02546ff 100644 (file)
--- a/embed.fnc
+++ b/embed.fnc
@@ -2457,6 +2457,7 @@ Es        |SSize_t|study_chunk    |NN RExC_state_t *pRExC_state \
                                 |I32 stopparen|U32 recursed_depth \
                                |NULLOK regnode_ssc *and_withp \
                                |U32 flags|U32 depth
+EsR    |SV *   |get_ANYOFM_contents|NN const regnode * n
 EsRn   |U32    |add_data       |NN RExC_state_t* const pRExC_state \
                                |NN const char* const s|const U32 n
 rs     |void   |re_croak2      |bool utf8|NN const char* pat1|NN const char* pat2|...
@@ -2532,6 +2533,9 @@ ERp       |bool   |_is_grapheme   |NN const U8 * strbeg|NN const U8 * s|NN const U8 *stren
 ERs    |bool   |isFOO_utf8_lc  |const U8 classnum|NN const U8* character
 ERns   |char *|find_next_ascii|NN char* s|NN const char * send|const bool is_utf8
 ERns   |char *|find_next_non_ascii|NN char* s|NN const char * send|const bool is_utf8
+ERns   |char * |find_next_masked|NN char * s                           \
+                                |NN const char * send                  \
+                                |const U8 byte|const U8 mask
 ERns   |char *|find_span_end   |NN char* s|NN const char * send|const char span_byte
 ERns   |U8 *|find_span_end_mask|NN U8 * s|NN const U8 * send   \
                                |const U8 span_byte|const U8 mask
diff --git a/embed.h b/embed.h
index 6208033..d53dff9 100644 (file)
--- a/embed.h
+++ b/embed.h
 #define compute_EXACTish       S_compute_EXACTish
 #define construct_ahocorasick_from_trie(a,b,c) S_construct_ahocorasick_from_trie(aTHX_ a,b,c)
 #define edit_distance          S_edit_distance
+#define get_ANYOFM_contents(a) S_get_ANYOFM_contents(aTHX_ a)
 #define get_ANYOF_cp_list_for_ssc(a,b) S_get_ANYOF_cp_list_for_ssc(aTHX_ a,b)
 #define get_invlist_iter_addr  S_get_invlist_iter_addr
 #define grok_bslash_N(a,b,c,d,e,f,g)   S_grok_bslash_N(aTHX_ a,b,c,d,e,f,g)
 #define backup_one_WB(a,b,c,d) S_backup_one_WB(aTHX_ a,b,c,d)
 #define find_byclass(a,b,c,d,e)        S_find_byclass(aTHX_ a,b,c,d,e)
 #define find_next_ascii                S_find_next_ascii
+#define find_next_masked       S_find_next_masked
 #define find_next_non_ascii    S_find_next_non_ascii
 #define find_span_end          S_find_span_end
 #define find_span_end_mask     S_find_span_end_mask
diff --git a/proto.h b/proto.h
index a72c0fb..0755630 100644 (file)
--- a/proto.h
+++ b/proto.h
@@ -5179,6 +5179,11 @@ STATIC int       S_edit_distance(const UV *src, const UV *tgt, const STRLEN x, const S
 #define PERL_ARGS_ASSERT_EDIT_DISTANCE \
        assert(src); assert(tgt)
 
+STATIC SV *    S_get_ANYOFM_contents(pTHX_ const regnode * n)
+                       __attribute__warn_unused_result__;
+#define PERL_ARGS_ASSERT_GET_ANYOFM_CONTENTS   \
+       assert(n)
+
 STATIC SV*     S_get_ANYOF_cp_list_for_ssc(pTHX_ const RExC_state_t *pRExC_state, const regnode_charclass* const node);
 #define PERL_ARGS_ASSERT_GET_ANYOF_CP_LIST_FOR_SSC     \
        assert(pRExC_state); assert(node)
@@ -5572,6 +5577,11 @@ STATIC char *    S_find_next_ascii(char* s, const char * send, const bool is_utf8)
 #define PERL_ARGS_ASSERT_FIND_NEXT_ASCII       \
        assert(s); assert(send)
 
+STATIC char *  S_find_next_masked(char * s, const char * send, const U8 byte, const U8 mask)
+                       __attribute__warn_unused_result__;
+#define PERL_ARGS_ASSERT_FIND_NEXT_MASKED      \
+       assert(s); assert(send)
+
 STATIC char *  S_find_next_non_ascii(char* s, const char * send, const bool is_utf8)
                        __attribute__warn_unused_result__;
 #define PERL_ARGS_ASSERT_FIND_NEXT_NON_ASCII   \
index 1efaaa5..1cd5329 100644 (file)
--- a/regcomp.c
+++ b/regcomp.c
@@ -5516,6 +5516,27 @@ Perl_re_printf( aTHX_  "LHS=%" UVuf " RHS=%" UVuf "\n",
                                                           (regnode_charclass *) scan);
                    break;
 
+                case ANYOFM:
+                  {
+                    SV* cp_list = get_ANYOFM_contents(scan);
+
+                    if (flags & SCF_DO_STCLASS_OR) {
+                        ssc_union(data->start_class,
+                                  cp_list,
+                                  FALSE /* don't invert */
+                                  );
+                    }
+                    else if (flags & SCF_DO_STCLASS_AND) {
+                        ssc_intersection(data->start_class,
+                                         cp_list,
+                                         FALSE /* don't invert */
+                                         );
+                    }
+
+                    SvREFCNT_dec_NN(cp_list);
+                    break;
+                  }
+
                case NPOSIXL:
                     invert = 1;
                     /* FALLTHROUGH */
@@ -17999,25 +18020,20 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state, I32 *flagp, U32 depth,
      * certain common classes that are easy to test.  Getting to this point in
      * the code means that the class didn't get optimized there.  Since this
      * code is only executed in Pass 2, it is too late to save space--it has
-     * been allocated in Pass 1, and currently isn't given back.  But turning
-     * things into an EXACTish node can allow the optimizer to join it to any
-     * adjacent such nodes.  And if the class is equivalent to things like /./,
-     * expensive run-time swashes can be avoided.  Now that we have more
-     * complete information, we can find things necessarily missed by the
-     * earlier code.  Another possible "optimization" that isn't done is that
-     * something like [Ee] could be changed into an EXACTFU.  khw tried this
-     * and found that the ANYOF is faster, including for code points not in the
-     * bitmap.  This still might make sense to do, provided it got joined with
-     * an adjacent node(s) to create a longer EXACTFU one.  This could be
-     * accomplished by creating a pseudo ANYOF_EXACTFU node type that the join
-     * routine would know is joinable.  If that didn't happen, the node type
-     * could then be made a straight ANYOF */
+     * been allocated in Pass 1, and currently isn't given back.  XXX Why not?
+     * But turning things into an EXACTish node can allow the optimizer to join
+     * it to any adjacent such nodes.  And if the class is equivalent to things
+     * like /./, expensive run-time swashes can be avoided.  Now that we have
+     * more complete information, we can find things necessarily missed by the
+     * earlier code. */
 
     if (optimizable && cp_list && ! invert) {
         UV start, end;
         U8 op = END;  /* The optimzation node-type */
         int posix_class = -1;   /* Illegal value */
         const char * cur_parse= RExC_parse;
+        U8 ANYOFM_mask;
+        U32 anode_arg = 0;
 
         invlist_iterinit(cp_list);
         if (! invlist_iternext(cp_list, &start, &end)) {
@@ -18156,6 +18172,106 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state, I32 *flagp, U32 depth,
                 }
               found_posix: ;
             }
+
+            /* If it didn't match a POSIX class, it might be able to be turned
+             * into an ANYOFM node.  Compare two different bytes, bit-by-bit.
+             * In some positions, the bits in each will be 1; and in other
+             * positions both will be 0; and in some positions the bit will be
+             * 1 in one byte, and 0 in the other.  Let 'n' be the number of
+             * positions where the bits differ.  We create a mask which has
+             * exactly 'n' 0 bits, each in a position where the two bytes
+             * differ.  Now take the set of all bytes that when ANDed with the
+             * mask yield the same result.  That set has 2**n elements, and is
+             * representable by just two 8 bit numbers: the result and the
+             * mask.  Importantly, matching the set can be vectorized by
+             * creating a word full of the result bytes, and a word full of the
+             * mask bytes, yielding a significant speed up.  Here, see if this
+             * node matches such a set.  As a concrete example consider [01],
+             * and the byte representing '0' which is 0x30 on ASCII machines.
+             * It has the bits 0011 0000.  Take the mask 1111 1110.  If we AND
+             * 0x31 and 0x30 with that mask we get 0x30.  Any other bytes ANDed
+             * yield something else.  So [01], which is a common usage, is
+             * optimizable into ANYOFM, and can benefit from the speed up.  We
+             * can only do this on UTF-8 invariant bytes, because the variance
+             * would throw this off.  */
+            if (   op == END
+                && invlist_highest(cp_list) <=
+#ifdef EBCDIC
+                                               0xFF
+#else
+                                               0x7F
+#endif
+            ) {
+                Size_t cp_count = 0;
+                bool first_time = TRUE;
+                unsigned int lowest_cp;
+                U8 bits_differing = 0;
+
+                /* Only needed on EBCDIC, as there, variants and non- are mixed
+                 * together.  Could #ifdef it out on ASCII, but probably the
+                 * compiler will optimize it out */
+                bool has_variant = FALSE;
+
+                /* Go through the bytes and find the bit positions that differ */
+                invlist_iterinit(cp_list);
+                while (invlist_iternext(cp_list, &start, &end)) {
+                    unsigned int i = start;
+
+                    cp_count += end - start + 1;
+
+                    if (first_time) {
+                        if (! UVCHR_IS_INVARIANT(i)) {
+                            has_variant = TRUE;
+                            continue;
+                        }
+
+                        first_time = FALSE;
+                        lowest_cp = start;
+
+                        i++;
+                    }
+
+                    /* Find the bit positions that differ from the lowest code
+                     * point in the node.  Keep track of all such positions by
+                     * OR'ing */
+                    for (; i <= end; i++) {
+                        if (! UVCHR_IS_INVARIANT(i)) {
+                            has_variant = TRUE;
+                            continue;
+                        }
+
+                        bits_differing  |= i ^ lowest_cp;
+                    }
+                }
+                invlist_iterfinish(cp_list);
+
+                /* At the end of the loop, we count how many bits differ from
+                 * the bits in lowest code point, call the count 'd'.  If the
+                 * set we found contains 2**d elements, it is the closure of
+                 * all code points that differ only in those bit positions.  To
+                 * convince yourself of that, first note that the number in the
+                 * closure must be a power of 2, which we test for.  The only
+                 * way we could have that count and it be some differing set,
+                 * is if we got some code points that don't differ from the
+                 * lowest code point in any position, but do differ from each
+                 * other in some other position.  That means one code point has
+                 * a 1 in that position, and another has a 0.  But that would
+                 * mean that one of them differs from the lowest code point in
+                 * that position, which possibility we've already excluded. */
+                if ( ! has_variant
+                    && cp_count == 1U << PL_bitcount[bits_differing])
+                {
+                    assert(cp_count > 1);
+                    op = ANYOFM;
+
+                    /* We need to make the bits that differ be 0's */
+                    ANYOFM_mask = ~ bits_differing; /* This goes into FLAGS */
+
+                    /* The argument is the lowest code point */
+                    anode_arg = lowest_cp;
+                    *flagp |= HASWIDTH|SIMPLE;
+                }
+            }
         }
 
         if (op != END) {
@@ -18163,7 +18279,7 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state, I32 *flagp, U32 depth,
             RExC_emit = (regnode *)orig_emit;
 
             if (regarglen[op]) {
-                ret = reganode(pRExC_state, op, 0);
+                ret = reganode(pRExC_state, op, anode_arg);
             } else {
                 ret = reg_node(pRExC_state, op);
             }
@@ -18178,6 +18294,9 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state, I32 *flagp, U32 depth,
             else if (PL_regkind[op] == POSIXD || PL_regkind[op] == NPOSIXD) {
                 FLAGS(ret) = posix_class;
             }
+            else if (PL_regkind[op] == ANYOFM) {
+                FLAGS(ret) = ANYOFM_mask;
+            }
 
             SvREFCNT_dec_NN(cp_list);
             return ret;
@@ -19030,6 +19149,36 @@ S_regtail_study(pTHX_ RExC_state_t *pRExC_state, regnode *p,
 }
 #endif
 
+STATIC SV*
+S_get_ANYOFM_contents(pTHX_ const regnode * n) {
+
+    /* Returns an inversion list of all the code points matched by the ANYOFM
+     * node 'n' */
+
+    SV * cp_list = _new_invlist(-1);
+    const U8 lowest = ARG(n);
+    unsigned int i;
+    U8 count = 0;
+    U8 needed = 1U << PL_bitcount[ (U8) ~ FLAGS(n)];
+
+    PERL_ARGS_ASSERT_GET_ANYOFM_CONTENTS;
+
+    /* Starting with the lowest code point, any code point that ANDed with the
+     * mask yields the lowest code point is in the set */
+    for (i = lowest; i <= 0xFF; i++) {
+        if ((i & FLAGS(n)) == ARG(n)) {
+            cp_list = add_cp_to_invlist(cp_list, i);
+            count++;
+
+            /* We know how many code points (a power of two) that are in the
+             * set.  No use looking once we've got that number */
+            if (count >= needed) break;
+        }
+    }
+
+    return cp_list;
+}
+
 /*
  - regdump - dump a regexp onto Perl_debug_log in vaguely comprehensible form
  */
@@ -19556,6 +19705,15 @@ Perl_regprop(pTHX_ const regexp *prog, SV *sv, const regnode *o, const regmatch_
 
         SvREFCNT_dec(unresolved);
     }
+    else if (k == ANYOFM) {
+        SV * cp_list = get_ANYOFM_contents(o);
+
+       Perl_sv_catpvf(aTHX_ sv, "[%s", PL_colors[0]);
+        put_charclass_bitmap_innards(sv, NULL, cp_list, NULL, NULL, TRUE);
+       Perl_sv_catpvf(aTHX_ sv, "%s]", PL_colors[1]);
+
+        SvREFCNT_dec(cp_list);
+    }
     else if (k == POSIXD || k == NPOSIXD) {
         U8 index = FLAGS(o) * 2;
         if (index < C_ARRAY_LENGTH(anyofs)) {
index 2fcfd2e..31a133f 100644 (file)
--- a/regexec.c
+++ b/regexec.c
@@ -741,6 +741,78 @@ S_find_span_end(char * s, const char * send, const char span_byte)
     return s;
 }
 
+STATIC char *
+S_find_next_masked(char * s, const char * send, const U8 byte, const U8 mask)
+{
+    /* Returns the position of the first byte in the sequence between 's'
+     * and 'send-1' inclusive that when ANDed with 'mask' yields 'byte';
+     * returns 'send' if none found.  It uses word-level operations instead of
+     * byte to speed up the process */
+
+    PERL_ARGS_ASSERT_FIND_NEXT_MASKED;
+
+    assert(send >= s);
+    assert((byte & mask) == byte);
+
+    if ((STRLEN) (send - s) >= PERL_WORDSIZE
+                          + PERL_WORDSIZE * PERL_IS_SUBWORD_ADDR(s)
+                          - (PTR2nat(s) & PERL_WORD_BOUNDARY_MASK))
+    {
+        PERL_UINTMAX_T word_complemented, mask_word;
+
+        while (PTR2nat(s) & PERL_WORD_BOUNDARY_MASK) {
+            if (((* (U8 *) s) & mask) == byte) {
+                return s;
+            }
+            s++;
+        }
+
+        word_complemented = ~ (PERL_COUNT_MULTIPLIER * byte);
+        mask_word =            PERL_COUNT_MULTIPLIER * mask;
+
+        do {
+            PERL_UINTMAX_T masked = (* (PERL_UINTMAX_T *) s) & mask_word;
+
+            /* If 'masked' contains 'byte' within it, anding with the
+             * complement will leave those 8 bits 0 */
+            masked &= word_complemented;
+
+            /* This causes the most significant bit to be set to 1 for any
+             * bytes in the word that aren't completely 0 */
+            masked |= masked << 1;
+            masked |= masked << 2;
+            masked |= masked << 4;
+
+            /* The msbits are the same as what marks a byte as variant, so we
+             * can use this mask.  If all msbits are 1, the word doesn't
+             * contain 'byte' */
+            if ((masked & PERL_VARIANTS_WORD_MASK) == PERL_VARIANTS_WORD_MASK) {
+                s += PERL_WORDSIZE;
+                continue;
+            }
+
+            /* Here, the msbit of bytes in the word that aren't 'byte' are 1,
+             * and any that are, are 0.  Complement and re-AND to swap that */
+            masked = ~ masked;
+            masked &= PERL_VARIANTS_WORD_MASK;
+
+            /* This reduces the problem to that solved by this function */
+            s += _variant_byte_number(masked);
+            return s;
+
+        } while (s + PERL_WORDSIZE <= send);
+    }
+
+    while (s < send) {
+        if (((* (U8 *) s) & mask) == byte) {
+            return s;
+        }
+        s++;
+    }
+
+    return s;
+}
+
 STATIC U8 *
 S_find_span_end_mask(U8 * s, const U8 * send, const U8 span_byte, const U8 mask)
 {
@@ -2184,6 +2256,12 @@ S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s,
         }
         break;
 
+    case ANYOFM:    /* ARG() is the base byte; FLAGS() the mask byte */
+        /* UTF-8ness doesn't matter, so use 0 */
+        REXEC_FBC_FIND_NEXT_SCAN(0,
+                                 find_next_masked(s, strend, ARG(c), FLAGS(c)));
+        break;
+
     case EXACTFA_NO_TRIE:   /* This node only generated for non-utf8 patterns */
         assert(! is_utf8_pat);
        /* FALLTHROUGH */
@@ -6659,6 +6737,13 @@ S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
            }
            break;
 
+        case ANYOFM:
+            if (NEXTCHR_IS_EOS || (UCHARAT(locinput) & FLAGS(scan)) != ARG(scan)) {
+                sayNO;
+            }
+            locinput++;
+            break;
+
         case ASCII:
             if (NEXTCHR_IS_EOS || ! isASCII(UCHARAT(locinput))) {
                 sayNO;
@@ -9338,7 +9423,7 @@ S_regrepeat(pTHX_ regexp *prog, char **startposp, const regnode *p,
        }
        break;
 
-    case ASCII:
+    case ANYOFM:
         if (utf8_target && loceol - scan > max) {
 
             /* We didn't adjust <loceol> at the beginning of this routine
@@ -9347,6 +9432,14 @@ S_regrepeat(pTHX_ regexp *prog, char **startposp, const regnode *p,
             loceol = scan + max;
         }
 
+        scan = (char *) find_span_end_mask((U8 *) scan, (U8 *) loceol, (U8) ARG(p), FLAGS(p));
+        break;
+
+    case ASCII:
+        if (utf8_target && loceol - scan > max) {
+            loceol = scan + max;
+        }
+
         scan = find_next_non_ascii(scan, loceol, utf8_target);
        break;
 
index d24e4a7..12fb9b3 100644 (file)
@@ -31,7 +31,7 @@ BEGIN {
 # skipped and not skipped.
 
 my @tests = (
-    '[[{]' => 'ANYOF[\[\{]',
+    '[[{]' => 'ANYOFM[\[\{]',
     '[^\S ]' => 'ANYOFD[\t\n\x0B\f\r{utf8}\x85\xA0][1680 2000-200A 2028-2029 202F 205F 3000]',
     '[^\n\r]' => 'ANYOF[^\n\r][0100-INFINITY]',
     '[^\/\|,\$\%%\@\ \%"\<\>\:\#\&\*\{\}\[\]\(\)]' => 'ANYOF[^ "#$%&()*,/:<>@\[\]\{|\}][0100-INFINITY]',