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"
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.
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.
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.
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.
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.
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.
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.
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.
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"?
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.)
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.
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.
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.
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.
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.
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.
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.
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.
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
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
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
62 comments
[ 7.7 ms ] story [ 419 ms ] threadPCMPESTRI isn't for comparing C strings since it takes an explicit length. PCMPISTRI is the one for implicit (null-terminated) length.
"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"
Nonetheless, interesting article. I had no idea it could handle UTF-16!
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.
Why, i have no idea. My expectation would have been the same as yours
(also, it's pcmp* and tzcnt)
That said, even the comparisons you were showing look like they would add up pretty fast.
Though for all that it's still limited to simplistic comparisons of non-textual strings.
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.
Note that pcmpxstrx isn't really that fast in many cases compared to just doing ordinary SIMD operations.
This was a good article, though.
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...
I'm not even kidding: Notepad should die in a fire.
One problem is that I haven't found any handy tool that lets me just write and execute assembly without jumping through hoops.
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.
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.
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.
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.