computer performance In computing, computer performance is the amount of useful work accomplished by a computer system. Outside of specific contexts, computer performance is estimated in terms of accuracy, efficiency and speed of executing computer program instructio ...

, the instruction path length is the number of

machine code In computer programming, machine code is any low-level programming language, consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). Each instruction causes the CPU to perform a very ...

instructions required to execute a section of a

computer program A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components. A computer program ...

. The total path length for the entire program could be deemed a measure of the

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

's performance on a particular

computer hardware Computer hardware includes the physical parts of a computer, such as the computer case, case, central processing unit (CPU), Random-access memory, random access memory (RAM), Computer monitor, monitor, Computer mouse, mouse, Computer keyboard, ...

. The path length of a simple conditional instruction would normally be considered as equal to 2, one instruction to perform the comparison and another to take a branch if the particular condition is satisfied. The length of time to execute each instruction is not normally considered in determining path length and so path length is merely an indication of relative performance rather than in any sense absolute. When executing a

benchmark program In computing, a benchmark is the act of running a computer program, a set of programs, or other operations, in order to assess the relative performance of an object, normally by running a number of standard tests and trials against it. The ter ...

, most of the instruction path length is typically inside the program's

inner loop Inner loop may refer to: * Inner loop in computer programs * Inner Loop (Phoenix), a section of Interstate 10 in downtown Phoenix, Arizona, United States * Inner Loop (Rochester), an expressway around downtown Rochester, New York, United States * I ...

. Before the introduction of

cache Cache, caching, or caché may refer to: Places United States * Cache, Idaho, an unincorporated community * Cache, Illinois, an unincorporated community * Cache, Oklahoma, a city in Comanche County * Cache, Utah, Cache County, Utah * Cache County ...

s, the path length was an approximation of running time, but in modern CPUs with caches, it can be a much worse approximation, with some load instructions taking hundreds of cycles when the data is not in cache, or orders of magnitude faster when in cache (even the same instruction in another round in a loop).

Assembly programs

Since there is, typically, a one-to-one relationship between

assembly Assembly may refer to: Organisations and meetings * Deliberative assembly, a gathering of members who use parliamentary procedure for making decisions * General assembly, an official meeting of the members of an organization or of their representa ...

instructions and machine instructions, the instruction path length is frequently taken as the number of assembly instructions required to perform a function or particular section of code. Performing a simple table lookup on an un sorted list of 1,000 entries might require perhaps 2,000 machine instructions (on average, assuming uniform distribution of input values), while performing the same lookup on a sorted list using a

binary search algorithm In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...

might require only about 40 machine instructions, a very considerable saving. Expressed in terms of instruction path length, this

metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathem ...

would be reduced in this instance by a massive ''factor'' of 50 a reason why actual instruction timings might be a secondary consideration compared to a good choice of

requiring a shorter path length. The instruction path length of an assembly language program is generally vastly different than the number of

source lines of code Source lines of code (SLOC), also known as lines of code (LOC), is a software metric used to measure the size of a computer program by counting the number of lines in the text of the program's source code. SLOC is typically used to predict the am ...

for that program, because the instruction path length includes only code in the executed control flow for the given input and does not include code that is not relevant for the particular input, or

unreachable code In computer programming, unreachable code is part of the source code of a program which can never be executed because there exists no control flow path to the code from the rest of the program. Unreachable code is sometimes also called ''dead code' ...

High-level language (HLL) programs

Since one statement written in a high-level language can produce multiple machine instructions of variable number, it is not always possible to determine instruction path length without, for example, an

instruction set simulator An instruction set simulator (ISS) is a simulation model, usually coded in a high-level programming language, which mimics the behavior of a mainframe or microprocessor by "reading" instructions and maintaining internal variables which represent t ...

that can count the number of 'executed' instructions during simulation. If the high-level language supports and optionally produces an 'assembly list', it is sometimes possible to estimate the instruction path length by examining this list.

Factors determining instruction path length

* in-line code versus the overheads of calling and returning from a function, procedure, or method containing the same statements * order of items in unsorted lookup list most frequently occurring items should be placed first to avoid long searches * choice of algorithm indexed,

binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that ta ...

or linear (item-by-item) search * calculate afresh versus retain earlier calculated ( memoization) may reduce multiple complex

iteration Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...

s * read some tables into memory once versus external read afresh each time{{snd avoiding high path length through multiple I/O function calls

Use of instruction path lengths

From the above, it can be realized that knowledge of instruction path lengths can be used: * to choose an appropriate algorithm to minimize overall path lengths for programs in any language * to monitor how well a program has been optimized in any language * to determine how efficient particular HLL statements are for any HLL language * as an approximate measure of overall

External links

Computer Architecture By John L. Hennessy, David A. Patterson, David Goldberg, Krste Asanovic

IBM – Glossary of Performance Terms Analysis of algorithms Software optimization