20 ms·
Why is this C++ code faster than my hand-written assembly (2016)
- barrkel 9y agoThis was a borderline help vampire question, but it ended up working out well, probably for nerd-sniping reasons.
- propublica 9y agoOur AI has detected meanness. Please only post substantive comments or not at all. Report to the nearest reeducation camp of your choice.
- abainbridge 9y agoA couple of weeks ago I'd never heard of Peter Cordes. Now the linked article is the third time I've seen his work. He's doing a fine job of fixing Stackoverflow's low-level optimization knowledge. Not so long ago all I seemed to find there was people saying something like, "well, you shouldn't optimize that anyway", or, "modern computers are very complex, don't even try to understand what's happening".
- fhood 9y ago> "modern computers are very complex, don't even try to understand what's happening" I live my life by that adage
- mark-r 9y agoIf I ever see Knuth's quote "premature optimization is the root of all evil" in response to a question again, I think I'll puke. Not only is it hard for outsiders to know what's premature and what isn't, but sometimes it's nice to make a habit of doing things the faster way when you have two choices that are otherwise indistinguishable. For example I try to use ++x instead of x++, even though 99% of the time it makes no difference.
- ww520 9y agoAh, hindsight is 20/20. It's easy to criticize premature optimization after the fact.
- santaclaus 9y ago> For example I try to use ++x instead of x++ ++x can be slower, depending on the context -- it introduces a sequence point.
- mark-r 9y agoReally? If you have the time, I'd love an explanation. Or if you can point to some other resource that would be great too.
- santaclaus 9y agoI remember seeing a blog post from Andrei Alexandrescu that I can't seem to dig up, but this SO post seems to be a nice summary [1]. In short, in 99.9999999% of usages post increment is probably better. [1] https://stackoverflow.com/a/38947878 https://stackoverflow.com/a/38947878
- mark-r 9y agoThanks. I guess I'm applying this rule only when the result of the increment isn't being used directly, so there is no dependency on the operation. When the result is used, the semantic difference between ++x and x++ obviously determines the choice.
- deleted 9y ago[deleted]
- flamedoge 9y agoJust look at the liveness of the expression x+1. post-increment means expression has to be alive before whatever uses '++x' whereas pre-increment can delay until next usage of x.
- 9y ago
- jdcarter 9y ago> "modern computers are very complex, don't even try to understand what's happening" One thing to keep in mind is that the CPU is no longer the CPU you think it is. While the x86 instruction set used to directly control the processor, today it's just a compatibility shim. Under the covers, the CPU is converting your assembly into its own microcode and it's that microcode which is doing the real work. For example, look at some of the block diagrams in section 2 of this Intel manual: https://software.intel.com/sites/default/files/managed/a4/60/253665-sdm-vol-1.pdf https://software.intel.com/sites/default/files/managed/a4/60... Combine that with all kinds of other voodoo they've added--fancy caches, branch prediction, and so forth--and the "don't even try" maxim starts to make sense. I'd amend that to say "don't even try unless you're just curious." Personally, I think assembly is a great learning tool, e.g. for understanding how pointers work, how the stack works vs. the heap, how function calls work, and so-forth. I was exposed to Motorola 68K assembly in college and it completely changed my world--lots of C++ things I considered voodoo suddenly made total sense. But I've never used assembly in production code and probably never will.
- dws 9y agoThe CPU is no longer the CPU that the CPU designers (often) think it is. A few years back someone who worked on CPUs at Intel related how his group pulling their hair out trying to characterize how a small section of code in a loop could have wildly different performance characteristics depending on the preceding instructions.
- mark-r 9y agoThe Motorola 68K was nearly ideal for assembly programming. You're lucky to have learned on it.
- jdcarter 9y agoOh very much so, 68K was great. Even better, at my first job we had a custom 68K-based embedded device and no source-level debugger, so you could only debug in assembly. That reinforced everything I had learned just a few years before. Our next device was MIPS-based, and MIPS was a great RISC system to learn on. I count myself very blessed.
- setzer22 9y ago> Not so long ago all I seemed to find there was people saying something like, "well, you shouldn't optimize that anyway I find this "Why would you even do that?" attitude in StackOverflow to be very irritating. And it's not just in low-level optimization questions. StackOverflow should be a place for questions and answers, not a collection of lessons on corporate best practices where curiosity and experimentation is discouraged.
- jimmaswell 9y agoI've had the same annoyance in IRC channels - getting an unhelpful lecture on the right way to do things from people who don't fully understand the use case or that "best practices" might not always be worth it or matter, especially in a small script/application
- ryandrake 9y agoI agree. Programming forums are full of this crap. I hate asking a pretty straightforward question online and getting that patronizing "But what are you really trying to do?" response. What I'm really trying to do is get an answer to this specific question. I'm not asking you to re-think my problem statement. Thanks for not helping.
- eXpl0it3r 9y agoAt the same time we're getting a lot of people with XY-problems. They think they know what the problem is and they think they know what they about have to do, while the real problem is somewhere else. If someone's intend with an asked question isn't clear, then "But what are you really trying to do?" is a valid question. It's impossible for anyone to just know what you're intentions are and whether you understand the deeper semantics of a problem. More often than not, people try to do things for the wrong reasons.
- colomon 9y agoI dunno, I've been on both sides of this. I agree it's really annoying when someone waltzes around without answering my question. But I've also seen people asking questions which sounded goofy to me, and when you finally get them to tell you want they are actually trying to do, there's a much easier and more direct approach.
- bjoli 9y agoI know is it is not the point of the question, but that problem would benefit greatly from memoization. Calculate it recursively and memoize the result of every step. With all the neat trickery that they are doing with assembly they could easily go sub 10ms. I whipped together a short poc in chezscheme, and it clocks in at about 50ms on my 4 yo laptop.
- Veedrac 9y agoWhen everything is in cache and you're calculating sequentially, definitely, but equally why not just precompute the whole range and do a binary search? Once you're looking for better algorithms the whole problem just falls away! That said, I do think it's neat that the fastest brute-force variant is a rough factor-2 from your naïve memoized version. It might even win if it was fighting a hyperthread for cache space! Just shows how much throughput modern CPUs have... if only they were used this well all the time ;).
- bjoli 9y ago> That said, I do think it's neat that the fastest brute-force variant is a rough factor-2 from your naïve memoized version. My naive memoized version in a GCd language that is consistently 4-5x slower than my own (pretty bad) C versions of the same project Euler problems without any of the tricks the fastest C++ version is doing. Still pretty impressive considering most solutions in the project euler forums take more than 1s.
- shoo 9y ago> but equally why not just precompute the whole range and do a binary search? what do you mean?
- Veedrac 9y agoThe code finds the longest Collatz sequence below N, where N is a 32-bit integer. There are only ~1k longest sequences possible, so just list them all. Given N, search for the largest N below that and return its corresponding iteration count.
- elcapitan 9y agotldr: compiler replaces /2 with a shift.
- bluedino 9y ago>> Have you examined the assembly code that GCC generates for your C++ program? A very polite way of saying, "why are you even using assembly, when you don't understand assembly?"
- eterm 9y agoAnd why wouldn't they be polite? The OP clearly does understand assembly enough to start doing project Euler type problems, which is a good way to learn basic programming in any language. They get a solution in assembler which is more than many people here would be able to do I suspect. And they're looking to expand their knowledge by asking on stack-overflow about something they don't understand. So why do you think they should they be met with rudeness and hostility?
- marsRoverDev 9y agoBecause apparently it's a rite of passage / hazing ritual to go on IRC / stackoverflow and be flamed for asking simple questions. It's been that way since the dawn of time.
- bshimmin 9y agoThe ritual isn't really complete until someone has complained about the people complaining about people asking simple questions and someone else has posted the ESR document about how to ask smart questions, a document so astonishingly, vastly patronising that it probably ought to be compulsory reading for every developer starting out, with the addendum, "If you've made it all the way through this soul-crushing drivel, congratulations! It can't get worse than this!"
- deleted 9y ago[deleted]
- godelski 9y agoSome rituals are meant to die.
- raphlinus 9y agoApologies if this is somewhat off-topic for the thread, but I suspect this will be a fun puzzle for fans of low-level optimization. The theme is "optimized fizzbuzz". The classic fizzbuzz will use %3 and %5 operations to test divisibility. As we know from the same source as OP, these are horrifically slow. In addition, the usual approach to fizzbuzz has an annoying duplication, either of the strings or of the predicates. So, the challenge is, write an optimized fizzbuzz with the following properties: the state for the divisibility testing is a function with a period of 15, which can be calculated in 2 C operations. There are 3 tests for printing, each of the form 'if (...) printf("...");' where each if test is one C operation. Good luck and have fun!
- dmitrygr 9y ago#define FIZZ 1 #define BUZZ 2 static const uint8_t divs[] = {FIZZ+BUZZ,0,0,FIZZ,0,BUZZ,FIZZ,0,0,FIZZ,BUZZ,0,FIZZ,0,0}; static const char* strs[] = { [0] = "%u\n", [FIZZ] = "fizz\n", [BUZZ] = "buzz\n", [FIZZ+BUZZ] = "fizzbuzz\n" }; void fizzbuzz(uint32_t upTo) { uint32_t i, state; for(i = state = 0; i < upTo; i++) { printf(strs[divs[state]], i); if(++state == sizeof(divs) / sizeof(*divs)) state = 0; } No divisibility tests at all One level of arrays may be skipped at cost of extra .rodata size (store string pointers directly in divs). But in a modern cpu cost of the extra load is small
- raphlinus 9y agoI should have stated extra constraints; you're not allowed to use either additional memory (memory accesses are slow) or an if statement to update your state (branch mispredicts are slow). Yes, these are arbitrary (and I know the total time would be dominated by the cost of printf), but the point is to shave nanoseconds. Also, you've still got the duplication of strings.
- dmitrygr 9y agoMemory accesses are not slow on modern CPUs. With speculative loads and large L1d caches these loads won't stall even a single cycle String duplication helps speed here. Branch misprediction will happen once every fifteen times worst case. Plus, if shaving nanoseconds, printing is a bad idea
- SeanDav 9y agoGeneral comment and not aimed at this specific instance: Just because you are writing in assembler, does not mean it is going to run faster than the same code in a compiled language. There has been decades of research and who knows how many man-years of effort that has gone into producing efficient compiled code from C, C++, Fortran etc. Your assembly skills have to be of quite a decent order to beat a modern compiler. BTW: The answer to the question on Stack Overflow by Peter Cordes is a must-read. Brilliant.
- Veedrac 9y agoQuite decent is perhaps a bit pessimistic. Yes, you need to be fairly fluent if you want to write hand-optimised vector code. On the other hand, you only need to know a little assembly to be able to write C code that compiles better; that compilers are frequently not stupid doesn't mean the level below has nothing to teach. I personally find it a shame that there are so many juicy instructions that compilers have no hope of ever using effectively. How often is a compiler smart enough to solve a problem with PDEP/PEXT, for example? Those functions are versatile as heck, but you need to plan for them if you want them to show up.
- 15155 9y ago> Your assembly skills have to be of quite a decent order to beat a modern compiler. Start with compiler output, add intrinsics where you can see help is needed, benchmark, repeat. Pathologically-slow ASM is pretty rare from modern compilers in my experience.
- jzwinck 9y ago> Pathologically-slow ASM is pretty rare from modern compilers Here are some I've found: https://stackoverflow.com/questions/45496987/gcc-optimizes-fixed-range-based-for-loop-as-if-it-had-longer-variable-length https://stackoverflow.com/questions/45496987/gcc-optimizes-f... (horrific codegen for known-size C++11 loops in member functions, all GCC versions prior to 8 which is not yet released) https://stackoverflow.com/questions/43651923/gcc-fails-to-optimize-aligned-stdarray-like-c-array https://stackoverflow.com/questions/43651923/gcc-fails-to-op... (SIMD opportunity squandered when C++11 features are used) https://stackoverflow.com/questions/42263537/gcc-sometimes-doesnt-inline-stdarrayoperator https://stackoverflow.com/questions/42263537/gcc-sometimes-d... (failure to inline trivial operators) https://stackoverflow.com/questions/26052640/why-does-gcc-implement-isnan-more-efficiently-for-c-cmath-than-c-math-h https://stackoverflow.com/questions/26052640/why-does-gcc-im... (C isnan() not efficient, for many years)
- ericfrederich 9y agoFor fun I ported the C++ to Python and Cython without any kind of mathematical or programmatic optimizations. C++ was 0.5 seconds, then Python was 5.0 seconds. Cython, which was the same exact code as Python except sprinkled with "cdef long" to declare C types, was just 0.7 seconds.
- AdmiralAsshat 9y agoThe question was more interesting than the answer. tl;dr version--the author's hand-written assembly was poor. I guess the more interesting takeaway is "Just because it's assembly doesn't mean it's good assembly."
- bluedino 9y agoRight - you have to have a bit of hardware knowledge to use it effectively
- pdpi 9y agoThat takeaway is more or less uniformly true, though. It also often comes up as saying that $LANGUAGE is slower than C or C++. Your algorithms aren't naturally faster just because you're writing in C++. You don't magically stop allocating and double-buffering all over the place just because you're writing C++. In fact, coming in from the likes of Java you're liable to underestimate just how much (relatively expensive) copying is going on if you're careless. What C and C++ give you (and Assembly gives you even more of) is control. If you can, and know how to, capitalise on that control, you _will_ get more performance. But those requirements are non-trivial.
- payne92 9y agotl;dr -- the asm author used DIV to divide by a constant 2 More fundamentally: it's theoretically possible to at least match compiled code performance with assembly, because you could just write the code the compiler generates. BUT, it requires a LOT of experience. Modern compilers "know" a lot of optimizations (e.g. integer mult by fixed constant --> shifts, adds, and subtracts). Avoiding pipeline stalls requires a lot of tedious register bookkeeping, and modern processors have very complicated execution models. It's almost always better to start with a compiler-generated critical section and see if there are possible hand optimizations.
- copperred 9y agoYour use of the phrase "critical section" threw me off for a second. All good now.
- dingo_bat 9y agoWhat did you think of first?
- pcordes 9y agoPresumably the usual technical meaning: https://en.wikipedia.org/wiki/Critical_section https://en.wikipedia.org/wiki/Critical_section i.e. the part protected by a lock() / unlock() in multi-threaded code.
- dingo_bat 9y agoBut isn't that exactly what OP meant?
- marcosdumay 9y agoThat deserves a place on the CS bad names gallery, just right of "strong type system". There isn't anything even critical about it, just exclusive. The usage on the context of optimization is much more deserved, although I never heard anybody calling it "section" before, just critical code, critical loop, or stuff like that.
- hathym 9y agolet me guess, you are a javascript developer?
- Waterluvian 9y agoStanding on the shoulders of those who came before so that we may focus on solving real problems ;) I tease. I'm also a pretty big Python/JS developer in the robotics industry and I definitely live, to an extent, by that adage. Intentionally so, as I only have so much time in a day and optimization would be a sub-optimal use of company resources. Admittedly I have a comfortable baseline understanding of how computers work, but I do mentally map certain things as black boxes.
- heavenlyblue 9y agoI've spent my childhood reverse-engineering packed and obfuscated code in assembly, writing matrix multiplication libraries in C++ for fun, also did a lot with the first available frameworks for GPU programming in assembly (e.g. implementing kernel applications to images). I can sit down and estimate how much my code is going to take (including the cache misses and other nonlinearities). The way I earn money is by programming python. Why is it so? Because it's a cheaper solution and because you know that there's a multitude of libraries in Python that already do that for you. Optimisation is the overhead where you hire a developer solely to sit down and optimise; and quite frankly it is quite commoditised in that sense.
- trollopTheJope 9y ago>Why is it so? Because you weren't any good at all that hard stuff?
- pjmlp 9y agoI am coding since the mid-80's, so I have also done a lot of low level stuff in the past, but eventually ended up earning money by focusing on managed languages. Knowing how everything works helps to understand how to write code with performance in mind when required, write that occasional function/method or VM plugin in C++, or even read the Assembly code generated by the AOT/JIT compiler. But for the typical application use cases, the performance for the types of applications I write is more than enough.
- iamjk 9y agoThe people who write "article answers" like this on SO are the real MVP's of the web.
- kazinator 9y agoTL; DR: > If you think a 64-bit DIV instruction is a good way to divide by two, then no wonder the compiler's asm output beat your hand-written code. Once (maybe 25 years ago?) I came across a book on assembly language programming for the Macintosh. The authors wrote a circle-filling graphic routine which internally calculated the integer square root in assembly language, drawing the circle using the y = sqrt(r * r - x * x) formula! What is more, the accompanying description of the function in book featured sentences that were boasting about how it draws a big circle in a small amount of time (like a "only" quarter of a second or some eternity of that order) because of the blazing speed of assembly language! How could the authors not have used, say, MacPaint, and not be aware that circles and ellipses can be drawn instantaneously on the same hardware: fast enough for drag-and-drop interactive resizing?
- cmiller1 9y agoRelevant: https://www.folklore.org/StoryView.py?story=Round_Rects_Are_Everywhere.txt https://www.folklore.org/StoryView.py?story=Round_Rects_Are_...
- bhaak 9y agoHow are rounded corners on rects harder than circles and ovals? Is a rounded rect not just a circle sliced with straight lines between the quarter circles?
- shdon 9y agoI get the feeling that what you mention is the precise realisation that Atkinson had when he figured out a way to draw them quickly. It's quite possible that he was initially thinking of ways to describe rounded rects using a single equation. Even one as undeniably brilliant as Atkinson can get stuck in thinking and overcomplicate things. A good night's sleep can bring a fresh perspective and make simplicity much more apparent.
- phire 9y ago
- m3kw9 9y agoBecause the complier has optimized it better than you.
- msimpson 9y ago> If you think a 64-bit DIV instruction is a good way to divide by two, then no wonder the compiler's asm output beat your hand-written code... Compilers employ multitudes of optimizations that will go overlooked in hand-written ASM unless you, as the author, are very knowledgeable. End of story.
- coldcode 9y agoWhen I started programming on a Apple II+ assembly was important. Today there are likely only a few people in the world who truly understand what any particular CPU family is actually doing sufficiently to beat the compiler in some cases, and they probably are the ones writing the optimizer. But 6502 was fun to code for and the tricks were mighty clever but you could understand them.
- mark-r 9y agoI had the same kind of fun with the 8080/Z80. My favorite was the conditional function return instruction, it was only 1 byte instead of 3 bytes for a conditional jump.
- abainbridge 9y ago> Today there are likely only a few people in the world who truly understand what any particular CPU family is actually doing sufficiently to beat the compiler I'm not sure that's true. There are hundreds of compilers in the world, being maintained by thousands of developers. Then there are all the JITs. And the people who make the standard library implementations. And performance critical stuff in game engines, OS kernels, hardware drivers, high-frequency trading. Then there's the embedded space. And then there's Fabrice Bellard. My previous employer, Cambridge Silicon Radio (one of hundreds of similar companies nobody's heard of) had dozens of people on the staff that worked on this kind of thing. I have friends at ARM, Broadcom, Samsung and Raspberry Pi that mess around with processor designs for a living. This is just my little experience of the industry. There are armies of these people.
- takeda 9y agoNot too surprising answer: "your assembly sucks"
- smegel 9y ago> but I don't see many ways to optimize my assembly solution further I can't do it therefore it must be impossible!
- otempomores 9y agoThe last mile from abstraction to hardware can be pretty long