Transcoding Latin 1 strings to UTF-8 strings at 12 GB/s using AVX-512
lemire.me
lemire.me
That doesn't seem to be correct. UTF-8 is used by 98% of all the websites. I am not sure if it's even worth the trouble for libraries to implement this algorithm, since Latin-1 encoding is being phased out.
Also headers, mostly relevant for header values, are I think ISO-8859-1.
> The Encoding standard requires use of the UTF-8 character encoding and requires use of the "utf-8" encoding label to identify it. Those
Sounds to me like it tells you that you have to explicitly declare the charset as UTF-8, so you don't get the HTTP default of Latin-1.
(But that's just one "living standard" not exactly synonymous with with HTML5 and it might change, or might have been different last week..)
That's not what your linked spec says. You can try it yourself, in any browser. If you omit the encoding the browser uses heuristics to guess, but it will always work if you write UTF-8 even without meta charset or encoding header.
But if you insist, here is this quote:
https://www.w3docs.com/learn-html/html-character-sets.html
> UTF-8 is the default character encoding for HTML5. However, it was used to be different. ASCII was the character set before it. And the ISO-8859-1 was the default character set from HTML 2.0 till HTML 4.01.
or another:
https://www.dofactory.com/html/charset
> If a web page starts with <!DOCTYPE html> (which indicates HTML5), then the above meta tag is optional, because the default for HTML5 is UTF-8.
Nobody disagrees with this, but this is a very different statement from what you said originally in regards to what the default is. Things can be phased out but still have the old default with no plan to change the default.
Re other sources - how about citing the actual spec instead of sketchy websites that seem likely to have incorrect information.
In point 8, it says an implementation may use heuristics to detect the encoding. It has a note which states:
> The UTF-8 encoding has a highly detectable bit pattern. Files from the local file system that contain bytes with values greater than 0x7F which match the UTF-8 pattern are very likely to be UTF-8, while documents with byte sequences that do not match it are very likely not. When a user agent can examine the whole file, rather than just the preamble, detecting for UTF-8 specifically can be especially effective.
In point 9, the implementation can return an implementation or user-defined encoding. Here, it suggests a locale-based default encoding, including windows-1252 for "en".
As such, implementations may be capable of detecting/defaulting to UTF-8, but are equally likely to default to windows-1252, Shift_JIS, or other encoding.
[1] https://html.spec.whatwg.org/#determining-the-character-enco...
Do you have a source on that "should" part. Because the spec disagrees https://www.rfc-editor.org/rfc/rfc7230#section-3.2.4:
> Historically, HTTP has allowed field content with text in the ISO-8859-1 charset [ISO-8859-1], supporting other charsets only through use of [RFC2047] encoding. In practice, most HTTP header field values use only a subset of the US-ASCII charset [USASCII]. Newly defined header fields SHOULD limit their field values to US-ASCII octets.
In practice and by spec, HTTP headers should be ASCII encoded.
The section you quoted actually suggests that implementations should support ISO-8859-1 to ensure compatibility with systems that use it.
> Newly defined header fields SHOULD limit their field values to US-ASCII octets
ASCII octets! That means you SHOULD NOT send Latin1 encoded headers. The opposite of what pzmarzly was saying. I don't disagree Latin-1 being a superset of ASCII or having backward compatibility in mind, but that's not relevant to my response.
Web servers need to be able to receive and decode latin1 into utf-8 regardless of what the RFC recommends people send. The fact that it's going to become rarer over time to have the 8th bit set in headers, means you can write a simpler algorithm than what Lemire did that assumes an ASCII average case. https://github.com/jart/cosmopolitan/blob/755ae64e73ef5ef7d1... That goes 23 GB/s on my machine using just SSE2 (rather than AVX512). However it goes much slower if the text is full of european diacritics. Lemire's algorithm is better at decoding those.
Otherwise known as "Making other people's incompetence and inability to implement a specification your problem." Just because it's a widely quoted maxim doesn't make it good advice.
> SHOULD This word, or the adjective "RECOMMENDED", mean that there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighed before choosing a different course.
I do agree that latin1 headers shouldn't be _sent_ out though.
> Browsers don't use utf-8 unless you tell them to
This is wrong. You can prove this very easily by creating a HTML file with UTF-8 text while omitting the charset. It will render correctly.
> This is wrong. You can prove this very easily by creating a HTML file with UTF-8 text
No, but I will create an HTML file with latin-1 text, because that's what we're discussing: HTML files that don't use UTF-8 (and so by definition don't contain UTF-8 either).
While modern browsers will guess the encoding by examining the content, if you make an html file that just has plain text, then it won't magically convert it to UTF-8: create a file with `<html><head><title>encoding check</title></head><body><h1>Not much here, just plain text</h1><p>More text that's not special</p></body></html>` in it. Load it in your browser through an http server (e.g. `python -m http.server`), and then hit up the dev tools console and look at `document.characterSet`.
Both firefox and chrome give me "windows-1252" on Windows, for which the "windows" part in the name is of course irrelevant; what matters is what it's not, which is that it's not UTF-8, because the content has nothing in it to warrant UTF-8.
Btw I appreciate your edited response, but still you were factually incorrect about:
> Browsers don't use utf-8 unless you tell them to
Browsers can use UTF-8 even if we don't tell them. I am already aware of the extra heuristics you wrote about.
> HTML file with latin-1 ... which is that it's not UTF-8, because the content has nothing in it to warrant UTF-8
You are incorrect here as well, try using some latin-1 special character like "ä" and you will see that browsers default to document.characterSet UTF-8 not windows-1252
I decided to try this experimentally. In my findings, if neither the server nor the page contents indicate that a file is UTF-8, then the browser NEVER defaults to setting document.characterSet to UTF-8, instead basically always assuming that it's "windows-1252" a.k.a. "latin1". Read on for my methodology, an exact copy of my test data, and some particular oddities at the end.
To begin, we have three '.html' files, one with ASCII only characters, a second file with two separate characters that are specifically latin1 encoded, and a third with those same latin1 characters but encoded using UTF-8. Those two characters are:
Ë - "Latin Capital Letter E with Diaeresis" - Latin1 encoding: 0xCB - UTF-8 encoding: 0xC3 0x8B - https://www.compart.com/en/unicode/U+00CB
¥ - "Yen Sign" - Latin1 encoding: 0xA5 - UTF-8 encoding: 0xC2 0xA5 - https://www.compart.com/en/unicode/U+00A5
$ cat ascii.html | xxd -p
3c68746d6c3e3c686561643e3c7469746c653e656e636f64696e67206368
65636b2041534349493c2f7469746c653e3c2f686561643e3c626f64793e
3c68313e4e6f74206d75636820686572652c206a75737420706c61696e20
746578743c2f68313e3c703e4d6f7265207465787420746861742773206e
6f74207370656369616c3c2f703e3c2f626f64793e3c2f68746d6c3e0a
$ cat latinone.html | xxd -p
3c68746d6c3e3c686561643e3c7469746c653e656e636f64696e67206368
65636b206c6174696e313c2f7469746c653e3c2f686561643e3c626f6479
3e3c68313e546869732069732061206c6174696e31206368617261637465
7220307841353a20a53c2f68313e3c703e54686973206973206368617220
307843423a20cb3c2f703e3c2f626f64793e3c2f68746d6c3e0a
$ cat utf8.html | xxd -p
3c68746d6c3e3c686561643e3c7469746c653e656e636f64696e67206368
65636b207574663820203c2f7469746c653e3c2f686561643e3c626f6479
3e3c68313e54686973206973206120757466382020206368617261637465
7220307841353a20c2a53c2f68313e3c703e546869732069732063686172
203078433338423a20c38b3c2f703e3c2f626f64793e3c2f68746d6c3e0a
$ ls -a .
. .. ascii.html latinone.html utf8.html
$ curl -s -vvv 'http://127.0.0.1:8000/ascii.html' 2>&1 | egrep -v -e 'Last|Length|^\*|^<html|^{|Date:|Agent|Host'
> GET /ascii.html HTTP/1.1
> Accept: */*
>
< HTTP/1.0 200 OK
< Server: SimpleHTTP/0.6 Python/3.10.7
< Content-type: text/html
$ curl -s -vvv 'http://127.0.0.1:8000/latinone.html' 2>&1 | egrep -v -e 'Last|Length|^\*|^<html|^{|Date:|Agent|Host'
> GET /latinone.html HTTP/1.1
> Accept: */*
>
< HTTP/1.0 200 OK
< Server: SimpleHTTP/0.6 Python/3.10.7
< Content-type: text/html
$ curl -s -vvv 'http://127.0.0.1:8000/utf8.html' 2>&1 | egrep -v -e 'Last|Length|^\*|^<html|^{|Date:|Agent|Host'
> GET /utf8.html HTTP/1.1
> Accept: */*
>
< HTTP/1.0 200 OK
< Server: SimpleHTTP/0.6 Python/3.10.7
< Content-type: text/html
Firefox (v116.0.3):
http://127.0.0.1:8000/ascii.html result of `document.characterSet`: "windows-1252"
http://127.0.0.1:8000/latinone.html result of `document.characterSet`: "windows-1252"
http://127.0.0.1:8000/utf8.html result of `document.characterSet`: "windows-1252"
Chromium (v115.0.5790.170):
http://127.0.0.1:8000/ascii.html result of `document.characterSet`: "windows-1252"
http://127.0.0.1:8000/latinone.html result of `document.characterSet`: "macintosh"
http://127.0.0.1:8000/utf8.html result of `document.characterSet`: "windows-1252"
data:text/html,<html>
(You can type the complete document, but <html> is sufficient. Browsers autocomplete a valid document. BTW, data:text/html,<html contenteditable> is something I use quite a lot)
But yeah, I think windows-1252 is standard for quirks mode, for historical reasons.
edit: Trying data:text/html,<html>日本語 makes Chrome also use Shift_JIS, resulting in mojibake as it's actually UTF-8. Firefox shows a warning about it guessing the character set, and then it chooses windows-1252 and displays more garbage.
thank you, I learned nice trick today.
re windows1252 - this could be driven by system encoding settings, for most people it is 1252, but for eastern europe it is windows-1251.
when viewed from IBM z mainframe - encoding will be something like IBM EBCDIC
While technically latin-1/iso-8859-1 is a different encoding than windows-1252, html5 spec says browsers are supposed to treat latin1 as windows-1252.
That is, the following UTF-8 encoded .html files all produce document.characterSet == "UTF-8" and render as expected without mojibake, despite not saying anything about UTF-8. Change "ä" to "a" to get windows-1252 again.
<html>ä
<!DOCTYPE html><html>ä
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"><html>ä
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"><html>äI'm pretty sure this is incorrect.
<html>ä
My (intended) claim is that in practise the statement is almost always untrue. There may be weird edge cases when loading from local disk where it is true sometimes, but not in a way that web developers will usually ever encounter since you don't put websites on local disk.
This part of the html5 spec isn't binding so who knows what different browsers do, but it is a reccomendation of the spec that browsers should handle charset of documents differently depending on if they are on local disk or from the internet.
To quote: "User agents are generally discouraged from attempting to autodetect encodings for resources obtained over the network, since doing so involves inherently non-interoperable heuristics. Attempting to detect encodings based on an HTML document's preamble is especially tricky since HTML markup typically uses only ASCII characters, and HTML documents tend to begin with a lot of markup rather than with text content." https://html.spec.whatwg.org/multipage/parsing.html#determin...
Indeed, in the Chromium source code we can see a special case for local files with some comment explanation. https://github.com/chromium/chromium/blob/dea8b2608dd5d95e38...
I've observed Chrome to usually default to windows-1252 (latin1) for UTF-8 documents loaded from the network.
However, once that optimization has been decided, there's no point in leaving the high bit unused, so the engines keep optimized "1-byte char" strings as Latin1.
What advantage would this have over UTF-7, especially since the upper 128 characters wouldn't match their Unicode values?
(I'm going to assume you mean UTF-8 here rather than UTF-7 since UTF-7 is not really useful for anything, it's jus a way to pack Unicode into only 7-bit ascii characters.)
Fixed width string encodings like Latin-1 let you directly index to a particular character (code point) within a string without having to iterate from the beginning of the string.
JavaScript was originally specified in terms of UCS-2 which is a 16 bit fixed width encoding as this was commonly used at the time in both Windows and Java. However there are more than 64k characters in all the world's languages so it eventually evolved to UTF-16 which allows for wide characters.
However because of this history indexing into a JavaScript string gives you the 16-bit code unit which may be only part of a wide character. A string's length is defined in terms of 16-bit code units but iterating over a string gives you full characters.
Using Latin-1 as an optimisation allows JavaScript to preserve the same semantics around indexing and length. While it does require translating 8 bit Latin-1 character codes to 16 bit code points, this can be done very quickly through a lookup table. This would not be possible with UTF-8 since it is not fixed width.
EDIT: A lookup table may not be required. I was confused by new TextDecoder('latin1') actually using windows-1252.
More modern languages just use UTF-8 everywhere because it uses less space on average and UTF-16 doesn't save you from having to deal with wide characters.
I think it makes total sense to implement this.
A dual channel DDR4 system memory bandwidth is ~40GB/s, and DDR5 ~80GB/s.
Since this operation requires both a read and a write, you'd expect half that.
It's impossible to saturate the memory bandwidth on a modern CPU with a single thread, even if all you do is reads with absolutely no processing. The bottleneck is how fast outstanding cache misses can be satisfied.
The article even links to a benchmark that attempts to measure what it calls "sustainable memory bandwidth": https://www.cs.virginia.edu/stream/ref.html
> Most Latin 1 text is really Windows 1252
You're right, ASCII is more common, but single-byte encoded prose that goes beyond ASCII is usually Windows 1252 in my experience.
> Windows 1252 served as Latin 1 used to be common enough that browsers
> interpret a Latin 1 declaration as Windows 1252.
But the humour may have been lost in translation. It's funnier in the original ASCII.
The benchmark result is cool, but I'm curious how well it works with smaller outputs. When I've played around with SIMD stuff in the past, you can't necessary go off of metrics like "bytes generated per cycle", because of how much CPU freq can vary when using SIMD instructions, context switching costs, and different thermal properties (eg maybe the work per cycles is higher per SIMD, but the CPU generates heat much more quickly and downclocks itself).
Once a program is optimized to the point where no leaf method / hot loop takes up more than a few percent of runtime and algorithmic improvements aren't available or extremely hard to implement the speed of all the basic routines (memcpy, allocations, string processing, data structures) start to matter. The constant factors elided by Big-O notation start to matter.
No, this is just a case of the right answer changing over time, as good AVX-512 implementations became available, long after its introduction. And nothing in this article even comes close to addressing the main concern with the early AVX-512 implementation: the significant performance penalty it imposes on other code due to Skylake's slow power state transitions. Microbenchmarks like this made AVX-512 look good even on Skylake, because they ignore the broader effects.
If you remember, Linux complained not about the particular implementation of AVX-512, but the concept itself. It is also kinda looks ignorant of him (and anyone else who thinks the same way) to believe that AVX-512 is only about 512 or it has no potential, being a just simply better SIMD ISA compared to AVX1/2. What he did he just expressed himself in his trademark silly edgy maximalist way. It is an absolute pleasure to work with, gives great performance boost, and he should have more careful with his statements.
No, their point is that this does not refute said hypothetical claim. That is, their point is that it is not, as you claimed:
> Another proof that Linus is not always right.
(I don't know if their point is correct, but it's of the form "your argument against X is invalid", not "X is correct".)
Now hearing that the upcoming Ryzen is also going with the hybrid P/E core approach I wonder if AMD is also preparing to adopt these instructions as well…
Besides Intel do not gurantee compatibility AVX10 with AVX512/256.
This code only makes people's lives better if many languages and frameworks that translates latin-1 to utf8 are updated to have this new faster implementation.
If this took 3 days to write and benchmark, then to save 3 days of human time, we probably need to get this into the hands of hundreds of millions of people, saving each person a few hundred microseconds.
Considering the author also created https://github.com/simdutf/simdutf it's likely used or will be used in NodeJs amongst other things. Is that good enough?
Except CPUs evolve and what was once a fast way of doing things may no longer be very fast. And with ASM you got no compiler to generate better targeted instructions.
I've seen many instances where significant performance was gained by swapping out and old hand-written ASM routine with a plain language version.
If you ever add some optimized ASM to your code, do a performance check at startup or similar, and have the plain language version as a fallback.
Compilers understand intrinsics and can optimize around them, and CPUs evolve improved SIMD instruction sets at a snails pace.
Intel doesn't even really support AVX512 yet for consumer hardware, and maybe never will, so this code is mostly only good for very modern AMD.
Back in the days REP MOVSB was the fastes way to copy bytes, then Pentium came and rolling your own loop was better. Then CPUs improved and REP MOVSB was suddenly better again[1], for those CPUs. And then it changed again...
Similar story for other idioms where implementation details on CPUs change. Compilers can respond and target your exact CPU.
[1]: https://github.com/golang/go/issues/14630 (notice how one comments the same patch that gives 1.6x boost for OP gives them a 5x degradation)
I'm sure I could get my tomato fix at the farmers market.
https://en.wikipedia.org/wiki/AVX-512#CPUs_with_AVX-512
I can't speak to being error free or other issues but it should at the very least be present on any modern desktop, laptop, or server x86 CPU you could buy today.
Edit: I forgot to mention but Intel's Alder lake CPUs only have partial support presumably due to some issue with E cores. I'd guess Intel will get their shit together eventually wrt this now that AMD is shipping all their hardware with this instruction set.
AMD also keeps making and selling Zen 3 and Zen 2 chips as lower-cost products, and those do not have AVX-512.
That's incorrect. On the consumer cpu side Intel introduced AVX-512 for one generation in 2021 (Rocket lake), but than removed AVX-512 from the subsequent Alder Lake using bios updates, and fused it off in later revisions. It's also absent from the current Raptor Lake. So actually it's only available on Intel's server grade cpus.
>Edit: I forgot to mention but Intel's Alder lake CPUs only have partial support presumably due to some issue with E cores.
No, this wiki page is outdated.
All that this means is that Zen 4 uses the same execution units both for 256-bit operations and for 512-bit operations. This means that the throughput in instructions per cycle for 512-bit operations is half of that for 256-bit operations, but the throughput in bytes per cycle is the same.
However the 512-bit operations need fewer resources for instruction fetching and decoding and for micro-operation storing and dispatching, so in most cases using 512-bit instructions on Zen 4 provides a big speed-up.
Even if Zen 4 is "double pumped", its 256-bit throughput is higher than that of Sapphire Rapids, so after dividing by two, for most instructions it has exactly the same 512-bit throughput as Sapphire Rapids, i.e. two 512-bit register-register instructions per cycle.
The only exceptions are that Sapphire Rapids (with the exception of the cheap SKUs) can do 2 FMA instructions per cycle, while Zen 4 can do only 1 FMA + 1 FADD instructions per cycle, and that Sapphire Rapids has a double throughput for loads and stores from the L1 cache memory. There are also a few 512-bit instructions where Zen 4 has better throughput or latency than Sapphire Rapids, e.g. some of the shuffles.
The audience for wicked-clever, low/no branch, cache aware, SIMD sorcery is admittedly not everyone, but if you end up with that kind of problem, this is a go to!
Quoting the article "I use GCC 11 on an Ice Lake server. My source code is available.", linking to https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/... .
From the README at the top-level:
> Unless otherwise stated, I make no copyright claim on this code: you may consider it to be in the public domain.
> Don't bother forking this code: just steal it.