Double Linked list and optimization...

GregBUG

hey guys!!!

in my particle engine i'm trying to optimize at my best to try to squeeze all possible fps from my devices...

in current implementation i use a table (fixed) and work quite well.

i tryed to implement a linked list to optimize more but some test demostrate that table are much faster...

here is the code to test: the linked list code ("strongly inspired" from a book that i'm reading)

CDLinkedList = Core.class()   ---------------------------- -- Init width a void list -- ---------------------------- function CDLinkedList:init() self.list = { first = nil, last = nil, } self.itemsCount = 0 end   ----------------------------- -- add an item to the list -- ----------------------------- function CDLinkedList:add(objectData) self.newItem = { prev = nil, next = self.list.first, data = objectData } self.itemsCount = self.itemsCount + 1 if not self.list.first then self.list.first = self.newItem self.list.last = self.newItem else self.list.first.prev = self.newItem self.list.first = self.newItem end end   -------------------------------- -- delete an item to the list -- -------------------------------- function CDLinkedList:delete(node) if node == self.list.first then self.list.first = node.next else node.prev.next = node.next end   if node == self.list.last then self.list.last = node.prev else node.next.prev = node.prev end self.itemsCount = self.itemsCount - 1 end   ------------------------------- -- for iterate with for loop -- ------------------------------- function getNext(list, node) return (not node and list.last) or node.prev end ù     --- TEST ---       local mylist = CDLinkedList.new()   s = os.timer() for j = 1, 1000000 do mylist:add(j) end   for node in getNext, mylist.list do --- no ops end     e = os.timer()   print(e-s)     --[[ a = {} s = os.timer() for j = 1, 1000000 do a[j] = j end   for j = 1, 1000000 do ---- no ops end   e = os.timer() print (e-s) --]]

the code with linked list took on my pc about 2.5 secs

the code with table about 0.10 secs

What am I doing wrong?
any advice?

atilim

Hi Gianluca,

I think you aren't doing anything wrong. IMHO, it's very normal that Lua's internal table implementation is much faster than linked lists.

Maybe you can also look at Penlight's (http://stevedonovan.github.com/Penlight/) implementation of linked lists but most probably you'll get smilar results.

Edit: I'm not sure if Penlight's List class is in fact a linked list.

GregBUG

thanks atilim for looking at this!

Yes, I suspected the slowness of the lists .. now I'm sure!
back to my beloved tables!
and back to optimize tnt engine!

atilim

\:D/