Instruction path length

Instruction path length is a term frequently used to simply describe 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 algorithms 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 determinining path length and so path length is merely an indication of relative performance rather than in any sense absolute.

Assembly programs

Since there is, typically, a one-to-one relationship between assembly 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) , 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.

=High level language (HLL) programs=

Since one statement written in a high level language can produce very many machine instructions, it is not always possible to determine instruction path length without, for example, an Instruction Set Simulator - 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 levbel 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 function call - function calls require Dynamic memory allocation ,initialization and possibly other overheads
* order of items in unsorted lookup list - most frequently occuring items should be placed first to avoid long searches
* choice of algorithm - indexed, binary or linear (item-by-item) search
* calculate afresh versus retain earlier calculated (memoization) - may reduce multiple complex iterations
* read some tables into memory once versus external read afresh each time - avoiding high path length through muliple 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 performance

ee also

* Algorithmic efficiency
* Optimization (computer science)