[deleted]
How the JVM compares strings on x86 using pcmpestri
31–40 of 73 posts
Re: How the JVM compares strings on x86 using pcmpestri
#32Earlier quoted context omitted.
The intrinsics for the HotSpot JVM are declared here: http://hg.openjdk.java.net/jdk10/jdk10/hotspot/file/5ab7a67b... (look for "java_lang_Math" for instance)
Are you telling us it's not a secret then?
Don’t know if this is sarcasm, but no, doubtful it’s a secret. Or might depend on the JVM license. OpenJDK obviously has no secrets.
But otherwise, assembly overrides for hot paths in execution targets that support them aren’t actually a big secret, just that they’re rarely visible. Think Go has a lot of processed architecture specific assembly for some functions, especially crypto iirc.
Re: How the JVM compares strings on x86 using pcmpestri
#33Earlier quoted context omitted.
Any non-Latin string operations. While technically UTF16 is variable length, 99.99% cases use single word per character. I.e. on modern hardware with branch prediction and speculative execution, these branches don't affect speed. With UTF8, CPU mispredicts branches all the time because spaces, punctuations and newlines are single bytes even in non Latin-1 text.
I think the most common operations are comparisons for equality and copying anyways. UTF-8 is faster for those. I tried out how fast I could make UTF-8 strlen, with an assumption of a valid UTF-8 string. The routine ran at 18 GB/s on a single core using SSE. > With UTF8, CPU mispredicts branches all the time because spaces, punctuations and newlines are single bytes I don't understand this sentence. Why would there b…
> most common operations are comparisons for equality and copying anyways
Indexing & substrings are common, too.
> These days code is so often bandwidth limited if anything
Right, and for 1 billion Chinese speaking people UTF16 is 2 bytes/character, UTF8 is 3 bytes/character.
Re: How the JVM compares strings on x86 using pcmpestri
#34Earlier quoted context omitted.
Well, not necessarily a curse, but a suboptimal solution. Are there any situations where UTF16 is a clear upgrade over UTF8?
Any non-Latin string operations. While technically UTF16 is variable length, 99.99% cases use single word per character. I.e. on modern hardware with branch prediction and speculative execution, these branches don't affect speed. With UTF8, CPU mispredicts branches all the time because spaces, punctuations and newlines are single bytes even in non Latin-1 text.
Not really.
UTF-8 is self-synchronizing, which means you can treat it as a byte string for most operations, including finding substrings. You don't need to convert UTF-8 to a sequence of codepoints for most tasks (particularly if you drop the insistence of using character boundaries). When you do have to do so, you're usually applying a complex Unicode algorithm like case conversion, and so the branch misprediction overhead of creating characters is likely small in comparison to the actual cost of doing the algorithm.
Re: How the JVM compares strings on x86 using pcmpestri
#35UTF-16 is one of these ill-fated developments that curse some languages & platforms (WinNT incl Win10, WinAPI32, Java, Flash, JS, Python 3) to his day. compareTo uses 0x19, which means doing the “equal each” (aka string comparison) operation across 8 unsigned words (thanks UTF-16!) with a negated result. This monster of an instruction takes in 4 registers of input:
That's path dependence [0]. When all of those were conceived in the nineties, 2-byte UCS-2 seemed to be enough to store all unicode code points. UTF-16 came only later, once it was clear 65535 code points is too few. Had those languages been designed in last 10 years, all of them would pick UTF-8 as their code point format. [0]: https://en.wikipedia.org/wiki/Path_dependence
Some JavaScript runtimes (Firefox's Spidermonkey for one) have an optimization that stores some strings in single-byte format where possible to mitigate the cost of the awful original choice to use UCS-2 for JS strings. I expect some other runtimes do this too, but I don't know any off-hand.
IIRC this was motivated by Firefox OS (strings eat up a lot of RAM on memory-starved $50 smartphones) but it pays off on desktops too.
Re: How the JVM compares strings on x86 using pcmpestri
#36Earlier quoted context omitted.
I think the most common operations are comparisons for equality and copying anyways. UTF-8 is faster for those. I tried out how fast I could make UTF-8 strlen, with an assumption of a valid UTF-8 string. The routine ran at 18 GB/s on a single core using SSE. > With UTF8, CPU mispredicts branches all the time because spaces, punctuations and newlines are single bytes I don't understand this sentence. Why would there b…
> most common operations are comparisons for equality and copying anyways Indexing & substrings are common, too. > These days code is so often bandwidth limited if anything Right, and for 1 billion Chinese speaking people UTF16 is 2 bytes/character, UTF8 is 3 bytes/character.
Represent indexes not as number-of-code-points from start but as byte offsets, and index/substring doesn't need to decode code points. You lose the ability to easily say "get me the 100th code point in this string", but I'm hard-pressed to actually think of any case where that is actually valuable.
> Right, and for 1 billion Chinese speaking people UTF16 is 2 bytes/character, UTF8 is 3 bytes/character.
The information density of a single hanzi character is roughly equivalent to 5 letters in English. A Chinese plaintext document in UTF-8 is still smaller in memory footprint than an equivalent English document in ASCII. Of course, most documents aren't plaintext, and where people use characters for metadata (e.g., email, HTML), there is a substantial corpus of ASCII metadata in those documents that UTF-8 is still smaller than UTF-16 even for East Asian languages.
Of course, it's moot since the people who don't like UTF-8 in China and Japan aren't using UTF-16 either. They're using GB18030 or ISO-2022-JP for their documents.
Re: How the JVM compares strings on x86 using pcmpestri
#37Earlier quoted context omitted.
I think the most common operations are comparisons for equality and copying anyways. UTF-8 is faster for those. I tried out how fast I could make UTF-8 strlen, with an assumption of a valid UTF-8 string. The routine ran at 18 GB/s on a single core using SSE. > With UTF8, CPU mispredicts branches all the time because spaces, punctuations and newlines are single bytes I don't understand this sentence. Why would there b…
> most common operations are comparisons for equality and copying anyways Indexing & substrings are common, too. > These days code is so often bandwidth limited if anything Right, and for 1 billion Chinese speaking people UTF16 is 2 bytes/character, UTF8 is 3 bytes/character.
> Indexing & substrings are common, too.
Indexing code points in both UTF-8 and UTF-16 requires reading the whole string up to index location. Substrings are the same as well.
> Right, and for 1 billion Chinese speaking people UTF16 is 2 bytes/character, UTF8 is 3 bytes/character.
That's true for a text file without markup. But most text is not like that in 2017. HTML is probably the most common text format nowadays.
So let's see how a popular Chinese language website does.
curl http://language.chinadaily.com.cn/ --silent | wc -c
52678
curl http://language.chinadaily.com.cn/ --silent | iconv -f utf8 -t utf-16le | wc -c
93368
Re: How the JVM compares strings on x86 using pcmpestri
#38One thing I learned about pcmpxstrx is that it's surprisingly slow: latency of 10-11 cycles and reciprocal throughput of 3-5 cycles on Haswell according to Agner's tables, depending on the precise instruction variant. The instructions are also limited in the ALU ports they can use. Since AVX2 has made SIMD on x86 fairly flexible, it can sometimes not be worth using the string comparison instructions if simpler instructions suffice: even a slightly longer sequence of simpler SIMD instructions sometimes beats a single string compare.
The SSE 4.2 string comparison instructions still have their uses, but it's always worth testing alternate instruction sequences when optimizing code that might use them.
Re: How the JVM compares strings on x86 using pcmpestri
#39I find it a bit sad that, instead of optimising the existing REP CMPS instruction to do vectorised compares like they did with REP MOVS/STOS and block copies/writes, Intel introduced another even more complex instruction that itself requires a bunch of additional support code to use. I certainly don't think it's a "good use of CISC".
Re: How the JVM compares strings on x86 using pcmpestri
#40The JVM has a number of cool features that enable you to efficiently drop down into C (FFI) yourself: these tricks aren't just for built-ins.
A quick overview:
- First there was JNI. JNI means that you write method stubs with the "native" keyword. Then you run javah, which gives you some C glue code that you eventually need to compile. This is very fast, but it's annoying because now you need a tool chain everywhere. The Python equivalent of this is roughly writing CPython extensions.
- People thought JNI was annoying, so Sun developed JNA. JNA lets you bind a library directly: all the magic comes with the JVM, and you can just dlopen something and call some syms. This works fine, but it's very slow. The Python equivalent of this is roughly ctypes.
- Most recently, there's JNR and jnr-ffi. They do a very clever trick: you use JNI to get to libffi, and then you use libffi to call everything else performantly. You get roughly the performance of JNI, with the convenience of JNR. The Python equivalent of this is roughly cffi.
JNR is way more usable than I thought it would be. I develop caesium[0], a Clojure libsodium binding, using jnr-ffi and a pile of macros. I gave a talk about this at Clojure Conj (recording [1], slides [2]) if you're interested.
To be fair: this code uses intrinsics, which means that it's implemented differently than the three methods shown above, so it's still slightly different. It's just not different in a way that's meaningful to you unless you're working on the JVM itself :)
[0]: https://github.com/lvh/caesium [1]: https://dev-videos.com/videos/Lf-M1ZH6KME/Using-Clojure-with... [2]: https://www.lvh.io/CCryptoClojure/#/sec-title-slide