Posted By
indi
on 2006-01-24
14:58:03
|  Fast allocator....
I thought I'd share this.... I've no idea if anyone else does this already, but since I just stumbled over it....I thought I'd "share and enjoy".
In the old days (when I was doing C64 stuff), my allocation routines tended to be bog standard, and very simple, like this....(in fact...I still tend to do this now...)
Alloc: ldx #MAX_OBJECTS
CheckAll:
lda InUse,x
beq GotOne
dex
bpl CheckAll
rts
GotOne:
lda #$ff
sta BullInUse,x
rts
Now this is all very well and good, but the more "slots" you have the worse it'll get. The easy answer is a simple linked list or something... but this requires you to link and unlink, and setup is't as simple either, not to mention the overhead of the links themselves.
So, while I was struggling to find a solution, I stated thinking of some sort of "stack" method... and stumbled into this method- timings were based on 16 slots. (hope the code comes out readable)
;****************************************************************************************
;
; Allocate/Free a bullet.
; Out: X=spare slot or -1 for error
;
; Alloc - BEST/WORST - 12/25
; Free - Best/Worst - 24 (constant)
;
;****************************************************************************************
FreeList db 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,$ff
;
; Usage:- AllocBullet [x|y] Specify the X or Y register that hold the bullet to free
;
AllocBullet macro
ld FreeIndex ; 3 ldx FreeIndex
lda FreeList, ; 4 lda FreeList
bmi !NoneFree ; 2 bmi !NoneFree
in ; 2 inx
st FreeIndex ; 3 stx FreeIndex
ta ; 2 tax
dec BullInUse, ; 7 dec BullInUse,x
!NoneFree: ; tax
ta ; 2 get next free bullet (or $ff for none left)
endm
;
; Usage:- FreeBullet [x|y] Specify the X or Y register that hold the bullet to free
;
FreeBullet macro
t a ; 2 txa
ld FreeIndex ; 3 ldx FreeIndex
de ; 2 dex
st FreeIndex ; 3 stx FreeIndex
sta FreeList, ; 5 sta FreeList,x
ta ; 2 tax - restore index
lda #0 ; 2 lda #0
sta BullInUse, ; 5 sta BullInUse,x
endm
Now, the best thing about it is that it doesn't matter how many you have, its aconstant speed, and all you need to do is setup an array with the freelist in it. You can type it in here as I've done, or calculate it at runtime... In effect its a simple stack, but it never occured to me to use a stack as an allocator before, its very quick and thanks to macros, you can use X or Y to allocate depending on your needs....
I used this for bullet allocation, and when firing many at once, I took a huge hit... now allocation is virtually invisible... which is nice 
|
