> I know of no compiler that generates the Intel string instructions. Not even Forth!
Yes, because they are measurably slower than their equivalent primitive instruction sequences, and the space saved isn't really all that significant when you consider all the other loads and stores necessary to run them. I think they've been actually slower since either the 486 or Pentium days. I'm pretty sure, for instance, Watcom C++ would generate "rep movsd" sequences for memcpy back in the 386/486 days, back when it was actually an optimization to do so.
Actually I have to update my own comment here, due to a completely unexpected circumstance. I just happened to diassemble some 64-bit test code I wrote tonight (unrelated to testing out the string instruction theory) and lo and behold, Apple gcc-4.2.1 with -O3 turned memset(x, 0, 7*sizeof(uint64_t)) into a 3-byte "rep stos" instruction:
Ironically, the vast majority of "improvements" listed in the post (everything except using scasd) are algorithmic ones that are in fact doable in a compiled language.
And even special machine instructions seem quite achievable with a pattern-matching code generator.
Overall I think the HN title is very misleading - the article seems more "compilers don't do this well yet", definitely not "compilers can never do this".
You'd need dependent types and a compiler that understood exactly how much information in bits was required for a particular proposition, I'm guessing. I think this is the sort of thing (not using tricky assembly instructions specifically, but using unboxed types with expressive type systems) that makes languages like ATS[1] possibly faster than C.
The point is: good code generation is possible in theory, even if "sufficiently smart" compilers are too hard to write. (Or are equivalent to general A.I.)
It is not responsibility of a compiler to recognize specific problems in specific domains and perform optimizations, it is a job for a human programmer. Sure, you can make compiler aware of Riemann zeta function values in specific ranges, but what's the use of that outside of very specialized programs? Optimizations mentioned in the article could be programmed in C and compiler would happily translate these savings into assembly.
The reasons why we don't really program assembly anymore is that _on average and on a large scale_ compilers generate vastly better machine code than humans. Take for example register allocation problem which is proven to be NP-complete. Obviously compiler does an approximated algorithm but save for a case of few registers, no human can match it.
Some architectures, like VLIW, actually rely on the compiler to generate well-performing machine code.
> It looks like the Intel 8086 architecture and its descendents will be with us for ever ... Why not take advantage of every idiosyncrasy of that instruction set?
Also because you're permanently locking yourself to yesterday's speed.
> I know of no compiler that generates the Intel string instructions.
The x86 instruction set has over 20 years of cruft. There are entire sections on modern processors dedicated to handling weird addressing modes and complex CISC instructions that are unnecessary now. I don't know the specific reason why 'scasd' isn't generated when he wants it, but I do know that a lot of these special purpose instructions are often superseded by more powerful instructions less than a decade after they are introduced.
In fact, due to the unique awesomeness of x86, sometimes instructions are superseded by inferior instructions. My favorite is 'loop.' Most x86 loops are executed with two instructions -- decrement a counter and jump if not zero (dec/jnz). x86 has a 'loop' instruction that does this operation in one step, yet on modern processors (Athlon and up) it is at least 8 times slower than dec/jnz (http://crackthecode.us/amd64_opt/OptExperiment.html).
How could that be? Does 'loop' handle some edge case or trigger some crufty microcode that slows things down? Nope. Windows 98 relied on the 'loop' instruction for hard-coded timing loops in drivers. The k6-2 executed these very efficiently, and as the processor hit 350 mhz the speed of the processor triggered race conditions making Windows 98 crash. Consumers obviously found fault with AMD for making a chip that was too good, so loop was artificially slowed in the Athlon (and all processors afterward) forever crippling a perfectly good instruction. A wily assembly programmer optimizing for a k6-2 would have dramatically slower execution on tight loops for no good reason.
Processors get tuned for the code that runs on them, and the code that runs on them is generated by compilers which have generally broken down high-level operations into low-level operations to seek out other kinds of optimization opportunities. Idiosyncratic opcodes end up as backwaters because so few general-purpose back ends can target them in broad scenarios. So they receive less focus from chip manufacturers, and their original purpose gets lost; they often end up slower than a handful of the simpler opcodes.
Additionally, the 8086 is not much like the 386! And the 386 isn't much like the 486, which differed surprisingly from the Pentium. And each subsequent revision has followed this trend of being (at the very least) different enough from its predecessors that assembly language programmers need to re-read the manuals.
Today we even have a 64-bit version, which differs from its trail of 32-bit ancestors even more than they differed from one another...
If there is one lesson that people in this industry should have learned by now, it is, "never say forever". Or 640Kb of RAM still would have been enough for anybody.
Like what? I have some experience with ARM assembly, and found it refreshingly simple compared to x86. All registers are handled in the same way, and instructions are very regular.
There are fewer instructions and most importantly, every instruction can be used, there are no 'cruft, don't use! slow and old' instructions like in x86.
I'm sure he agrees that algorithmic improvements are more effective than constant-factor improvements like optimizing the assembly code. I think he'd also agree that algorithmic improvements are also easier to make in higher-level languages than in assembly. I'd argue, then, that it's more worth your time to spend your time iterating and squeezing as much algorithmic optimization of the higher-level program, than squeezing as much assembly optimization out of x86 as you can.
There is the case that there is a solution is known to be algorithmically optimal, or there is only one leading contender for optimal and it's unlikely to be toppled and you have to have a PhD and a couple postdocs in theoretical CS to begin to approach a way to challenge it, in which case it would indeed be more worth your time to optimize the assembly code. I hear Adobe Photoshop uses an FFT written in optimized assembly because almost every CPU-intensive thing they do uses it. Has he taken a gander at that? Pretty sure the fastest known way to calculate prime numbers changes a couple times a year.
However, that is only the case with textbook CS problems, and I think most HN members would agree that in industry, software engineering is almost never actually about solving textbook problems, and tends to have quirks that lead to clever algorithmic optimizations that are continually being discovered.
> The current vogue among computer users is to get
> as far from the real hardware as possible.
> ...
> Assembly is the epitome of using the features of
> a given machine.
But what about the features of a particular language? Mucking in assembly is great if you're trying to squeeze out every ounce of power, but it's much too verbose for building complex systems. If you're trying to build user-facing features, layers and layers of language abstraction is great. See http://www.paulgraham.com/hundred.html
If you're building a prime-number generator, go ahead and write in assembly. But if you're writing an application, like most of us on here (I assume?), use a high-level language. "[Taking] advantage of every idiosyncrasy of [the] instruction set" is a waste of time.
Compilers have been written which (for tiny microbenchmarks like this one) search every possible machine code sequence to find the fastest. Of course they take absolutely forever to run, but they do exist.
That was quite an arrogant post that really seemed to miss the forest for the trees. Sure, perhaps you can build a faster prime number generator in assembly, but you'll never build a better application in assembly (where better is defined as feature rich, secure, etc), and that's what the job is about.
Absolutely! But performance in most applications is not determined at the bit level. Most apps performance needs are met at the architectural level (prevent blocking on whatever). Fewer apps performance needs are met at the algorithmic level (O(log n) is much faster than O(n log n)). It is a rare app that finds it's performance requirements in the ops and bits (Highly math-centric apps. Others exist, I'm sure).
I've generally found that's the order I go in meeting performance requirements. When I've failed to meet those requirements, I've generally worked backwards up the list, with each step getting more expensive in an exponential fashion.
"Abstract - People often write less readable code because they think it will produce faster code. Unfortunately, in most cases, the code will not be faster. Warning: advanced topic, contains assembly language code."
Articles on how fast some program is, with no benchmarks, are not that persuasive. Especially since it's based mostly on the claim that "no compiler would do that".
Actually, if you're using a higher level language you stand a chance of implementing a much faster algorithm which would trump any of these O(1) speed-ups.
Machines and CPU time are cheap...at least compared to the price of hiring additional programmers to maintain the mess of assembly code you just wrote.
Assembly code doesn't need to be a mess. Usual rules apply - you can write a mess in any language, much as you can write well structured code in any language.
Obsessive micro-optimization obscuring the function of code is always a mess.
You are correct that the mess is language agnostic. For example, if he'd attempted to discard the low order bit of his prime numbers in C, it would result in the same awful maintenance.
Some optimizations waste too much programmer time to be worth tackling. Distorting the meaning of code for some tiny performance gains never constitutes "well-structured" code.
Optimisation is not the same as programming. You can program in Assembly without trying to make your code as performant as possible. Just because you use Assembly as your medium of describing your intent, doesn't mean that you're obsessive about micro-optimisation.
Maybe I am missing something but all the optimizations in this article except the xor (2) and the scasd (4) can be done in high level programming languages.
Number 3 (output of a sequence of integers as the sequence of differences between consecutive elements) is a very common optimization for inverted indexes formats, IIRC lucene, written in java, does it.
I actually think this is a subtle parody of the "Scala/Haskell/Java/Ocaml is impractical because you can't write performant code in it" crowd.
On tiny and contrived micro-benchmarks, it's nearly impossible for a (non-contrived) expressive language to beat less expressive languages like machine code, X86 assembly, or C. For real, large software projects, the case for a less expressive language is not nearly as convincing, because the shortcomings of the language mean that programmers aren't able to write the same quality of code. For example, compare the outright mess that is concurrency in C or Java to the much easier concurrency available in more expressive languages. As parallelism becomes far more important for people who need high performance (yes, I know concurrency and parallelism aren't exactly the same thing, but they're similar) this advantage of the less expressive languages is likely to diminish, if not disappear outright.
[Edit: Added-- This is analogous to the static/dynamic typing debate. Dynamic typing test drives extremely well but multi-developer projects in dynamically typed languages usually turn into outright nightmares, due to problems around interfaces. Static typing's better for large projects. Same with expressive languages: assembly's going to win on microbenchmarks, but writing good code in less expressive languages becomes impossible as the size and scope of the project gets large.]
Yes, because they are measurably slower than their equivalent primitive instruction sequences, and the space saved isn't really all that significant when you consider all the other loads and stores necessary to run them. I think they've been actually slower since either the 486 or Pentium days. I'm pretty sure, for instance, Watcom C++ would generate "rep movsd" sequences for memcpy back in the 386/486 days, back when it was actually an optimization to do so.