Nselect/uniformDoubleRand is the source of my java program slowdown

[Paul E Johnson]

At the end of this message, I pasted profiling information on a java
program and it points at usage of the
UniformDoubleDistImpl as the worst slow point.  I've done some 
experimenting and I've found that I caused this slowdown by writing my 
own java version of NSelect (which I called NSelectPJ). I think I did 
this because I could get Swarm's NSelect to work with Java classes. 
NSelectPJ is just a boneheaded translation of Swarm's own NSelect from C 
to Java.  When the number of objects among which  the selection needs to 
be made grows large, say 10000 or 20000, the NSelectPJ's usage of 
uniformDoubleDist brings the program to its knees.

Do I need to go study some book of algorithms to get random selection 
from large collections?  Or have I unwittingly done something that slows 
down NSelect?  Maybe my selection class has a flaw:


// Adaptation (ripoff) of Swarm: src/simtools/NSelect.m
import swarm.Globals;
import java.util.Iterator;
import java.util.Collection;

public class NSelectPJ {

  public static void select$from$into ( int n, Collection aCollection, 
Collection bCollection){
    Iterator a;
    int N; // total number of items in aCollection
    int t; // items seen
    int m; // items selected
    float r;
    if ( n == 0)
      return;
    t = m = 0;
    N = aCollection.size();
    if (N < n)
    {

      System.err.println ("Your collection size is smaller than your 
number of desired objects");

    }
    a = aCollection.iterator();
    while (m < n)
      {
        r = (float)Globals.env.uniformDblRand.getDoubleWithMin$withMax (0, 1.0);
        if ((((float)(N - t)) * r) >= ((float)(n - m)))
            a.next();
        else
        {
          m++;
          bCollection.add(a.next());
        }
      t++;
      }
        
      }
  }




Flat profile of 185.75 secs (3080 total ticks): main
  Interpreted + native   Method
  4.1%     0  +   126    swarm.simtoolsgui.ControlPanelImpl.setStateStopped
  1.4%    21  +    21    java.lang.Object.hashCode
  0.6%     0  +    18    swarm.simtoolsgui.ProbeDisplayManagerImpl.update
  0.2%     0  +     6 
swarm.SwarmEnvironmentImpl.createArchivedProbeDisplay
  0.2%     0  +     5    swarm.SwarmEnvironmentImpl.initSwarm
  0.1%     0  +     4    swarm.gui.ZoomRasterImpl.pack
  0.1%     0  +     4    java.lang.ClassLoader$NativeLibrary.load
  0.1%     0  +     4    java.io.FileOutputStream.writeBytes
  0.1%     0  +     3    swarm.analysis.EZGraphImpl.step
  0.1%     0  +     3    java.util.zip.Inflater.inflateBytes
  0.1%     0  +     2    java.lang.Throwable.fillInStackTrace
  0.1%     0  +     2    swarm.SwarmEnvironmentImpl.getCurrentTime
  0.1%     0  +     2    swarm.simtoolsgui.GUISwarmImpl.go
  0.1%     0  +     2    java.lang.Class.getMethods0
  0.1%     0  +     2 
swarm.random.NormalDistImpl.getSampleWithMean$withVariance
  0.1%     1  +     1    Citizen.<init>
  0.0%     0  +     1    swarm.SwarmEnvironmentCImpl.createBegin
  0.0%     0  +     1    swarm.random.UniformDoubleDistImpl.getDoubleSample
  0.0%     0  +     1    swarm.simtoolsgui.ActionCacheImpl.doTkEvents
  0.0%     0  +     1    swarm.simtoolsgui.GUISwarmImpl.getActionCache
  0.0%     0  +     1    java.lang.ClassLoader$NativeLibrary.find
  0.0%     0  +     1 
swarm.gui.ZoomRasterCImpl.create$setWindowGeometryRecordName
  0.0%     0  +     1    swarm.gui.ZoomRasterImpl.setWidth$Height
  0.0%     0  +     1 
swarm.analysis.EZGraphImpl.createSequence$withFeedFrom$andSelector
  0.0%     0  +     1    swarm.gui.ZoomRasterImpl.drawPointX$Y$Color
  8.2%    29  +   224    Total interpreted (including elided)

