Обсуждение: speed up text_position() for utf-8

Hi,

Commit 9556aa01c69 (Use single-byte Boyer-Moore-Horspool search even
with multibyte encodings), was a speed improvement for the majority of
cases, but when the match was toward the end of the string, the
slowdown in text_position_get_match_pos() was noticeable. It was found
that there was a lot of overhead in pg_mblen(). [1]

The attached exploratory PoC improves this for utf-8. It applies on
top v25 of my utf-8 verification patch in [2], since one approach
relies on the DFA from it. The other three approaches are:
- a version of pg_utf_mblen() that uses a lookup table [3]
- an inlined copy of pg_utf_mblen()
- an ascii fast path with a fallback to the inlined copy of pg_utf_mblen()

The test is attached and the test function is part of the patch. It's
based on the test used in the commit above. The test searches for a
string that's at the end of a ~1 million byte string. This is on gcc
11 with 2-3 runs to ensure repeatability, but I didn't bother with
statistics because the differences are pretty big:

                  patch                  | no match | ascii | mulitbyte
-----------------------------------------+----------+-------+-----------
 PG11                                    |     1120 |  1100 |       900
 master                                  |      381 |  2350 |      1900
 DFA                                     |      386 |  1640 |      1640
 branchless utf mblen                    |      387 |  4100 |      2600
 inline pg_utf_mblen()                   |      380 |  1080 |       920
 inline pg_utf_mblen() + ascii fast path |      382 |   470 |       918

Neither of the branchless approaches worked well. The DFA can't work
as well here as in verification because it must do additional work.
Inlining pg_utf_mblen() restores worst-case performance to PG11
levels. The ascii fast path is a nice improvement on top of that. A
similar approach could work for pg_mbstrlen() as well, but I haven't
looked into that yet. There are other callers of pg_mblen(), but I
haven't looked into whether they are performance-sensitive. A more
general application would be preferable to a targeted one.

[1] https://www.postgresql.org/message-id/b65df3d8-1f59-3bd7-ebbe-68b81d5a76a4%40iki.fi
[2] https://www.postgresql.org/message-id/CAFBsxsHG%3Dg6W8Mie%2B_NO8dV6O0pO2stxrnS%3Dme5ZmGqk--fd5g%40mail.gmail.com
[3] https://github.com/skeeto/branchless-utf8/blob/master/utf8.h

--
John Naylor
EDB: http://www.enterprisedb.com

I wrote:

> The test is attached and the test function is part of the patch. It's
> based on the test used in the commit above. The test searches for a
> string that's at the end of a ~1 million byte string. This is on gcc
> 11 with 2-3 runs to ensure repeatability, but I didn't bother with
> statistics because the differences are pretty big:
>
>                   patch                  | no match | ascii | mulitbyte
> -----------------------------------------+----------+-------+-----------
>  PG11                                    |     1120 |  1100 |       900
>  master                                  |      381 |  2350 |      1900
>  DFA                                     |      386 |  1640 |      1640
>  branchless utf mblen                    |      387 |  4100 |      2600
>  inline pg_utf_mblen()                   |      380 |  1080 |       920
>  inline pg_utf_mblen() + ascii fast path |      382 |   470 |       918

I failed to mention that the above numbers are milliseconds, so
smaller is better.

-- 
John Naylor
EDB: http://www.enterprisedb.com

Attached is a short patch series to develop some ideas of inlining
pg_utf_mblen().

0001 puts the main implementation of pg_utf_mblen() into an inline
function and uses this in pg_mblen(). This is somewhat faster in the
strpos tests, so that gives some measure of the speedup expected for
other callers. Text search seems to call this a lot, so this might
have noticeable benefit.

0002 refactors text_position_get_match_pos() to use
pg_mbstrlen_with_len(). This itself is significantly faster when
combined with 0001, likely because the latter can inline the call to
pg_mblen(). The intention is to speed up more than just text_position.

0003 explicitly specializes for the inline version of pg_utf_mblen()
into pg_mbstrlen_with_len(), but turns out to be almost as slow as
master for ascii. It doesn't help if I undo the previous change in
pg_mblen(), and I haven't investigated why yet.

0002 looks good now, but the experience with 0003 makes me hesitant to
propose this seriously until I can figure out what's going on there.

The test is as earlier, a worst-case substring search, times in milliseconds.

 patch  | no match | ascii | multibyte
--------+----------+-------+-----------
 PG11   |     1220 |  1220 |      1150
 master |      385 |  2420 |      1980
 0001   |      390 |  2180 |      1670
 0002   |      389 |  1330 |      1100
 0003   |      391 |  2100 |      1360


-- 
John Naylor
EDB: http://www.enterprisedb.com

I wrote:

> 0001 puts the main implementation of pg_utf_mblen() into an inline
> function and uses this in pg_mblen(). This is somewhat faster in the
> strpos tests, so that gives some measure of the speedup expected for
> other callers. Text search seems to call this a lot, so this might
> have noticeable benefit.
>
> 0002 refactors text_position_get_match_pos() to use
> pg_mbstrlen_with_len(). This itself is significantly faster when
> combined with 0001, likely because the latter can inline the call to
> pg_mblen(). The intention is to speed up more than just text_position.
>
> 0003 explicitly specializes for the inline version of pg_utf_mblen()
> into pg_mbstrlen_with_len(), but turns out to be almost as slow as
> master for ascii. It doesn't help if I undo the previous change in
> pg_mblen(), and I haven't investigated why yet.
>
> 0002 looks good now, but the experience with 0003 makes me hesitant to
> propose this seriously until I can figure out what's going on there.
>
> The test is as earlier, a worst-case substring search, times in milliseconds.
>
>  patch  | no match | ascii | multibyte
> --------+----------+-------+-----------
>  PG11   |     1220 |  1220 |      1150
>  master |      385 |  2420 |      1980
>  0001   |      390 |  2180 |      1670
>  0002   |      389 |  1330 |      1100
>  0003   |      391 |  2100 |      1360

I tried this test on a newer CPU, and 0003 had no regression. Both
systems used gcc 11.2. Rather than try to figure out why an experiment
had unexpected behavior, I plan to test 0001 and 0002 on a couple
different compilers/architectures and call it a day. It's also worth
noting that 0002 by itself seemed to be decently faster on the newer
machine, but not as fast as 0001 and 0002 together.

Looking at the assembly, pg_mblen is inlined into
pg_mbstrlen_[with_len] and pg_mbcliplen, so the specialization for
utf-8 in 0001 would be inlined in the other 3 as well. That's only a
few bytes, so I think it's fine.


--
John Naylor
EDB: http://www.enterprisedb.com

I wrote:

> I tried this test on a newer CPU, and 0003 had no regression. Both
> systems used gcc 11.2. Rather than try to figure out why an experiment
> had unexpected behavior, I plan to test 0001 and 0002 on a couple
> different compilers/architectures and call it a day. It's also worth
> noting that 0002 by itself seemed to be decently faster on the newer
> machine, but not as fast as 0001 and 0002 together.

I tested four machines with various combinations of patches, and it
seems the only thing they all agree on is that 0002 is a decent
improvement (full results attached). The others can be faster or
slower. 0002 also simplifies things, so it has that going for it. I
plan to commit that this week unless there are objections.
-- 
John Naylor
EDB: http://www.enterprisedb.com