Speed

[Doug Donalson]

Peridodiaclly we have had discussions of speed tradeoffs.  I just ran a little test and was blown away by the difference between two list removes.

 

Background:  I am presently developing a model to simulate mussel populations in continuous space.  The two major demographic parameters are recrutement and death rates.    There are presently 4 active graphs updated once per time step, a Zoom Raster, a standard 2-D display, a Histogram, and a time series.  (I point this out because they are generally big time hogs so measurable speed ups in their presence are even more interesting.  There quite a number of lists in the system, but most are reasonably short i.e. local spatial lists.  One exception is the main list of all mussels handeled my my model swarm. 

 

I ran a test to see how much of a speedup an O(1) remove from this list was compared to an O(n).  There were an average of 15,000 individuals in the system with a mean lifetime of 20 time steps.  (Death rate is the important parameter as death is when the list must be searched.  Insert is just addLast.)  This gives a remove about every 0.001 time steps.  I ran each type for exactly 15 min and recorded the model time at that point. 

 

O(n)=229 time steps

O(1)=722 time steps

 

I have to admit, I was not expecting anywhere close to that magnitude of difference!

 

For anyone who has very long lists of agents with a lot of replacements here is what I did:

 

1.)  The agent definition needs a variable:

 

member_t   listMember; (of course, it doesn't have to be called listMember)

 

2.) When creating the list, define the type:

 

  listType = [List customizeBegin: [self getZone]];
  [listType setIndexFromMemberLoc: offsetof( Mussel, listMember )];

// Note that here Mussel is the class type.
  listType = [listType customizeEnd];

  musselList=[listType create: self ];

 

DON'T MAKE MY MISTAKE, YOU NEED A SEPERATE "member_t" LINK FOR EACH SEPERATE LIST OF THIS TYPE!

 

3.)  On remove, instead of

 

[musselList remove: aMussel]

 

use:

 

  index=[musselList createIndex: [self getZone] fromMember: aMussel];
  removedMussel=[index remove];
  [index drop];

 

Thanks to Marcus for passing this on to me.

 

Cheers,

 

   D3

*********************************************************************
* Doug Donalson                 Office: (805) 893-2962
* Ecology, Evolution,           Home:   (805) 961-4447
* and Marine Biology            email address@hidden 
* UC Santa Barbara
* Santa Barbara Ca. 93106
*********************************************************************
*                                                                        
*   The most exciting phrase to hear in science, the one that            
*   heralds new discoveries, is not "EUREKA" (I have found it) but       
*   "That's funny ...?"                                                  
*                                                                        
*       Isaac Asimov                                                     
*                                                                        
*********************************************************************