CS 70

Instruction Counting?

  • LHS Cow speaking

    Theoretical analyses abstract away certain details in exchange for certainty and generalizability.

  • RHS Cow speaking

    Depending on the questions we want to answer, we make choices about which details to consider in an analysis.

In CS theory, we might consider analyzing the time it takes to solve problems and run algorithms/programs at different levels of granularity:

  • Exact instruction count of a program: Exactly how many CPU clock cycles are needed to run this program, depending on the input?
  • Exact operation count of an algorithm: Exactly how many times does an algorithm perform a particularly important operation, depending on the input?
  • Approximate operation count of an algorithm: Roughly how many times does an algorithm perform a particularly important operation, depending on the input? Here we leave off smaller or unimportant terms.
  • Asymptotic complexity of an algorithm: How does the time it takes to run this algorithm grow, as the input size approaches infinity? (This is the \(\mathrm{O}(n)\) type stuff you saw in CS 42/CS 60; we'll dig into it a lot deeper today!)
  • Complexity class of a problem: Is it possible to develop an algorithm that can promise to solve this problem within some set of asymptotic complexities (for example polynomial complexity)? (This question raises all sorts of interesting issues. For more, see CS 140: Algorithms.)
  • Decidability of a problem: Is it possible to develop an algorithm that can promise to solve this problem in finite time? (Remember from CS5/42 that there are some really cool problems for which the answer is no! For more, see CS 81: Computability and Logic.)
  • Duck speaking

    What's a CPU clock cycle? I'm not sure I've heard that term before.

  • LHS Cow speaking

    Processors use a clock signal to control their operations. When you have, say, a 3.5 GHz processor, that means it has a clock that runs at 3.5 billion cycles per second. In other words, each clock cycle would be 0.286 ns.

  • RHS Cow speaking

    A cycle is thus the smallest unit of time for the processor.

  • LHS Cow speaking

    Remember how the compiler turns our C++ code into machine instructions? Different processor instructions require different numbers of cycles; for example, maybe addition requires four cycles, but multiplication requires seven.

  • RHS Cow speaking

    When people want to precisely measure how much time it takes to execute a set of processor instructions, they tend to measure it in clock cycles.

CPU Instruction Counting?

In principle, counting the CPU cycles necessary to run a program could be great!

It's closely related to how long it will take to run, but at the same time it abstracts away external factors (like what other programs are running) that could impact the actual time spent.

  • Dog speaking

    Sounds great! Sign me up!

  • LHS Cow speaking

    Not so fast…

  • RHS Cow speaking

    Here's a C++ program that takes a number, a pointer to an array, and the size of the array. It returns true if the number would be below the 50th percentile of the elements of the array.

  • LHS Cow speaking

    In other words, it returns true if fewer than half of the elements of the array are less than the given number.

bool lowerHalf(float x, const float* arr, size_t arrSize) {  // 1
    size_t numLessThan = 0;                                  // 2
    for (size_t i = 0; i < arrSize; ++i) {                   // 3
        if (arr[i] < x) {                                    // 4
            ++numLessThan;                                   // 5
        }                                                    // 6
    }                                                        // 7
    return numLessThan < arrSize/2.0;                        // 8
}                                                            // 9

Brainstorm some reasons that this might be challenging or unhelpful about trying to figure out the number of CPU cycles (or just instructions) it would take to run this program.

  • Cat speaking

    Uhh… I have no idea how many instructions (or CPU cycles!) each operation takes...

  • Duck speaking

    Is it even consistent from one computer to another?

  • LHS Cow speaking

    Yes, exactly!

Here are some reasons we don't usually do instruction counting in practice:

  1. It's still specific to a very particular situation (or platform):
    • What CPU architecture are we using?
    • What compiler we are using?
    • What compiler options we are using?
    • What libraries and operating system are we using?
      • We've already seen, for example, that operating systems will define what the size of a int is, and they also define many other little details about how programs run on that system.
  2. This would be a very tedious analysis:
    • In order to perform this analysis we need to know everything about how the compiler works.
    • Very small details in the program syntax would result in significant changes in what instructions the compiler writes.
    • We might need to consider lots of cases for the input (e.g. when it's processing fewer than 100 elements it's \( X \), but when it's more it's \( Y \)).
  • Hedgehog speaking

    So what do we do instead?

  • LHS Cow speaking

    Let's see...

(When logged in, completion status appears here.)