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...


Some news

Hello, everyone! If anyone still visits this :P
Well... I wanted to say that lately, I haven't been coding at all. So Orbit hasn't moved much in the past 3 months. Quite dissapointing, yes... I'm sorry.
And as a direct result of that and lack of patience to work on, my other project - Lighthouse - has been shelved for an undertermined period of time. I do not know if I'll go back to it. When I started it, there weren't any tools like MSN Desktop Search or Google Desktop Search available. At the moment, I feel that my efforts would go in vain. So I'll just give it a break.

I've been feeling alright. But just haven't been in the mood for coding - Which I find very weird for my own standards, cause I love coding. Maybe it's just university getting to me :)

Cheers!


Click here to see previous messages
Rate my devblog
Give my blog a rating

Security Tips
Protect yourself agains the Sasser worm! Get WindowsXP Service Pack 2

Message History
30/04/2006 to 06/05/2006
06/11/2005 to 12/11/2005
04/09/2005 to 10/09/2005
03/04/2005 to 09/04/2005
20/03/2005 to 26/03/2005
23/01/2005 to 29/01/2005
16/01/2005 to 22/01/2005
02/01/2005 to 08/01/2005
26/12/2004 to 01/01/2005
19/12/2004 to 25/12/2004
12/12/2004 to 18/12/2004
28/11/2004 to 04/12/2004
14/11/2004 to 20/11/2004
17/10/2004 to 23/10/2004
10/10/2004 to 16/10/2004
03/10/2004 to 09/10/2004
19/09/2004 to 25/09/2004
12/09/2004 to 18/09/2004
05/09/2004 to 11/09/2004
29/08/2004 to 04/09/2004
22/08/2004 to 28/08/2004

Other sites
Orbit Homepage
Enhanced Labs & Orbit Support Forums
Enhanced Labs
Neowin


Disclaimer: All posts are provided "as is". All code snippets are provided for free use as long as credit is given.
2004 Lucas Mendes Menge