     Compiled + native   Method
  0.6%    20  +     0    Citizen.calcDisutility
  0.4%    12  +     0    java.util.AbstractList$Itr.next
  0.3%    10  +     0    java.util.ArrayList.get
  0.3%    10  +     0    NSelectPJ.select$from$into
  0.3%     7  +     1    java.util.LinkedList.listIterator
  0.2%     7  +     0    java.lang.Object.equals
  0.2%     6  +     0    java.util.HashMap.get
  0.1%     2  +     2    java.util.HashMap.getHashIterator
  0.1%     4  +     0    java.util.ArrayList.add
  0.1%     3  +     0    java.util.LinkedList$ListItr.<init>
  0.1%     3  +     0    Citizen.receiveInvitation$Offer$Status
  0.1%     3  +     0    Citizen.step
  0.1%     2  +     0    java.util.LinkedList$ListItr.hasNext
  0.1%     2  +     0    Recruiter.contactAllIn$Offer$Status
  0.0%     1  +     0    java.util.AbstractList.listIterator
  0.0%     1  +     0    java.util.HashMap$2.iterator
  0.0%     0  +     1    java.io.BufferedOutputStream.flush
  0.0%     1  +     0    java.util.AbstractList$Itr.checkForComodification
  0.0%     1  +     0    java.util.AbstractList$Itr.hasNext
  0.0%     1  +     0    java.util.LinkedList$Entry.<init>
  0.0%     1  +     0    ObserverSwarm.drawFeature$PointX$Y$Color
  0.0%     1  +     0    Citizen.setIdealPoint
  0.0%     1  +     0    java.util.ArrayList.RangeCheck
  0.0%     1  +     0    Citizen.flushRenewalList
  0.0%     1  +     0    Citizen.drawSelfOn
  3.6%   106  +     5    Total compiled (including elided)
         Stub + native   Method
 62.6%    11  +  1917 
swarm.random.UniformDoubleDistImpl.getDoubleWithMin$withMax
  6.4%     1  +   197    swarm.SwarmEnvironmentImpl.getCurrentTime
  5.5%     0  +   170    swarm.gui.ZoomRasterImpl.drawPointX$Y$Color
  3.7%     0  +   114 
swarm.random.NormalDistImpl.getSampleWithMean$withVariance
  2.0%     0  +    63    swarm.random.UniformDoubleDistImpl.getDoubleSample
  0.6%     5  +    14    java.lang.StrictMath.pow
  0.1%     0  +     4    swarm.objectbase.SwarmImpl.getZone
  0.0%     0  +     1    java.io.FileOutputStream.writeBytes
 81.1%    17  +  2480    Total stub
  Runtime stub + native  Method
  0.2%     7  +     0    interpreter_entries
  0.2%     7  +     0    Total runtime stubs
  Thread-local ticks:
  0.0%     1             Blocked (of total)
  0.0%     1             Class loader
  1.1%    33             Interpreter
  5.3%   163             Unknown: running frame
  0.0%     1             Unknown: no last frame
  0.4%    13             Unknown: thread_state
Global summary of 185.87 seconds:
100.0%  3128             Received ticks
  1.5%    46             Received GC ticks
  0.1%     4             Compilation
  0.0%     1             Class loader
  1.1%    33             Interpreter
  5.7%   177             Unknown code

--
Paul E. Johnson                       email: address@hidden
Dept. of Political Science            http://lark.cc.ukans.edu/~pauljohn
University of Kansas                  Office: (785) 864-9086
Lawrence, Kansas 66045                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.