Skip to content

Commit

Permalink
[Truffle] Pull out array packing logic for hashes.
Browse files Browse the repository at this point in the history
@chrisseaton
chrisseaton committed May 1, 2015
1 parent a9e1b0b commit 630660c
Showing 6 changed files with 82 additions and 48 deletions.
2 changes: 1 addition & 1 deletion core/src/main/java/org/jruby/util/cli/Options.java
View file
Original file line number Diff line number Diff line change
@@ -134,7 +134,7 @@ public class Options {
public static final Option<Integer> TRUFFLE_ARRAYS_UNINITIALIZED_SIZE = integer(TRUFFLE, "truffle.arrays.uninitialized_size", 32, "How large an array to allocate when we have no other information to go on.");
public static final Option<Boolean> TRUFFLE_ARRAYS_OPTIMISTIC_LONG = bool(TRUFFLE, "truffle.arrays.optimistic.long", true, "If we allocate an int[] for an Array and it has been converted to a long[], directly allocate a long[] next time.");
public static final Option<Integer> TRUFFLE_ARRAYS_SMALL = integer(TRUFFLE, "truffle.arrays.small", 3, "Maximum size of an Array to consider small for optimisations.");
public static final Option<Integer> TRUFFLE_HASHES_SMALL = integer(TRUFFLE, "truffle.hashes.small", 3, "Maximum size of a Hash to consider small for optimisations.");
public static final Option<Integer> TRUFFLE_HASH_PACKED_ARRAY_MAX = integer(TRUFFLE, "truffle.hash.packed_array_max", 3, "Maximum size of a Hash to use with the packed array storage strategy.");

public static final Option<Boolean> TRUFFLE_LOAD_CORE = bool(TRUFFLE, "truffle.load_core", true, "Load the Truffle core library.");

77 changes: 36 additions & 41 deletions truffle/src/main/java/org/jruby/truffle/nodes/core/HashNodes.java
View file
Original file line number Diff line number Diff line change
@@ -29,10 +29,7 @@
import org.jruby.truffle.runtime.UndefinedPlaceholder;
import org.jruby.truffle.runtime.control.RaiseException;
import org.jruby.truffle.runtime.core.*;
import org.jruby.truffle.runtime.hash.Entry;
import org.jruby.truffle.runtime.hash.HashOperations;
import org.jruby.truffle.runtime.hash.HashSearchResult;
import org.jruby.truffle.runtime.hash.KeyValue;
import org.jruby.truffle.runtime.hash.*;
import org.jruby.truffle.runtime.methods.InternalMethod;

import java.util.Arrays;
@@ -58,9 +55,9 @@ public Object construct(VirtualFrame frame, RubyClass hashClass, Object[] args)
final Object[] store = (Object[]) array.getStore();

final int size = array.getSize();
final Object[] newStore = new Object[HashOperations.SMALL_HASH_SIZE * 2];
final Object[] newStore = new Object[PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2];

for (int n = 0; n < HashOperations.SMALL_HASH_SIZE; n++) {
for (int n = 0; n < PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX; n++) {
if (n < size) {
final Object pair = store[n];

@@ -77,9 +74,7 @@ public Object construct(VirtualFrame frame, RubyClass hashClass, Object[] args)
}

final Object[] pairStore = (Object[]) pairArray.getStore();

newStore[n * 2] = pairStore[0];
newStore[n * 2 + 1] = pairStore[1];
PackedArrayStrategy.setKeyValue(newStore, n, pairStore[0], pairStore[1]);
}
}

@@ -110,7 +105,7 @@ public static boolean isSmallArrayOfPairs(RubyClass hashClass, Object[] args) {

final Object[] store = (Object[]) array.getStore();

if (store.length > HashOperations.SMALL_HASH_SIZE) {
if (store.length > PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX) {
return false;
}

@@ -165,18 +160,18 @@ public Object getPackedArray(VirtualFrame frame, RubyHash hash, Object key) {
final Object[] store = (Object[]) hash.getStore();
final int size = hash.getSize();

for (int n = 0; n < HashOperations.SMALL_HASH_SIZE; n++) {
for (int n = 0; n < PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX; n++) {
if (n < size) {
final boolean equal;

if (byIdentityProfile.profile(hash.isCompareByIdentity())) {
equal = equalNode.executeReferenceEqual(frame, key, store[n * 2]);
equal = equalNode.executeReferenceEqual(frame, key, PackedArrayStrategy.getKey(store, n));
} else {
equal = eqlNode.callBoolean(frame, key, "eql?", null, store[n * 2]);
equal = eqlNode.callBoolean(frame, key, "eql?", null, PackedArrayStrategy.getKey(store, n));
}

if (equal) {
return store[n * 2 + 1];
return PackedArrayStrategy.getValue(store, n);
}
}
}
@@ -255,7 +250,7 @@ public SetIndexNode(RubyContext context, SourceSection sourceSection) {

@Specialization(guards = { "isNullStorage(hash)", "!isRubyString(key)" })
public Object setNull(VirtualFrame frame, RubyHash hash, Object key, Object value) {
final Object[] store = new Object[HashOperations.SMALL_HASH_SIZE * 2];
final Object[] store = new Object[PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2];
hashNode.call(frame, key, "hash", null);
store[0] = key;
store[1] = value;
@@ -281,18 +276,18 @@ public Object setPackedArray(VirtualFrame frame, RubyHash hash, Object key, Obje
final Object[] store = (Object[]) hash.getStore();
final int size = hash.getSize();

for (int n = 0; n < HashOperations.SMALL_HASH_SIZE; n++) {
for (int n = 0; n < PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX; n++) {
if (n < size) {
final boolean equal;

if (byIdentityProfile.profile(hash.isCompareByIdentity())) {
equal = equalNode.executeReferenceEqual(frame, key, store[n * 2]);
equal = equalNode.executeReferenceEqual(frame, key, PackedArrayStrategy.getKey(store, n));
} else {
equal = eqlNode.callBoolean(frame, key, "eql?", null, store[n * 2]);
equal = eqlNode.callBoolean(frame, key, "eql?", null, PackedArrayStrategy.getKey(store, n));
}

if (equal) {
store[n * 2 + 1] = value;
PackedArrayStrategy.setValue(store, n, value);
return value;
}
}
@@ -302,7 +297,7 @@ public Object setPackedArray(VirtualFrame frame, RubyHash hash, Object key, Obje

final int newSize = size + 1;

if (newSize <= HashOperations.SMALL_HASH_SIZE) {
if (newSize <= PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX) {
extendProfile.enter();
store[size * 2] = key;
store[size * 2 + 1] = value;
@@ -459,9 +454,9 @@ public Object deletePackedArray(VirtualFrame frame, RubyHash hash, Object key, O
final Object[] store = (Object[]) hash.getStore();
final int size = hash.getSize();

for (int n = 0; n < HashOperations.SMALL_HASH_SIZE; n++) {
if (n < size && eqlNode.callBoolean(frame, store[n * 2], "eql?", null, key)) {
final Object value = store[n * 2 + 1];
for (int n = 0; n < PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX; n++) {
if (n < size && eqlNode.callBoolean(frame, PackedArrayStrategy.getKey(store, n), "eql?", null, key)) {
final Object value = PackedArrayStrategy.getValue(store, n);

// Move the later values down
int k = n * 2; // position of the key
@@ -549,13 +544,13 @@ public RubyHash eachPackedArray(VirtualFrame frame, RubyHash hash, RubyProc bloc
int count = 0;

try {
for (int n = 0; n < HashOperations.SMALL_HASH_SIZE; n++) {
for (int n = 0; n < PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX; n++) {
if (CompilerDirectives.inInterpreter()) {
count++;
}

if (n < size) {
yield(frame, block, new RubyArray(getContext().getCoreLibrary().getArrayClass(), new Object[]{store[n * 2], store[n * 2 + 1]}, 2));
yield(frame, block, new RubyArray(getContext().getCoreLibrary().getArrayClass(), new Object[]{PackedArrayStrategy.getKey(store, n), PackedArrayStrategy.getValue(store, n)}, 2));
}
}
} finally {
@@ -688,7 +683,7 @@ public RubyHash dupPackedArray(RubyHash self, RubyHash from) {
}

final Object[] store = (Object[]) from.getStore();
self.setStore(Arrays.copyOf(store, HashOperations.SMALL_HASH_SIZE * 2), from.getSize(), null, null);
self.setStore(Arrays.copyOf(store, PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2), from.getSize(), null, null);

copyOther(self, from);

@@ -747,10 +742,10 @@ public RubyArray mapPackedArray(VirtualFrame frame, RubyHash hash, RubyProc bloc
int count = 0;

try {
for (int n = 0; n < HashOperations.SMALL_HASH_SIZE; n++) {
for (int n = 0; n < PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX; n++) {
if (n < size) {
final Object key = store[n * 2];
final Object value = store[n * 2 + 1];
final Object key = PackedArrayStrategy.getKey(store, n);
final Object value = PackedArrayStrategy.getValue(store, n);
result[n] = yield(frame, block, key, value);

if (CompilerDirectives.inInterpreter()) {
@@ -795,7 +790,7 @@ public abstract static class MergeNode extends YieldingCoreMethodNode {
private final BranchProfile considerResultIsSmallProfile = BranchProfile.create();
private final BranchProfile resultIsSmallProfile = BranchProfile.create();

private final int smallHashSize = HashOperations.SMALL_HASH_SIZE;
private final int smallHashSize = PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX;

public MergeNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
@@ -805,7 +800,7 @@ public MergeNode(RubyContext context, SourceSection sourceSection) {
@Specialization(guards = {"isPackedArrayStorage(hash)", "isNullStorage(other)", "!isCompareByIdentity(hash)"})
public RubyHash mergePackedArrayNull(RubyHash hash, RubyHash other, UndefinedPlaceholder block) {
final Object[] store = (Object[]) hash.getStore();
final Object[] copy = Arrays.copyOf(store, HashOperations.SMALL_HASH_SIZE * 2);
final Object[] copy = Arrays.copyOf(store, PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2);

return new RubyHash(hash.getLogicalClass(), hash.getDefaultBlock(), hash.getDefaultValue(), copy, hash.getSize(), null);
}
@@ -826,11 +821,11 @@ public RubyHash mergePackedArrayPackedArray(VirtualFrame frame, RubyHash hash, R

int conflictsCount = 0;

for (int a = 0; a < HashOperations.SMALL_HASH_SIZE; a++) {
for (int a = 0; a < PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX; a++) {
if (a < storeASize) {
boolean merge = true;

for (int b = 0; b < HashOperations.SMALL_HASH_SIZE; b++) {
for (int b = 0; b < PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX; b++) {
if (b < storeBSize) {
if (eqlNode.callBoolean(frame, storeA[a * 2], "eql?", null, storeB[b * 2])) {
conflictsCount++;
@@ -850,14 +845,14 @@ public RubyHash mergePackedArrayPackedArray(VirtualFrame frame, RubyHash hash, R

if (mergeFromACount == 0) {
nothingFromFirstProfile.enter();
return new RubyHash(hash.getLogicalClass(), hash.getDefaultBlock(), hash.getDefaultValue(), Arrays.copyOf(storeB, HashOperations.SMALL_HASH_SIZE * 2), storeBSize, null);
return new RubyHash(hash.getLogicalClass(), hash.getDefaultBlock(), hash.getDefaultValue(), Arrays.copyOf(storeB, PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2), storeBSize, null);
}

considerNothingFromSecondProfile.enter();

if (conflictsCount == storeBSize) {
nothingFromSecondProfile.enter();
return new RubyHash(hash.getLogicalClass(), hash.getDefaultBlock(), hash.getDefaultValue(), Arrays.copyOf(storeA, HashOperations.SMALL_HASH_SIZE * 2), storeASize, null);
return new RubyHash(hash.getLogicalClass(), hash.getDefaultBlock(), hash.getDefaultValue(), Arrays.copyOf(storeA, PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2), storeASize, null);
}

considerResultIsSmallProfile.enter();
@@ -867,21 +862,21 @@ public RubyHash mergePackedArrayPackedArray(VirtualFrame frame, RubyHash hash, R
if (storeBSize + mergeFromACount <= smallHashSize) {
resultIsSmallProfile.enter();

final Object[] merged = new Object[HashOperations.SMALL_HASH_SIZE * 2];
final Object[] merged = new Object[PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2];

int index = 0;

for (int n = 0; n < storeASize; n++) {
if (mergeFromA[n]) {
merged[index] = storeA[n * 2];
merged[index + 1] = storeA[n * 2 + 1];
merged[index] = PackedArrayStrategy.getKey(storeA, n);
merged[index + 1] = PackedArrayStrategy.getValue(storeA, n);
index += 2;
}
}

for (int n = 0; n < storeBSize; n++) {
merged[index] = storeB[n * 2];
merged[index + 1] = storeB[n * 2 + 1];
merged[index] = PackedArrayStrategy.getKey(storeB, n);
merged[index + 1] = PackedArrayStrategy.getValue(storeB, n);
index += 2;
}

@@ -1026,7 +1021,7 @@ public RubyArray shiftPackedArray(RubyHash hash) {
final Object key = store[0];
final Object value = store[1];

System.arraycopy(store, 2, store, 0, HashOperations.SMALL_HASH_SIZE * 2 - 2);
System.arraycopy(store, 2, store, 0, PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2 - 2);

hash.setSize(hash.getSize() - 1);

5 changes: 3 additions & 2 deletions truffle/src/main/java/org/jruby/truffle/nodes/literal/HashLiteralNode.java
View file
Original file line number Diff line number Diff line change
@@ -24,6 +24,7 @@
import org.jruby.truffle.runtime.core.RubyString;
import org.jruby.truffle.runtime.hash.HashOperations;
import org.jruby.truffle.runtime.hash.KeyValue;
import org.jruby.truffle.runtime.hash.PackedArrayStrategy;

import java.util.ArrayList;
import java.util.List;
@@ -57,7 +58,7 @@ public RubyNode getValue(int index) {
public static HashLiteralNode create(RubyContext context, SourceSection sourceSection, RubyNode[] keyValues) {
if (keyValues.length == 0) {
return new EmptyHashLiteralNode(context, sourceSection);
} else if (keyValues.length <= HashOperations.SMALL_HASH_SIZE * 2) {
} else if (keyValues.length <= PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2) {
return new SmallHashLiteralNode(context, sourceSection, keyValues);
} else {
return new GenericHashLiteralNode(context, sourceSection, keyValues);
@@ -108,7 +109,7 @@ public SmallHashLiteralNode(RubyContext context, SourceSection sourceSection, Ru
@ExplodeLoop
@Override
public RubyHash executeRubyHash(VirtualFrame frame) {
final Object[] storage = new Object[HashOperations.SMALL_HASH_SIZE * 2];
final Object[] storage = new Object[PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2];

int end = 0;

5 changes: 3 additions & 2 deletions truffle/src/main/java/org/jruby/truffle/runtime/core/RubyHash.java
View file
Original file line number Diff line number Diff line change
@@ -16,6 +16,7 @@
import org.jruby.truffle.runtime.hash.Entry;
import org.jruby.truffle.runtime.hash.HashOperations;
import org.jruby.truffle.runtime.hash.KeyValue;
import org.jruby.truffle.runtime.hash.PackedArrayStrategy;
import org.jruby.truffle.runtime.subsystems.ObjectSpaceManager;

public class RubyHash extends RubyBasicObject {
@@ -111,11 +112,11 @@ public boolean verifyStore(Object store, int storeSize, Entry firstInSequence, E
assert firstInSequence == null || foundFirst;
assert lastInSequence == null || foundLast;
} else if (store instanceof Object[]) {
assert ((Object[]) store).length == HashOperations.SMALL_HASH_SIZE * 2 : ((Object[]) store).length;
assert ((Object[]) store).length == PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX * 2 : ((Object[]) store).length;

final Object[] packedStore = (Object[]) store;

for (int n = 0; n < HashOperations.SMALL_HASH_SIZE; n++) {
for (int n = 0; n < PackedArrayStrategy.TRUFFLE_HASH_PACKED_ARRAY_MAX; n++) {
if (n < storeSize) {
assert packedStore[n * 2] != null;
assert packedStore[n * 2 + 1] != null;
2 changes: 0 additions & 2 deletions truffle/src/main/java/org/jruby/truffle/runtime/hash/HashOperations.java
View file
Original file line number Diff line number Diff line change
@@ -24,8 +24,6 @@

public class HashOperations {

public static final int SMALL_HASH_SIZE = Options.TRUFFLE_HASHES_SMALL.load();

private static final int[] CAPACITIES = Arrays.copyOf(org.jruby.RubyHash.MRI_PRIMES, org.jruby.RubyHash.MRI_PRIMES.length - 1);
private static final int SIGN_BIT_MASK = ~(1 << 31);

39 changes: 39 additions & 0 deletions truffle/src/main/java/org/jruby/truffle/runtime/hash/PackedArrayStrategy.java
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,39 @@
/*
* Copyright (c) 2015 Oracle and/or its affiliates. All rights reserved. This
* code is released under a tri EPL/GPL/LGPL license. You can use it,
* redistribute it and/or modify it under the terms of the:
*
* Eclipse Public License version 1.0
* GNU General Public License version 2
* GNU Lesser General Public License version 2.1
*/
package org.jruby.truffle.runtime.hash;

import org.jruby.util.cli.Options;

public abstract class PackedArrayStrategy {

public static final int TRUFFLE_HASH_PACKED_ARRAY_MAX = Options.TRUFFLE_HASH_PACKED_ARRAY_MAX.load();

public static Object getKey(Object[] store, int n) {
return store[n * 2];
}

public static Object getValue(Object[] store, int n) {
return store[n * 2 + 1];
}

public static void setKey(Object[] store, int n, Object key) {
store[n * 2] = key;
}

public static void setValue(Object[] store, int n, Object value) {
store[n * 2 + 1] = value;
}

public static void setKeyValue(Object[] store, int n, Object key, Object value) {
setKey(store, n, key);
setValue(store, n, value);
}

}

0 comments on commit 630660c

Please sign in to comment.