Here's a comparison of a purely hash-based ivar map versus one that just
does a linear search.
For objects with only a few instance variables, the linear search
mechanism is going to be faster. Perhaps what we need is a map that's
optimized so that small sizes are linear searches and after a certain
threshold it switches to hash-based?
hash map:
100k loop of 100 ivar accesses and assign to local; one ivar
1.192000 0.000000 1.192000 ( 1.192000)
1.182000 0.000000 1.182000 ( 1.182000)
0.396000 0.000000 0.396000 ( 0.396000)
0.389000 0.000000 0.389000 ( 0.389000)
0.389000 0.000000 0.389000 ( 0.389000)
100k loop of 100 ivar accesses and assign to local; two ivars
0.391000 0.000000 0.391000 ( 0.391000)
0.391000 0.000000 0.391000 ( 0.391000)
0.389000 0.000000 0.389000 ( 0.389000)
0.389000 0.000000 0.389000 ( 0.389000)
0.390000 0.000000 0.390000 ( 0.390000)
100k loop of 100 ivar accesses and assign to local; four ivars
0.392000 0.000000 0.392000 ( 0.392000)
0.389000 0.000000 0.389000 ( 0.389000)
0.389000 0.000000 0.389000 ( 0.389000)
0.390000 0.000000 0.390000 ( 0.390000)
0.390000 0.000000 0.390000 ( 0.390000)
100k loop of 100 ivar accesses and assign to local; eight ivars
0.392000 0.000000 0.392000 ( 0.392000)
0.389000 0.000000 0.389000 ( 0.390000)
0.390000 0.000000 0.390000 ( 0.390000)
0.389000 0.000000 0.389000 ( 0.389000)
0.388000 0.000000 0.388000 ( 0.388000)
100k loop of 100 ivar accesses and assign to local; sixteen ivars
0.393000 0.000000 0.393000 ( 0.393000)
0.390000 0.000000 0.390000 ( 0.390000)
0.388000 0.000000 0.388000 ( 0.388000)
0.398000 0.000000 0.398000 ( 0.398000)
0.390000 0.000000 0.390000 ( 0.390000)
linear search map:
100k loop of 100 ivar accesses and assign to local; one ivar
1.094000 0.000000 1.094000 ( 1.093000)
1.057000 0.000000 1.057000 ( 1.057000)
0.296000 0.000000 0.296000 ( 0.296000)
0.295000 0.000000 0.295000 ( 0.295000)
0.294000 0.000000 0.294000 ( 0.294000)
100k loop of 100 ivar accesses and assign to local; two ivars
0.319000 0.000000 0.319000 ( 0.319000)
0.315000 0.000000 0.315000 ( 0.315000)
0.314000 0.000000 0.314000 ( 0.314000)
0.314000 0.000000 0.314000 ( 0.314000)
0.319000 0.000000 0.319000 ( 0.319000)
100k loop of 100 ivar accesses and assign to local; four ivars
0.350000 0.000000 0.350000 ( 0.350000)
0.354000 0.000000 0.354000 ( 0.354000)
0.348000 0.000000 0.348000 ( 0.349000)
0.349000 0.000000 0.349000 ( 0.349000)
0.350000 0.000000 0.350000 ( 0.351000)
100k loop of 100 ivar accesses and assign to local; eight ivars
0.432000 0.000000 0.432000 ( 0.432000)
0.432000 0.000000 0.432000 ( 0.433000)
0.432000 0.000000 0.432000 ( 0.432000)
0.432000 0.000000 0.432000 ( 0.432000)
0.434000 0.000000 0.434000 ( 0.434000)
100k loop of 100 ivar accesses and assign to local; sixteen ivars
0.576000 0.000000 0.576000 ( 0.576000)
0.573000 0.000000 0.573000 ( 0.573000)
0.572000 0.000000 0.572000 ( 0.573000)
0.573000 0.000000 0.573000 ( 0.573000)
0.575000 0.000000 0.575000 ( 0.575000)
The bottom line is that for objects with anywhere below four to six
ivars, a really dumb linear-searching map is faster. Note also this is a
fully-synchronized map; there would certainly be smarter ways to ensure
concurrency.
- Charlie
Index: src/org/jruby/runtime/DynamicScope.java
===================================================================
--- src/org/jruby/runtime/DynamicScope.java (revision 4182)
+++ src/org/jruby/runtime/DynamicScope.java (working copy)
@@ -106,9 +106,8 @@
parent.setValue(offset, value, depth - 1);
} else {
- assert offset < variableValues.length : "Setting " + offset + " to
" + value + ", O: " + this;
-
lazy();
+ assert offset < variableValues.length : "Setting " + offset + " to
" + value + ", O: " + this;
variableValues[offset] = value;
}
}
Index: src/org/jruby/RubyStruct.java
===================================================================
--- src/org/jruby/RubyStruct.java (revision 4182)
+++ src/org/jruby/RubyStruct.java (working copy)
@@ -189,7 +189,7 @@
if (args.length > 0) {
if (args[0] instanceof RubyString) {
- name = args[0].toString();
+ name = args[0].toString().intern();
} else if (args[0].isNil()) {
nilName = true;
}
Index: src/org/jruby/RubyObject.java
===================================================================
--- src/org/jruby/RubyObject.java (revision 4182)
+++ src/org/jruby/RubyObject.java (working copy)
@@ -37,6 +37,10 @@
***** END LICENSE BLOCK *****/
package org.jruby;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicBoolean;
import org.jruby.evaluator.EvaluationState;
import org.jruby.exceptions.JumpException;
@@ -53,6 +57,7 @@
import org.jruby.runtime.callback.Callback;
import org.jruby.util.IdUtil;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
@@ -62,6 +67,187 @@
import org.jruby.runtime.ClassIndex;
import org.jruby.runtime.MethodIndex;
+class LinearSearchMap implements Map {
+ Object[] keys;
+ Object[] values;
+
+ public LinearSearchMap() {
+ clear();
+ }
+
+ public LinearSearchMap(Map other) {
+ clear();
+ putAll(other);
+ }
+
+ public int size() {
+ return keys.length;
+ }
+
+ public boolean isEmpty() {
+ return keys.length == 0;
+ }
+
+ private int linearSearch(Object[] source, Object key) {
+ for (int i = 0; i < source.length; i++) if (source[i] == key) return i;
+ return -1;
+ }
+
+ public boolean containsKey(Object arg0) {
+ assert arg0 == ((String)arg0).intern();
+ return linearSearch(keys, arg0) != -1;
+ }
+
+ public boolean containsValue(Object arg0) {
+ return linearSearch(values, arg0) != -1;
+ }
+
+ public Object get(Object arg0) {
+ assert arg0 == ((String)arg0).intern();
+ int i = linearSearch(keys, arg0);
+ if (i == -1) return null;
+ return values[i];
+ }
+
+ public Object put(Object arg0, Object arg1) {
+ assert arg0 == ((String)arg0).intern();
+ int i = linearSearch(keys, arg0);
+ if (i == -1) {
+ i = grow(arg0);
+ values[i] = arg1;
+ return null;
+ }
+ arg0 = values[i];
+ values[i] = arg1;
+ return arg0;
+ }
+
+ private int grow(Object key) {
+ Object[] newKeys = new Object[keys.length + 1];
+ System.arraycopy(keys, 0, newKeys, 0, keys.length);
+ keys = newKeys;
+ keys[keys.length - 1] = key;
+ Object[] newValues = new Object[values.length + 1];
+ System.arraycopy(values, 0, newValues, 0, values.length);
+ values = newValues;
+ return keys.length - 1;
+ }
+
+ public Object remove(Object arg0) {
+ assert arg0 == ((String)arg0).intern();
+ int i = Arrays.binarySearch(keys, arg0);
+ if (i == -1) return null;
+ return remove(i);
+ }
+
+ private Object remove(int i) {
+ Object[] newKeys = new Object[keys.length - 1];
+ System.arraycopy(keys, 0, newKeys, 0, i);
+ System.arraycopy(keys, i + 1, newKeys, i, keys.length - (i + 1));
+ Object old = keys[i];
+ keys = newKeys;
+ return old;
+ }
+
+ public void putAll(Map arg0) {
+ for (Map.Entry entry : (Set<Map.Entry>)arg0.entrySet()) {
+ put(entry.getKey(), entry.getValue());
+ }
+ }
+
+ public void clear() {
+ keys = new Object[0];
+ values = new Object[0];
+ }
+
+ public Set keySet() {
+ return new AbstractSet() {
+ Object[] setKeys = keys;
+
+ public Iterator iterator() {
+ return new Iterator() {
+ int i = -1;
+
+ public boolean hasNext() {
+ return i + 1 < setKeys.length;
+ }
+
+ public Object next() {
+ if (i + 1 >= setKeys.length) {
+ throw new ArrayIndexOutOfBoundsException();
+ }
+ return keys[++i];
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException("Not supported
yet.");
+ }
+
+ };
+ }
+
+ public int size() {
+ return keys.length;
+ }
+
+ };
+ }
+
+ public Collection values() {
+ return Arrays.asList(values);
+ }
+
+ public Set entrySet() {
+ return new AbstractSet() {
+ Object[] setKeys = keys;
+ Object[] setValues = values;
+
+ public Iterator iterator() {
+ return new Iterator() {
+ int i = -1;
+
+ public boolean hasNext() {
+ return i + 1 < setKeys.length;
+ }
+
+ public Object next() {
+ if (i + 1 >= setKeys.length) {
+ throw new ArrayIndexOutOfBoundsException();
+ }
+ ++i;
+ return new Map.Entry() {
+ Object key = setKeys[i];
+ Object value = setValues[i];
+ public Object getKey() {
+ return key;
+ }
+
+ public Object getValue() {
+ return value;
+ }
+
+ public Object setValue(Object arg0) {
+ throw new UnsupportedOperationException("Not
supported yet.");
+ }
+
+ };
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException("Not supported
yet.");
+ }
+
+ };
+ }
+
+ public int size() {
+ return keys.length;
+ }
+
+ };
+ }
+}
+
/**
*
* @author jpetersen
@@ -231,7 +417,7 @@
}
public static void puts(Object obj) {
- System.out.println(obj.toString());
+ System.out.println(obj == null ? "null" : obj.toString());
}
/**
@@ -283,7 +469,7 @@
if (instanceVariables == null) {
synchronized (this) {
if (instanceVariables == null) {
- instanceVariables =
Collections.synchronizedMap(new HashMap());
+ instanceVariables = new LinearSearchMap();
}
}
}
@@ -291,7 +477,7 @@
}
public void setInstanceVariables(Map instanceVariables) {
- this.instanceVariables =
Collections.synchronizedMap(instanceVariables);
+ this.instanceVariables = new LinearSearchMap(instanceVariables);
}
/**
Index: src/org/jruby/RubyModule.java
===================================================================
--- src/org/jruby/RubyModule.java (revision 4182)
+++ src/org/jruby/RubyModule.java (working copy)
@@ -461,6 +461,7 @@
* @see RubyObject#setInstanceVariable(String, IRubyObject, String, String)
*/
public IRubyObject setConstant(String name, IRubyObject value) {
+ name = name.intern();
IRubyObject oldValue = getInstanceVariable(name);
if (oldValue == getRuntime().getUndef()) {
@@ -1094,7 +1095,7 @@
attributeScope = Visibility.PRIVATE;
// FIXME warning
}
- final String variableName = "@" + name;
+ final String variableName = ("@" + name).intern();
final Ruby runtime = getRuntime();
ThreadContext context = getRuntime().getCurrentContext();
if (readable) {
---------------------------------------------------------------------
To unsubscribe from this list please visit:
http://xircles.codehaus.org/manage_email
