How the JVM compares strings on x86 | Hacker News Reader

How the JVM compares strings on x86

jcdav.is

142 pointsjcdavis60 comments

Am I seriously the only person on HN who doesn't know x86 backwards and forwards? Because it seems from the comments like I'm the only one here that didn't know this.

This was a good article, though.

I would be surprised if more than 5% of programmers in the world knew more assemble then 10 instructions. Maybe only 10% know even 1.

This reminds me of a (not so interesting) story.

In about 1997 I was really into hanging out in yahoo chat rooms and making websites. I was 11. I asked for a book on computer programming. I wanted to do something more than hack away at the perl scripts that ran my guest book. Neither my father or I really knew what I was asking. I received a nice book on PowerPC programming [0]. If I recall it read like assembly.

I still have the book on my bookshelf at home. I may have gotten 10% way through that book. It was quickly replaced with Sam's teach yourself perl in 24 hours.

[0]: https://www.amazon.com/PowerPC-Programming-Intel-Programmers...

Ouch. I tried to learn C as a first language. The language isn't so bad... but the compiler errors are. Thanfully, I settled on Python.

Yeah, I didn't understand much of the gcc compile errors until I took a course in compilers...

GCC: Great compiler, terrible feedback.

I lost the lotto with teach yourself Java in 24 hours. I did not learn anything in 24 hours. Notepad is a terrible IDE.

Anybody who actually recommends Notpad as a programming tool in a serious conversations deserves unbearable agony for the subsequent week. Because that's what they just set up somebody else for.

I'm not even kidding: Notepad should die in a fire.

You only need to know one: subtract and branch if <= 0.

https://twitter.com/FredericJacobs/status/770027539284758528

You're not the only one. I know a tiny bit of x86, enough to read some short snippets, but my eyes glaze over at something as long as this.

One problem is that I haven't found any handy tool that lets me just write and execute assembly without jumping through hoops.

Well, you don't need to know all of asm to write it. You don't need to know this strcmp instruction.

As for convenient writing and execution of assembly, it depends on how low-level you want to go. You can write x86 asm on top of your unix or windows system relatively simply: Just write asm, and compile it with GAS/MASM/NASM/TASM/YASM. You'll need to know instructions, assembler syntax, and your OS's system call mechanism, as well as the calling conventions for any static or dynamic libraries you plan to use (except on systems where syscalls are not a formally exposed stable interface, like Solaris, where you only need learn the calling conventions for libraries). If you're utterly lost, and running Linux, I would recommend the excellent "Programming From The Ground Up," which is freely available online.

If you want to write atop the bare metal, with no OS, an emulator is your best bet. Virtualbox or QEMU both work, but whatever you pick, it'll be a bit of a pain to work with.

rule #1 about Hacker News:

ALWAYS make sure you comment to let people know how smart you are. This is IMPERATIVE.

...even if you have to Google it a bit to brush up, always come back to let people know that you are knowledgeable.

...you know, that explains a lot...

You might say this facetiously, but this is would lead to some very informative comments, right?

I disagree. If you never reveal a lack of knowledge, than you'll never learn anything from the conversation: some of my best experiences on HN were times I was totally wrong.

Probably people don't bother posting if they don't already know. Harder to show off if it's something you don't know about.

CPUs have gotten so complex that mastering their language (and behavior) is a skill on its own. Most people can get on with compiled/interpreted languages.

I agree with the "most people" part. On a tangential note, While it's true that nobody can be expected to master and write a large and well performing application in assembly language anymore (or better than a compiler could optimize it), there's something to be said for learning the deepest and most basic building blocks (ok, if we have to go even deeper, then learning the actual opcodes for assembly language instructions). IMO, it makes it easier to understand many higher level concepts as well as different kinds of technologies (the latter to some extent). This in turn helps with different kinds of thinking when designing and debugging a program written in a high level language. Something similar could be said for "closer to the machine" languages like C.

Additionally, for those interested in the area of software security, this is a very useful layer to know well about, even if one has learned assembly language in another (popular) processor family. Knowing what features processors provide (like the support for virtual memory, among other things), and how they work, are also quite useful.

This is a fundamental distinction between true geeks who grew up hacking 6502, Z80, 68000 etc etc, and wannabes who jumped on the bandwagon later and think Javascript is "low level"...

