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?

Improve this question
8
  • 1
    wow i posted this 5 seconds ago and there's already a downvote
    – HiddenToad
    Commented Feb 9, 2022 at 18:02
  • 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
    Commented Feb 9, 2022 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
    Commented Feb 9, 2022 at 19:30
  • 1
    Stepping back a bit here: why do you care what people might think is the runtime of your convoluted prime finder?
    – Philip Kendall
    Commented Feb 9, 2022 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
    Commented Feb 10, 2022 at 7:44

2 Answers 2

Reset to default
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.)

Improve this answer
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.

Improve this answer
3
  • 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
    Commented Feb 9, 2022 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
    Commented Feb 10, 2022 at 1:19
  • Rate of discovered primes = number of primes examined / log n. Practically linear.
    – gnasher729
    Commented Feb 11, 2022 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.