2

It's mostly all in the title. How do you report the runtime of a C++ program that has intensive calculations at compile-time?

If I have a program that, when I use the bash time command on it, appears to run in .5 seconds, but the COMPILE TIME CALCULATIONS take over 10 minutes, can I honestly say my program runs in .5 seconds?

Christophe
  • 74,672
  • 10
  • 115
  • 187
HiddenToad
  • 31
  • 3
  • 1
    wow i posted this 5 seconds ago and there's already a downvote – HiddenToad Feb 09 '22 at 18:02
  • Are you intending on re-compiling the program before every run? – Peter M Feb 09 '22 at 18:03
  • the program is a Sieve of Eratosthenes. so yes, if i want to calculate up to a different N then i would need to re-compile. – HiddenToad Feb 09 '22 at 18:05
  • 5
    Then I'd suggest the architecture of your code is sub-optimal and you are addressing the wrong issue. And why do you think "run time" is anything other than the time required to run the program? – Peter M Feb 09 '22 at 18:09
  • 1
    If you are compiling as a precursor step, then you create a shell script and use the `time` command on that. – Berin Loritsch Feb 09 '22 at 19:30
  • Sounds like a major optimization would be to generalize your code a bit. – Berin Loritsch Feb 09 '22 at 19:31
  • 1
    Stepping back a bit here: why do you care what people might think is the runtime of your convoluted prime finder? – Philip Kendall Feb 09 '22 at 23:17
  • 2
    "*can i honestly say my program runs in .5 seconds?*" Are the people using your program compiling it? Will they care how long it takes to execute? – Nicol Bolas Feb 10 '22 at 07:44

2 Answers2

8

You don't. Run-time is not compile-time, and nobody except the developer cares in the least how long compilation took.

(But also what Peter said: if your system really works like this, then something is very wrong to begin with.)

Kilian Foth
  • 107,706
  • 45
  • 295
  • 310
5

The Sieve of Eratosthenes calculates all prime numbers up to any given limit. If you're calculating primes at compile time you're simply shifting what would have been a run time speed cost to a space cost. Yes your program runs faster when ran for primes "under a certain limit" but the bigger that limit the bigger your program.

It's called the space time tradeoff. It's why algorithms aren't only rated in big O for speed but also space.

In terms of speed the Sieve is O(n log log n). Space is O(n).

Your pre-calculated Sieve has speed at O(1) and space is the same. Except the pre-calculation invents a new big O category to consider: distribution size. Where the classic Sieve algorithm's distribution size is O(1) your pre-calculated Sieve distribution size is O(n).

Congrats. It's a different way to tradeoff. One that requires maintaining and distributing n binaries. Enjoy.

candied_orange
  • 102,279
  • 24
  • 197
  • 315
  • I would be surprised if running a sieve at compile time is as fast as running the same sieve at runtime. For this specific problem, you should be able to run a sieve that can examine several hundred million integers per second. How long does it take to load these integers from the compiled file? – gnasher729 Feb 09 '22 at 23:42
  • @gnasher729 it takes O(n) to load if you insist on loading the whole thing. You don’t have to. Also, the rate of examined numbers isn’t what we’re competing with. It’s the rate of discovered primes. – candied_orange Feb 10 '22 at 01:19
  • Rate of discovered primes = number of primes examined / log n. Practically linear. – gnasher729 Feb 11 '22 at 16:57