No, it's not. It's a fundamental distinction between those who have learned to operate at that level, and those who haven't. That is it. People who started out on HLLs can gain those skills, because it's ultimately just another paradigm.

Saying those of us who didn't grow up on asm aren't true geeks rings of No True Scotsman to me.

In addition, just because we weren't born a decade earlier doesn't mean we think JS is low level. That's just a flat-out mischaracterization.

Don't sweat it. If you were maintaining a VM you'd also know this stuff.

What VM are you maintaining? Just curious...

Sorry, didn't mean to imply I was. I just didn't want you to judge yourself too harshly. The OP works on OpenJDK, deep diving into the JIT, JNI, etc. If you did similar work, you'd also likely know x86 much better.

I saw “the x86 instruction you've never heard of” and thought, hey, it's probably the SSE strcmp instructions. So, the title is clickbait.

Nonetheless, interesting article. I had no idea it could handle UTF-16!

"Compare strings faster with this one weird x86 instruction!"

"ARM CPU vendors HATE HIM!"

At some point, someone is going to write the most popular plug-in ever that rewrites all titles in clear language and does a quick fetch of the page to answer the questions posed by the title. That's the kind of expert system I'm looking for.

I wonder if the autotldr bot on reddit might be able to help with that.

But then what happens when somebody writes a clickbait title about said expert system?

I HATE MYSELF! Bzz.. whirr click... Destroy all humans!

Clearly your programming team needs this manager https://www.youtube.com/watch?v=d70OfGfMtIA if you're thinking of releasing software that goes into "Destroy all humans!" mode.

For awhile, CISC architectures (basically, just "architectures" before RISC came around) kept accumulating features. I took a VAX assembly language ("VAX Macro") class, and I remember that there was a string compare command in VAX Macro that was about as full featured as what you'd expect in some kind of standard library.

So I'm not surprised to learn that there's something in an Intel architecture like this: Intel is just showing its CISC roots. Since it's associated with SSE, there's probably something advantageously parallel about it.

It's really more about SIMD than about CISC or RISC. The pcmpxstrx family of instructions aren't like classical CISC string-compare instructions (though note that those are there too—"repe cmps"). Rather, they take 16-byte registers and perform operations (find first byte matching X, etc) on the bytes in them. I imagine that they can take advantage of effectively map-reduce style techniques for this (which is what you would do in software too if you were using simpler SIMD instructions).

Note that pcmpxstrx isn't really that fast in many cases compared to just doing ordinary SIMD operations.

The string compare operations built into old CISC architectures also weren't that fast. It's more like they were designed as bullet points for the salesmen. (Who were talking to execs who remember managing people who wrote things in assembly.)

Let me spoil the title - it's the SSE4.2 instruction dedicated to comparing C strings. Also, I had actually heard of it.

> it's the SSE4.2 instruction dedicated to comparing C strings.

PCMPESTRI isn't for comparing C strings since it takes an explicit length. PCMPISTRI is the one for implicit (null-terminated) length.

Not only C strings; this code uses the Pascal string variant:

"This monster of an instruction takes in 4 registers of input: the 2 strings themselves as parameters, plus their lengths in %rax and %rdx (‘e’ meaning explicit length - pcmpistri & pcmpistrm instead look for terminating nulls"

You ever been hacked ? or You wanna hack someone or anything? You wanna test the protection strength of your website, computer or network ? Do you wanna hack into a computer, website or network? Social Media Threats Has your Facebook, Twitter or Google+ account .He can help get it restored and track the person who did it in many cases. Computer Spying and Surveillance. Do you want to install spyware on a cellphone or computer? Do you want to know if you have spyware on your computer? Bank account transfer to all Banks.......Hack and upgrade or change university grades Bank accounts hackErase criminal records hack Facebook, hack Any social media account, hack Android & iPhone Hack.....Text message interception.. hack email interception, hack Untraceable IpTwitters, hack email accounts, hack (Grade Changes), restore crashed Website, hack servers, hack Skype, hack Databases, hack Word Press & Blogs, hack Individual computers, hack Control devices remotely, hack Burner Numbers, hack Verified Paypal Accounts. I am a hacker looking for some one who got old bank account in usa and i wil load it with 4k to 40 k we share 5050 no upfront fee. I need BOA, USA navy chase, welsfargo, retirement account old bank account asap no upfront fee 5050......emaIL ME Lorddigital.hacker@gmail.com

