Revision: 3358
http://vexi.svn.sourceforge.net/vexi/?rev=3358&view=rev
Author: clrg
Date: 2009-01-14 21:19:18 +0000 (Wed, 14 Jan 2009)
Log Message:
-----------
More efficiency work for arrays and hashmaps
- Use arraycopy for splice/slice in JSArray
- Reduce Hash to little more than a HashMap (removes indirection, saves memory)
Modified Paths:
--------------
trunk/core/org.ibex.js/src/org/ibex/js/JSArray.jpp
trunk/core/org.ibex.js/src/org/ibex/js/JSArrayLike.java
trunk/core/org.ibex.js/src_junit/test/js/exec/array/testsplice.js
trunk/core/org.ibex.util/src/org/ibex/util/Basket.java
trunk/core/org.ibex.util/src/org/ibex/util/Cache.java
Modified: trunk/core/org.ibex.js/src/org/ibex/js/JSArray.jpp
===================================================================
--- trunk/core/org.ibex.js/src/org/ibex/js/JSArray.jpp 2009-01-14 02:44:57 UTC
(rev 3357)
+++ trunk/core/org.ibex.js/src/org/ibex/js/JSArray.jpp 2009-01-14 21:19:18 UTC
(rev 3358)
@@ -6,7 +6,7 @@
import org.ibex.util.*;
-/** A JavaScript JSArray */
+/** A JavaScript array implementation */
public class JSArray extends Basket.Array implements Basket.CompareFunc,
Constants, JSArrayLike {
public JSArray() { }
@@ -14,7 +14,7 @@
public JSArray(JS[] args) { super(args.length); addAll(args); }
public JSArray(JS arg) { super(1); add(arg); }
- public JS type(){ return SC_array; }
+ public JS type() { return SC_array; }
public JS unclone() { return this; }
public JS.Keys keys() throws JSExn { return new JSArrayLike.Keys(this); }
@@ -45,20 +45,19 @@
} catch (IndexOutOfBoundsException e) { return null; }
}
public void put(JS key, JS val) throws JSExn {
- if (JSU.toString(key).equals("length")) { setSize(JSU.toInt(val)); }
+ if (JSU.toString(key).equals("length")) { size(JSU.toInt(val)); }
- if (key == null || !(JSU.isInt(key)))//
+ if (key == null || !(JSU.isInt(key)))
throw new JSExn("Arrays only support positive integer keys, can
not use: "+JSU.toString(key));
int i = JSU.toInt(key);
if (i < 0) throw new JSExn("Attempt to put to negative key '"+i+" on
an array");
if (size() < i+1) size(i + 1);
- //while (size() < i) add(null);
set(i, val);
}
public String[] getFormalArgs() { return EMPTY_STRING_ARRAY; }
public int callType(){ return CALLTYPE_METHOD; }
- public String coerceToString(){ return "array$" +
Integer.toHexString(hashCode());}
+ public String coerceToString() { return "array$" +
Integer.toHexString(hashCode()); }
public JS call(JS method, JS[] args) throws JSExn {
//#switch(JSU.toString(method))
@@ -93,70 +92,63 @@
/** FEATURE: move to specialised ArrayStore superclass. */
public void addAll(JS[] entries) { for (int i=0; i < entries.length; i++)
add(entries[i]); }
- public void setSize(int newSize) {
- size(newSize);
- for (int i=size(); i < newSize; i++) add(null);
- for (int i=size() - 1; i >= newSize; i--) remove(i);
- }
-
// ECMA Implementation ////////////////////////////////////////////////////
+ /** joins tegether array contents into a string */
private JS join(String sep) throws JSExn {
int length = size();
- if(length == 0) return SC_;
+ if (length == 0) return SC_;
StringBuffer sb = new StringBuffer(64);
int i=0;
- while(true) {
+ while (true) {
JS o = (JS)get(i);
- if(o != null) sb.append(JSU.toString(o));
- if(++i == length) break;
+ if (o != null) sb.append(JSU.toString(o));
+ if (++i == length) break;
sb.append(sep);
}
return JSU.S(sb.toString());
}
-
+
+ /** create a copy of an array between indice start and end */
private JS slice(int start, int end) {
int length = size();
- if(start < 0) start = length+start;
- if(end < 0) end = length+end;
- if(start < 0) start = 0;
- if(end < 0) end = 0;
- if(start > length) start = length;
- if(end > length) end = length;
- JSArray a = new JSArray(end-start);
- for(int i=0;i<end-start;i++) // FEATURE: with ArrayStore do
System.arraycopy()
- a.set(i, get(start+i));
- return a;
+ if (start < 0) start = length+start;
+ if (end < 0) end = length+end;
+ if (start < 0) start = 0;
+ if (end < 0) end = 0;
+ if (start > length) start = length;
+ if (end > length) end = length;
+ JSArray ret = new JSArray(end-start);
+ Array.arraycopy(this, start, ret, 0, end-start);
+ return ret;
}
+ /** remove and return the portion of an array between the specified indice
*/
private JS splice(JS[] args) throws JSExn {
int oldLength = size();
int start = JSU.toInt(args.length < 1 ? null : args[0]);
int deleteCount = JSU.toInt(args.length < 2 ? null : args[1]);
int newCount = args.length - 2;
- if(newCount < 0) newCount = 0;
- if(start < 0) start = oldLength+start;
- if(start < 0) start = 0;
- if(start > oldLength) start = oldLength;
- if(deleteCount < 0) deleteCount = 0;
- if(deleteCount > oldLength-start) deleteCount = oldLength-start;
+ if (newCount < 0) newCount = 0;
+ if (start < 0) start = oldLength+start;
+ if (start < 0) start = 0;
+ if (start > oldLength) start = oldLength;
+ if (deleteCount < 0) deleteCount = 0;
+ if (deleteCount > oldLength-start) deleteCount = oldLength-start;
int newLength = oldLength - deleteCount + newCount;
- int lengthChange = newLength - oldLength;
JSArray ret = new JSArray(deleteCount);
- for(int i=0;i<deleteCount;i++) // FEATURE: ArrayStore
System.arraycopy()
- ret.set(i, get(start+i));
- if(lengthChange > 0) {
- setSize(newLength);
- for(int i=newLength-1;i>=start+newCount;i--)
- set(i, get(i-lengthChange));
- } else if(lengthChange < 0) {
- for(int i=start+newCount;i<newLength;i++)
- set(i, get(i-lengthChange));
- setSize(newLength);
- }
- for(int i=0;i<newCount;i++)
- set(start+i, args[i+2]);
+ ret.size(deleteCount);
+ // first copy the specified indice into the return array
+ Array.arraycopy(this, start, ret, 0, deleteCount);
+ // if array grows, must grow it before shuffling remaining contents
+ if (newLength > oldLength) size(newLength);
+ // copy the remaining array contents to new position
+ Array.arraycopy(this, start+deleteCount, this, start+newCount,
oldLength-deleteCount-start);
+ // copy in the additionally specified elements required
+ if (newCount > 0) Array.arraycopy(new Array(args, 2, args.length-2),
0, this, start, newCount);
+ // hide remaining contents
+ if (oldLength > newLength) size(newLength);
return ret;
}
Modified: trunk/core/org.ibex.js/src/org/ibex/js/JSArrayLike.java
===================================================================
--- trunk/core/org.ibex.js/src/org/ibex/js/JSArrayLike.java 2009-01-14
02:44:57 UTC (rev 3357)
+++ trunk/core/org.ibex.js/src/org/ibex/js/JSArrayLike.java 2009-01-14
21:19:18 UTC (rev 3358)
@@ -1,11 +1,11 @@
package org.ibex.js;
-public interface JSArrayLike extends JS{
+public interface JSArrayLike extends JS {
public JS[] toArray() throws JSExn;
public int length() throws JSExn;
- static public class Keys extends JS.Keys{
+ static public class Keys extends JS.Keys {
JSArrayLike keysof;
- public Keys(JSArrayLike obj){
+ public Keys(JSArrayLike obj) {
super(obj);
this.keysof = obj;
}
@@ -19,6 +19,6 @@
public JS _next() { return JSU.N(n++); }
};
}
- protected JS size() throws JSExn {return
JSU.N(keysof.length());}
+ protected JS size() throws JSExn { return
JSU.N(keysof.length()); }
}
}
Modified: trunk/core/org.ibex.js/src_junit/test/js/exec/array/testsplice.js
===================================================================
--- trunk/core/org.ibex.js/src_junit/test/js/exec/array/testsplice.js
2009-01-14 02:44:57 UTC (rev 3357)
+++ trunk/core/org.ibex.js/src_junit/test/js/exec/array/testsplice.js
2009-01-14 21:19:18 UTC (rev 3358)
@@ -1,8 +1,11 @@
var x = ["a","b","c","x","y","z"];
var y = x.splice(2,2);
+assert(x.length==4);
+assert(y.length==2);
assert(x.join(",")=="a,b,y,z");
-assert(y.join(","),"a,b,y,z");
+assert(y.join(",")=="c,x");
var z = x.splice(2,0,"m","n");
assert(z.length==0);
+assert(x.length==6);
assert(x.join(","),"a,b,m,n,y,z");
Modified: trunk/core/org.ibex.util/src/org/ibex/util/Basket.java
===================================================================
--- trunk/core/org.ibex.util/src/org/ibex/util/Basket.java 2009-01-14
02:44:57 UTC (rev 3357)
+++ trunk/core/org.ibex.util/src/org/ibex/util/Basket.java 2009-01-14
21:19:18 UTC (rev 3358)
@@ -11,7 +11,7 @@
public boolean containsValue(Object object);
public void clear();
public int size();
- public void remove(Object object);
+ public Object remove(Object object);
public interface List extends Basket {
public void add(Object object);
@@ -59,8 +59,12 @@
public Array() { this(10); }
public Array(int initialCapacity) { o = new Object[initialCapacity]; }
public Array(Object entry) { this(1); add(entry); }
+ public Array(Object[] src, int start, int num) {
+ this(num);
+ System.arraycopy(src, start, o, 0, num);
+ }
- public void enqueue(Object o) { add(o); }
+ public void enqueue(Object o) { add(o); }
// FEATURE: make this more efficient with general wraparound
public Object dequeue() {
@@ -70,16 +74,16 @@
public void add(Object obj) { add(size, obj); }
public void add(int i, Object obj) {
- size(size + 1);
- if (size - 1 > i) System.arraycopy(o, i, o, i + 1, size - i);
- o[i] = obj; size++;
+ size(size+1);
+ if (size-1 > i) System.arraycopy(o, i, o, i+1, size-i);
+ o[i] = obj;
}
public Object set(int i, Object obj) {
if (i >= o.length) throw new IndexOutOfBoundsException(
"index "+i+" is beyond list boundary "+size);
Object old = o[i]; o[i] = obj;
- size = Math.max(i+1, size);
- return old;
+ size = Math.max(i+1, size);
+ return old;
}
public Object get(int i) {
if (i >= size) throw new IndexOutOfBoundsException(
@@ -89,11 +93,13 @@
public Object remove(int i) {
if (i >= size || i < 0) throw new IndexOutOfBoundsException(
"index "+i+" is beyond list boundary "+size);
- Object old = o[i]; o[i] = null;
- if (size - 1 > i) System.arraycopy(o, i + 1, o, i, size - i - 1);
- size--; return old;
+ Object old = o[i];
+ o[i] = null;
+ if (size-1 > i) System.arraycopy(o, i+1, o, i, size-i-1);
+ size--;
+ return old;
}
- public void remove(Object obj) { remove(indexOf(obj)); }
+ public Object remove(Object obj) { return remove(indexOf(obj)); }
public int indexOf(Object obj) {
for (int i=0; i < size; i++)
@@ -109,35 +115,43 @@
public void clear() { for (int i=0; i < size; i++) o[i] = null; size =
0; }
public int size() { return size; }
public void size(int s) {
- if (o.length >= s) return;
+ if (o.length >= s) {
+ // housekeeping
+ if (size > s) java.util.Arrays.fill(o, s, size-1, null);
+ size = s;
+ return;
+ }
Object[] newo = new Object[s];
System.arraycopy(o, 0, newo, 0, size);
o = newo;
+ size = s;
}
public void reverse() {
Object tmp;
- if(size==1) return;
+ if (size==1) return;
int last = size - 1;
- for (int i=0; i < (size/2); i++) {
- tmp = o[i];
- o[i] = o[last - i];
- o[last - i] = tmp; }
+ int half = (size/2);
+ for (int i=0; i < half; i++) {
+ tmp = o[i];
+ o[i] = o[last - i];
+ o[last - i] = tmp;
+ }
}
public void sort(CompareFunc c) { sort(this, null, c, 0, size-1); }
public static void sort(Array a, Array b, CompareFunc c, int start,
int end) {
Object tmpa, tmpb = null;
- if(start >= end) return;
+ if (start >= end) return;
//if(end-start==1)return;
- if(end-start <= 6) {
- for(int i=start+1;i<=end;i++) {
+ if (end-start <= 6) {
+ for (int i=start+1; i<=end; i++) {
tmpa = a.o[i];
if (b != null) tmpb = b.o[i];
int j;
- for(j=i-1;j>=start;j--) {
- if(c.compare(a.o[j],tmpa) <= 0) break;
+ for (j=i-1; j>=start; j--) {
+ if (c.compare(a.o[j],tmpa) <= 0) break;
a.o[j+1] = a.o[j];
if (b != null) b.o[j+1] = b.o[j];
}
@@ -150,8 +164,8 @@
int lo = start - 1;
int hi = end;
do {
- while(c.compare(a.o[++lo],pivot) < 0) { }
- while((hi > lo) && c.compare(a.o[--hi],pivot) > 0) { }
+ while (c.compare(a.o[++lo],pivot) < 0) { }
+ while ((hi > lo) && c.compare(a.o[--hi],pivot) > 0) { }
swap(a, lo,hi);
if (b != null) swap(b, lo,hi);
} while(lo < hi);
@@ -161,9 +175,14 @@
sort(a, b, c, start, lo-1);
sort(a, b, c, lo+1, end);
}
+
+ /** proxy for System.arraycopy */
+ public static void arraycopy(Array src, int srcPos, Array dest, int
destPos, int length) {
+ System.arraycopy(src.o, srcPos, dest.o, destPos, length);
+ }
private static final void swap(Array vec, int a, int b) {
- if(a != b) {
+ if (a != b) {
Object tmp = vec.o[a];
vec.o[a] = vec.o[b];
vec.o[b] = tmp;
@@ -184,45 +203,39 @@
*
* @author Charles Goodwin <[email protected]>
*/
- public class Hash implements Basket, Map {
- private int indexMultiple;
- private int initialCapacity;
- private float loadFactor;
- public HashMap[] maps;
+ public class HashInternal implements Basket, Map {
+ private static final int initialCapacity = 16;
+ private static final float loadFactor = 0.75f;
+ public HashMap map;
- public Hash() { this(16, 0.75F); }
- public Hash(int initialCapacity, float loadFactor) { this(1, 16,
0.75F); }
- public Hash(int indexMultiple, int initialCapacity, float loadFactor) {
- this.indexMultiple = indexMultiple;
- this.initialCapacity = initialCapacity;
- this.loadFactor = loadFactor;
- clear();
- }
+ public HashInternal() { clear(); }
+ public HashInternal(int initialCapacity, float loadFactor) { clear(); }
+ public HashInternal(int indexMultiple, int initialCapacity, float
loadFactor) { clear(); }
- public void clear() {
- maps = new HashMap[indexMultiple];
- for (int i=0; indexMultiple>i; i++)
- maps[i] = new HashMap(initialCapacity, loadFactor);
- }
- public boolean containsKey(Object key) {
- for(int i=0; indexMultiple>i; i++)
- if (maps[i].containsKey(key)) return true;
- return false;
- }
- public boolean containsValue(Object value) {
- for(int i=0; indexMultiple>i; i++)
- if (maps[i].containsValue(value)) return true;
- return false;
- }
- public Object[] dumpkeys() { return maps[0].keySet().toArray(); }
- public Object get(Object key) { return get(key, 0); }
- public Object get(Object key, int whichval) { return
maps[whichval].get(key); }
- public Object put(Object key, Object val) { return put(key, val, 0); }
- public Object put(Object key, Object val, int whichval) {
maps[whichval].put(key, val); return null; }
- public void remove(Object key) { for(int i=0; indexMultiple>i; i++)
maps[i].remove(key); }
- public void remove(Object key, int i) { maps[0].remove(key);}
- public int size() { return maps[0].size(); }
+ public void clear() { map = new HashMap(initialCapacity, loadFactor); }
+ public boolean containsKey(Object key) { return map.containsKey(key); }
+ public boolean containsValue(Object value) { return
map.containsValue(value); }
+ public Object[] dumpkeys() { return map.keySet().toArray(); }
+ public Object get(Object key) { return map.get(key); }
+ public Object put(Object key, Object val) { return map.put(key, val); }
+ public Object remove(Object key) { return map.remove(key); }
+ public void remove(Object key, int i) { map.remove(key);}
+ public int size() { return map.size(); }
}
+
+ /** Utterly minimalistic implementation directly extending HashMap
+ *
+ * @author Charles Goodwin <[email protected]>
+ */
+ public class Hash extends HashMap implements Basket, Map {
+ public Hash() { super(); }
+ public Hash(int initialCapacity) { super(initialCapacity); }
+ //public Hash(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor); }
+ //public Hash(int indexMultiple, int initialCapacity, float
loadFactor) {
+ // super(initialCapacity, loadFactor);
+ //}
+ public Object[] dumpkeys() { return keySet().toArray(); }
+ }
/** Implementation of a hash table using Radke's quadratic residue
* linear probing. Uses a single array to store all entries.
Modified: trunk/core/org.ibex.util/src/org/ibex/util/Cache.java
===================================================================
--- trunk/core/org.ibex.util/src/org/ibex/util/Cache.java 2009-01-14
02:44:57 UTC (rev 3357)
+++ trunk/core/org.ibex.util/src/org/ibex/util/Cache.java 2009-01-14
21:19:18 UTC (rev 3358)
@@ -11,10 +11,11 @@
* @author [email protected]
*/
public class Cache extends Basket.Hash {
- public Cache(int maxSize){//, boolean accessOrder) {
+ public Cache(int maxSize) { super(maxSize * 2); }
+ /*
+ public Cache(int maxSize, boolean accessOrder) {
super(maxSize * 2, 0.75F);
}
- /*
private static final long serialVersionUID = 23498092L;
private final int maxSize;
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
------------------------------------------------------------------------------
This SF.net email is sponsored by:
SourcForge Community
SourceForge wants to tell your story.
http://p.sf.net/sfu/sf-spreadtheword
_______________________________________________
Vexi-svn mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/vexi-svn
