Instruction path length
Encyclopedia
In computer performance
, the instruction path length is the number of machine code
instructions required to execute a section of a computer program
. The total path length for the entire program could be deemed a measure of the algorithm
's performance on a particular computer hardware
. 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, most of the instruction path length is typically inside the program's inner loop
.
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 a unsorted
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 might require only about 40 machine instructions, a very considerable saving. Expressed in terms of instruction path length, this metric
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 algorithm
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
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
.
– 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. Unfortunately most high-level language programmers do not have the knowledge to understand the assembly instructions produced and have no way to appreciate the instruction path lengths of their code – except perhaps through anecdote or bad experience.
Therefore choice of particular high-level language statements can have dramatic effects on instruction path lengths without the programmer having any means of knowing this in many cases.
Computer performance
Computer performance is characterized by the amount of useful work accomplished by a computer system compared to the time and resources used.Depending on the context, good computer performance may involve one or more of the following:...
, the instruction path length is the number of machine code
Machine code
Machine code or machine language is a system of impartible instructions executed directly by a computer's central processing unit. Each instruction performs a very specific task, typically either an operation on a unit of data Machine code or machine language is a system of impartible instructions...
instructions required to execute a section of a computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
. The total path length for the entire program could be deemed a measure of the algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
's performance on a particular computer hardware
Computer hardware
Personal computer hardware are component devices which are typically installed into or peripheral to a computer case to create a personal computer upon which system software is installed including a firmware interface such as a BIOS and an operating system which supports application software that...
. 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, most of the instruction path length is typically inside the program's inner loop
Inner loop
In computer programs, an important form of control flow is the loop. For example, this small pseudo-code program uses two nested loops to iterate over all the entries of an n×n matrix, changing their values so that the matrix becomes an identity matrix: for a in 1..n for b in 1..n ...
.
Assembly programs
Since there is, typically, a one-to-one relationship between assemblyAssembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
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
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
on a unsorted
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
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
Sorting
Sorting is any process of arranging items in some sequence and/or in different sets, and accordingly, it has two common, yet distinct meanings:# ordering: arranging items of the same kind, class, nature, etc...
list using a binary search algorithm might require only about 40 machine instructions, a very considerable saving. Expressed in terms of instruction path length, this metric
Software metric
A software metric is a measure of some property of a piece of software or its specifications. Since quantitative measurements are essential in all sciences, there is a continuous effort by computer science practitioners and theoreticians to bring similar approaches to software development...
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 algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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
Source lines of code is a software metric used to measure the size of a software program by counting the number of lines in the text of the program's source code...
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
Unreachable code
Unreachable code is a computer programming term for code in 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....
.
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 simulatorInstruction Set Simulator
An instruction set simulator 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 the processor's registers.Instruction simulation is a...
– 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. Unfortunately most high-level language programmers do not have the knowledge to understand the assembly instructions produced and have no way to appreciate the instruction path lengths of their code – except perhaps through anecdote or bad experience.
Therefore choice of particular high-level language statements can have dramatic effects on instruction path lengths without the programmer having any means of knowing this in many cases.
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 listAssociative arrayIn computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....
– most frequently occurring items should be placed first to avoid long searches - choice of algorithm – indexedIndexed searchIndexed search, also called the cutpoint method, is an algorithm for discrete-distribution pseudo-random number sampling, invented by Chen and Asau in 1974.- Literature :...
, binary or linear (item-by-item) searchBrute-force searchIn computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's... - calculate afresh versus retain earlier calculated (memoizationMemoizationIn computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs...
) – may reduce multiple complex iterationIterationIteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
s - read some tables into memory onceCacheIn computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...
versus external read afresh each time – 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 optimizedOptimization (computer science)In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...
in any language - to determine how efficient particular HLL statements are for any HLL language
- as an approximate measure of overall performance
External references
- http://books.google.co.uk/books?id=R7Frpn3g9AEC&pg=PA43&lpg=PA43&dq=%22instruction+path+length%22&source=web&ots=f1d-77XzLV&sig=EuQVc3kKLMWN-Wrvk-Y0tHKSlZs&hl=en&sa=X&oi=book_result&resnum=5&ct=result#PPP1,M1 Computer Architecture By John L. Hennessy, David A. Patterson, David Goldberg, Krste Asanovic
- http://www.vm.ibm.com/perf/reports/zvm/html/gloss.html IBM – Glossary of Performance Terms