How the JVM compares strings on x86 using pcmpestri | Hacker News Reader

How the JVM compares strings on x86 using pcmpestri

jcdav.is

239 pointsmpweiher70 comments

The 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

JNR (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.

To 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.

Ah, not true! You'll have as much type-checking as C allows for, which is actually quite substantial. Moreso in C++. The opportunities for accidental type mismatch are much reduced: basically, to the JNI->function bindings (eliminated if you codegen the glue).

I see what you’re saying, but that piece of code doesn’t exist at all in JNR (so it can’t have bugs) and you can codegen JNR/FFI too to eliminate the same hole, right?

I feel like saying “don’t mess up this signature” is not only plausible but it’s a lot better than having to deal with writing and compiling the stub for every platform.

This is why pycparser exists, for example. https://github.com/eliben/pycparser

The solution is to have some tool which parses C header files and uses them to build the Java bindings.

Unfortunately, C is a pretty nasty language to parse, so you end up using something like http://www.swig.org/ or https://github.com/rpav/c2ffi to parse it for you. But the challenge with adopting those sort of tools for Java is they aren't written in Java, they are written in C and/or C++. (Obviously that doesn't stop you from using them with Java, but it does make the whole thing less pleasant.)

There is a project to get something like JNR bundled with the JDK – see http://openjdk.java.net/jeps/191 and http://openjdk.java.net/projects/panama/

If folks are interested in this, I figured some folks might like our c++ version of this (been around for 5 years ish now): https://github.com/bytedeco/javacpp

Also comes with tons of pre cooked projects already ready to go: https://github.com/bytedeco/javacpp-presets

We use it in production at skymind and it powers our whole cpu and gpu stack with built in memory management among other things.

Also has maven and sbt plugins so you can plug it right in to your workflow automatically just maintaining the java code.

One of the coolest features is the name matching so you can get semi automatic mapping.

We auto generate our JNI bindings from this.

> Then you run javah, which gives you some C glue code that you eventually need to compile.

That's deprecated and no longer supported in Java 10. The recommend way is to use javac -h.

> This is very fast

There is a certain call overhead for JNI that JNA and JNR necessarily share as well. As a normal Java application you don't really have a way to get around this.

See https://stackoverflow.com/questions/36298111/is-it-possible-...

> but it's annoying because now you need a tool chain everywhere.

You only need a toolchain for building, you can just ship the .so. These days you get pretty far with Linux 64bit, macOS 64bit and Windows 64bit.

One 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.

I 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.

Go 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_amd... [2] https://en.wikipedia.org/wiki/Duff%27s_device

This 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.

I 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".

pcmpxstrx 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).

What 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?

Sounds like a good idea to me. Seems similar to how GPUs work, which is generally a good path to follow.

Another excellent series on JVM perf/internals https://shipilev.net/jvm-anatomy-park/

> 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?

The feature is called "intrinsics", this claims to be a list: https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc

Interesting. 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?

They 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.

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.

Yeah, it was a sarcasm. The article (quoted in parent comment) called it a secret implementation.

I 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.

That version exists - it's called equals(), and it generates different code that doesn't need to distinguish the less than/greater than cases.

Of course, silly me, haven't touched Java for a while.

> 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?

What a lovely ready; I enjoy learning about the intricate details of the JVM. Thank you for sharing!

tl;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.)

Thanks 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.

Is there any place to get a proper manual of all these uses?

Agree 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.

Click here to discover that crazy instruction! C++ programmers HATE IT!!

(I am just ironizing about the title, the content is actually great!)

"You wouldn't believe what CRAZY instruction the JVM uses!"

Or even better (Yay for Betteridge!):

"Has the JVM found the ultimate string comparison solution in this CRAZY instruction?"

Yes indeed. We've un-clickbaited the title. Nothing is safe, it seems.

UTF-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:

Java uses UTF8 in latest release for strings without special characters.

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.

UTF-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)

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.

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 be any more mispredictions because of those being single bytes? These days code is so often bandwidth limited if anything, so smaller data helps.

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. Speculative execution (counting in two or three ways simultaneously) might mitigate the performance hit.

> 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?

You don't need to check the representation doing anything specifically with spaces or newlines. All 0x0A bytes are newline characters in UTF8 and all 0x20 bytes are spaces.

The only place you really need to decode UTF8 characters is when you convert it to another format (which you hopefully won't need to do anymore in the far future) or display it (where the decoding is a minuscule factor in performance)

> 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.

> A Chinese plaintext document in UTF-8 is still smaller in memory footprint than an equivalent English document in ASCII.

When you need to process Chinese text you don’t care how much an equivalent English document would take. You only care about the difference between different encodings of Chinese language. And UTF16 is more compact for East Asian languages.

> most documents aren't plaintext

That’s true for the web, and that’s why UTF8 is the clear winner there. In a desktop software, in a videogame, in a database — not so much.

> 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

So UTF-8 seems to be quite a bit more efficient in this case, 52678 bytes. When converted to UTF-16, same page was 93368 bytes.

Even in 2017, not everyone is a Web or Electron developer. I certainly am not.

I don’t advocate using UTF16 for the web, but people still code native desktop apps, mobile apps, embedded software, videogames, store stuff in various databases, etc. For such use, markup is irrelevant.

Even outside Web, you still have mostly-ASCII:

* filenames

* identifiers

* config files

* text protocols

* host names, email addresses

* embedded scripts (including SQL and OpenGL shaders)

* command line interfaces

* translations for languages using Latin alphabets

I don't think 2/3 size reduction for some languages will offset the cost in all the other places.

If English is your world yeah.

Some of us use other languages and like to use them everywhere we can.

For some of these things we don’t have much choice, because the encoding is part of some lower-level API (file system, OpenGL, CLI), which usually don’t accept arbitrary encoding. They accept only one, and unless you want to waste time converting, you better use that exact encoding.

Other stuff like IDs, shaders before GL 4.2, and many text protocols aren’t Unicode at all.

For configs I usually use UTF-8 myself, because I don’t like writing parsers for custom formats and just use XML, and any standard-compliant parser supports all of them.

> 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.

Java's String functions don't index by Unicode code points, though. Java strings are encoded in UCS-2, or at least the API needs to pretend that they are.

Right. Same in C#, C++ STL, and in Apple’s obj-c/swift.

Swift takes a different approach than Objective C[0].

[0] https://www.mikeash.com/pyblog/friday-qa-2015-11-06-why-is-s...

That can sure lead to interesting bugs!

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.

No, 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.

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.

V8 and JavaScriptCore do it, I believe.

Java 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

Python 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.

What about https://www.python.org/dev/peps/pep-0393/ ?

PEP-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.

Reply on news.ycombinator.com