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 :)
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
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.
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.)
> 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.
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.
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".
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?
> 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?
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.
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.
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.
> 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?
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.
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.
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:
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.
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.
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)
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.
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.
> 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.
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.
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.
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.
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.
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)
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.
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.
It 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.
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.
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