added load factor, improved docs, java/cs in sync

2 files changed, 45 insertions, 13 deletions

diff --git a/src/cli/runtime/PersistentArray.cs b/src/cli/runtime/PersistentArray.cs
index 654aa2e8..c618a5c3 100644
--- a/src/cli/runtime/PersistentArray.cs
+++ b/src/cli/runtime/PersistentArray.cs
@@ -17,9 +17,31 @@ using System.Collections;
 namespace org.clojure.runtime

 {

 /**

- * Hybrid range/BitArray, multi-thread-safe

- * 

+ * Note that instances of this class are constant values

+ * i.e. set() returns a new array, old one is intact

+ *

+ * Multiple revisions (thread-safely) share the same master array

+ *

+ * Constant time most-recent-revision lookups

+ * Amortized constant-time sequential revisions (when loadFactor > 1)

+ * where a sequential revision is a revision of the most recent revision

+ *

+ * Non-sequential revisions are O(length), but with a small constant multiplier of 1/32

+ * Worst-case O(r) lookups for oldest revs where r is number of revisions

+ * at index i since last (automatic or manual) isolate. If set()s are roughly evenly

+ * distributed, r should be approximately == loadFactor, i.e. constant

+ * In pathological case (all mods to same index), r == (loadFactor * length)

+ *

+ * (loadFactor * length) old values are retained, even if the array revisions aren't

+ * Default loadFactor is 2.1

+ * When the load exceeds (loadFactor * length) the next revision is automatically isolated

+ * You can determine how many values are in the shared master by calling load()

+ * and can trim them by calling isolate() or resize(), which yield a new array with no

+ * sharing and no old values

+ *

  * 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 : IEnumerable{

@@ -38,13 +60,14 @@ internal class Master{
 	internal readonly Object defaultVal;

 	internal int rev;

 	internal int load;

+	internal readonly int maxLoad;

 

-	internal Master(int size, Object defaultVal)

-		{

+	internal Master(int size,Object defaultVal, double loadFactor){

 		this.array = new Entry[size];

 		this.defaultVal = defaultVal;

 		this.rev = 0;

 		this.load = 0;

+		this.maxLoad = (int)(size * loadFactor);

 		}

 }

 

@@ -99,8 +122,18 @@ public void Reset()
 	internal readonly int baseline;

 	internal readonly BitArray history;

 

-public PersistentArray(int size,Object defaultVal){

-	this.master = new Master(size, defaultVal);

+public PersistentArray(int size)

+		: this(size, null)

+		{

+		}

+		

+public PersistentArray(int size, Object defaultVal)

+	:this(size,defaultVal,2.1)

+	{

+	}

+

+public PersistentArray(int size, Object defaultVal, double loadFactor){

+	this.master = new Master(size, defaultVal, loadFactor);

 	this.rev = 0;

 	this.baseline = 0;

 	this.history = null;

@@ -114,10 +147,7 @@ public PersistentArray(int size,Object defaultVal){
 	this.history = history;

 }

 

-	public PersistentArray(int size)

-		: this(size, null)

-		{

-		}

+

 

 public int length(){

 	return master.array.Length;

@@ -136,7 +166,7 @@ public bool has(int i){
 

 public PersistentArray resize(int newLength)

 	{

-	PersistentArray ret = new PersistentArray(newLength, master.defaultVal);

+	PersistentArray ret = new PersistentArray(newLength, master.defaultVal, ((double)master.maxLoad) / length());

 	for (int i = 0; i < Math.Min(length(), newLength); i++)

 		{

 		Entry e = getEntry(i);

@@ -172,6 +202,8 @@ Entry getEntry(int i){
 }

 

 public PersistentArray set(int i,Object val) {

+	if(master.load >= master.maxLoad)

+		return isolate().set(i,val);

 	PersistentArray ret = getSetArray();

 	ret.doSet(i, val);

 	return ret;

@@ -228,7 +260,7 @@ static public void Main(String[] args){
 	int size = Int32.Parse(args[0]);

 	int writes = Int32.Parse(args[1]);

 	int reads = Int32.Parse(args[2]);

-	ArrayList v = new ArrayList(size);

+	ArrayList v = ArrayList.Synchronized(new ArrayList(size));

 	//v.setSize(size);

 	PersistentArray p = new PersistentArray(size);

 

diff --git a/src/org/clojure/runtime/PersistentArray.java b/src/org/clojure/runtime/PersistentArray.java
index 7d6a9cb4..58321629 100644
--- a/src/org/clojure/runtime/PersistentArray.java
+++ b/src/org/clojure/runtime/PersistentArray.java
@@ -29,7 +29,7 @@ import java.util.Random;
  * Amortized constant-time sequential revisions (when loadFactor > 1)
  * where a sequential revision is a revision of the most recent revision
  *
- * Non-sequential revisions are O(length), but with a small constant multiplier of .03
+ * Non-sequential revisions are O(length), but with a small constant multiplier of 1/32
  * Worst-case O(r) lookups for oldest revs where r is number of revisions
  * at index i since last (automatic or manual) isolate. If set()s are roughly evenly
  * distributed, r should be approximately == loadFactor, i.e. constant