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 18:08
Oswald

Registered: Apr 2002
Posts: 4126
Sorting

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-12 14:10
Color Bar

Registered: Oct 2012
Posts: 133
Btw, if you just want to sort 32 random numbers, the phase 2 code could be modified into
.bucketK
bcc .nextBucket
lda #K
pha
lda #K
pha
...
pha
sty .BucketK+1

and the fill code can be limited to
ldy .bucketK+1 
lda newBranchValue,y		
sta .bucketK+1


Resulting in 3*(220-32)+12*32 + 33.5*32 -> 32 lines. Put perhaps that application requires 256 buckets and then it takes 33.8 lines.
2017-09-12 18:19
ChristopherJam

Registered: Aug 2004
Posts: 682
Quoting Color Bar
Not sure I understand this. You need a separate fill routine for every possible Y-value/bucket.


True, but every one of the 220 routines ends with
.hitableN
  sta *+4
  jmp ($xxxx) ;jump table for buckets >=128
.phase2N
  clc	                ;to branch always.
  ldy #27	   	;to restore the branch value of the bucket
  jmp .Bucket0


You can leave that tail off two thirds of them, eg only keeping it for buckets 1,4,7,10 etc.
The routine for bucket 0 would replace the bcs *+8 with a branch to the hitable lable in the the routine for bucket 1, as would the routine for bucket 2
2017-09-12 18:23
ChristopherJam

Registered: Aug 2004
Posts: 682
Quoting Color Bar
The routine probably uses too much memory for many applications.


A quarter of all RAM? Yes, that's probably a tad excessive in practice :)

It'd be interesting to have a map of best worst case routine for different numbers of actors, and different limits on memory use... could even have CPU time as altitude…
2017-09-12 19:30
Color Bar

Registered: Oct 2012
Posts: 133
Quoting ChristopherJam
Quoting Color Bar
Not sure I understand this. You need a separate fill routine for every possible Y-value/bucket.


True, but every one of the 220 routines ends with
.hitableN
  sta *+4
  jmp ($xxxx) ;jump table for buckets >=128
.phase2N
  clc	                ;to branch always.
  ldy #27	   	;to restore the branch value of the bucket
  jmp .Bucket0


You can leave that tail off two thirds of them, eg only keeping it for buckets 1,4,7,10 etc.
The routine for bucket 0 would replace the bcs *+8 with a branch to the hitable lable in the the routine for bucket 1, as would the routine for bucket 2


Yes, I understand it now. Thanks!
2017-09-12 19:41
Color Bar

Registered: Oct 2012
Posts: 133
Quote: Quoting Color Bar
The routine probably uses too much memory for many applications.


A quarter of all RAM? Yes, that's probably a tad excessive in practice :)

It'd be interesting to have a map of best worst case routine for different numbers of actors, and different limits on memory use... could even have CPU time as altitude…


I am wondering if there aren't any theoretical bounds known in computer science, about memory usage and/or/vs CPU time. But I guess these would have to be C64 specific to be of any use.
2017-09-13 08:58
ChristopherJam

Registered: Aug 2004
Posts: 682
Got a new record now, I think.

We can pack 221 addresses into a 222 byte table by using the high byte of each address as the low byte of the next address.
If we use something like this:
for i in 0..73:
    .byt 64+(i%74)*(1+i//74*24)%74)
.. there are no two addresses less than 24 bytes apart.


The fill routine then drops down to this:
    ;code to fill out bucketK.   24 bytes, 36 cycles
fillK
    ldy .bucketK+1
    lda newBranchValue,y
    sta .bucketK+1         ; 12
    tay
    txa
    sta .bucketK+3,y       ;  9

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

    ; 36*32 =  1152 cycle, 36 per actor

Just 24 bytes long :)
We avoid the check for x becoming negative by placing actor $ff at y=0, and having the 0 entry of the branch table point to a routine
that checks X to determine whether we've reached the end of the actor list, or are just dealing with an actor that has gone offscreen.

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
    pha
...
    sty .bucketK+1    ;Restore branch (to skip all sprites for empty buckets). Call with y=$1e for max 8 sprites per bucket.
