Thread: 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
Attachment
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
Attachment
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