perf tweaks

4 files changed, 47 insertions, 29 deletions

diff --git a/src/org/clojure/runtime/ListMap.java b/src/org/clojure/runtime/ListMap.java
index a87a699a..16c77e9c 100644
--- a/src/org/clojure/runtime/ListMap.java
+++ b/src/org/clojure/runtime/ListMap.java
@@ -14,6 +14,18 @@ package org.clojure.runtime;
 
 import java.util.Iterator;
 
+/**
+ * Immplementation of persistent map on a linked list
+
+ * Note that instances of this class are constant values
+ * i.e. add/remove etc return new values
+ *
+ * Lookups/changes are linear, so only appropriate for _very_small_ maps
+ * ArrayMap is generally faster, but this class avoids the double allocation,
+ * and so is better/faster as a bucket for hash tables
+ *
+ * null keys and values are ok, but you won't be able to distinguish a null value via get - use contains/find
+ */
 public class ListMap implements IMap, IMapEntry
 {
 
@@ -194,16 +206,14 @@ static class Link extends ListMap{
 	}
 
 	public ListMap put(Object key, Object val){
-		if(equalKey(key,_key))
+		IMapEntry e = find(key);
+		if(e != null)
 			{
-			if(val == _val)
+			if(e.val() == val)
 				return this;
-			return new Link(key,val,_rest);
+			return create(_key,_val,remove(key));
 			}
-		ListMap r = _rest.put(key,val);
-		if(r == _rest)  //already there with same value
-			return this;
-		return new Link(_key,_val,r);
+		return new Link(key,val,this);
 	}
 
 	public ListMap remove(Object key){
@@ -212,9 +222,7 @@ static class Link extends ListMap{
 		ListMap r = _rest.remove(key);
 		if(r == _rest)  //not there
 			return this;
-		if(r == EMPTY)
-			return new Tail(_key,_val);
-		return new Link(_key, _val, r);
+		return create(_key,_val,r);
 	}
 
 	public Object get(Object key){
@@ -228,6 +236,12 @@ static class Link extends ListMap{
 		return count();
 	}
 
+	ListMap create(Object k,Object v,ListMap r){
+		if(r == EMPTY)
+			return new Tail(k,v);
+		return new Link(k, v, r);
+	}
+
 }
 
 boolean equalKey(Object k1,Object k2){
diff --git a/src/org/clojure/runtime/PersistentArray.java b/src/org/clojure/runtime/PersistentArray.java
index 11c38be7..b581ecf6 100644
--- a/src/org/clojure/runtime/PersistentArray.java
+++ b/src/org/clojure/runtime/PersistentArray.java
@@ -44,7 +44,6 @@ import java.util.Random;
  *
  * See Cohen for basic idea
  * I added hybrid most-recent-sequential-range + shared-bitset idea, multi-thread-safety
- * Java implementation is lock-free
  */
 
 public class PersistentArray implements Iterable{
diff --git a/src/org/clojure/runtime/PersistentHashMap.java b/src/org/clojure/runtime/PersistentHashMap.java
index 40fb50dc..f4ac6330 100644
--- a/src/org/clojure/runtime/PersistentHashMap.java
+++ b/src/org/clojure/runtime/PersistentHashMap.java
@@ -15,7 +15,7 @@ import java.util.Iterator;
 public class PersistentHashMap implements IMap, Iterable{

 

 IMap impl;

-static final int CAPACITY_THRESHOLD = 10;

+static final int CAPACITY_THRESHOLD = 42;

 

 public PersistentHashMap(Object[] init){

     if(init.length/2 < CAPACITY_THRESHOLD)

@@ -26,7 +26,8 @@ public PersistentHashMap(Object[] init){
 public PersistentHashMap(int initialCapacity){

     if(initialCapacity < CAPACITY_THRESHOLD)

         impl = createArrayMap();

-    impl = createHashtableMap(initialCapacity);

+	else

+        impl = createHashtableMap(initialCapacity);

 }

 

 PersistentHashMap(IMap impl){

diff --git a/src/org/clojure/runtime/RBTree.java b/src/org/clojure/runtime/RBTree.java
index e9ebe7bb..6aec53e2 100644
--- a/src/org/clojure/runtime/RBTree.java
+++ b/src/org/clojure/runtime/RBTree.java
@@ -675,23 +675,26 @@ static public void main(String args[]){
 		ints[i] = new Integer(i);
 		}
 	Collections.shuffle(Arrays.asList(ints));
+	//force the ListMap class loading now
+	ListMap.EMPTY.add(1).add(2).add(3);
 	System.out.println("Building set");
-	  long startTime = System.nanoTime();
-	//IMap set = new PersistentHashMap(1);
-	IMap set = new HashtableMap(1001);
+	IMap set = new PersistentHashMap(1001);
+	//IMap set = new HashtableMap(1001);
 	//IMap set = new ListMap();
+	//IMap set = new ArrayMap();
 	//IMap set = new RBTree();
 //	for(int i = 0; i < ints.length; i++)
 //		{
 //		Integer anInt = ints[i];
 //		set = set.add(anInt);
 //		}
+	long startTime = System.nanoTime();
 	for(int i = 0; i < ints.length; i++)
 		{
 		Integer anInt = ints[i];
 		set = set.put(anInt, anInt);
 		}
-    System.out.println("_count = " + set.count());
+    //System.out.println("_count = " + set.count());
 
 
 //	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
@@ -702,8 +705,8 @@ static public void main(String args[]){
 		IMapEntry o = (IMapEntry) it.next();
 		if(!set.contains(o.key()))
 			System.err.println("Can't find: " + o);
-		else if(n < 2000)
-			System.out.print(o.key().toString() + ",");
+		//else if(n < 2000)
+		//	System.out.print(o.key().toString() + ",");
 		}
 
 	for(int i = 0; i < ints.length/2; i++)
@@ -712,10 +715,10 @@ static public void main(String args[]){
 		set = set.remove(anInt);
 		}
 
-	System.out.println();
 	long estimatedTime = System.nanoTime() - startTime;
+	System.out.println();
 
-	System.out.println("_count = " + set.count() + ", time: " + estimatedTime/1000000);
+	System.out.println("_count = " + set.count() + ", time: " + estimatedTime/10000);
 
 	System.out.println("Building ht");
 	Hashtable ht = new Hashtable(1001);
@@ -730,15 +733,15 @@ static public void main(String args[]){
 		Integer anInt = ints[i];
 		ht.put(anInt, anInt);
 		}
-    System.out.println("size = " + ht.size());
-	Enumeration e = ht.keys();
-	while(e.hasMoreElements())
+    //System.out.println("size = " + ht.size());
+	it = ht.entrySet().iterator();
+	while(it.hasNext())
 		{
-		Integer o = (Integer) e.nextElement();
-		if(!ht.containsKey(o))
+		Map.Entry o = (Map.Entry) it.next();
+		if(!ht.containsKey(o.getKey()))
 			System.err.println("Can't find: " + o);
-		else if(n < 2000)
-			System.out.print(o.toString() + ",");
+		//else if(n < 2000)
+		//	System.out.print(o.toString() + ",");
 		}
 
 	for(int i = 0; i < ints.length/2; i++)
@@ -747,7 +750,8 @@ static public void main(String args[]){
 		ht.remove(anInt);
 		}
 	estimatedTime = System.nanoTime() - startTime;
-	System.out.println("size = " + ht.size() + ", time: " + estimatedTime/1000000);
+	System.out.println();
+	System.out.println("size = " + ht.size() + ", time: " + estimatedTime/10000);
 
 //	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
 //	                   + ", depth: " + set.depth());