[Optimization] Faster string reversal with bitshift (and bswap/rev/movbe)?

[richardleach]

Description
In a nutshell, pp_reverse reverses strings using a loop that in each iteration swaps a byte from the front of the char buffer with a byte from the back.

            while (down > up) {
                const char tmp = *up;
                *up++ = *down;
                *down-- = tmp;
            }

That seems like a common and portable string reversal technique. However, Fast array reversal with SIMD! is a lovely little explainer that shows how string reversal can be done much more quickly by reversing and swapping whole registers full of bytes at a time. Maximum speedup (see the SSSE3, AVX, AVX2 sections) might involve using intrinsics for which CPU support is far from guaranteed. (I imagine that the implementation complexity and maintenance overhead would therefore be too great at this time.)

However, it looks like it should be possible to use a generic and portable bit-shifting implementation (see the bswap section), which should be faster than pp_reverse's current method AND decent compilers can recognize this implementation and replace it with faster CPU instructions (bswap, rev, movbe) where possible.

The C++ code from that post:

inline std::uint64_t Swap64(std::uint64_t x)
{
    return (
        ((x & 0x00000000000000FF) << 56) |
        ((x & 0x000000000000FF00) << 40) |
        ((x & 0x0000000000FF0000) << 24) |
        ((x & 0x00000000FF000000) <<  8) |
        ((x & 0x000000FF00000000) >>  8) |
        ((x & 0x0000FF0000000000) >> 24) |
        ((x & 0x00FF000000000000) >> 40) |
        ((x & 0xFF00000000000000) >> 56)
    );
}

inline std::uint32_t Swap32(std::uint32_t x)
{
    return(
        ((x & 0x000000FF) << 24) |
        ((x & 0x0000FF00) <<  8) |
        ((x & 0x00FF0000) >>  8) |
        ((x & 0xFF000000) >> 24)
    );
}

inline std::uint16_t Swap16(std::uint16_t x)
{
    // This tends to emit a 16-bit `rol` or `ror` instruction
    return (
        ((x & 0x00FF) <<  8) |
        ((x & 0xFF00) >>  8)
    );
}

Note: I've had this on my ideas queue for ages and am just not likely to get around to it any time soon. So it's totally waiting for someone enthusiastic to take a look.

Perl configuration
pp_reverse's 2-bytes-at-a-time implementation goes way back.

[tonycoz]

If we use non-overlapping source and destination, and tell the compiler that, it can generate SIMD code for us, see https://godbolt.org/z/Pze1oMPqd

Note the compiler's use of vmovdqu which allows unaligned access.

It appears to generate vectorized code on ARM too.

[demerphq]

On Wed, 18 Jan 2023, 11:38 Tony Cook, ***@***.***> wrote: If we use non-overlapping source and destination, and tell the compiler that, it can generate SIMD code for us, see https://godbolt.org/z/Pze1oMPqd

Of course that would mean reverse would temporarily double the ram used. Ok for most cases and we could fallback to the existing method for very long strings.

Note the compiler's use of vmovdqu which allows unaligned access.

This is the big question IMO. On some platforms you can do unaligned access even if it is strictly speaking UB. But on those you can't does loading K values into a register, reversing them and then writing them back outperform a straight reversal. Also does the bookkeeping involved get complicated enough that a generic approach would be too slow, from what I could tell the original idea is intended to statically resolve this at compile time, where we would have to resolve it at run time. Lastly there is the issue that the algorithm only works on non-utf8 strings. I guess the only way to know for sure is to try it and see. Yves

[richardleach]

Lastly there is the issue that the algorithm only works on non-utf8 strings.

I think it's applicable to UTF8 strings as well. pp_reverse first walks the char buffer and reverses each UTF8 character in place (using the same two-at-a-time algorithm noted above), then falls through to the general case to reverse the whole string. (I don't know if the per-UTF8 char reversal would be sped up by changing its algorithm, but the general case speedup would sill apply.)

[demerphq]

I think it's applicable to UTF8 strings as well. pp_reverse first walks the char buffer and reverses each UTF8 character in place

For what its worth, with unicode it is super helpful to use the correct terms: It walks the octet buffer and reverses in place each sequence of octets which represents a utf8 codepoint over 127, and then reverses the entire string of octets as though it were not utf8.

So yes, in that sense, an optimised reverse algorithm would work fine for the second part. But you have to wonder, would it be possible to be even faster under utf8 if we only traversed the string once?

FWIW, I started looking into this today, but I got distracted by "a quick fix for re::engine::GNU" which ended up taking over an hour of Dist::Zilla related yak shaving before I could finish a 3 minute patch. Ill take another look into implementing this in the next days if and when i get time. Thanks for the follow up, i hadnt looked closely at the reverse code yet.

[tonycoz]

