Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in 
CSDb User Forums

Forums > C64 Coding > Sorting
2007-10-08 16:08

Registered: Apr 2002
Posts: 4241

are sorters really so slow in games? :) I have made my unrolled version for my theoretical game (;), and it takes 132 rlines to sort 32 numbers o_O worst case is ~200 lines. tho when its the case of 4 numbers have to be swapped only it does the job in ~10 lines. wastes a lot of memory but I like it :)
... 149 posts hidden. Click here to view all posts....
2017-09-13 08:10
Rastah Bar

Registered: Oct 2012
Posts: 151
Quote: Ah, so you're always storing 3 bytes earlier than the previous branch target?

I like it, but I'm not sure if that works for the very first sprite inserted into that bucket, unless you have the branch starting out by landing on the sty .bucketK+1

..which would then cost you an extra four cycles per empty bucket.

Yes, you are right.
2017-09-13 10:18
Rastah Bar

Registered: Oct 2012
Posts: 151
Quoting ChristopherJam

The bucket emptying code remains the same as in Color Bar's original:
.bucketK ;32 bytes
    bcc .nextBucket        ;Branches always: decrease this value by 3 with selfmodifying code in phase 1 for every new sprite in the bucket.
    !byt 0,0,0
    lda #sprite_index   ; repeat lda/pha eight times
    sty .bucketK+1

!byt 0,0,0 could be replaced by LDA #value + PHA, i.e., allow a maximum of 9 sprites per bucket, but I guess it doesn't really matter.
2017-09-14 14:12

Registered: Aug 2004
Posts: 795
The Human Code Machine, thanks for that codebase link. Must admit, I didn't find that area when I added the flagged bucket sort to the maths and algorithms section. Might need to add some crosslinks..

FWIW though, looks like that one has the same worst case as the one Oswald referenced in the opening remark to this thread. (32*31/2)=496 swaps, 26 cycles per swap, 496*26/63=204 raster lines.
2017-09-14 14:19

Registered: Mar 2003
Posts: 1339
I added some crosslinks @ codebase to make people aware about this partial overlap in contents in the two different sections.

Preferably generic sorting algorithms should be placed in the maths and algorithms section, and sorting tailored specifically towards fast sorting of sprites/multiplexing could be kept on the sprites page, if someone feels like cleaning this up.
2017-09-15 03:47

Registered: Aug 2004
Posts: 795
Thanks Frantic, I'll move my post.
2017-09-16 07:31
Rastah Bar

Registered: Oct 2012
Posts: 151
Quoting ChristopherJam

    ;code to fill out bucketK.   24 bytes, 36 cycles
    ldy .bucketK+1
    lda newBranchValue,y
    sta .bucketK+1         ; 12
    sta .bucketK+3,y       ;  9

    lda Yvalues,x
    sta *+4
    jmp ($xxxx)            ; 15

    ; 36*32 =  1152 cycle, 36 per actor

I think another 2 cycles per actor can be gained by using A as the actor counter:
ldy .bucketK+1
ldx newBranchValue,y
stx .bucketK+1
sta .bucketK+3,x
sbc #$01
ldy Yvalues,x
sty *+4
jmp ($xxxx)

Initialize with SEC, LDA #$1f, JMP .start

Total time: 220*3+43*32 = 2036 cycles or 32.3 rasters!
2017-09-16 14:32

Registered: Aug 2004
Posts: 795
Quoting Color Bar

I think another 2 cycles per actor can be gained by using A as the actor counter

Sweet! Yes, that should work. Should probably do a test implementation and upload this beast somewhere. Now if we could just shave off one more cycle per actor...
2017-09-18 10:03
Rastah Bar

Registered: Oct 2012
Posts: 151
Perhaps not practical, but maybe interesting to discuss:
If you are sure the maximum number of actors in a bucket is never exceeded, 2 more cycles per actor (and 2 bytes) can be shaved off the bucket filling routines by using some BOCs (bonus opcodes = illegals)
lax .bucketK+1
sbx #$06
stx .bucketK+1
sta .bucketK+3,x
lda Yvalues,y
sta *+4
jmp ($xxxx)

