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

Re: How the JVM compares strings on x86 using pcmpestri

#11

Post by oblio » Sun, Jan 07, 2018, 11:49 AM UTC

zakk wrote: post #5

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

Re: How the JVM compares strings on x86 using pcmpestri

#12

Post by ghusbands » Sun, Jan 07, 2018, 11:59 AM UTC

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

Re: How the JVM compares strings on x86 using pcmpestri

#13

Post by r4um » Sun, Jan 07, 2018, 12:10 PM UTC

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

Re: How the JVM compares strings on x86 using pcmpestri

#14

Post by lmm » Sun, Jan 07, 2018, 12:19 PM UTC

RyanZAG wrote: post #10

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:

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)

Re: How the JVM compares strings on x86 using pcmpestri

#15

Post by oblio » Sun, Jan 07, 2018, 12:20 PM UTC

RyanZAG wrote: post #10

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:

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.

Well, not necessarily a curse, but a suboptimal solution. Are there any situations where UTF16 is a clear upgrade over UTF8?

Re: How the JVM compares strings on x86 using pcmpestri

#16

Post by nwellnhof » Sun, Jan 07, 2018, 12:26 PM UTC

RyanZAG wrote: post #10

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:

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.

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.

Re: How the JVM compares strings on x86 using pcmpestri

#17

Post by amelius » Sun, Jan 07, 2018, 12:50 PM UTC

ghusbands wrote: post #12

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.

Re: How the JVM compares strings on x86 using pcmpestri

#18

Post by dullgiulio » Sun, Jan 07, 2018, 12:53 PM UTC

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

Re: How the JVM compares strings on x86 using pcmpestri

#19

Post by B4TMAN » Sun, Jan 07, 2018, 1:00 PM UTC

amelius wrote: post #17

ghusbands wrote: post #12

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?

Re: How the JVM compares strings on x86 using pcmpestri

#20

Post by Const-me » Sun, Jan 07, 2018, 1:10 PM UTC

oblio wrote: post #15

RyanZAG wrote: post #10

Earlier quoted context omitted.

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.

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.