Wanneer Compilers het Oneens zijn over UTF-8
Waarom een eenvoudige ASCII fast-path de prestaties van Clang verdrievoudigde, maar die van GCC ongewijzigd liet
In de zomer van 2006 startte ik een open-source C++ bibliotheek voor het verwerken van UTF-8 strings. Ik wilde dat deze draagbaar zou zijn en goed zou samenwerken met de STL, maar ik ben destijds niet obsessief bezig geweest met optimalisaties.
Onlangs, toen ik begon te schrijven over UTF-8 decoding, ben ik opnieuw gaan kijken naar de interne werking van de bibliotheek. De functie die ik besloot te optimaliseren, decodeert een UTF-8 gecodeerd codepunt:
template <typename octet_iterator>
utf_error validate_next(octet_iterator& it, octet_iterator end, utfchar32_t& code_point)
{
if (it == end)
return NOT_ENOUGH_ROOM;
// Bewaar de oorspronkelijke waarde van 'it' zodat we kunnen terugkeren bij een fout.
// Dit heeft overigens weinig zin bij bijvoorbeeld stream-iterators.
octet_iterator original_it = it;
utfchar32_t cp = 0;
// Bepaal de sequentielengte op basis van het lead-octet
const int length = utf8::internal::sequence_length(it);
// Haal trail-octetten op en bereken het codepunt
utf_error err = UTF8_OK;
switch (length) {
case 0:
return INVALID_LEAD;
case 1:
err = utf8::internal::get_sequence_1(it, end, cp);
break;
case 2:
err = utf8::internal::get_sequence_2(it, end, cp);
break;
case 3:
err = utf8::internal::get_sequence_3(it, end, cp);
break;
case 4:
err = utf8::internal::get_sequence_4(it, end, cp);
break;
}
if (err == UTF8_OK) {
// Decoding is geslaagd. Nu de beveiligingscontroles...
if (utf8::internal::is_code_point_valid(cp)) {
if (!utf8::internal::is_overlong_sequence(cp, length)){
// Geslaagd! Return hier.
code_point = cp;
++it;
return UTF8_OK;
}
else
err = OVERLONG_SEQUENCE;
}
else
err = INVALID_CODE_POINT;
}
// Fout-branch: herstel de oorspronkelijke waarde van de iterator
it = original_it;
return err;
}De werking is vrij rechttoe rechtaan: op basis van de waarde van het lead-byte wordt de lengte van de sequentie bepaald. Afhankelijk van die lengte wordt de waarde van het codepunt geconstrueerd door de juiste bitvelden uit de bytes te extraheren. Nadat het codepunt succesvol is gedecodeerd, worden er twee extra controles uitgevoerd: één voor de validiteit van het codepunt en één om te controleren op een 'overlong' UTF-8 sequentie. Als beide controles slagen, wordt de status 'success' teruggegeven en wordt de iterator naar de volgende sequentie verplaatst.
De optimalisatie
Een kans voor optimalisatie lag in het feit dat ASCII triviaal voldoet aan alle validiteitseisen van UTF-8. Als blijkt dat het hoogste bit van het lead-byte nul is, hebben we een "ASCII-karakter" — een waarde in het bereik [U+0000, U+007F] die altijd geldig is. Alles wat we hoeven te doen is dit zero-extenden en we hebben ons codepunt.
Dit ziet er als volgt uit:
template <typename octet_iterator>
utf_error validate_next(octet_iterator& it, octet_iterator end, utfchar32_t& code_point)
{
if (it == end)
return NOT_ENOUGH_ROOM;
// Bewaar de oorspronkelijke waarde van 'it' zodat we kunnen terugkeren bij een fout.
// Dit heeft overigens weinig zin bij bijvoorbeeld stream-iterators.
octet_iterator original_it = it;
utfchar32_t cp = 0;
// Bepaal de sequentielengte op basis van het lead-octet
const int length = utf8::internal::sequence_length(it);
// Haal trail-octetten op en bereken het codepunt
utf_error err = UTF8_OK;
switch (length) {
case 0:
return INVALID_LEAD;
case 1:
err = utf8::internal::get_sequence_1(it, end, cp);
// Geen verdere validaties nodig
if (err == UTF8_OK) {
code_point = cp;
++it;
return UTF8_OK;
} else {
it = original_it;
return err;
}
break; // om waarschuwingen te voorkomen
case 2:
err = utf8::internal::get_sequence_2(it, end, cp);
break;
case 3:
err = utf8::internal::get_sequence_3(it, end, cp);
break;
case 4:
err = utf8::internal::get_sequence_4(it, end, cp);
break;
}
if (err == UTF8_OK) {
// Decoding is geslaagd. Nu de beveiligingscontroles...
if (utf8::internal::is_code_point_valid(cp)) {
if (!utf8::internal::is_overlong_sequence(cp, length)){
// Geslaagd! Return hier.
code_point = cp;
++it;
return UTF8_OK;
}
else
err = OVERLONG_SEQUENCE;
}
else
err = INVALID_CODE_POINT;
}
// Fout-branch: herstel de oorspronkelijke waarde van de iterator
it = original_it;
return err;
}Resultaten en compilerverschillen
Mijn verwachting was dat er een zichtbare verbetering zou zijn bij het verwerken van strings die alleen uit ASCII bestaan, met een geringe impact op gemengde ASCII/non-ASCII strings. Tests met Clang 18.1.3 overtroffen mijn verwachtingen: voor pure ASCII-tekst verdrievoudigde de doorvoersnelheid (throughput) van de UTF-8 decoding, en zelfs voor gemengde tekst was de verbetering aanzienlijk: ongeveer 34%.
Ik had de wijziging inmiddels naar GitHub gepusht, maar besloot daarna te testen met GCC. Compilers houden op te verrassen: ditmaal was er voor ASCII-tekst helemaal geen verschil! Nul! Voor zwaar gemengde tekst was de doorvoersnelheid consistent 3-4% slechter, wat minder verrassend was.
Analyse van de assembly-code
Tijd om de handen vuil te maken en naar de gegenereerde assembly-code te kijken. Dit is wat er gebeurt voor een ASCII-codepunt in de oorspronkelijke versie gecompileerd met g++:
15e0: ldrb w0, [x22] ; laad byte
15e4: tbz w0, #7, 1700 ; als bit 7 == 0 (ASCII) return direct
...
1700: add x22, x22, #1 ; consumeer 1 byte
1704: cmp x2, x22 ; check end-of-buffer
1708: b.ne 15e0 ; loop als er meer input isDit is een geoptimaliseerde build met veel inlining, en de laatste twee instructies komen uit een functie die validate_next in een loop aanroept. Het is echter duidelijk dat er geen validatiecontroles in de ASCII-branch zitten: de compiler kon beredeneren dat de controles altijd zouden slagen en heeft ze simpelweg verwijderd. Mijn optimalisatie veranderde niets — de gegenereerde code voor de ASCII-branch bleef hetzelfde.
Nu Clang:
1870: ldrsb w13, [x20] ; laad byte, sign-extended
1874: and w12, w13, #0xff ; w12 = unsigned versie
1878: tbnz w13, #31, 1890 ; als sign bit is gezet, spring naar non-ASCII path
187c: mov w14, wzr ; geen continuation bytes
1880: mov w15, #1 ; sequentielengte = 1 byte
1884: mov x13, x20 ; x13 = pointer naar lead byte
1888: mov w16, w12 ; gedecodeerd codepunt = byte waarde
188c: b 19ac ; ga naar generieke validiteitscontroles
...
19ac: lsr w17, w16, #16
19b0: and w18, w16, #0x1ff800
19b4: cmp w17, #0x10
19b8: ccmp w18, w11, #4, ls
19bc: b.eq 2300 ; ongeldig codepunt
19c0: cmp w16, #0x7f
19c4: b.ls 1860 ; geldig ASCII: iterator verplaatsenOverduidelijk heeft Clang de validiteitscontroles voor het codepunt niet geëlimineerd. Met mijn optimalisatie wordt de code:
15e0: ldrb w0, [x22]
15e4: tbz w0, #7, 16c8 # ASCII
...
# ASCII early-return completion
16c8: add x22, x22, #1
16cc: cmp x2, x22
16d0: b.ne 15e0Dat verklaart zeker de enorme prestatieverbetering bij Clang.
Conclusie
Uiteindelijk heb ik gekozen voor een iets grotere wijziging waar beide compilers tevreden mee waren. In plaats van de validiteit van het codepunt en overlong-sequenties te controleren nadat het decoderen is voltooid, heb ik de getsequence* functies uitgebreid om de validatie inline uit te voeren. Dit behield alle prestatiewinst bij Clang en leidde tot een verbetering van 15-20% bij GCC met gemengde tekst (geen verschil voor pure ASCII).
De moraal van het verhaal? Compilers zijn grillig, maar tijd investeren in optimalisaties kan zeer lonend zijn.
Groetjes,