Optimization Ideas I collected: [Re: Ok, what about benchmarks

[Paul E Johnson]

Darold Higa wrote:
> OK, with all of this being thrown around about the different environments and 
> languages, has anyone done an informal performance benchmark?
>
> I ran my CasinoWorld simulation (the one from Luna and Perrone) using Swarm 
> 1.4/Objective-C and got about 10x performance going from Windows 98 to Windows 
> NT/2000 and then another 10x Windows NT to Redhat (on roughly the same 
> hardware).  This fact prompted my co-author Michael Harrington, to move from a 
> Win2k environment to Redhat.
>
> The LinuxPPC implementation was slightly slower than Redhat.  The only 
> subjective proof I have that there was rough hardware parity was that between 
> the mac running under MacOS9 and wintel hardware running under Win98, the mac 
> won running address@hidden (Probably not a good comparison, but the only cross 
> platform benchmark I had handy).
If your simulation prints out anything to the terminal as it runs, and 
the terminal is not on top in MS Windows, then it causes a huge 
slowdown.  The Hugeness of the slowdown varies across WIndows system. If 
you eliminate any printf's you will see a huge difference.

Steve Railsback reported a performance test where the Windows version 
took significantly longer than Linux, but not on the 10x scale you report.

Now, concerning ways to speed up code, I've got a few things that really 
make a difference.

I'm starting a list since this comes up a lot. Here goes.

1. Avoid use of slow operators like %.  Recall I sped up heatbugs by 
about one half by changing that one little bit, see, here the 
replacement HeatSpace:

http://lark.cc.ku.edu/~pauljohn/Swarm/MySwarmCode/HeatSpace.m

I wish I had a good Idiot's Guide to tell me what other things besides % 
are really slow so I can avoid them.

Ken Cline told me once that creating objects is really slow, so I 
started rewriting programs to not destroy object, but rather recycle 
them.  I never measured the impact, though.

2. The advice from yesterday/today about processing of lists is very 
good, especially if you are doing permuted indexes.  Instead of 
createForEach, just create one action to self and then iterate over the 
list by hand.

3. Sometimes if you process a huge list of objects, you get overhead in 
the method look up for each one.  That's when the IMP cache of a method 
helps.  I lost my HOWTO document on that (I had sent it to Benedikt and 
Lars Erik a few years ago with a title like "Optimization advice for 
people who hail from frozen Northern Countries") but I still have the 
Next doc on it:


http://lark.cc.ku.edu/~pauljohn/SwarmFaq/Memos/IMP_Nextstep.txt

If you profile your program and you find a huge amount of 
obj_message_lookup, this might be recommended.

4. I've found dramatic speedups by redesigning algorithms. I had one 
really slow model where the agents would look around them on every step, 
collecting information within a radius of X units.  That was really 
slow.  SO I redesigned so that the agents would act, and "put" their 
action onto a Grid that would diffuse the impact of their action across 
the cells.  The Grid would remember its state, and only recorded the 
impact of relatively infrequent changes.  WHen agents needed to know 
"what can I see from where I am", that number was already calculated.

Doing that converted a model that took 2 days into a model that took 3 
minutes. That's this one:

http://lark.cc.ku.edu/~pauljohn/Swarm/MySwarmCode/activists-20020412.tar.gz


5. Sometimes you run into slowdowns because you are doing slow things 
with Swarm collections, Removing an item from a Swarm List, Map, or Set 
is slow because it works by looking, one-by-one, until it finds the one 
you want.

I have a class AVLSet which uses an avl tree (binary search tree) that 
really speeds up the search for specific items.  IT is a bit slower in 
the insertion of items, and slower on iteration, compared against a 
Swarm List, but much faster than removal.

--
Paul E. Johnson                       email: address@hidden
Dept. of Political Science            http://lark.cc.ku.edu/~pauljohn
1541 Lilac Lane, Rm 504
University of Kansas                  Office: (785) 864-9086
Lawrence, Kansas 66044-3177           FAX: (785) 864-5700


                 ==================================
  Swarm-Support is for discussion of the technical details of the day
  to day usage of Swarm.  For list administration needs (esp.
  [un]subscribing), please send a message to <address@hidden>
  with "help" in the body of the message.