Meta tags:
Headings (most frequently used words):
unrolling, loop, example, mips, manual, in, to, assembly, language, contents, advantages, disadvantages, static, dynamic, see, also, references, further, reading, external, links, simple, early, complexity, while, loops, assembler, ibm, 360, or, architecture, converting, the,
Text of the page (most frequently used words):
the (200), loop (95), #unrolling (46), 100 (45), 256 (42), code (33), and (32), array (31), mvc (30), this (28), example (25), for (25), that (25), with (24), from (23), bytes (23), move (22), f10 (22), process (21), edit (20), entry (20), can (20), number (18), instructions (18), entries (16), pointer (15), instruction (15), printf (15), size (14), r15 (14), which (14), analysis (13), each (12), statements (11), compiler (11), f12 (11), will (11), case (11), not (11), program (11), are (11), all (10), optimizing (10), branch (10), address (10), offset (10), optimization (9), variable (9), assembly (9), element (9), int (9), only (9), manual (9), print (9), remove (9), wikipedia (8), may (8), static (8), time (8), language (8), iteration (8), then (8), while (8), more (8), condition (8), elimination (7), constant (7), repeat (7), also (7), one (7), mips (7), could (7), break (7), set (7), dynamic (7), simple (7), sequence (7), maxm1 (7), maximum (7), action (7), add (6), value (6), performance (6), loops (6), cache (6), addi (6), following (6), double (6), two (6), left (6), label (6), assembler (6), arithmetic (6), after (6), variables (6), overhead (6), about (5), use (5), page (5), articles (5), parallel (5), index (5), control (5), jump (5), function (5), other (5), register (5), links (5), compilers (5), unwinding (5), duff (5), device (5), just (5), mul (5), displacement (5), above (5), increment (5), initialize (5), here (5), remaining (5), bunchsize (5), required (5), used (5), where (5), iterations (5), increase (5), have (5), start (5), first (5), these (5), any (5), often (5), might (5), do_odd_stuff (5), do_even_stuff (5), toggle (4), contents (4), search (4), additional (4), using (4), list (4), optimizations (4), data (4), flow (4), technique (4), reading (4), university (4), journal (4), cite (4), computer (4), has (4), server (4), speed (4), memory (4), see (4), loop3 (4), same (4), but (4), note (4), arrays (4), count (4), base (4), drop (4), through (4), main (4), still (4), possible (4), into (4), similar (4), length (4), would (4), executed (4), goto (4), unrolled (4), normal (4), next (4), prediction (4), hide (4), sidebar (4), table (3), view (3), statement (3), text (3), was (3), march (3), 2026 (3), cs1 (3), multiple (3), short (3), computing (3), retrieved (3), execution (3), checking (3), store (3), reduction (3), 2012 (3), programming (3), external (3), modern (3), further (3), model (3), requires (3), cpu (3), eliminating (3), because (3), references (3), continue (3), test (3), dot (3), product (3), below (3), switch (3), calculate (3), times (3), per (3), course (3), make (3), techniques (3), field (3), approximately (3), require (3), original (3), r14 (3), registers (3), end (3), init (3), than (3), al2 (3), ilen (3), pre (3), architecture (3), ibm (3), 360 (3), known (3), instead (3), advantages (3), small (3), values (3), part (3), endwhile (3), consider (3), large (3), therefore (3), such (3), programmer (3), result (3), significant (3), increased (3), article (3), transformation (3), tools (3), languages (2), contact (2), privacy (2), policy (2), available (2), terms (2), you (2), last (2), categories (2), generated (2), maint (2), names (2), authors (2), description (2), matches (2), wikidata (2), dependence (2), inline (2), expansion (2), expression (2), dead (2), compile (2), global (2), call (2), conditional (2), numbering (2), based (2), define (2), induction (2), software (2), pipelining (2), unswitching (2), splitting (2), fusion (2), automatic (2), agner (2), fog (2), subroutines (2), introduction (2), x86 (2), book (2), pages (2), 2001 (2), isbn (2), approach (2), optimized (2), pdf (2), help (2), parallelism (2), link (2), august (2), over (2), much (2), faster (2), lines (2), some (2), portal (2), bgtz (2), implemented (2), again (2), compute (2), vectors (2), converting (2), dotproduct (2), source (2), processed (2), unroll (2), get (2), elements (2), divisible (2), include (2), written (2), generate (2), single (2), library (2), parameters (2), clear (2), rest (2), immediately (2), copied (2), whereas (2), saving (2), execute (2), unwound (2), even (2), there (2), return (2), equ (2), unconditional (2), zero (2), them (2), hexadecimal (2), plus (2), addressing (2), being (2), order (2), previous (2), reduce (2), beyond (2), batch (2), except (2), dynamically (2), 50cl256 (2), programmers (2), including (2), able (2), benefit (2), referenced (2), particular (2), less (2), specified (2), machine (2), run (2), standard (2), relatively (2), requiring (2), tweaked (2), pseudocode (2), performed (2), automatically (2), jumps (2), general (2), content (2), replicating (2), many (2), etc (2), produce (2), reference (2), new (2), later (2), its (2), replaced (2), however (2), need (2), procedure (2), involves (2), merely (2), done (2), early (2), complexity (2), expanded (2), operations (2), become (2), branches (2), potentially (2), should (2), accomplished (2), calls (2), correct (2), executing (2), without (2), penalty (2), pressure (2), systems (2), when (2), inlining (2), due (2), leading (2), manually (2), space (2), misses (2), occur (2), cause (2), storage (2), learn (2), information (2), disadvantages (2), independent (2), well (2), tests (2), reducing (2), appearance (2), upload (2), file (2), changes (2), history (2), read (2), subsection (2), log (2), create (2), account (2), donate (2), menu (2), topic, mobile, cookie, statistics, developers, conduct, legal, safety, contacts, disclaimers, under, apply, site, agree, registered, trademark, non, profit, organization, wikimedia, foundation, inc, creative, commons, attribution, sharealike, license, rendered, parsoid, edited, utc, hidden, disputed, december, 2009, accuracy, disputes, containing, suspected, texts, errors, missing, periodical, https, org, php, title, loop_unrolling, oldid, 1345639607, range, shape, escape, access, alias, profile, guided, partial, evaluation, threading, templates, bounds, interprocedural, tail, deforestation, functional, rematerialization, allocation, selection, scheduling, generation, sparse, propagation, ssa, reaching, definitions, chain, upwards, exposed, uses, live, recognition, folding, common, subexpression, strength, nest, interchange, inversion, invariant, motion, vectorization, parallelization, local, peephole, basic, block, handbook, gives, concise, generalized, graphics, black, michael, abrash, chapter, kennedy, ken, allen, randy, morgan, kaufmann, 55860, 286, architectures, minnesota, adam, horvath, far, away, sarkar, vivek, nested, 581, 3353104, s2cid, 1023, 1012246031671, doi, 545, international, copenhagen, college, engineering, smt, theory, lists, nicolau, alexandru, 1985, quantization, fine, grain, exploitation, dept, science, technical, report, ithaca, cornell, 14638257, oclc, petersen, arbenz, 2004, oxford, press, ullman, jeffrey, aho, alfred, 1977, mass, addison, wesley, pub, 201, 10073, 471, principles, design, tso, ted, 2000, jim, gettys, wonderful, explanation, effect, turns, out, predictions, relative, changing, past, decade, pretty, pointless, fact, instances, shrunk, _half_, _a_, _megabyte_, boot, excess, meant, wasn, thrashing, xfree86, 2014, linux, kernel, mailing, lkml, indiana, edu, patch, input, drivers, word, needed, compilation, level, don, yourself, factor, thus, displacements, decrement, before, implementing, omits, initializations, type, duplication, avoided, writing, parts, together, none, rely, complete, jumping, update, amount, bunches, remainder, most, processing, total, counter, void, constexpr, reflecting, stdio, demonstrates, unlike, full, absolute, indexes, replacement, perfectly, specifying, four, five, operands, alternatively, subroutine, accessed, passing, making, readily, accessible, macro, involved, long, combined, adjusted, accordingly, nulls, byte, added, every, 156, 202, conventional, had, consisted, 108, thousands, defined, starting, starts, point, always, contain, subtract, bnp, positive, meaning, entire, bypassed, multiply, calculated, specific, allowable, f00, character, decreases, avoids, permissible, within, fff, 255, decreasing, moved, bnpr, reload, destroyed, calculation, constants, passed, addresses, pointers, loaded, beginning, actual, elsewhere, acquired, 1st, 2nd, 3rd, 4th, 5th, 6th, 7th, 8th, 9th, 10th, 11th, 12th, 13th, 14th, 15th, 16th, assemblers, assumes, both, having, lengths, section, writers, method, efficient, advantage, greatest, flagged, exceeded, tables, since, benefits, frequently, dependent, until, determine, whether, invoke, individual, flexibility, versus, context, situation, savings, useful, quite, overall, included, once, jit, better, altogether, involving, intricate, indexing, cases, probably, best, innermost, allow, optimisations, yet, yield, gain, unless, compiled, lot, notorious, makes, latter, develop, given, developed, usages, change, mean, staying, derived, carries, forward, becomes, whose, changed, invocation, computation, mod, else, administrative, arranges, productive, itself, contributes, nothing, results, desired, tedium, hundred, been, processor, generating, replications, editor, similarly, replication, programs, easily, track, combinations, find, repetition, boring, mistakes, bloat, hand, expands, produced, checked, debugged, allocate, addition, inside, structure, chosen, carefully, indeed, assuming, already, working, implications, were, amendments, somewhat, complicated, conditions, discuss, dubious, modification, afterwards, taken, represents, decrease, administration, optimal, usually, rather, indexed, referencing, delete, items, collection, normally, means, resources, compared, those, item_number, analyzing, interpreting, contrast, cpus, try, guess, way, waiting, resolve, incorrect, flush, pipeline, lead, mispredictions, lower, hardware, relies, renaming, temporary, across, limiting, reuse, superscalar, conflict, body, contains, prevent, excessive, trade, off, between, reduced, harder, understand, maintain, readability, increases, larger, binaries, consumes, exceeds, frequent, severe, degradation, costly, accesses, higher, requirements, takes, problematic, embedded, limited, microcontrollers, how, message, claims, cited, sources, material, removed, fictitious, research, verified, copyright, violations, hallucinated, incorporate, prohibited, sometimes, perform, upon, request, unknown, earlier, affect, follow, minimized, gains, realized, compensates, caused, tight, consists, offsets, built, directly, individually, certain, bounded, formal, verification, goal, penalties, hiding, latencies, delay, eliminate, repeated, computational, attempts, optimize, expense, undertaken, processors, counterproductive, tradeoff, binary, free, encyclopedia, item, projects, printable, version, download, export, legacy, parser, shortened, url, permanent, related, what, actions, english, talk, українська, türkçe, српски, srpski, русский, polski, 한국어, 日本語, italiano, français, فارسی, español, deutsch, top, personal, special, recent, community, contribute, random, current, events, navigation,
Text of the page (random words):
ng the loop in mips 5 see also 6 references 7 further reading 8 external links toggle the table of contents loop unrolling 13 languages deutsch español فارسی français italiano 日本語 한국어 polski русский српски srpski türkçe українська 中文 edit links article talk english read edit view history tools tools move to sidebar hide actions read edit view history general what links here related changes upload file permanent link page information cite this page get shortened url switch to legacy parser print export download as pdf printable version in other projects wikidata item appearance move to sidebar hide from wikipedia the free encyclopedia loop transformation technique loop unrolling also known as loop unwinding is a loop transformation technique that attempts to optimize a program s execution speed at the expense of its binary size which is an approach known as space time tradeoff the transformation can be undertaken manually by the programmer or by an optimizing compiler on modern processors loop unrolling is often counterproductive as the increased code size can cause more cache misses cf duff s device 1 the goal of loop unwinding is to increase a program s speed by reducing or eliminating instructions that control the loop such as pointer arithmetic and end of loop tests on each iteration 2 reducing branch penalties as well as hiding latencies including the delay in reading data from memory 3 to eliminate this computational overhead loops can be re written as a repeated sequence of similar independent statements 4 loop unrolling is also part of certain formal verification techniques in particular bounded model checking 5 advantages edit the overhead in tight loops often consists of instructions to increment a pointer or index to the next element in an array pointer arithmetic as well as end of loop tests if an optimizing compiler or assembler is able to pre calculate offsets to each individually referenced array variable these can be built into the machine code instructions directly therefore requiring no additional arithmetic operations at run time significant gains can be realized if the reduction in executed instructions compensates for any performance reduction caused by any increase in the size of the program branch penalty is minimized 6 if the statements in the loop are independent of each other i e where statements that occur earlier in the loop do not affect statements that follow them the statements can potentially be executed in parallel can be implemented dynamically if the number of array elements is unknown at compile time as in duff s device optimizing compilers will sometimes perform the unrolling automatically or upon request disadvantages edit this article may incorporate text from a large language model which is prohibited in wikipedia articles it may include hallucinated information copyright violations claims not verified in cited sources original research or fictitious references any such material should be removed march 2026 learn how and when to remove this message increased code size unrolling increases the number of instructions leading to larger program binaries higher storage requirements the expanded code takes up more memory which can be problematic for microcontrollers or embedded systems with limited storage instruction cache pressure the unrolled loop consumes more space in the instruction cache if it exceeds the cache size frequent cache misses can occur which can cause severe performance degradation due to costly memory accesses reduced code readability if loop unrolling is done manually instead of by an optimizing compiler the code can become harder to understand and maintain conflict with function inlining when the loop body contains function calls unrolling may prevent inlining due to excessive code expansion leading to a trade off between these two optimizations increased register pressure on hardware that relies on software pipelining for performance e g systems without register renaming or with in order superscalar execution unrolling may require additional registers to store temporary variables across iterations limiting register reuse 7 branch prediction modern cpus use branch prediction to try to guess which way a branch will go if the prediction is correct the cpu can continue executing instructions without waiting for the branch to resolve however if the prediction is incorrect the cpu has to flush the pipeline and start executing the correct instructions which can be a performance penalty loop unrolling can increase the number of branches in the code which could lead to more branch mispredictions and lower performance 8 static manual loop unrolling edit manual or static loop unrolling involves the programmer analyzing the loop and interpreting the iterations into a sequence of instructions which will reduce the loop overhead this is in contrast to dynamic unrolling which is accomplished by the compiler simple manual example in c edit a procedure in a computer program is to delete 100 items from a collection this is normally accomplished by means of a for loop which calls the function remove item_number if this part of the program is to be optimized and the overhead of the loop requires significant resources compared to those for the remove x function unwinding can be used to speed it up normal loop after loop unrolling for int x 0 x 100 x remove x for int x 0 x 100 x 5 remove x remove x 1 remove x 2 remove x 3 remove x 4 as a result of this modification the new program has to make only 20 iterations instead of 100 afterwards only 20 of the jumps and conditional branches need to be taken and represents over many iterations a potentially significant decrease in the loop administration overhead to produce the optimal benefit no variables should be specified in the unrolled code that require pointer arithmetic this usually requires base plus offset addressing rather than indexed referencing on the other hand this manual loop unrolling expands the source code size from 3 lines to 7 that have to be produced checked and debugged and the compiler may have to allocate more registers to store variables in the expanded loop iteration dubious discuss in addition the loop control variables and number of operations inside the unrolled loop structure have to be chosen carefully so that the result is indeed the same as in the original code assuming this is a later optimization on already working code for example consider the implications if the iteration count were not divisible by 5 the manual amendments required also become somewhat more complicated if the test conditions are variables see also duff s device early complexity edit in the simple case the loop control is merely an administrative overhead that arranges the productive statements the loop itself contributes nothing to the results desired merely saving the programmer the tedium of replicating the code a hundred times which could have been done by a pre processor generating the replications or a text editor similarly if statements and other flow control statements could be replaced by code replication except that code bloat can be the result computer programs easily track the combinations but programmers find this repetition boring and make mistakes consider normal loop after loop unrolling for i 1 8 do if i mod 2 0 then do_even_stuff i else do_odd_stuff i next i do_odd_stuff 1 do_even_stuff 2 do_odd_stuff 3 do_even_stuff 4 do_odd_stuff 5 do_even_stuff 6 do_odd_stuff 7 do_even_stuff 8 but of course the code performed need not be the invocation of a procedure and this next example involves the index variable in computation normal loop after loop unrolling x 1 1 for i 2 9 do x i x i 1 i print i x i next i x 1 1 x 2 x 1 2 print 2 x 2 x 3 x 2 3 print 3 x 3 x 4 x 3 4 print 4 x 4 etc which if compiled might produce a lot of code print statements being notorious but further optimization is possible this example makes reference only to x i and x i 1 in the loop the latter only to develop the new value x i therefore given that there is no later reference to the array x developed here its usages could be replaced by a simple variable such a change would however mean a simple variable whose value is changed whereas if staying with the array the compiler s analysis might note that the array s values are constant each derived from a previous constant and therefore carries forward the constant values so that the code becomes print 2 2 print 3 6 print 4 24 etc in general the content of a loop might be large involving intricate array indexing these cases are probably best left to optimizing compilers to unroll replicating innermost loops might allow many possible optimisations yet yield only a small gain unless n is large unrolling while loops edit consider a pseudocode while loop similar to the following normal loop after loop unrolling unrolled tweaked loop while condition do action endwhile while condition do action if not condition then goto break action if not condition then goto break action endwhile label break if condition then repeat action if not condition then goto break action if not condition then goto break action while condition label break in this case unrolling is faster because the endwhile a jump to the start of the loop will be executed 66 less often even better the tweaked pseudocode example that may be performed automatically by some optimizing compilers eliminating unconditional jumps altogether dynamic unrolling edit since the benefits of loop unrolling are frequently dependent on the size of an array which may often not be known until run time jit compilers for example can determine whether to invoke a standard loop sequence or instead generate a relatively short sequence of individual instructions for each element this flexibility is one of the advantages of just in time techniques versus static or manual optimization in the context of loop unrolling in this situation it is often with relatively small values of n where the savings are still useful requiring quite small if any overall increase in program size that might be included just once as part of a standard library assembly language programmers including optimizing compiler writers are also able to benefit from the technique of dynamic loop unrolling using a method similar to that used for efficient branch tables here the advantage is greatest where the maximum offset of any referenced field in a particular array is less than the maximum offset that can be specified in a machine instruction which will be flagged by the assembler if exceeded assembler example ibm 360 or z architecture edit for an x86 example see the external links section this example is for ibm 360 or z architecture assemblers and assumes a field of 100 bytes at offset zero is to be copied from array from to array to both having 50 entries with element lengths of 256 bytes each the return address is in r14 initialize registers r15 r0 r1 and r2 from data defined at the end of the program starting with label init maxm1 lm r15 r2 init set r15 maximum number of mvc instructions maxm1 16 r0 number of entries of array r1 address of from array and r2 address of to array the loop starts here loop equ define loop label at this point r15 will always contain the number 16 maxm1 sr r15 r0 subtract the remaining number of entries in the array r0 from r15 bnp all if r15 is not positive meaning we have more than 16 remaining entries in the array jump to do the entire mvc sequence and then repeat calculate an offset from start of mvc sequence for unconditional branch to the unwound mvc loop below if the number of remaining entries in the arrays is zero r15 will be 16 so all the mvc instructions will be bypassed mh r15 al2 ilen multiply r15 by the length of one mvc instruction b all r15 jump to all r15 the address of the calculated specific mvc instruction with drop through to the rest of them mvc instruction table first entry has maximum allowable offset with single register hexadecimal f00 15 256 in this example all 16 of the following mvc move character instructions use base plus offset addressing and each to from offset decreases by the length of one array element 256 this avoids pointer arithmetic being required for each element up to a maximum permissible offset within the instruction of hexadecimal fff 15 256 255 the instructions are in order of decreasing offset so the last element in the set is moved first all mvc 15 256 100 r2 15 256 r1 move 100 bytes of 16th entry from array 1 to array 2 with drop through ilen equ all set ilen to the length of the previous mvc instruction mvc 14 256 100 r2 14 256 r1 move 100 bytes of 15th entry mvc 13 256 100 r2 13 256 r1 move 100 bytes of 14th entry mvc 12 256 100 r2 12 256 r1 move 100 bytes of 13th entry mvc 11 256 100 r2 11 256 r1 move 100 bytes of 12th entry mvc 10 256 100 r2 10 256 r1 move 100 bytes of 11th entry mvc 09 256 100 r2 09 256 r1 move 100 bytes of 10th entry mvc 08 256 100 r2 08 256 r1 move 100 bytes of 9th entry mvc 07 256 100 r2 07 256 r1 move 100 bytes of 8th entry mvc 06 256 100 r2 06 256 r1 move 100 bytes of 7th entry mvc 05 256 100 r2 05 256 r1 move 100 bytes of 6th entry mvc 04 256 100 r2 04 256 r1 move 100 bytes of 5th entry mvc 03 256 100 r2 03 256 r1 move 100 bytes of 4th entry mvc 02 256 100 r2 02 256 r1 move 100 bytes of 3rd entry mvc 01 256 100 r2 01 256 r1 move 100 bytes of 2nd entry mvc 00 256 100 r2 00 256 r1 move 100 bytes of 1st entry s r0 maxm1 reduce the number of remaining entries to process bnpr r14 if no more entries to process return to address in r14 ah r1 al2 16 256 increment from array pointer beyond first set ah r2 al2 16 256 increment to array pointer beyond first set l r15 maxm1 reload the maximum number of mvc instructions per batch into r15 destroyed by the calculation in the first instruction of the loop b loop execute loop again static constants and variables these could be passed as parameters except maxm1 init ds 0a 4 addresses pointers to be pre loaded with the lm instruction in the beginning of the program maxm1 dc a 16 maximum number of mvc instructions executed per batch n dc a 50 number of actual entries in array a variable set elsewhere dc a from address of start of array 1 pointer dc a to address of start of array 2 pointer static arrays these could be dynamically acquired from ds 50cl256 array of 50 entries of 256 bytes each to ds 50cl256 array of 50 entries of 256 bytes each in this example approximately 202 instructions would be required with a conventional loop 50 iterations whereas the above dynamic code would require only about 89 instructions or a saving of approximately 56 if the array had consisted of only two entries it would still execute in approximately the same time as the original unwound loop the increase in code size is only about 108 bytes even if there are thousands of entries in the array similar techniques can of course be used where multiple instructions are involved as long as the c...
|
