| |
Rudi
Account closed
Registered: May 2010
Posts: 125 |
Speedcode
Let's say my loop has to iterate 16K times.
unrolling the loop would not be ideal, because then it would be 16K*the amount of bytes inside the loop.
What does speedcode actually do? Unroll loops?
I saw lecture by Ninja at a conference about just LDA's and STA's to specific address locations. But what do these address locations store? tables or opcode+data?
First I thought about actually loading and storing the opcode and data, but afterwards I thought this wouldn't be right! The LDA's and STA's take each x-amount of cycles that I really dont need, and the opcodes and data themselves are the only thing I need :D
I got an idea now about using only one opcode for doing a same operation, but loading and storing the data in 1 or 2 byte format. Perhaps the LDA and STA needs to jump back and forth (as a consequence, i dont know).
Still its a subject that I recently am looking into since i would guess (as an approximation that) my routine will only run in 7 fps as it is now. Ideas or ramblings are welcome about this issue and topic!
(I forgot to ask. Do you make your own tools/or generators for speedcode generation?) |
|
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
Speedcode can have so many faces. In its cheapest fashion in can just be an unrolled loop. Generated speedcode might do more, like representing an intrinsic mapping, like for colors (fading/cycling) or such.
More complex situations might have a bunch of speedcode-fragments that are jumped to on request to do some subtasks. Here it is also important to have a slick and fast way to set up the jump target.
Recently i added another small article about optimizing on codebase64 (http://www.codebase64.org/doku.php?id=base:loops_vs_unrolled) but you might also want to read the other stuff about optimization there. Finally it would also help to know your project a bit closer to give suggestions that fit to your specific problem/algorithm. |
| |
Frantic
Registered: Mar 2003
Posts: 1648 |
Speedcode is the idea of repeating code literally (hence filling up a lot of memory) also called "unrolled code" instead of repeating the code using assembler instructions (looping by use of branch/compare instructions etc). The gain is obviously that you get rid of the branch/compare instructions and just execute the operations that are crucial for what you actually want to do. Not really anything more complicated than this. Then you can of course make various hybrid approaches, as Bitbreaker says.
Since the unrolled code can become quite large, as you noticed yourself, many people also write code to generate the unrolled speedcode, rather than loading it directly from disk. A more lazy approach is to generate chunks of speedcode by using macro features of your assembler or some script that generates unrolled source code, before assembling it. Then you get the problem of large binaries of course, since the code is already generated in the assembled binary. (Then again I suppose good crunchers may do a quite good job on packing the kind of repeated sequences of bytes you find in unrolled code.)
Have you checked these articles on codebase?
http://codebase64.org/doku.php?id=base:speedcode
http://codebase64.org/doku.php?id=base:loops_vs_unrolled |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
speedcode generator to add sinus tables, 256 byte table at <sinus> should be page aligned and repeated once, sinus movement is achieved by calling the routine with stepping values in X/Y:
w0 lda sinus,x
w1 adc sinus,y
w2 sta result
w3
speedcodegenerator
lda #<speedcode
sta fc
lda #>speedcode
sta fd
lda #0
sta counter
sta w0+1
sta w1+1
-
ldy #$00
- lda w0,y
sta (fc),y ;copy speedcode segment (w0-w3) into memory
iny
cpy #w3-w0
bne -
inc w2+1 ;update sta address
bne *+5
inc w2+2
lda w0+1 ;update load addresses
clc
adc #$03
sta w0+1
lda w1+1
clc
adc #$07
sta w1+1
tya ;move 16 bit pointer in memory where speedcode is copyed
clc
adc fc
sta fc
bcc *+4
inc fd
inc counter
lda counter
cmp #100
bne -
ldy #$00
lda #$60
sta (fc),y ;RTS to the end of the speedcode
rts
|
| |
Frantic
Registered: Mar 2003
Posts: 1648 |
Regarding the hybrid approaches Bitbreaker mentioned, where you need to jump to various chunks of speedcode, the following article may be useful reading:
http://codebase64.org/doku.php?id=base:dispatch_on_a_byte |
| |
Rudi
Account closed
Registered: May 2010
Posts: 125 |
Thanks alot for the feedback! You gave me some helpfull ideas im going to look further into. |
| |
algorithm
Registered: May 2002
Posts: 705 |
Also not necessary to unroll everything unless you need every bit of cpu processing or may need an additional register (if using this as a counter) etc. usually unrolling more than 8 times will give less performance gains in comparison with unrolling twice or more.
Changing the routine itself will give the biggest speed gains. The usual cycle saving tricks such as branching if required to code that would less likely be run and trying to avoid using dec/inc opcodes if possible (huge 5-6 cycle usage) and ofcourse code in zeropage, some illegal opcodes, table usage and more etc..
|
| |
Fresh
Registered: Jan 2005
Posts: 101 |
A bit off topic.
Quote:
Regarding the hybrid approaches Bitbreaker mentioned, where you need to jump to various chunks of speedcode, the following article may be useful reading:
http://codebase64.org/doku.php?id=base:dispatch_on_a_byte
That article may be a little misleading: choose the right jumptable and there's no reason you can't have your 256 indirect jump entries.
|
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
Fucking around with branch optimizing and shit like that doesnt helps you much when your approach is slow. Try to think backwards, dont translate an algorithm to 6502 opcodes, try to translate 6502 opcodes into effects. The more primitive solution you find the faster the code will get. Dont try to be smart, try to be primitive and lazy. Try to see the world as the CPU. and then the power will be with you my son :) |
| |
algorithm
Registered: May 2002
Posts: 705 |
Theres only so much a simple speedcode with less branches can do. Although can reduce computational time for example with decompression or so relying on packed bits to jump to a routine based on the byte containing packed bits and doing it all in one go.instead of bit shifting and comparisons. One example was in the just dance 64 demo that can decode 4 bytes from a byte adpcm2 decode in a single raster line. That is around 50000 bytes per second potential. Better to be smart and fast :-) |
| |
Rudi
Account closed
Registered: May 2010
Posts: 125 |
Ok. I have 3 branches in my loop (or for-loop to be exact). It's where the "?" and ":" conditionals are.
just for the heck of it i paste it here:
(i have yet to make those lut tables one dimentional)
for (ushort w=0; w<16384; w++)
{
ushort i = w>>3;
uchar j = (w&7);
uchar a = shrlut[p[i]][j]&1;
uchar b = (j<7 ? shrlut[p[i]][j+1]:p[i+128&2047])&1;
uchar c = shrlut[p[i+1&0x7ff]][j]&1;
uchar d = (j<7 ? shrlut[p[i+1&2047]][j+1]:p[i+129&2047])&1;
uchar z = a|shllut2[b][0]|shllut2[c][1]|shllut2[d][2];
z = swaplut[rand()&7][z];
uchar s = shllut[j];
p[i] = (r>>z)&1 ? p[i]|s : p[i]&(s^255);
}
hope you dont mind me pasting C-code here. This was not was Oswald wanted, but just to let you know how many complicated arithmetics and branches this code needs. It also has some 16-bit numbers. Altho i know that for (w&7) i need only to AND the lo-byte, and not the hi-byte. Anyway, here you see what challenge i got. 'r' is a 16-bit number. And for those who dont remember types in the C-language, uchar is unsigned char: 8-bit. and ushort is unsigned short: 16-bits. |
... 15 posts hidden. Click here to view all posts....
|
| Previous - 1 | 2 | 3 - Next |
