Horton

Thread

Commits

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

  1. Use C11 char16_t and char32_t for Unicode code points.

  1. Optimization of the is_normalized() function.

    Alexander Borisov <lex.borisov@gmail.com> — 2025-10-21T16:17:00Z

    Hi, hackers!

I continue to work on optimizations and improvements in Unicode.
This patch changes the approach to storing data to determine whether
a code point is normalized (YES, NO, MAYBE).
In other words, we are talking about Normalization Quick Check.

Currently, a perfect hash is used to store knowledge about the
code point. I suggest abandoning the use of perfect hash and storing
code point data in bits packed into uint8.
This will give us almost direct access to the data.

The essence is simple.
1. Take the code point and divide it by 8. This gives us the index
    in the uint8 table.
2. We need to get the bit for the code point. Take the code point
    modulo 8 to get the desired offset.

Since we need to store one of three values (YES, NO, MAYBE) for each
code point, we are forced to use two bits. So everything is simply
multiplied by 2.

This is how obtaining a value by code point looks like in code:

uc = ch * 2;
index = uc / 8;
bit = uc % 8;

found = UnicodeNormProps_NFC_QC[index];
found >>= bit;
found &= ~(PG_UINT8_MAX << 2);

In terms of speed:

Used code points: 0-9, a-z, A-Z (ASCII)
With patch: tps = 256.279737
Without patch: tps = 218.902135

Used code points: а-я, А-Я (Cyrillic)
With patch: tps = 156.979941
Without patch: tps = 146.339438

Tested using pgbench.

# 620KB
select 
is_normalized('0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ...', 
'NFC');
# 1280KB
select 
is_normalized('абвгдежзийклмнопрстуфхцчшщъыьэюяАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ...', 
'NFC');


Thoughts out loud:
It is also known that in Postgres, Normalization Quick Check does
not perform a fair check for NFD and NFKD because the hash tables became
too large. For these forms, the result MAYBE is always returned.
We can implement a fair check for NFD and NFKD forms using the specified
approach. In this case, the binary file will increase in size by 99040
bytes. Considering that this is only used on the backend.

P.S.:
If you review and accept the patches [0] that accelerate
Unicode Normalization Forms, the speed of Quick Check will automatically
increase.

[0] 
https://www.postgresql.org/message-id/flat/844d3dd7-2955-4794-95d1-7f4c13cb89fc%40gmail.com

--
Best regards,
Alexander Borisov

  2. Re: Optimization of the is_normalized() function.

    Alexander Borisov <lex.borisov@gmail.com> — 2025-10-31T10:42:30Z

    21.10.2025 19:17, Alexander Borisov wrote:
> Hi, hackers!
> 
> I continue to work on optimizations and improvements in Unicode.
> This patch changes the approach to storing data to determine whether
> a code point is normalized (YES, NO, MAYBE).
> In other words, we are talking about Normalization Quick Check.
Rebase after commit
https://github.com/postgres/postgres/commit/3853a6956c3e3bc7a6fa9bcdb205a2997f46bac2.

--
Best regards,
Alexander Borisov