Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How the JVM compares strings on x86 using pcmpestri

jcdav.is

Post reply on HN
Print view View original

21–30 of 73 posts

Re: How the JVM compares strings on x86 using pcmpestri

#21

Post by vardump »

Const-me wrote: post #20
oblio wrote: post #15

Earlier quoted context omitted.

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.

Re: How the JVM compares strings on x86 using pcmpestri

#22

Post by rplnt »

nicoulaj wrote: post #9
exikyut wrote: post #6

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

Re: How the JVM compares strings on x86 using pcmpestri

#23

Post by vardump »

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:

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

Re: How the JVM compares strings on x86 using pcmpestri

#24

Post by maxerickson »

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

Re: How the JVM compares strings on x86 using pcmpestri

#25

Post by HelloNurse »

vardump wrote: post #21
Const-me wrote: post #20

Earlier quoted context omitted.

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

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.

Re: How the JVM compares strings on x86 using pcmpestri

#26

Post by vardump »

HelloNurse wrote: post #25
vardump wrote: post #21

Earlier quoted context omitted.

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

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?

Re: How the JVM compares strings on x86 using pcmpestri

#27

Post by legulere »

HelloNurse wrote: post #25
vardump wrote: post #21

Earlier quoted context omitted.

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

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.

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)

Re: How the JVM compares strings on x86 using pcmpestri

#28

Post by djsumdog »

kaeluka wrote: post #8
exikyut wrote: post #6

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

Re: How the JVM compares strings on x86 using pcmpestri

#29

Post by brianon99 »

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

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.
Post reply on HN