I'm actually wondering why they do not compare the lengths first, anyone know? To me that would seem like the first obvious optimization, do not run the character compare at all if the lengths are different.

If the strings are not equal, they still need to say which string is "smaller" (eg. comes first alphabetically).

Well, that explains it! :)

This is lexical comparison (<, >, =) not just equality.

In addition to what has been said about lexicographic ordering, if the strings are large, say several kB (as they may well be), the entire operation would be dominated by memory latency. In this case it is much cheaper to read each string once, instead of going an extra pass just to find the length.

These are not null-terminated strings; it's not necessary to read the whole string to find its length.

Ah, sorry, my bad. There is so much talk about null-terminated strings here, and I had only skimmed the article. Whoops :P

Need a hacker? A senior member of icefog hackers.A professional in the areas mentioned below: 1.facebook,whatsapp,emails,twitter and instagram hack 2- Hacking computer system 3- Cloning of phones 4- Changing DMV records without leaving traces 5- Changing school grades without leaving traces 6- Retrieving hacked social media accounts 7- Credit card hack 8- Clearing criminal records 9- Clearing of bad driving records without leaving traces 10- Website hack 11- Retrieving hacked social media accounts 12- P.I - Private investigator like cheating husbands or wives and any other P.I activities and so many other services. 13- Catch hacker scammers 14- Wire transfer to any bank 15- Retrieval of hacked accounts (facebook,twitter,instagram,zoosk,match etc..) 16- Bank login 16- Phishing emails. to mention a few..He is at your service if you need him. Contact .Email- lorddigital.hacker@gmail.com.. BEWARE OF FAKE HACKERS..TAKE RECOMMENDATIONS AND GO FOR IT

Just doing simple SIMD compares is as fast on most microarchitectures, and faster on Haswell+. You need to be doing something more involved than simple equality testing for the SSE4.2 instructions to be beneficial.

this does lexicographical comparison, not just equality

It can do more than just string equality too (the first operand can be treated as a character sequence, a character set, a substring needle or a union of character ranges)

Though for all that it's still limited to simplistic comparisons of non-textual strings.

It's no faster at that either. You need to be doing something more interesting like prefix scanning for these instructions to be beneficial.

And not just string compare. There are many operations where general purpose CPUs have problems for giving optimum results when operating with elements of 1 or 2 bytes at once with dependencies between them. E.g. UTF-8 string search implemented in hardware using the Rabin-Karp algorithm with a simple enough reversible hash window guarantying O(n) time could outperform current string search optimal O(n) implementations by e.g. 16x on CPUs with 128 bit / cycle load capabilities.

I would be interested to see speed comparisons to know how much this instruction helps. My gut would be that it helps. A lot.

In my experience it doesn't. I don't think any of the open source C/C++ libraries use it. Also you really need a machine-specific routine because the early machines that offered this instruction did so very slowly. Only in later Intel parts was SSE4.2 worth using.

For short strings, it basically doesn't help. For longer strings, it's a bit faster, it depends how bad what you were doing before was.

Straight string comparison is not a great application for this in part because it's to intel's advantage to make string compare loops work fast without it.

But you can be sure it speeds some customer's serious workload up significantly. That said, it all depends.

It's great for "figure out if there is newline in the next 16 characters".

But again, compared to basic SSE compares, it often falls down for random string comparison.

See, e.g, https://www.strchr.com/strcmp_and_strlen_using_sse_4.2 which has timings on core i5.

it's of course, likely possible to find processors where it is faster/slower.

Edit: I'm stupid and this comment was totally wrong; see below.

FWIW: it actually does. i measured it in clang :)

Why, i have no idea. My expectation would have been the same as yours

(also, it's pcmp* and tzcnt)

I think my biggest misunderstanding was thinking in terms of the size of strings that this compares. Seemed somewhat silly to think about comparing really small strings. Though, actually thinking about it, that makes a ton of sense. You rarely compare strings at the same level that you multiply a large matrix.

That said, even the comparisons you were showing look like they would add up pretty fast.

Definitely a clickbait title... dang, can you edit this down to "How the JVM compares strings" or possibly "Comparing strings using the x86 SSE4.2 pcmpestri instruction"?

Thanks, we've updated the title.

Reply on news.ycombinator.com