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

Re: How the JVM compares strings on x86 using pcmpestri

#41

Post by Const-me » Sun, Jan 07, 2018, 5:50 PM UTC

jcranmer wrote: post #36

Const-me wrote: post #33

Earlier quoted context omitted.

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

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

Re: How the JVM compares strings on x86 using pcmpestri

#42

Post by Const-me » Sun, Jan 07, 2018, 5:54 PM UTC

vardump wrote: post #37

Const-me wrote: post #33

Earlier quoted context omitted.

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

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

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.

Re: How the JVM compares strings on x86 using pcmpestri

#43

Post by Ded7xSEoPKYNsDd » Sun, Jan 07, 2018, 6:10 PM UTC

vardump wrote: post #37

Const-me wrote: post #33

Earlier quoted context omitted.

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

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

Re: How the JVM compares strings on x86 using pcmpestri

#44

Post by vardump » Sun, Jan 07, 2018, 6:12 PM UTC

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.

Re: How the JVM compares strings on x86 using pcmpestri

#45

Post by Const-me » Sun, Jan 07, 2018, 6:21 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.

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

Re: How the JVM compares strings on x86 using pcmpestri

#46

Post by pcwalton » Sun, Jan 07, 2018, 6:48 PM UTC

userbinator wrote: post #39

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

Re: How the JVM compares strings on x86 using pcmpestri

#47

Post by pcwalton » Sun, Jan 07, 2018, 7:11 PM UTC

kevingadd wrote: post #35

vardump wrote: post #23

Earlier quoted context omitted.

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

V8 and JavaScriptCore do it, I believe.

Re: How the JVM compares strings on x86 using pcmpestri

#48

Post by banthar » Sun, Jan 07, 2018, 7:33 PM UTC

Const-me wrote: post #42

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

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.

Re: How the JVM compares strings on x86 using pcmpestri

#49

Post by tjalfi » Sun, Jan 07, 2018, 7:37 PM UTC

Const-me wrote: post #45

Ded7xSEoPKYNsDd wrote: post #43

Earlier quoted context omitted.

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

Re: How the JVM compares strings on x86 using pcmpestri

#50

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

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.