<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">2016-08-26 3:43 GMT+02:00 MarLinn via Haskell-Cafe <span dir="ltr"><<a href="mailto:haskell-cafe@haskell.org" target="_blank">haskell-cafe@haskell.org</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">[...]  Divisions are expensive, too.<br></blockquote><div><br></div><div>Yes, considered in isolation they are, but things are totally different if you consider modern CPU architectures and the program as a whole: With highly pipelined architectures, out-of-order execution, register renaming etc. it is not uncommon that the high cost of the division itself is hidden because e.g. its result is not immediately needed. And the other observation is: The cunning bit-fiddling algorithms of the past often have very high hidden costs because they need more registers, have strong value dependencies (leading to pipeline stalls), interact badly with branch prediction etc.  As a result, it is not uncommon that the most straightforward code is the fastest. In the end you have to measure... (on various platforms)</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
(interesting fact: Java uses a seven-fingered merge sort with bit-shift-trickery to approximate a division by seven because the division is so damn expensive) [...]<br></blockquote><div><br></div><div>This is a perfect example for a bad algorithm on current CPUs: An integer division by a constant can and should be replaced by an integer multiplication plus some tiny correction by a shift/add, see e.g. section "8.1 Replacing division with multiplication" in AMD's optimization guide (<a href="http://support.amd.com/TechDocs/25112.PDF">http://support.amd.com/TechDocs/25112.PDF</a>) or "Computing Magic Numbers" in Hacker's Delight (<a href="http://www.hackersdelight.org/">http://www.hackersdelight.org/</a>). Looking at e.g. the Skylake table in <a href="http://www.agner.org/optimize/instruction_tables.pdf">http://www.agner.org/optimize/instruction_tables.pdf</a> (the CPU performance "bible" ;-), you can see how blazingly fast that is.</div><div><br></div><div>In a nutshell: We don't program on our grandpa's CPUs anymore, :-D at least not on the desktop/server, so a lot of traditional advice from the past is misleading nowadays.</div></div></div></div>