Horton
Menu

Re: speed up verifying UTF-8

John Naylor <john.naylor@enterprisedb.com>

View thread
From: John Naylor <john.naylor@enterprisedb.com>
To: Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>, Amit Khandekar <amitdkhan.pg@gmail.com>, Heikki Linnakangas <hlinnaka@iki.fi>, Thomas Munro <thomas.munro@gmail.com>, Greg Stark <stark@mit.edu>
Date: 2021-08-24T16:00:28Z
Lists: pgsql-hackers

Attachments

Naively, the shift-based DFA requires 64-bit integers to encode the
transitions, but I recently came across an idea from Dougall Johnson of
using the Z3 SMT solver to pack the transitions into 32-bit integers [1].
That halves the size of the transition table for free. I adapted that
effort to the existing conventions in v22 and arrived at the attached
python script. Running the script outputs the following:

$ python dfa-pack-pg.py
offsets: [0, 11, 16, 1, 5, 6, 20, 25, 30]
transitions:
00000000000000000000000000000000 0x0
00000000000000000101100000000000 0x5800
00000000000000001000000000000000 0x8000
00000000000000000000100000000000 0x800
00000000000000000010100000000000 0x2800
00000000000000000011000000000000 0x3000
00000000000000001010000000000000 0xa000
00000000000000001100100000000000 0xc800
00000000000000001111000000000000 0xf000
01000001000010110000000000100000 0x410b0020
00000011000010110000000000100000 0x30b0020
00000010000010110000010000100000 0x20b0420

I'll include something like the attached text file diff in the next patch.
Some comments are now outdated, but this is good enough for demonstration.

[1] https://gist.github.com/dougallj/166e326de6ad4cf2c94be97a204c025f
--
John Naylor
EDB: http://www.enterprisedb.com

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Simplify coding style of is_valid_ascii()

  2. Apply auto-vectorization to the inner loop of numeric multiplication.