where Y is now the actor counter. The bucket emptying code should then be modified according to
bcc .nextBucket
lda #sprite_index
skw $abcd          ;opcode $0c
lda #sprite_index  ;Always 6 bytes for every sprite.
pha                ;Therefore sbx #$06 can be used in the fill routines.
skw $abcd
lda #sprite_index
sty .bucketK+1

If we allow up to 10 actors and patch the filling routines with 2 bytes to 64 bytes total, the page crossing penalties can be avoided. Although this algorithm uses a LOT of memory, it may be worth it in some demo effects if speed is the bottleneck. And besides, the absolute minimum possible CPU time is a worthy goal by itself.

As Christopher Jam suggested, we can have the 0 entry of the branch table point to a routine that checks whether we've reached the end of the actor list, or are just dealing with an actor that has gone offscreen.

I think we can then shave off 2 more bytes if the Y values are stored on the stack (terminated by 0) and LDA Yvalues,Y is replaced by PLA.
2017-09-18 11:44

Registered: Jan 2002
Posts: 103
I dont think this is really exactly what you guys are discussing but I suggest you all to have a look at the sortingroutines used in Time Machine, I have been given an explanation but I don't really understand how it works. I have code that sorts 32 elements just shy of 1400 cycles (if I remember correctly) with a constant speed using the explanation I was given, since it's HCLs I wont share it without his explicit permission but dropping a hint on where to look must be forgiven.
2017-09-18 12:25

Registered: Aug 2004
Posts: 795
re. SKW etc: Ooh, dangerous! So I think we're up to around 10k for the PHA routines now?

Will have to see if that can be sanely(!) combined with my thinking from today:

I managed to trim two cycles off the populate routine by switching to just using even numbers for the actor IDs (can interleave most of the data tables), and using a section of the stack to store Y values interleaved with actor IDs.
    ldx bucketK+1
    ldy newBranchTableValue,x
    sty bucketK+1
    pla ; grab this actor's index
    sta bucketK+3,y       ;21

    pla ; grab next Yvalue
    sta *+4
    jmp (jumptable)       ;11

(I was going to read the actor ID out of one of the CIA timers while pulling Y value off the stack, but realised that the timer will be counting down while the stack address increases, so had to abandon that idea).

so, 220*3+41*32=1972 cycles, 61.6 per actor, 31.3 raster lines :)
Previous - 1 | ... | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Users Online
Rock/Finnish Gold
Guests online: 29
Top Demos
1 Uncensored  (9.7)
2 Comaland 100%  (9.7)
3 Edge of Disgrace  (9.7)
4 Coma Light 13  (9.6)
5 The Shores of Reflec..  (9.6)
6 Wonderland XII  (9.6)
7 We Come in Peace  (9.6)
8 Lunatico  (9.6)
9 Incoherent Nightmare  (9.5)
10 Wonderland XIII  (9.5)
Top onefile Demos
1 Daah, Those Acid Pil..  (9.6)
2 FMX Music Demo  (9.5)
3 Pandemoniac Part 2 o..  (9.5)
4 Dawnfall V1.1  (9.5)
5 Treu Love [reu]  (9.5)
6 Arok 20 Invitation  (9.5)
7 Merry Xmas 2017  (9.4)
8 In Memoriam BHF  (9.4)
9 Dawnfall  (9.4)
10 Synthesis  (9.4)
Top Groups
1 Oxyron  (9.4)
2 Booze Design  (9.4)
3 Censor Design  (9.4)
4 Finnish Gold  (9.4)
5 Crest  (9.3)
Top Swappers
1 Derbyshire Ram  (10)
2 Splatterhead  (9.8)
3 Zyron  (9.8)
4 Acidchild  (9.8)
5 Walker  (9.7)

Home - Disclaimer
Copyright © No Name 2001-2018
Page generated in: 0.063 sec.