Tried changing Data Structure in mainqueue.c

Compiling, libraries, modules, coding guidelines and porting

Moderators: jesterKing, stiv

Post Reply
Lgilmour
Posts: 0
Joined: Mon Oct 29, 2007 9:50 pm

Tried changing Data Structure in mainqueue.c

Post by Lgilmour »

Hi,

We were talking with some of you about trying to change one of the data structures in the rendering aspect of Blender for a project in one of our college classes.

Well...
After looking through the render files and feeling slightly overwhelmed, we came across the mainqueue.c (in the source/blender/src folder) and decided that would be a much more manageable modification that would still have a profound effect on the performance of the entire program.

We changed the current array into a linked list (basically a real queue) with basic functionality of push/pop from the front and back.

We inserted some timers and noticed that our list was significantly slower than the current array already there - even in the mainqenter_ext function (which we thought would be an improvement over the memmov call with the current array).

Our original thought was that this memory movement may take some extra time over our simple remove node function. We are assuming that this memmov function must be pretty optimized and such, accounting for its speed. Do any of you know if this is true?

We thought our linked list had a shot against the current array, but we were definitely blown out of the water. You beat Notre Dame. Props to you guys and all of the optimization and everything you have put into this program!

Thanks,

Lindsay and Greg

diresu
Posts: 0
Joined: Tue May 23, 2006 10:50 am

how about using an index?

Post by diresu »

Hi :)

Once upon a time, I started to work on the same thing - and as I never made it a patch, it got lost somewhere :(

As far as I remember all the entries of the mainqueue are shifted when a new entry is entered. In my own approach, I used two pointers - one to the start of the queue, one to its last entry - and just moved the pointers when entering a new entry. This should be faster I suppose (but never actually tested...)

Code: Select all

queue:                   [x][x][x][ ][ ][ ][ ][ ][ ][x][x][x][x]
pointer to first entry:                              ^
pointer to last entry:          ^

after entering a new entry:

queue:                   [x][x][x][ ][ ][ ][ ][ ][x][x][x][x][x]
pointer to first entry:                           ^
pointer to last entry:          ^

after taking away the last entry:

queue:                   [x][x][ ][ ][ ][ ][ ][ ][x][x][x][x][x]
pointer to first entry:                           ^
pointer to last entry:       ^

[ ] is supposed to be the storage place used by an entry :)
Of course, start and end of the storage used to model the queue are supposed to "touch" each other:

Code: Select all

  +-> [4][5][ ][ ][ ][ ][ ][0][1][2][3]-+
  |                                     |
  +-------------------------------------+
I hope I got the indentation right :)

I wrote these notes without looking at the sources again - so if they do not match the current situation anymore - I beg you to forgive me :)

Cheers, Dietrich

Post Reply