[CSDb] - User Forums - Sparse Bubble Sort

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Sparse Bubble Sort

2020-01-06 04:52

DanPhillips

Registered: Jan 2003
Posts: 30

Sparse Bubble Sort

Hey,

Over the holidays I was messing with a "get as many sprites around with a proper multiplexor" background for a boot menu.

Had some success, unrolling and using some illegal opcodes, bit packing some data to reduce the amount of data read from memory and some algorithmic re working.

Final attempt sees 82 sprites bouncing (They all move at 50fps, each allows x,y,msb,color,definition and bounce off the left/right border and scanline 0 and $FD.

<Not sure if this is original, but thought it was worth pointing out)
While looking at the simple bubble sort and doing the obvious unrolling I noticed something about the data being read/re-read.

The project is in DASM, so DASM macro syntax...

The original:

MAC BubbleYSortMacro ;param {1} index, param {2} source offset
LDY YORDER+1+{1}
LDX YORDER+{1}
LDA YTAB+{2},X
CMP YTAB+{2},Y
BCS .NoNeedToSwap
STX YORDER+1+{1}
STY YORDER+{1}
.NoNeedToSwap
ENDM

The YTAB is double buffered.

New macros (probably only need 2, but 3 for added complexity)

MAC BubbleYSortMacro0 ;param 1 index, param 2 source offset
LDY YORDER+1+{1}
LDX YORDER+{1}
LDA YTAB+{2},X
CMP YTAB+{2},Y
BCS .NoNeedToSwap1
STX YORDER+1+{1}
STY YORDER+{1}
.if {1} > 0
LDX YORDER+{1}
LDA YTAB+{2},X
.endif
.NoNeedToSwap1
ENDM

; x needs to be {1}+1 a needs to be YTAB+{2},x
MAC BubbleYSortMacro1 ;param 1 index, param 2 source offset
LDY YORDER+{1}
CMP YTAB+{2},Y
BCC .NoNeedToSwap2
STY YORDER+1+{1}
STX YORDER+{1}
.if {1} > 0
LDY YORDER+{1}
.endif
.NoNeedToSwap2
ENDM

; y needs to be {1}+1
MAC BubbleYSortMacro2 ;param 1 index, param 2 source offset
LDX YORDER+{1}
LDA YTAB+{2},X
CMP YTAB+{2},Y
BCS .NoNeedToSwap3
STX YORDER+1+{1}
STY YORDER+{1}
.if {1} > 0
LDX YORDER+{1}
LDA YTAB+{2},X
.endif
.NoNeedToSwap3
ENDM

You use the 1st macro, then alternate the 2nd and 3rd.

The savings come from not reloading and alternating the comparison.
If no swapping is needed this saves 7 cycles for the 2nd macro and 3 for the 3rd macro.

In my boot menu background with 82 sprites this saves 360 cycles (average of 10 swaps needed per frame)

Amyway, not sure if this is new, but kinda funny looking at the same simple bubble sort for 30 odd years and not spotting this pattern :D

Cheers

Dan

... 10 posts hidden. Click here to view all posts....

2020-01-09 06:46

Oswald

Registered: Apr 2002
Posts: 5022

Quote: Hah! I've been thinking about trying to optimise a gnome sort (in particular, not putting the pot down while moving it left), but I didn't know it had a name.

Thanks, Pararaum :)

edit: oh wait... I just realised that the difference between gnome sort and insertion sort is that the gnome sort "forgets" the high water mark, and does redundant comparisons on its way back to the next unseen pot. Back to insertion sort it is, probably.

you can remember where you started and skip those checks. read wiki as I did :)

2020-01-09 09:26

ChristopherJam

Registered: Aug 2004
Posts: 1380

Yes, but then (as the wikipedia article itself concedes) it's just insertion sort with a different name :P

Previous - 1 | 2 - Next

Refresh

Subscribe 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

Mixer
Compyx/Focus
Ghost/Quantum
tlr
goerp/F4CG
megasoftargentina
Guests online: 131

Top Demos

1 Next Level  (9.8)
2 Mojo  (9.7)
3 Coma Light 13  (9.7)
4 Edge of Disgrace  (9.6)
5 Comaland 100%  (9.6)
6 No Bounds  (9.6)
7 Uncensored  (9.6)
8 Wonderland XIV  (9.6)
9 Memento Mori  (9.6)
10 Bromance  (9.5)

Top onefile Demos

1 It's More Fun to Com..  (9.7)
2 Party Elk 2  (9.7)
3 Cubic Dream  (9.6)
4 Copper Booze  (9.5)
5 TRSAC, Gabber & Pebe..  (9.5)
6 Rainbow Connection  (9.5)
7 Dawnfall V1.1  (9.5)
8 Quadrants  (9.5)
9 Daah, Those Acid Pil..  (9.5)
10 Birth of a Flower  (9.5)

Top Groups

1 Nostalgia  (9.3)
2 Oxyron  (9.3)
3 Booze Design  (9.3)
4 Censor Design  (9.3)
5 Crest  (9.3)

Top Original Suppliers

1 Black Beard  (9.7)
2 Derbyshire Ram  (9.5)
3 hedning  (9.2)
4 Baracuda  (9.1)
5 Jazzcat  (8.6)

Page generated in: 0.041 sec.