.nextBucket    ;unrolled

    ; 3 cycles for an empty bucket, 12 voor buckets with 1 sprite => 3*(220-32)+12*32 = 948 cycli , 29.6 per actor



The bucket filling routines are packed three to a page over 74 pages, so around 19kb. Each page has an average of 184 bytes empty, so we can probably pack the bucket emptying code into the gaps. Note that some of the buckets would then need to branch past a group of bucket filling routines, so we'd need to use both X and Y for the two different values to restore the branches to "this bucket is empty"

So - total time, 36*32+3*(220-32)+12*32= 220*3+45*32 = 2100 cycles. 65.6 per sprite, 33.33 rasters total.

For 37 sprites or more, we're down to under a raster per sprite :D
2017-09-13 09:16
Color Bar

Registered: Oct 2012
Posts: 133
Great! I still have to study your post in detail, but maybe another 64 cycles gain be gained by adding 3 NOPs before the first sprite in the bucket, like this:
.bucketK
bcc .nextBucket
lda #sprite_index8
pha
...
nop
nop
nop
lda #sprite_index1
pha
sty .bucketK+1


Then the TAY can be removed from the fill code:
ldy .bucketK+1
lda newBranchValue,y
sta .bucketK+1
txa
sta .bucketK,y

and the branch value table changes to:
newBranchValue
 BYTE 0 x x 0 x x 3 x x 6 x x 9 x x 12 x x 15 x x 18 x x 21 x x x x x 27 x

Worst case for the phase 2 code is still 948 cycles, I think.
2017-09-13 09:46
ChristopherJam

Registered: Aug 2004
Posts: 682
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.
2017-09-13 09:53
Color Bar

Registered: Oct 2012
Posts: 133
Quoting ChristopherJam
Got a new record now, I think.

We can pack 221 addresses into a 222 byte table by using the high byte of each address as the low byte of the next address.

Clever idea!

I am not familiar with this notation
for i in 0..73:
    .byt 64+(i%74)*(1+i//74*24)%74)

What do i%74 and i//74 mean?
2017-09-13 10:01
ChristopherJam

Registered: Aug 2004
Posts: 682
Thanks!

Mod and divide (TBH I should have dropped from // back to / when I switched from python to pseudo asm). Oh, and that loop should have been to 74*3

Really, better expressed as

for i in 0..73:
    .byt 64+(i*1)%74

for i in 0..73:
    .byt 64+(i*25)%74

for i in 0..73:
    .byt 64+(i*49)%74
Previous - 1 | ... | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ... | 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
Advanced
Users Online
Flavioweb/🇮🇹ASR/HF🇮🇹..
JAYCE - THE MiNiSTRY
zenda
Bieno64/Commodore Plus
Linus/MSL^Oxy^SHAPE
Joe/WD/HXS/EXON/Arts..
Magic/Nah-Kolor
Guests online: 38
Top Demos
1 Uncensored  (9.7)
2 Edge of Disgrace  (9.7)
3 Coma Light 13  (9.6)
4 The Shores of Reflec..  (9.6)
5 Lunatico  (9.6)
6 Comaland 100%  (9.5)
7 Incoherent Nightmare  (9.5)
8 Wonderland XII  (9.5)
9 Comaland  (9.5)
10 Wonderland XIII  (9.5)
Top onefile Demos
1 Pandemoniac Part 2 o..  (9.6)
2 FMX Music Demo  (9.6)
3 Daah, Those Acid Pil..  (9.5)
4 Dawnfall V1.1  (9.5)
5 Synthesis  (9.5)
6 Dawnfall  (9.4)
7 Treu Love [reu]  (9.4)
8 Field Sort  (9.4)
9 KAOS 64  (9.3)
10 One-Der  (9.2)
Top Groups
1 Oxyron  (9.4)
2 Booze Design  (9.4)
3 Censor Design  (9.3)
4 Crest  (9.3)
5 The Judges  (9.3)
Top Organizers
1 Burglar  (9.9)
2 Wotnau  (9.7)
3 Sixx  (9.7)
4 MWS  (9.7)
5 Frantic  (9.6)

Home - Disclaimer
Copyright © No Name 2001-2017
Page generated in: 0.216 sec.