Bug 1326 - ArrayList usage that results in very slow removeChild calls

The use of ArrayList supplies fast addChild speed but
dis-proportionately poor removeChild speed, so the worst culprits have
been swapped for LinkedHashSet

4 files changed, 35 insertions, 39 deletions

diff --git a/src/main/java/org/jogamp/java3d/NodeComponentRetained.java b/src/main/java/org/jogamp/java3d/NodeComponentRetained.java
index d8ca286..b209866 100644
--- a/src/main/java/org/jogamp/java3d/NodeComponentRetained.java
+++ b/src/main/java/org/jogamp/java3d/NodeComponentRetained.java
@@ -26,7 +26,7 @@
 
 package org.jogamp.java3d;
 
-import java.util.ArrayList;
+import java.util.LinkedHashSet;
 
 /**
  * Retained version of NodeComponent
@@ -48,7 +48,7 @@ class NodeComponentRetained extends SceneGraphObjectRetained {
 
     // A list of NodeRetained Objects that refer, directly or indirectly, to this
     // NodeComponentRetained
-    ArrayList users = new ArrayList(1);
+    LinkedHashSet<NodeRetained> users = new LinkedHashSet<NodeRetained>();
 
     // Mirror object of this node compoenent object
     NodeComponentRetained mirror = null;
@@ -115,27 +115,22 @@ class NodeComponentRetained extends SceneGraphObjectRetained {
 	}
     }
 
-    // Copy the list of useres passed in into this
+    // Copy the list of users passed in into this
     void copyMirrorUsers(NodeComponentRetained node) {
 	synchronized(mirror.users) {
 	  synchronized(node.mirror.users) {
-	      int size = node.mirror.users.size();
-	      for (int i=0; i<size ; i++) {
-		  mirror.users.add(node.mirror.users.get(i));
-	      }
+		  mirror.users.addAll(node.mirror.users);
 	    }
 	}
     }
 
 
-    // Remove the users of "node" from "this" node compoenent
+    // Remove the users of "node" from "this" node component
     void removeMirrorUsers(NodeComponentRetained node) {
 
 	synchronized(mirror.users) {
 	  synchronized(node.mirror.users) {
-	      for (int i=node.mirror.users.size()-1; i>=0; i--) {
-		  mirror.users.remove(mirror.users.indexOf(node.mirror.users.get(i)));
-	      }
+		  mirror.users.removeAll(node.mirror.users);
 	    }
 	}
     }
@@ -143,13 +138,13 @@ class NodeComponentRetained extends SceneGraphObjectRetained {
     // Add a user to the list of users
     synchronized void removeUser(NodeRetained node) {
 	if (node.source.isLive())
-	    users.remove(users.indexOf(node));
+		users.remove(node);
     }
 
     // Add a user to the list of users
     synchronized void addUser(NodeRetained node) {
 	if (node.source.isLive())
-	    users.add(node);
+		users.add(node);
     }
 
 
@@ -160,9 +155,13 @@ class NodeComponentRetained extends SceneGraphObjectRetained {
 	    return;
 	}
 
-	for (int i=users.size()-1; i >=0; i--) {
-	    ((NodeRetained)users.get(i)).notifySceneGraphChanged(false);
-	}
+	// the reverse order does not appear to be compulsory
+	// cahnge from ArayList to LinkedHashMap prevents ordered traversal
+	for (NodeRetained nr : users)
+		nr.notifySceneGraphChanged(false);
+	//for (int i=users.size()-1; i >=0; i--) {
+	//    ((NodeRetained)users.get(i)).notifySceneGraphChanged(false);
+	//}
     }
 
     /**
diff --git a/src/main/java/org/jogamp/java3d/RenderBin.java b/src/main/java/org/jogamp/java3d/RenderBin.java
index 6ab4481..99def73 100644
--- a/src/main/java/org/jogamp/java3d/RenderBin.java
+++ b/src/main/java/org/jogamp/java3d/RenderBin.java
@@ -33,6 +33,7 @@ import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 
 import org.jogamp.vecmath.Color3f;
@@ -263,7 +264,7 @@ ArrayList<ArrayList<OrderedBin>> toBeAddedBinList = new ArrayList<ArrayList<Orde
  * that the same snapshot of the geometry is rendered
  * across all canvases
  */
