8 ms·
How the JVM compares strings on x86 using pcmpestri
- JanecekPetr 9y agoThis guy's blog is awesome. A lot of in-depth information, original research, nice and funny writing style. I hope he finds some time to write / speak more soon.
- frik 9y agoUTF-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:
- RyanZAG 9y agoJava uses UTF8 in latest release for strings without special characters. http://www.baeldung.com/java-9-compact-string http://www.baeldung.com/java-9-compact-string UTF16 is not really a curse for languages that require it. String operations in non-English languages are very fast because of it, and most software these days has to deal with localization.
- lmm 9y agoUTF-16 is the worst of all worlds: it's less efficient than UTF8 for most use cases, requires you to think about endianness, but is still a variable-length encoding. (And the cases that require variable-length encoding are rarer than they are for UTF-8, meaning you're less likely to hit them in testing)
- oblio 9y agoWell, not necessarily a curse, but a suboptimal solution. Are there any situations where UTF16 is a clear upgrade over UTF8?
- Const-me 9y agoAny 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.
- vardump 9y agoI 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 be any more mispredictions because of those being single bytes? These days code is so often bandwidth limited if anything, so smaller data helps.
- HelloNurse 9y agoIn non-Latin text, if most characters are 2 bytes but a large minority are 1 byte, the branch prediction in charge of guessing between the different codepoint representation lengths expects 2 bytes and fails very often. Speculative execution (counting in two or three ways simultaneously) might mitigate the performance hit.
- vardump 9y ago> In non-Latin text, if most characters are 2 bytes but a large minority are 1 byte, the branch prediction in charge of guessing between the different codepoint representation lengths expects 2 bytes and fails very often You wouldn't want to process a single code point (or unit) at a time anyways, but 16, 32 or 64 code units (or bytes) at once. That UTF-8 strlen I wrote had no mispredicts, because it was vectored. Indexing is slow, but the difference to UTF-16 is not significant. I guess locale based comparisons or case insensitive operations could be slow, but then again, they'll need a slow array lookup anyways. Which string operation(s) are you talking about?
- nwellnhof 9y agoNo, it uses the fixed-width LATIN1 (ISO-8859-1) encoding for compact strings. It wouldn't make much sense to use another variable-width encoding like UTF-8.
- vardump 9y agoThat'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 https://en.wikipedia.org/wiki/Path_dependence
- kevingadd 9y agoSome 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.
- pcwalton 9y agoV8 and JavaScriptCore do it, I believe.
- BeeOnRope 9y agoJava has taken a couple different shots at this, going back a decade or more, and the newer option is currently enabled in Java 9. Some background: https://stackoverflow.com/q/8833385/149138 https://stackoverflow.com/q/8833385/149138
- ubernostrum 9y agoPython as of 3.3 uses any of three different internal storage mechanisms for strings: 1-byte (latin-1), 2-byte (UCS-2) or 4-byte (UCS-4) depending on the width of the highest code point in the string. This allows the internal storage to always be fixed-width, while still saving space for strings which contain, say, only code points representable in a single byte. Prior to 3.3, the internal storage of Unicode was determined by a flag during compilation of the interpreter; a "narrow" compiled interpreter would use 2-byte strings with surrogate pairs for non-BMP code points, and a "wide" compiled interpreter would use 4-byte strings.
- maxerickson 9y agoWhat about https://www.python.org/dev/peps/pep-0393/ https://www.python.org/dev/peps/pep-0393/ ?
- banthar 9y agoPEP-393 is a stupid compromise. They couldn't choose between UCS-2 and UCS-4, so they are using both. They are wasting tons of CPU cycles converting between them and single character outside of range doubles the size of string. I don't fully understand the use case for extracting codepoints from strings, but they could have just added Java-like: codePoints and keep returning code units from old methods. This is CPU and memory efficient and 100% backwards compatible. I think the problem is the same could have been done in Python 2 (with UTF-8) that would mean less reasons for Python 3.
- goldenkey 9y agoIt's great to see the disassembly. Would be curious to see the assembly performance-tested against other similar implementations (UTF-16 compatible.) Btw, frik, you are shadow banned. I sense it is for the frigid opinions. Personally, I see them as "ok" as long as you provide technical reasons for your opinions and are polite enough.
- exikyut 9y agoI figured out the 2nd part of this comment is talking about https://news.ycombinator.com/item?id=16090274 https://news.ycombinator.com/item?id=16090274. I can see this post fine; it's not "dead". If you ever browse /newest and/or have showdead on you've probably seen the occasional genuine spam that turns up on here. I think the HN admins have a genuinely hard time with the current volume. To deal with the current state of affairs Arc apparently has to be exceptionally aggressive, and I've seen it generates a very small stream of false negatives. In future, open the post (click the timestamp) and click "vouch". If it stays [dead], hopefully enough other people also vouch for it.
- dang 9y agoIt has nothing to do with "frigid opinions"; we banned the account for egregious serial abuse of the site. Please don't do such digressions in HN comments. If you don't think a user should be banned, you're welcome to email us. And of course you can vouch for their good comments.
- zakk 9y agoClick here to discover that crazy instruction! C++ programmers HATE IT!! (I am just ironizing about the title, the content is actually great!)
- exikyut 9y ago> But did you know there is also a secret second implementation? String.compareTo is one of a few methods that is important enough to also get a special hand-rolled assembly version. oooooh. Is there a list somewhere of all the functions that have had such special treatment?
- kaeluka 9y agoThe feature is called "intrinsics", this claims to be a list: https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc
- djsumdog 9y agoInteresting. So do all those functions have assembly implementations or do some of them have c implementations? I'm assuming the list of functions also changes depending on the architecture?
- BeeOnRope 9y agoThey are implemented in different ways, depending on the instrinsic. Many are implemented in the in-memory intermediate SSA (?) representation the JVM uses for its JIT, so they essentially get compiled down to assembly at the same time as the surrounding bytecode. Some are implemented as jumps to various native methods, which in turn might be implemented in C++ or assembly. Most intrinsics are available on most platforms: only some of the hand-coded assembly versions are less likely to have wide support.
- nicoulaj 9y agoThe intrinsics for the HotSpot JVM are declared here: http://hg.openjdk.java.net/jdk10/jdk10/hotspot/file/5ab7a67bc155/src/share/vm/classfile/vmSymbols.hpp#l679 http://hg.openjdk.java.net/jdk10/jdk10/hotspot/file/5ab7a67b... (look for "java_lang_Math" for instance)
- rplnt 9y ago
- ghusbands 9y agotl;dr: The string comparison intrinsic in the JVM uses a vectorised string comparison instruction. (vpcmpestri (of the pcmpxstrx family) isn't an especially crazy instruction to use for string comparison. That's what it's designed for.)
- amelius 9y agoThanks for the tl;dr. I think the "crazy" adjective refers to the instruction, and not to the use of it. As the article explains, the instruction is quite complicated and has a large number of parameters.
- B4TMAN 9y agoIs there any place to get a proper manual of all these uses?
- brianon99 9y agoAgree that using vector instruction is not crazy at all. I am quite interested when I see the article title, and then deeply disappointed after I read it. I was expecting something like the strlen shown in the book The Hackers Delight, which loads 4 bytes into a int, ad then some bit masking and subtraction and a nlz (number of leading zero) to index the first 0 byte. Please read it first and that is what really what meant by crazy.
- r4um 9y agoAnother excellent series on JVM perf/internals https://shipilev.net/jvm-anatomy-park/ https://shipilev.net/jvm-anatomy-park/
- dullgiulio 9y agoGo uses the same technique[1], or a Duff's device[2] when AVX2 is unsupported. I am convinced that similar tricks are employed by almost every language runtime or standard library (GNU libc also does this, etc.) [1] https://github.com/golang/go/blob/master/src/runtime/asm_amd64.s#L1530 https://github.com/golang/go/blob/master/src/runtime/asm_amd... [2] https://en.wikipedia.org/wiki/Duff%27s_device https://en.wikipedia.org/wiki/Duff%27s_device
- deleted 9y ago[deleted]
- pcwalton 9y agoOne 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.
- burntsushi 9y agoI have the same experience. I've tried using pcmpestr in substring search a few times, and it had always turned out to not be worth it. I have however never tried it in during comparison functions, so I can't speak to that, but I wouldn't be surprised if the latency of the instruction mad at impact there too.
- userbinator 9y agoI 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".
- pcwalton 9y agopcmpxstrx is a lot more powerful than rep cmps. I'm lukewarm on pcmpxstrx too, but for a different reason: I'd prefer the effort to go into more general purpose, highly flexible SIMD instructions (which is thankfully happening now with AVX 512).
- eddyb 9y agoWhat do you think about Cray-style vectors, which are coming back in the form of ARM SVE and the RISC-V V extension? At least the latter claims code compiled once is compatible with all possible hardware configurations, from the start (by way of giving the CPU a "remaining iterations count" and having it reply with how many it can do for the chosen vector lane shapes). IMO, if it does end up working that well in practice, it does put all of the various incompatible versions of packed SIMD extensions in a pretty awkward spot - could we have skipped all of MMX, SSE, AVX, NEON, etc. versions with technology that has been around for almost half a century?
- pcwalton 9y agoSounds like a good idea to me. Seems similar to how GPUs work, which is generally a good path to follow.
- lvh 9y agoThe 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 https://github.com/lvh/caesium [1]: https://dev-videos.com/videos/Lf-M1ZH6KME/Using-Clojure-with-C-APIs-for-crypto-and-more--lvh https://dev-videos.com/videos/Lf-M1ZH6KME/Using-Clojure-with... [2]: https://www.lvh.io/CCryptoClojure/#/sec-title-slide https://www.lvh.io/CCryptoClojure/#/sec-title-slide
- quotemstr 9y agoJNR (and JNA and cffi) strike me as unsafe due to the lack of type enforcement. Systems like this let you call any random pointer as if it were a C function of any type. That usually works, but sometimes doesn't. If you're lucky, mistakes make your program blow up right away. If you're unlucky, you get impossible to diagnose memory corruption. I'd much rather write conventional bridges and have the system check that I'm right.
- bdonlan 9y agoTo be fair, when you're writing the C side of your JNI bindings, it'll also let you call any random pointer as if it were a C function of any type. You'll have non-type-safe code _somewhere_, it's just a choice of where.
- vardump 9y agoI think it could be fairly profitable performance wise to write a specialized version of compareTo (simple memcmp) for cases where the result is directly compared to 0, equal or not equal case. Or to have compareEqualityTo() version. Current version supports greater and less as well, which is of course useful in many data structures and sorting, but might not represent bulk of the call sites. This feature does not come for free. This alternative version (memcmp alias) could be written to run faster. Only benchmarking could tell whether or not it's ultimately worth it.
- saagarjha 9y ago> The code that generates this, MacroAssembler::string_compare in macroAssembler_x86.cpp is well-documented for the curious. I was expecting that this would be some C++ code, or maybe inline assembly, but it turns out it's just a bunch of macros that are a thin layer over assembly instructions. Is this done for portability, to abstract over differing instruction names on different architectures?
- ahmadzaraei 9y agoWhat a lovely ready; I enjoy learning about the intricate details of the JVM. Thank you for sharing!