How the JVM compares strings on x86 using pcmpestri • Hacker News Board

Re: How the JVM compares strings on x86 using pcmpestri

#51

Post by BeeOnRope » Sun, Jan 07, 2018, 7:42 PM UTC

djsumdog wrote: post #28

kaeluka wrote: post #8

Earlier quoted context omitted.

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.

Re: How the JVM compares strings on x86 using pcmpestri

#52

Post by BeeOnRope » Sun, Jan 07, 2018, 7:46 PM UTC

pcwalton wrote: post #47

kevingadd wrote: post #35

Earlier quoted context omitted.

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 deskto…

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

Re: How the JVM compares strings on x86 using pcmpestri

#53

Post by quotemstr » Sun, Jan 07, 2018, 8:27 PM UTC

lvh wrote: post #40

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

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.

Re: How the JVM compares strings on x86 using pcmpestri

#54

Post by banthar » Sun, Jan 07, 2018, 8:42 PM UTC

maxerickson wrote: post #24

frik wrote: post #3

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:

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.

Re: How the JVM compares strings on x86 using pcmpestri

#55

Post by burntsushi » Sun, Jan 07, 2018, 8:57 PM UTC

pcwalton wrote: post #38

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 instru…

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.

Re: How the JVM compares strings on x86 using pcmpestri

#56

Post by bdonlan » Sun, Jan 07, 2018, 9:22 PM UTC

quotemstr wrote: post #53

lvh wrote: post #40

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

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…

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.

Re: How the JVM compares strings on x86 using pcmpestri

#57

Post by vardump » Sun, Jan 07, 2018, 9:25 PM UTC

BeeOnRope wrote: post #50

vardump wrote: post #44

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 co…

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.

Re: How the JVM compares strings on x86 using pcmpestri

#58

Post by vardump » Sun, Jan 07, 2018, 9:27 PM UTC

Ded7xSEoPKYNsDd wrote: post #43

vardump wrote: post #37

Earlier quoted context omitted.

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

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

That can sure lead to interesting bugs!

Re: How the JVM compares strings on x86 using pcmpestri

#59

Post by quotemstr » Sun, Jan 07, 2018, 9:39 PM UTC

bdonlan wrote: post #56

quotemstr wrote: post #53

Earlier quoted context omitted.

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…

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

Re: How the JVM compares strings on x86 using pcmpestri

#60

Post by saagarjha » Sun, Jan 07, 2018, 9:42 PM UTC

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