Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Poor Performance over time

Author
Message
BatVink
Moderator
22
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 16th Feb 2009 23:24 Edited at: 16th Feb 2009 23:25
Link
My setup is slightly different to this, in the hope that I can be as flexible as possible.

So, I have Texture Banks (what I would call a header record) (6 traffic light images = 1 bank, 52 cards = another bank).

The Texture Bank holds the index of the first image in the image array (this array holds the DBP image number amongst other things, and is what I would call the detail record.)

Each Image element holds the index of the next image in the bank.




Back to top
Profile PM Email
jason p sage
18
Years of Service
User Offline
Joined: 10th Jun 2007
Location: Ellington, CT USA
Posted: 17th Feb 2009 01:28
Link
Sounds like you are describing making a Data Index now for this "Linked List" of yours you described.

A Double Linked List BTW has a pointer to both the previous item and the next item... That's the tpye I usually use. They allow moveprevious, movenext, moveFirst, MoveLast... just like most recordsets from databases.

A Dataindex, again like a database is a "Fast Find" mechanism like you described! In a database, the DataIndex is updated each time you add,delete or change a record - JUST LIKE YOU THOUGHT YOU WOULD DO!

BTW - IanM is right in that you MIGHT be over complicating things, but all the same - I'm a fan of this type of programming! It's a 8i^c# sometimes - but when its all purring - its pure harmony! ESPECIALLY when you get performance increases!

Good Luck Man!


http://www.jasonpetersage.com/?PAGE=ironinfantry&SECTION=ironinfantry
Back to top
Profile PM Email Website
BatVink
Moderator
22
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 17th Feb 2009 09:01
Link
Sounds good.

I'm a database-driven business programmer by day, so my mind is in DB mode, I suppose. You can't beat looking at optimisation graphs and data

Back to top
Profile PM Email
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 17th Feb 2009 15:42 Edited at: 17th Feb 2009 15:43
Link
Batvink, so when you add a new image, do you keep track of the last image used in each bank?, so if you added a new image 15 to bank 1, then image 3 would link to image 15?

Nice technique BTW, never thought of referencing the next index like that.


On a slightly different but similar note, any thoughts on making indexes for things that are in use as well?. I've been thinking that it might not be the best idea to check every possible particle to see if it's active then act on it - instead I was thinking that when a new particle is created, it get's added to a list that is checked when updating the particles. Just an index again but the complex bit is what to do when you need to take something from the list, like when a particle dies.
One little idea I've had is to comb the data, like if you check the index array and find a dead particle, you would tell the index to tidy itself up by offsetting the index as it goes through them.

So if the index references that particles 1 through 10 are in use, but then particles 3 and 6 die...

ioff=0
for i=0 to index count
ind=index(i)
if part_dead then inc ioff
index(i)=ioff
next i
dec index count,ioff

So it would step through and when it comes to particle 3, it simply increases the offset and then the current index becomes the next one, then again at particle 6 - each index being replaced until it's left with a tidied list but with duplicate indexes at the end, then the count is reduced to suit. So after each index is checked and updated, the index can then be set to the next living index, leaving you with an optimized list every time but costing very little performance.

I think I'll try this and see if it works, seems like a very simple way to get some of the benefits without necessarily knowing all about indexes.


Health, Ammo, and bacon and eggs!
Back to top
Profile PM Email
BatVink
Moderator
22
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 17th Feb 2009 18:28
Link
Sounds like you need to make the changes I have made.

1. create an "In Use" and "Available" array, same size as your particle array.

2. initialise "Available" with indexes 0,1,2,3...to end

3. When you need a particle element, take it from the "Available" pile and put it in "In Use" pile.

4. When looking through active particles, use "In use" pile as the reference

5. You need 2 pointers to tell you where last "Available" and "In Use" elements are.

6. When a particle dies, you take it out of the "In Use" pile and back on to the available pile. Fill the hole with the last "In Use" element on the pile, and reduce the pointer.

7. The actual data associated with a dead particle can be left alone. You'll never read it, because there is no reference in the "In Use" pile.

Back to top
Profile PM Email
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 17th Feb 2009 19:00
Link
@Batvink,
You have to take care with indexes that you aren't spending too much time simply maintaining them, and you still have to keep the index sorted - using my sort plug-in will do that in an optimal way, but it will be at exactly the same cost as sorting your data array.

The reason it's fast and at no extra cost, and also much faster than coding your own sort, is that the plug-in does not move the data, it swaps the pointers to the data.

@VanB,
What I call an 'inuse' list is what you need.

You use an integer to keep track of the top of the list. When you run through the list, you determine whether that particle is to be deleted or not. If not, simply move on to the next item in the array.

Otherwise, swap the current item with the last item and reduce the top-of-list tracker by one and don't move on. Repeat until you hit the top-of-list tracker. That will give you an almost zero cost for maintaining the list and means you only ever access active particles.

You can use the SWAP ARRAY ITEMS command from my array plug-in to do the swap even faster.

A clever and not-so-obvious side effect of using an inuse list in this way, is that as well as telling you what is in use (everything <= top-of-list marker), it also tells you what is not in use (everything > top-of-list marker), so it can also be used as a fast free list too, as long as you populate it correctly from the start.

Utility plug-ins collection (updated 29/12/08) and
http://www.matrix1.demon.co.uk
Back to top
Profile PM Email Website
tiresius
22
Years of Service
User Offline
Joined: 13th Nov 2002
Location: MA USA
Posted: 17th Feb 2009 19:26
Link
Quote: "Otherwise, swap the current item with the last item and reduce the top-of-list tracker by one and don't move on. Repeat until you hit the top-of-list tracker. That will give you an almost zero cost for maintaining the list and means you only ever access active particles."

Holy cow this is pure genius and something I need in my project in several places. I'm sure this technique is hidden inside some Algorithms book I never read. Makes me wish I majored in Computer Science instead of English Lit!

I'm not a real programmer but I play one with DBPro!
Back to top
Profile PM Email
BatVink
Moderator
22
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 17th Feb 2009 21:50
Link
OK, I'm getting tired of rewriting my code with all these additional ideas! I never figured that you only need one list to manage "in use" and "available for use". For me, this is currently two arrays and twice as much storage and management as I need.

Back to top
Profile PM Email
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 17th Feb 2009 22:53
Link
Yeah, the single array technique sounds really good. Will have to try that as well.


Health, Ammo, and bacon and eggs!
Back to top
Profile PM Email
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 17th Feb 2009 23:04
Link
Ok, here are examples of both an unsorted list, combining inuse & free lists into a single array, and a sorted version too using a binary search.

These use my array plug-in to make them more efficient (much more for the sorted one).

First, the unsorted - add two items, remove one, then add another, plus/minus shows whether the item is in use (+), or in the free list (-):


This provides an unsorted inuse and free list - It's fairly simple to understand. If you wish to grow the array in chunks, this will also work.

Next the sorted list - this requires a binary search for insertion and removal, and this time I'm using the ROTATE ARRAY command to insert items into the correct place in the list:


Of course, if you have a lot to load, it may be better to insert into your list using an unordered insert, then sort the array for the inuse range, and then maintain it using the ordered insert from that point on.

@BatVink, You'll probably need to modify this slightly to use a two-part key as I said in a previous post (Group & ID).

Utility plug-ins collection (updated 29/12/08) and
http://www.matrix1.demon.co.uk
Back to top
Profile PM Email Website
Back to top

Login to post a reply

Server time is: 2025-08-09 01:36:41
Your offset time is: 2025-08-09 01:36:41