Linked Lists & Optimizations
Well... What can I say? I got really bored at university yesterday... And decided to write a Linked Lists implementation for Orbit. I previously was using Arrays. So I basically had this huge array that got re-allocated with extra space to fit the extra loaded items or smaller when removing items. I thought the linked lists would be faster for that. Turns out I was kinda right. Turns out that linked lists are a bit faster for loading (for some reason, they aren't much faster. I thought I'd get a HUGE improvement... but not...)... but they're terribly slower for seeking! When I ran Orbit with about 650 items loaded, the array took 10 seconds to load them. The linked list took 7 seconds. But it turns out that once those items were loaded, the array implementation ran at 18 frames per second while the linked list implementation ran at 11 seconds per frame!
I was dazzled. But frankly, my linked list implementation wasn't the best. It could only seek forward. And only from the start of the list. I, then, decided to optimize the seeking. Enabled the list to seek forward and backwards. Then, unsatisfied with that (didn't even test :P), I made it so that list remembered the index and the node for the last sought position. This way, it can start seeking from whichever known point is the closest to the index it wants to reach (also relieves the load from sequential seeking - cause all it does is get the previous node and return the next node). Turns out that now the linked list implementation ran at 3 fps. That, in itself was a 3200% improvement :)
I started to think something was wrong. Turns out it was. My code that I used in Orbit was just fine for arrays. But not so much for linked lists. For every frame, I was iterating through the list about 422500 times. That can't be good.
I removed all those iterations. Now I believe I don't run the list over more than 5 times per frame. It was a nasty bug.
Bottomline? Now arrays runs at 50 frames per second with 650 items opened. The linked list implementation runs at 40fps with that same amount. I really don't know which one I shoulw keep. I personally like the linked lists cause I like the implementation and I have control over what's disposed or not (you can't dispose the now-unused array... you just let it linger and wait for the garbage collector to catch it :\). But you know... The array code is faster for rendering and the linked list code isn't that much faster to load... So I'm in a serious dillema.
I guess I'll be returning to the array code...
Written by Lucas Menge on 08:52 PM
Send this message