8 ms·
How the JVM compares strings on x86
- faragon 10y agoAnd 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.
- astrange 10y agoLet me spoil the title - it's the SSE4.2 instruction dedicated to comparing C strings. Also, I had actually heard of it.
- masklinn 10y ago> 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.
- Someone 10y agoNot 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"
- TazeTSchnitzel 10y agoI 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!
- rcthompson 10y ago"Compare strings faster with this one weird x86 instruction!"
- avar 10y ago"ARM CPU vendors HATE HIM!"
- protomyth 10y agoAt 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.
- simcop2387 10y agoI wonder if the autotldr bot on reddit might be able to help with that.
- willismichael 10y agoBut then what happens when somebody writes a clickbait title about said expert system?
- brokenmachine 10y agoI HATE MYSELF! Bzz.. whirr click... Destroy all humans!
- protomyth 10y agoClearly your programming team needs this manager https://www.youtube.com/watch?v=d70OfGfMtIA https://www.youtube.com/watch?v=d70OfGfMtIA if you're thinking of releasing software that goes into "Destroy all humans!" mode.
- taeric 10y agoI would be interested to see speed comparisons to know how much this instruction helps. My gut would be that it helps. A lot.
- honkhonkpants 10y agoIn 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.
- DannyBee 10y agoFor 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 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.
- pcwalton 10y agoEdit: I'm stupid and this comment was totally wrong; see below.
- DannyBee 10y agoFWIW: 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)
- taeric 10y agoI 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.
- tyfon 10y agoI'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.
- gizmo686 10y agoIf the strings are not equal, they still need to say which string is "smaller" (eg. comes first alphabetically).
- tyfon 10y agoWell, that explains it! :)
- vkjv 10y agoThis is lexical comparison (<, >, =) not just equality.
- maggit 10y agoIn 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.
- stephencanon 10y agoJust 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.
- NegativeLatency 10y agothis does lexicographical comparison, not just equality
- masklinn 10y agoIt 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.
- stephencanon 10y agoIt's no faster at that either. You need to be doing something more interesting like prefix scanning for these instructions to be beneficial.
- cperciva 10y agoDefinitely 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"?
- deleted 10y ago[deleted]
- sctb 10y agoThanks, we've updated the title.
- stcredzero 10y agoFor 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.
- pcwalton 10y agoIt'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.
- stcredzero 10y agoThe 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.)
- qwertyuiop924 10y agoAm 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.
- brianwawok 10y agoI would be surprised if more than 5% of programmers in the world knew more assemble then 10 instructions. Maybe only 10% know even 1.
- mgr86 10y agoThis 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-McClanahan/dp/1568843062 https://www.amazon.com/PowerPC-Programming-Intel-Programmers...
- qwertyuiop924 10y agoOuch. 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.
- javier2 10y agoYeah, I didn't understand much of the gcc compile errors until I took a course in compilers...
- qwertyuiop924 10y ago
- Lorddigital 10y agoNeed 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
- Lorddigital 10y agoNeed 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
- Lorddigital 10y agoYou 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