Of course that would mean reverse would temporarily double the ram used. Ok for most cases and we could fallback to the existing method for very long strings.

We already make a copy of the source string and then reverse that in place.

We could instead reverse while copying, which saves a copy.

Note the compiler's use of vmovdqu which allows unaligned access.
This is the big question IMO. On some platforms you can do unaligned access even if it is strictly speaking UB. But on those you can't does loading K values into a register, reversing them and then writing them back outperform a straight reversal.

Note that in my example it's the compiler generating unaligned access instructions for well defined and frankly simple C code.

Also does the bookkeeping involved get complicated enough that a generic approach would be too slow, from what I could tell the original idea is intended to statically resolve this at compile time, where we would have to resolve it at run time.

My example is purely C compile time. It wouldn't be a useful improvement for say Debian, but an organization that built perl themselves could build with -march=haswell (released 2013) to get 32 byte at a time swaps, or -march=nehalem (released 2008) to get 16 byte at a time swaps.

These don't require platform specific code, just writing code compatible with the auto-vectorization done by the compiler. It doesn't require the use of compiler intrinsics like the "Fast array reversal with SIMD! " article does.

Lastly there is the issue that the algorithm only works on non-utf8 strings.

Right now pp_reverse copies the bytes into the new SV, byte reverses any UTF-8 sequences, then byte reverses the whole string.

We could instead, byte reverse while copying from the old string to the new SV, then byte reverse any now reversed UTF-8 sequences.

[demerphq]

On Thu, 19 Jan 2023, 08:03 Tony Cook, ***@***.***> wrote: Of course that would mean reverse would temporarily double the ram used. Ok for most cases and we could fallback to the existing method for very long strings. We already make a copy of the source string and then reverse that in place.

What? My brain just popped. We do 3n operations to reverse a string of n characters in worst case?! I don't get it. If we are not swapping in place why do we do two-tail reverse at all? If we have a temp buffer already there is no reason to do this double reversal at all. Am I missing something? We could instead reverse while copying, which saves a copy.

Note the compiler's use of vmovdqu which allows unaligned access. This is the big question IMO. On some platforms you can do unaligned access even if it is strictly speaking UB. But on those you can't does loading K values into a register, reversing them and then writing them back outperform a straight reversal. Note that in my example it's the compiler generating unaligned access instructions for well defined and frankly simple C code.

Godbolt isn't playing nicely on my phone so I'm not entirely with you on that part, but your c is better than mine so I take your word on it. Also does the bookkeeping involved get complicated enough that a generic

approach would be too slow, from what I could tell the original idea is intended to statically resolve this at compile time, where we would have to resolve it at run time. My example is purely C compile time. It wouldn't be a useful improvement for say Debian, but an organization that built perl themselves could build with -march=haswell (released 2013) to get 32 byte at a time swaps, or -march=nehalem (released 2008) to get 16 byte at a time swaps.

Nod. These don't require platform specific code, just writing code compatible

with the auto-vectorization done by the compiler. It doesn't require the use of compiler intrinsics like the "Fast array reversal with SIMD! " article does. Lastly there is the issue that the algorithm only works on non-utf8 strings. Right now pp_reverse copies the bytes into the new SV, byte reverses any UTF-8 sequences, then byte reverses the whole string.

Yeah, I hadn't closely looked at that. I was extrapolating from my experience from hashing, where I had to deal with platforms that don't allowed unaligned reads. We could instead, byte reverse while copying from the old string to the new

SV, then byte reverse any now reversed UTF-8 sequences.

If we have a temp buffer it seems unnecessary to do any of this. Read a character from the front, write it to the back. Done. I'll reach out to you on IRC to discuss further. Cheers Yves

[tonycoz]

What? My brain just popped. We do 3n operations to reverse a string of n characters in worst case?! I don't get it. If we are not swapping in place why do we do two-tail reverse at all? If we have a temp buffer already there is no reason to do this double reversal at all. Am I missing something? We could instead reverse while copying, which saves a copy.

I suspect part of the reason is to avoid complexity, don't forget reverse() even in scalar context takes a list, and the reverse operates on the join("", ...) of that list. The code does special case a single item list to avoid the join call.

Another thing to consider is whether trying to optimize scalar reverse is worth the effort - how much code uses scalar reverse where performance matters?

I expect there's some, but I doubt it's common.

[richardleach]

To recap, there are currently two main situations:

(1) Sometimes we will reverse an existing buffer in-place: either we have swiped the buffer from *SP or DEFSV via sv_setsv_flags, or do_join has concatenated the arguments into TARG.
(2) Otherwise we copy the buffer, then reverse that in-place.

For UTF-8 strings, we currently do a double pass: (1) reverse individual characters in-place (2) reverse all the bytes in the buffer.

I'll have a go at this and see what differences we can see.