3 ms·
Oh, a memory... The only time I was able to beat compiler optimization was in an algebraic task where remainders of M mod P were needed, but the number M was f
by inglor_cz 5y ago
Oh, a memory...
The only time I was able to beat compiler optimization was in an algebraic task where remainders of M mod P were needed, but the number M was fairly often between P and 2P, sometimes 3P, but rarely higher. (Due to the intrinsic character of the algorithm used.)
Of course, the compiler could not have known that in advance, but I did, so I tried subtracting P from M once or twice and checking whether it was already under P.
That was like 40 per cent faster than a single division of 32-bit numbers. But it was 2005, so YMMV.
- thethirdone 5y agoWhat made it not possible for the compiler to notice that M was small? I have been thinking about "Sufficiently Smart Compilers" recently and it seems like in most cases a SSC would be able to guess the distribution of numbers being divided.
- interroboink 5y agoDoes your SSC concept include things like profile-guided optimization (ie, consuming runtime statistics for some representative sample)? If your program is doing calculations on data read from a CSV, for example, and you happen to know facts about that data that allows you to make a better algorithm (for that data), then I don't see how a compiler would be able to compete. That aside, I am reminded of: https://ridiculousfish.com/blog/posts/old-age-and-treachery.html https://ridiculousfish.com/blog/posts/old-age-and-treachery.... "grep sells out its worst case (lots of partial matches) to make the best case (few partial matches) go faster"
- thethirdone 5y agoThe ideal SSC as I see it would need to be provided a set of "representative" inputs to optimize for. I don't think you should be able to expect a compiler to guess what the most common inputs would be. I completely agree that a SSC cannot beat a human who understands the typical input when the SSC does not. My original comment was based on the idea that a SSC would be able to deduce M's distribution from the "intrinsic character of the algorithm used". In that case the optimization would be based on the code not the data.
- Someone 5y agoProviding a set of "representative" inputs to optimize for is at least as much as what profile guided optimization gives the compiler (the compiler can always generate a profile from that input set) The “intrinsic character of the algorithm used”, I think, would mean the programmer has to tell the compiler how to do this faster, which I think the OP did when writing something along the lines of if n < divisor n else if n < 2 * divisor n - divisor else n % divisor