153:. 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.
25:
171:, 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).
236: – 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.
183:
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
231:
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
219:
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
192:
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
46:
97:
116:
69:
200:
might require only about 40 machine instructions, a very considerable saving. Expressed in terms of instruction path length, this
325:
208:
of 50 – a reason why actual instruction timings might be a secondary consideration compared to a good choice of
348:
303:
76:
353:
50:
83:
286:
versus external read afresh each time – avoiding high path length through multiple I/O function calls
65:
233:
35:
215:
The instruction path length of an assembly language program is generally vastly different than the number of
197:
54:
39:
313:
216:
130:
90:
268:
299:
to choose an appropriate algorithm to minimize overall path lengths for programs in any language
256: – most frequently occurring items should be placed first to avoid long searches
283:
253:
189:
180:
168:
157:
150:
220:
142:
295:
From the above, it can be realized that knowledge of instruction path lengths can be used:
201:
333:
328:
260:
16:
Number of machine code instructions required to execute a section of a computer program
342:
264:
185:
138:
249:
and returning from a function, procedure, or method containing the same statements
274:
145:. The total path length for the entire program could be deemed a measure of the
24:
327:
Computer
Architecture By John L. Hennessy, David A. Patterson, David Goldberg,
246:
161:
309:
to determine how efficient particular HLL statements are for any HLL language
278:
209:
146:
160:, most of the instruction path length is typically inside the program's
193:
18:
179:
Since there is, typically, a one-to-one relationship between
273:
calculate afresh versus retain earlier calculated (
277:) – may reduce multiple complex
141:instructions required to execute a section of a
204:would be reduced in this instance by a massive
8:
240:Factors determining instruction path length
53:. Unsourced material may be challenged and
117:Learn how and when to remove this message
302:to monitor how well a program has been
259:choice of algorithm –
312:as an approximate measure of overall
7:
51:adding citations to reliable sources
335:IBM – Glossary of Performance Terms
227:High-level language (HLL) programs
14:
284:read some tables into memory once
212:requiring a shorter path length.
23:
291:Use of instruction path lengths
149:'s performance on a particular
1:
269:linear (item-by-item) search
167:Before the introduction of
370:
234:instruction set simulator
66:"Instruction path length"
245:in-line code versus the
198:binary search algorithm
135:instruction path length
349:Analysis of algorithms
354:Software optimization
314:computer performance
254:unsorted lookup list
247:overheads of calling
217:source lines of code
131:computer performance
47:improve this article
252:order of items in
175:Assembly programs
158:benchmark program
156:When executing a
151:computer hardware
137:is the number of
127:
126:
119:
101:
361:
221:unreachable code
143:computer program
122:
115:
111:
108:
102:
100:
59:
27:
19:
369:
368:
364:
363:
362:
360:
359:
358:
339:
338:
322:
306:in any language
293:
242:
229:
177:
123:
112:
106:
103:
60:
58:
44:
28:
17:
12:
11:
5:
367:
365:
357:
356:
351:
341:
340:
337:
336:
331:
329:Krste Asanovic
321:
320:External links
318:
317:
316:
310:
307:
300:
292:
289:
288:
287:
281:
271:
257:
250:
241:
238:
228:
225:
176:
173:
125:
124:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
366:
355:
352:
350:
347:
346:
344:
334:
332:
330:
326:
324:
323:
319:
315:
311:
308:
305:
301:
298:
297:
296:
290:
285:
282:
280:
276:
272:
270:
266:
262:
258:
255:
251:
248:
244:
243:
239:
237:
235:
226:
224:
222:
218:
213:
211:
207:
203:
199:
196:list using a
195:
191:
187:
182:
174:
172:
170:
165:
163:
159:
154:
152:
148:
144:
140:
136:
132:
121:
118:
110:
107:November 2016
99:
96:
92:
89:
85:
82:
78:
75:
71:
68: –
67:
63:
62:Find sources:
56:
52:
48:
42:
41:
37:
32:This article
30:
26:
21:
20:
294:
230:
214:
205:
186:table lookup
178:
166:
155:
139:machine code
134:
128:
113:
104:
94:
87:
80:
73:
61:
45:Please help
33:
275:memoization
343:Categories
279:iterations
162:inner loop
77:newspapers
304:optimized
210:algorithm
147:algorithm
34:does not
188:on an un
181:assembly
261:indexed
91:scholar
55:removed
40:sources
265:binary
206:factor
202:metric
194:sorted
190:sorted
169:caches
133:, the
93:
86:
79:
72:
64:
98:JSTOR
84:books
70:news
38:any
36:cite
267:or
129:In
49:by
345::
263:,
223:.
164:.
120:)
114:(
109:)
105:(
95:·
88:·
81:·
74:·
57:.
43:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
