3 ms·

What 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

What 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 ago
Does 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 ago
  The 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 ago
    Providing 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

interroboink 5y ago

Does 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 ago
The 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 ago
  Providing 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