The Basic Axioms

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

The Basic Axioms

The running time performance of the C++ virtual machine is given by a set of axioms which we shall now postulate. For now we consider only operations on integers. The first axiom addresses the running time of simple variable references:

Axiom The time required to fetch an integer operand from memory is a constant, , and the time required to store an integer result in memory is a constant, .

According to Axiom , the assignment statement

y = x;

has running time

. I.e., the time taken to fetch the value of variable x is

and the time taken to store the value in variable y is

We shall apply Axiom to manifest constants too: The assignment

y = 1;

also has running time

. To see why this should be the case, consider that the constant typically needs to be stored in the memory of the computer, and we can expect the cost of fetching it to be the same as that of fetching any other operand.

The next axiom addresses the running time of simple arithmetic operations on integers:

Axiom The times required to perform elementary operations on integers, such as addition, subtraction, multiplication, division, and comparison, are all constants. These times are denoted by , , , , and , respectively.

According to Axiom , all the simple operations on integers can be accomplished in a fixed amount of time. In order for this to be feasible, the number of bits used to represent an integer must be fixed. Typically, between 16 and 64 bits are used to represent an integer. It is precisely because the number of bits used is fixed that we can say that the running times are also fixed. If arbitrarily large integers are allowed, then the basic arithmetic operations can take an arbitrarily long amount of time.

By applying Axioms and , we can determine that the running time of a statement like

y = y + 1;

. This is because we need to fetch two operands, y and 1; add them; and, store the result back in y.

C++ syntax provides several alternative ways to express the same computation:

y += 1;
++y;
y++;

We shall assume that these alternatives require exactly the same running time as the original statement.

The third basic axiom addresses the function call/return overhead:

Axiom The time required to call a function is a constant, , and the time required to return from a function is a constant, .

When a function is called, certain housekeeping operations need to be performed. Typically this includes saving the return address so that program execution can resume at the correct place after the call, saving the state of any partially completed computations so that they may be resumed after the call, and the allocation of a new execution context (stack frame or activation record ) in which the called function can be evaluated. Conversely, on the return from a function, all of this work is undone. While the function call/return overhead may be rather large, nevertheless it entails a constant amount of work.

In addition to the function call/return overhead, additional overhead is incurred when parameters are passed to the function:

Axiom The time required to pass an integer argument to a function or procedure is the same as the time required to store an integer in memory, .

The rationale for making the overhead associated with parameter passing the same as the time to store a value in memory is that the passing of an argument is conceptually the same as assignment of the actual parameter value to the formal parameter of the function.

According to Axiom , the running time of the statement

y = f (x);

would be

, where

is the running time of function f for input x. The first of the two stores is due to the passing of the parameter x to the function f; the second arises from the assignment to the variable y.