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)


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Path length — In chemistry, the path length is defined as the distance that light (UV/VIS) travels through a sample in an analytical cell. Typically, a sample cell is made of quartz, glass, or a plastic rhombic cuvette with a volume typically ranging from 0.1… …   Wikipedia

  • Very long instruction word — or VLIW refers to a CPU architecture designed to take advantage of instruction level parallelism (ILP). A processor that executes every instruction one after the other (i.e. a non pipelined scalar architecture) may use processor resources… …   Wikipedia

  • Algorithmic efficiency — In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or… …   Wikipedia

  • Control table — This simple control table directs program flow according to the value of the single input variable. Each table entry holds a possible input value to be tested for equality (implied) and a relevant subroutine to perform in the action column. The… …   Wikipedia

  • Comparison of programming paradigms — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computin …   Wikipedia

  • 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: Short response time for a given …   Wikipedia

  • Branch table — In computer programming, a branch table (sometimes known as a jump table) is a term used to describe an efficient method of transferring program control (branching) to another part of a program (or a different program that may have been… …   Wikipedia

  • Profiling (computer programming) — In software engineering, profiling ( program profiling , software profiling ) is a form of dynamic program analysis that measures, for example, the usage of memory, the usage of particular instructions, or frequency and duration of function calls …   Wikipedia

  • IBM OLIVER (CICS interactive test/debug) — OLIVER (CICS interactive test/debug) was a proprietary testing and debugging toolkit for interactively testing programs designed to run on IBM s Customer Information Control System (CICS) on IBM s System/360/370/390 architecture. It provided… …   Wikipedia

  • Program optimization — For algorithms to solve other optimization problems, see Optimization (mathematics). 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… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.