Encodings-Schnelligkeit UTF-8 vs. UTF-32

[GabrielleChanel]

Ich setzte mich gerade mit Encodings auseinander und habe folgendes gelernt: in UTF-32 wird ein Zeichen immer in genau 32 Bits kodiert (4Bytes), während UTF-8 in einer variablen Byte-Anzahl (1-4Bytes) kodiert wird. UTF-8 ist dadurch Speichereffizienter. Habe ich bis dahin alles richtig verstanden?
Nun kommt meine Frage (unabhängig vom Speicherplatz): UTF-8 verwendet einen intelligenten Algorithmus um die Zeichen zu lesen, während UTF-32 keinen braucht, weil alles schon in seiner Gesamtlänge kodiert ist. Wenn man nun keine Speicherlimite hätte, wäre UTF-32 (ohne Algorithmus) schneller als UTF-8 (mit Algorithmus)? Kann mir jemand in diesem Bereich weiterhelfen?
Vielen Dank im Voraus fürs Verständlicher machen

[Sirius3]

In den seltensten Fällen hat man so viel Text, dass der Speicher eine Rolle spielen würde.
Und was die Geschwindigkeit anbelangt, ist es immer die Frage was Du machen möchtest.

[kbr]

Theoretisch könnte das Interpretieren von UTF-8 etwas langsamer sein. Da das Einlesen der Datei aber mit Abstand langsamer ist, als das Interpretieren der Daten, spielt das praktisch keine Rolle. Im Gegenteil: es kann sogar sinnvoll sein, Daten zu komprimieren um Dateien klein zu halten und so den Zeitbedarf für I/O zu reduzieren. Bei überschaubaren Textumfängen sollte das aber alles unerheblich sein.

[DasIch]

Zugriff auf den Arbeitsspeicher ist relativ langsam, deswegen haben CPUs mehrere Caches, so dass man auf diese zugreifen kann und nicht immer auf den Arbeitsspeicher zugreifen muss. Es ist sehr wichtig diese auszunutzen wenn man schnelle Anwendungen schreiben möchte. Da UTF-32 i.d.R. mehr Platz verbraucht, wirst du damit wahrscheinlich mehr Cache misses haben (außer wir nehmen an CPU Cache ist auch unendlich groß), dass wirkt sich natürlich negativ auf die Geschwindigkeit aus.

[GabrielleChanel]

@kbr @DasIch Vielen herzlichen Dank für eure nützlichen Inputs
@Sirius3 Ich hätte vielleicht präzisieren sollen, dass es sich um eine theoretische Frage handelt, da ich noch kein mögliches Anwendungssbeispiel, wo dieser Unterschied eine wesentliche Rolle spielen würde, habe.

[jerch]

...
Wenn man nun keine Speicherlimite hätte, wäre UTF-32 (ohne Algorithmus) schneller als UTF-8 (mit Algorithmus)?

Wie von @kbr bereits angedeutet, kann man das nicht pauschal beantworten. Falls es Dir jetzt nur um Verarbeitungsgeschwindigkeit von Daten im Speicher geht (alles bereits im RAM), ist zu beachten, dass bei heutigen CPUs die internen Caches 10 - 100x schneller angebunden sind als RAM, heisst für die CPU ist ein uncached load aus dem RAM per se eine teure Aktion (L1 hit ~4 cycles vs. DRAM remote >300 cycles).

Nun belegt UTF8 für westliche Sprachen idR viel weniger Speicher, d.h. ein RAM load mit Cache line update erfasst mehr Nutzdaten, ergo muss die CPU weniger häufig den "langsamen" RAM anfragen. Auf der anderen Seite ist die Entscheidung, ob multibyte char oder ASCII, in UTF8 relativ billig und in wenigen Zyklen entscheidbar (<<20 cycles). Heisst, die algorithmische Zeichenentscheidung in UTF8 ist so billig für die CPU, dass andere Maschineneigenschaften wie Speicherzugriffszeit relevant werden.

Konsequenz des Ganzen ist, dass die Frage nach den anstehenden Operationen beantwortet werden muss:

• sequentielle Verarbeitung: Hier dürfte UTF8 kaum unterlegen sein, ggf. aufgrund von besserer Cache-Lokalität und Zyklus-Vorteilen durch seltenere Speicherzugriffe sogar schneller.

• random access (RA): Feste Speicherbreite in UTF32 erlaubt direkten Index/Offset-Sprung. Hier verliert UTF8, da es iterativ zur gesuchten Position laufen muss. Dieser Unterschied ist wesentlich, da in höherer Komplexitätsklasse (O(1) vs. O(n)). Das kann zwar mit jump tables abgekürzt werden, treibt aber den Speicheraufwand wieder nach oben. Das ist übrigens ein Grund, warum viele Programmiersprachen für die interne Stringrepräsentation UTF32 nehmen (RA-Operationen steht im Vordergrund, während Speicher(-zugriff) relativ immer billiger wird mit wachsendem n).

Übrigens verliert UTF8 die oben genannten Vorteile auch bei sequentieller Verarbeitung, wenn die Zeichen nicht mehr aus dem ASCII-Raum kommen (worst case: alles 4 Byte Zeichen).

[narpfel]

Bezüglich Random Access: Auch bei Encodings mit fester Breite kommt man unter Umständen nicht um lineares Suchen herum, weil ein Zeichen als mehr als ein Codepoint (und damit auch bei UTF-32 als mehr als eine Code Unit) kodiert sein kann. Zum Beispiel kann ä als U+00E4 (LATIN SMALL LETTER A WITH DIAERESIS) oder als U+0061 U+0308 (LATIN SMALL LETTER A + COMBINING DIAERESIS) kodiert sein.

Mit einem s[:42] slicet man sich also potentiell einen Umlaut kaputt, und man kann nicht wissen, wie viele Zeichen im Ergebnis enthalten sind. Obwohl Python O(1)-Stringzugriff garantiert.

[jerch]

@narpfel: Naja Unicode schlawinert sich damit aus der Affäre, dass bewusst zwischen codepoints (Datenschicht) und "human perceivable characters" unterschieden wird. Letztere können in grapheme clusters beliebig viele codepoints enthalten (also wieder Suche in n), praktisch sind in allen scripting systems diese auf wenige sinnvolle beschränkt (2 - 4 zusätzliche codepoints, damit konstant in der Umkreissuche). Nichtsdestotrotz - imho ist "Unicode broken by design", gerade weil der große Zeichenraum noch nicht ausgenutzt wird, während bereits wie wild geclustert wird.

Mit einem s[:42] slicet man sich also potentiell einen Umlaut kaputt, und man kann nicht wissen, wie viele Zeichen im Ergebnis enthalten sind.
Obwohl Python O(1)-Stringzugriff garantiert.

Die O(1) gehen in Ordnung, da Python das auch nur auf der Codepoint-Ebene garantiert (das Zerhacken wird in Kauf genommen). Am Ende beim codepoint-Slicen könnte man zumindest das Zerhacken in O(1) korrigieren (s.o.). Für echtes Zählen/Slicen über grapheme clusters wird die Sache allerdings sehr sehr teuer. Für die Frage nach UTF8 vs. UTF32 - UTF8 hat eine Matroschka-Hülle mehr zu durchlaufen für Bytes --> "human perceivable character".