-ArrayList<GeometryRetained> lockGeometryList = new ArrayList<GeometryRetained>(5);
+LinkedHashSet<GeometryRetained> lockGeometryList = new LinkedHashSet<GeometryRetained>(5);
 
 
     /**
@@ -296,7 +297,7 @@ ArrayList<OrderedBin> bgOrderedBins = new ArrayList<OrderedBin>(5);
 
     // List of node components that need special processing, due to
     // extensions
-    ArrayList nodeComponentList = new ArrayList(5);
+    LinkedHashSet<ImageComponentRetained> nodeComponentList = new LinkedHashSet<ImageComponentRetained>();
 
 
     // List of node components ***for this frame*** that need special
@@ -5665,8 +5666,8 @@ void reEvaluateEnv(ArrayList<LightRetained> mLts, ArrayList<FogRetained> fogs,
 
 	// Vertex array is locked for every time renderer is run
 	size =  lockGeometryList.size();
-	for (int i = 0; i < size; i++) {
-		GeometryRetained geo = lockGeometryList.get(i);
+	for (GeometryRetained geo : lockGeometryList)
+	{
 		geo.geomLock.getLock();
 	}
 
@@ -5680,9 +5681,9 @@ void reEvaluateEnv(ArrayList<LightRetained> mLts, ArrayList<FogRetained> fogs,
 
 	// Lock all the by reference image components
 	size = nodeComponentList.size();
-	for (int i = 0; i < size; i++) {
-	    ImageComponentRetained nc = (ImageComponentRetained)nodeComponentList.get(i);
-	    nc.geomLock.getLock();
+	for (ImageComponentRetained nc : nodeComponentList)
+	{
+		nc.geomLock.getLock();
 	}
     }
 
@@ -5691,8 +5692,8 @@ void reEvaluateEnv(ArrayList<LightRetained> mLts, ArrayList<FogRetained> fogs,
 	int size;
 
 	size = lockGeometryList.size();
-	for (int i = 0; i < size; i++) {
-		GeometryRetained geo = lockGeometryList.get(i);
+	for (GeometryRetained geo : lockGeometryList)
+	{
 		geo.geomLock.unLock();
 	}
 
@@ -5704,9 +5705,7 @@ void reEvaluateEnv(ArrayList<LightRetained> mLts, ArrayList<FogRetained> fogs,
 	// Clear the display list clear list
 	dlistLockList.clear();
 	// Lock all the by reference image components
-	size =  nodeComponentList.size();
-	for (int i = 0; i < size; i++) {
-	    ImageComponentRetained nc = (ImageComponentRetained)nodeComponentList.get(i);
+	for(ImageComponentRetained nc : nodeComponentList){
 	    nc.geomLock.unLock();
 	}
     }
diff --git a/src/main/java/org/jogamp/java3d/Renderer.java b/src/main/java/org/jogamp/java3d/Renderer.java
index 7150b86..54d426e 100644
--- a/src/main/java/org/jogamp/java3d/Renderer.java
+++ b/src/main/java/org/jogamp/java3d/Renderer.java
@@ -912,14 +912,10 @@ ArrayList<TextureRetained> textureIDResourceTable = new ArrayList<TextureRetaine
 			    listOfCtxs.add(canvas.ctx);
 			    listOfCanvases.add(canvas);
 
-			    if (renderBin.nodeComponentList.size() > 0) {
-				for (i = 0; i < renderBin.nodeComponentList.size(); i++) {
-				    NodeComponentRetained nc = (NodeComponentRetained)renderBin.nodeComponentList.get(i);
-                                    if(nc instanceof ImageComponentRetained) {
-                                        ((ImageComponentRetained)nc).evaluateExtensions(canvas);
-                                    }
+			    for (ImageComponentRetained nc : renderBin.nodeComponentList)
+				{			    	
+                   nc.evaluateExtensions(canvas);  
 				}
-                            }
 
                             // enable separate specular color
 			    canvas.enableSeparateSpecularColor();
diff --git a/src/main/java/org/jogamp/java3d/Shape3DRetained.java b/src/main/java/org/jogamp/java3d/Shape3DRetained.java
index 7270c0c..88f3823 100644
--- a/src/main/java/org/jogamp/java3d/Shape3DRetained.java
+++ b/src/main/java/org/jogamp/java3d/Shape3DRetained.java
@@ -28,6 +28,7 @@ package org.jogamp.java3d;
 
 import java.util.ArrayList;
 import java.util.Enumeration;
+import java.util.LinkedHashSet;
 import java.util.Vector;
 
 import org.jogamp.vecmath.Point3d;
@@ -2365,7 +2366,7 @@ Enumeration getAllGeometries(int id) {
      * This is used to send a message of the snapshot of the
      * geometry atoms that are affected by this change.
      */
-final static ArrayList<ArrayList<GeometryAtom>> getGeomAtomsList(ArrayList userList, ArrayList<VirtualUniverse> univList) {
+final static ArrayList<ArrayList<GeometryAtom>> getGeomAtomsList(LinkedHashSet<NodeRetained> userList, ArrayList<VirtualUniverse> univList) {
 	ArrayList<ArrayList<GeometryAtom>> listPerUniverse = new ArrayList<ArrayList<GeometryAtom>>();
 	int index;
 	ArrayList<GeometryAtom> gaList = null;
@@ -2374,9 +2375,10 @@ final static ArrayList<ArrayList<GeometryAtom>> getGeomAtomsList(ArrayList userL
 	VirtualUniverse firstFndUniv = null;
 
 	synchronized(userList) {
-	    for (int i = userList.size()-1; i >=0; i--) {
-		ms = (Shape3DRetained) userList.get(i);
-
+	    //for (int i = userList.size()-1; i >=0; i--) {
+		//ms = (Shape3DRetained) userList.get(i);
+		for(NodeRetained nr : userList){
+			ms = (Shape3DRetained)nr;
 		if(moreThanOneUniv == false) {
 		    if(firstFndUniv == null) {
 			firstFndUniv = ms.universe;