What is an "unrolled loop?"

[+Larry]

I've seen quite a few references to this method, but I really don't know what it is. Can someone explain with perhaps a brief example?

 

Thanks,

Larry

[Rybags]

A loop is generally reusing the same code for a repetitive process where not many variables or tasks change.

Generally a counter variable is maintained and tested at the end to decide whether to repeat or exit.

 

The increment and test adds overhead and other factors can also be wasteful.

Unrolled loop means repeating sections of the program within the loop either to eliminate the loop altogether or reduce the number of iterations needed drastically.

 

Examples might be rendering a softsprite, scrolling a screen by moving memory around, drawing lines or moving data from a buffer into other part of memory (IDE type devices using PIO on Atari can benefit from optimising the buffer move routines).

[TMR]

I've seen quite a few references to this method, but I really don't know what it is. Can someone explain with perhaps a brief example?

Okay, a brief example would be something like this...

 

        ldx #$00
loop    lda $0601,x
        sta $0600,x
        inx
        cpx #$1e
        bne loop

...becoming this after it gets unrolled...

 

        lda $0601
        sta $0600
        lda $0602
        sta $0601
        lda $0603
        sta $0602
        lda $0604
        sta $0603
        lda $0605
        sta $0604
        lda $0606
        sta $0605
        lda $0607
        sta $0606
        lda $0608
        sta $0607
        lda $0609
        sta $0608
        lda $060a
        sta $0609
        lda $060b
        sta $060a
        lda $060c
        sta $060b
        lda $060d
        sta $060c
        lda $060e
        sta $060d
        lda $060f
        sta $060e
        lda $0610
        sta $060f
        lda $0611
        sta $0610
        lda $0612
        sta $0611
        lda $0613
        sta $0612
        lda $0614
        sta $0613
        lda $0615
        sta $0614
        lda $0616
        sta $0615
        lda $0617
        sta $0616
        lda $0618
        sta $0617
        lda $0619
        sta $0618
        lda $061a
        sta $0619
        lda $061b
        sta $061a
        lda $061c
        sta $061b
        lda $061d
        sta $061c
        lda $061e
        sta $061d
        lda $061f
        sta $061e

The disadvantage is, obviously, that the space required for the code goes up by a massive amount but, if used in the right circumstances, it lops off a cycle per LDA or STA and all of the ones eaten by the INX / CPX / BNE during each iteration of the loop too.

[+Larry]

OoooH! That makes it perfectly clear -- it's speed versus space. Thanks to you both!

 

-Larry

[+Stephen]

OoooH! That makes it perfectly clear -- it's speed versus space. Thanks to you both!

 

-Larry

All coding comes down to speed vs space, readability vs performance, maintainability vs trickery

[flashjazzcat]

The cycle savings, naturally, decrease the more the loop is unrolled. If you have 256 iterations and unroll to sixteen in-line instructions, you remove 240 test and branch instructions (you need only iterate sixteen times, that is). Unroll again to 32 in-line instructions, and you get rid of only eight tests and branches. So one looks for a sensible compromise most of the time, since the savings eventually start to drop off drastically.

[TMR]

So one looks for a sensible compromise most of the time, since the savings eventually start to drop off drastically.

Yeah, fully unrolling like i did is more a demo coder's thing really for when each and every cycle is vital and the RAM overheads aren't as much of an issue (although that said, i'm aware of at least one C64 game using a fully unrolled loop for the colour scrolling). =-)

[Xuel]

@FJC I agree that you have diminishing returns the more you unroll, but if you can eliminate indexed addressing by fully unrolling then you get another significant boost since direct addressing requires fewer cycles. For example X:8 uses a fully unrolled loop to clear the screen every frame. But it only works because it writes to the same addresses every time.

[flashjazzcat]

...but if you can eliminate indexed addressing by fully unrolling then you get another significant boost since direct addressing requires fewer cycles.

Good point!