Skip to content

[Truffle] New implementation of non-small hashes #2328

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
chrisseaton merged 12 commits into from
Dec 17, 2014
Merged

[Truffle] New implementation of non-small hashes #2328

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
9810a50
[Truffle] Basic new implementation of large hashes.
chrisseaton Dec 15, 2014
0eee052
[Truffle] Fix default block in buckets hash.
chrisseaton Dec 16, 2014
3e82545
[Truffle] Pull out some hash classes to the top level.
chrisseaton Dec 16, 2014
579881f
[Truffle] Tidy up RubyHash.
chrisseaton Dec 16, 2014
4b6b34a
[Truffle] Make finding a bucket a node.
chrisseaton Dec 16, 2014
3c5c26d
[Truffle] Some documentation of hash.
chrisseaton Dec 16, 2014
18593e6
[Truffle] Fix a couple of hash bugs.
chrisseaton Dec 16, 2014
35c1350
[Truffle] Make the bucket chain singly linked.
chrisseaton Dec 16, 2014
96c8da6
[Truffle] Rename buckets entries.
chrisseaton Dec 16, 2014
b2a89e6
[Truffle] We don't need HashSearchResult as a DSL type at all.
chrisseaton Dec 16, 2014
639ecf6
[Truffle] Change hash guard terminology to PackedArray or Buckets
chrisseaton Dec 16, 2014
2bb0e15
[Truffle] Make the packed array guard for hash, which is complicated …
chrisseaton Dec 16, 2014
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
[Truffle] Pull out some hash classes to the top level.
  • Loading branch information
@chrisseaton
chrisseaton committed Dec 16, 2014
commit 3e82545ea04ce156df539519881d65d0029fd32d
5 changes: 3 additions & 2 deletions core/src/main/java/org/jruby/truffle/nodes/core/HashGuards.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -10,6 +10,7 @@
package org.jruby.truffle.nodes.core;

import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.hash.Bucket;

public class HashGuards {

Expand All @@ -19,11 +20,11 @@ public static boolean isNull(RubyHash hash) {

public static boolean isObjectArray(RubyHash hash) {
// Arrays are covariant in Java!
return hash.getStore() instanceof Object[] && !(hash.getStore() instanceof RubyHash.Bucket[]);
return hash.getStore() instanceof Object[] && !(hash.getStore() instanceof Bucket[]);
Copy link
Copy Markdown
Contributor

@eregon eregon Dec 16, 2014

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So this means there is no good way to check that the ObjectArray strategy is actually only using just a Object[] with instanceof?
But getClass() should do it then, so the assertions in RubyHash constructor should be adapted?
Wondering if 2 instanceof is also better than 1 getClass().

}

public static boolean isBucketArray(RubyHash hash) {
return hash.getStore() instanceof RubyHash.Bucket[];
return hash.getStore() instanceof Bucket[];
}

}
84 changes: 43 additions & 41 deletions core/src/main/java/org/jruby/truffle/nodes/core/HashNodes.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -16,7 +16,6 @@
import com.oracle.truffle.api.frame.*;
import com.oracle.truffle.api.utilities.BranchProfile;
import org.jruby.runtime.Visibility;
import org.jruby.truffle.nodes.RubyNode;
import org.jruby.truffle.nodes.RubyRootNode;
import org.jruby.truffle.nodes.dispatch.DispatchHeadNode;
import org.jruby.truffle.nodes.dispatch.PredicateDispatchHeadNode;
Expand All @@ -25,6 +24,9 @@
import org.jruby.truffle.runtime.core.*;
import org.jruby.truffle.runtime.core.RubyArray;
import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.hash.Bucket;
import org.jruby.truffle.runtime.hash.BucketSearchResult;
import org.jruby.truffle.runtime.hash.Entry;

import java.util.ArrayList;
import java.util.Arrays;
Expand Down Expand Up @@ -57,8 +59,8 @@ public boolean equalNull(RubyHash a, RubyHash b) {
public boolean equal(VirtualFrame frame, RubyHash a, RubyHash b) {
notDesignedForCompilation();

final List<RubyHash.Entry> aEntries = a.verySlowToEntries();
final List<RubyHash.Entry> bEntries = a.verySlowToEntries();
final List<Entry> aEntries = a.verySlowToEntries();
final List<Entry> bEntries = a.verySlowToEntries();

if (aEntries.size() != bEntries.size()) {
return false;
Expand All @@ -68,7 +70,7 @@ public boolean equal(VirtualFrame frame, RubyHash a, RubyHash b) {

final boolean[] bUsed = new boolean[bEntries.size()];

for (RubyHash.Entry aEntry : aEntries) {
for (Entry aEntry : aEntries) {
boolean found = false;

for (int n = 0; n < bEntries.size(); n++) {
Expand Down Expand Up @@ -177,10 +179,10 @@ public RubyHash construct(Object[] args) {
} else {
keyValues.enter();

final List<RubyHash.Entry> entries = new ArrayList<>();
final List<Entry> entries = new ArrayList<>();

for (int n = 0; n < args.length; n += 2) {
entries.add(new RubyHash.Entry(args[n], args[n + 1]));
entries.add(new Entry(args[n], args[n + 1]));
}

return RubyHash.verySlowFromEntries(getContext(), entries);
Expand Down Expand Up @@ -254,10 +256,10 @@ public Object getObjectArray(VirtualFrame frame, RubyHash hash, Object key) {
public Object getBucketArray(VirtualFrame frame, RubyHash hash, Object key) {
notDesignedForCompilation();

final RubyHash.BucketAndIndex bucketAndIndex = hash.verySlowFindBucket(key);
final BucketSearchResult bucketSearchResult = hash.verySlowFindBucket(key);

if (bucketAndIndex.getBucket() != null) {
return bucketAndIndex.getBucket().value;
if (bucketSearchResult.getBucket() != null) {
return bucketSearchResult.getBucket().getValue();
}

notInHashProfile.enter();
Expand Down Expand Up @@ -335,11 +337,11 @@ public Object setObjectArray(VirtualFrame frame, RubyHash hash, Object key, Obje

// TODO(CS): need to watch for that transfer until we make the following fast path

final List<RubyHash.Entry> entries = hash.verySlowToEntries();
final List<Entry> entries = hash.verySlowToEntries();

hash.setStore(new RubyHash.Bucket[RubyHash.capacityGreaterThan(newSize)], newSize, null, null);
hash.setStore(new Bucket[RubyHash.capacityGreaterThan(newSize)], newSize, null, null);

for (RubyHash.Entry entry : entries) {
for (Entry entry : entries) {
hash.verySlowSetInBuckets(entry.getKey(), entry.getValue());
}

Expand Down Expand Up @@ -433,43 +435,43 @@ public Object deleteObjectArray(VirtualFrame frame, RubyHash hash, Object key) {
public Object delete(RubyHash hash, Object key) {
notDesignedForCompilation();

final RubyHash.BucketAndIndex bucketAndIndex = hash.verySlowFindBucket(key);
final BucketSearchResult bucketSearchResult = hash.verySlowFindBucket(key);

if (bucketAndIndex.getBucket() == null) {
if (bucketSearchResult.getBucket() == null) {
return getContext().getCoreLibrary().getNilObject();
}

final RubyHash.Bucket bucket = bucketAndIndex.getBucket();
final Bucket bucket = bucketSearchResult.getBucket();

// Remove from the sequence chain

if (bucket.previousInSequence == null) {
hash.firstInSequence = bucket.nextInSequence;
if (bucket.getPreviousInSequence() == null) {
hash.firstInSequence = bucket.getNextInSequence();
} else {
bucket.previousInSequence.nextInSequence = bucket.nextInSequence;
bucket.getPreviousInSequence().setNextInSequence(bucket.getNextInSequence());
}

if (bucket.nextInSequence == null) {
hash.lastInSequence = bucket.previousInSequence;
if (bucket.getNextInSequence() == null) {
hash.lastInSequence = bucket.getPreviousInSequence();
} else {
bucket.nextInSequence.previousInSequence = bucket.previousInSequence;
bucket.getNextInSequence().setPreviousInSequence(bucket.getPreviousInSequence());
}

// Remove from the lookup chain

if (bucket.previousInLookup == null) {
((RubyHash.Bucket[]) hash.getStore())[bucketAndIndex.getIndex()] = bucket.nextInLookup;
if (bucket.getPreviousInLookup() == null) {
Copy link
Copy Markdown
Contributor

@eregon eregon Dec 16, 2014

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So here is the only usage of getPreviousInLookup().
I think it is sensibly OK to walk the chain of buckets at that index there and check with Bucket ==.
(The terminology is confusing to me, a bucket should contain the chain of entries, no?).

((Bucket[]) hash.getStore())[bucketSearchResult.getIndex()] = bucket.getNextInLookup();
} else {
bucket.previousInLookup.nextInLookup = bucket.nextInLookup;
bucket.getPreviousInLookup().setNextInLookup(bucket.getNextInLookup());
}

if (bucket.nextInLookup != null) {
bucket.nextInLookup.previousInLookup = bucket.previousInLookup;
if (bucket.getNextInLookup() != null) {
bucket.getNextInLookup().setPreviousInLookup(bucket.getPreviousInLookup());
}

hash.setStoreSize(hash.getStoreSize() - 1);

return bucket.value;
return bucket.getValue();
}

}
Expand Down Expand Up @@ -526,7 +528,7 @@ public RubyHash eachObjectArray(VirtualFrame frame, RubyHash hash, RubyProc bloc
public RubyHash eachBucketArray(VirtualFrame frame, RubyHash hash, RubyProc block) {
notDesignedForCompilation();

for (RubyHash.Entry entry : hash.verySlowToEntries()) {
for (Entry entry : hash.verySlowToEntries()) {
yield(frame, block, RubyArray.fromObjects(getContext().getCoreLibrary().getArrayClass(), entry.getKey(), entry.getValue()));
}

Expand Down Expand Up @@ -681,7 +683,7 @@ public RubyString inspectObjectArray(VirtualFrame frame, RubyHash hash) {

builder.append("{");

for (RubyHash.Entry entry : hash.verySlowToEntries()) {
for (Entry entry : hash.verySlowToEntries()) {
if (builder.length() > 1) {
builder.append(", ");
}
Expand Down Expand Up @@ -740,7 +742,7 @@ public boolean keyObjectArray(VirtualFrame frame, RubyHash hash, Object key) {
public boolean keyBucketArray(VirtualFrame frame, RubyHash hash, Object key) {
notDesignedForCompilation();

for (RubyHash.Entry entry : hash.verySlowToEntries()) {
for (Entry entry : hash.verySlowToEntries()) {
if (eqlNode.call(frame, entry.getKey(), "eql?", null, key)) {
return true;
}
Expand Down Expand Up @@ -788,13 +790,13 @@ public RubyArray keysBucketArray(RubyHash hash) {

final Object[] keys = new Object[hash.getStoreSize()];

RubyHash.Bucket bucket = hash.firstInSequence;
Bucket bucket = hash.firstInSequence;
int n = 0;

while (bucket != null) {
keys[n] = bucket.key;
keys[n] = bucket.getKey();
n++;
bucket = bucket.nextInSequence;
bucket = bucket.getNextInSequence();
}

return new RubyArray(getContext().getCoreLibrary().getArrayClass(), keys, keys.length);
Expand Down Expand Up @@ -852,7 +854,7 @@ public RubyArray mapBucketArray(VirtualFrame frame, RubyHash hash, RubyProc bloc

final RubyArray array = new RubyArray(getContext().getCoreLibrary().getArrayClass(), null, 0);

for (RubyHash.Entry entry : hash.verySlowToEntries()) {
for (Entry entry : hash.verySlowToEntries()) {
array.slowPush(yield(frame, block, entry.getKey(), entry.getValue()));
}

Expand Down Expand Up @@ -974,13 +976,13 @@ public RubyHash mergeObjectArrayObjectArray(VirtualFrame frame, RubyHash hash, R

@Specialization
public RubyHash mergeBucketArrayBucketArray(VirtualFrame frame, RubyHash hash, RubyHash other) {
final RubyHash merged = new RubyHash(getContext().getCoreLibrary().getHashClass(), null, null, new RubyHash.Bucket[RubyHash.capacityGreaterThan(hash.getStoreSize() + hash.getStoreSize())], 0, null);
final RubyHash merged = new RubyHash(getContext().getCoreLibrary().getHashClass(), null, null, new Bucket[RubyHash.capacityGreaterThan(hash.getStoreSize() + hash.getStoreSize())], 0, null);

for (RubyHash.Entry entry : hash.verySlowToEntries()) {
for (Entry entry : hash.verySlowToEntries()) {
merged.verySlowSetInBuckets(entry.getKey(), entry.getValue());
}

for (RubyHash.Entry entry : other.verySlowToEntries()) {
for (Entry entry : other.verySlowToEntries()) {
merged.verySlowSetInBuckets(entry.getKey(), entry.getValue());
}

Expand Down Expand Up @@ -1083,13 +1085,13 @@ public RubyArray valuesBucketArray(RubyHash hash) {

final Object[] values = new Object[hash.getStoreSize()];

RubyHash.Bucket bucket = hash.firstInSequence;
Bucket bucket = hash.firstInSequence;
int n = 0;

while (bucket != null) {
values[n] = bucket.value;
values[n] = bucket.getValue();
n++;
bucket = bucket.nextInSequence;
bucket = bucket.getNextInSequence();
}

return new RubyArray(getContext().getCoreLibrary().getArrayClass(), values, values.length);
Expand Down Expand Up @@ -1139,7 +1141,7 @@ public RubyArray toArrayBucketArray(RubyHash hash) {

int n = 0;

for (RubyHash.Entry entry : hash.verySlowToEntries()) {
for (Entry entry : hash.verySlowToEntries()) {
pairs[n] = RubyArray.fromObjects(getContext().getCoreLibrary().getArrayClass(), entry.getValue(), entry.getValue());
n++;
}
Expand Down
3 changes: 2 additions & 1 deletion core/src/main/java/org/jruby/truffle/nodes/core/KernelNodes.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -37,6 +37,7 @@
import org.jruby.truffle.runtime.core.*;
import org.jruby.truffle.runtime.core.RubyArray;
import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.hash.Entry;
import org.jruby.truffle.runtime.methods.RubyMethod;
import org.jruby.util.cli.Options;

Expand Down Expand Up @@ -596,7 +597,7 @@ private static void exec(RubyContext context, String[] commandLine) {

final RubyHash env = context.getCoreLibrary().getENV();

for (RubyHash.Entry entry : env.verySlowToEntries()) {
for (Entry entry : env.verySlowToEntries()) {
builder.environment().put(entry.getKey().toString(), entry.getValue().toString());
}

Expand Down
5 changes: 2 additions & 3 deletions core/src/main/java/org/jruby/truffle/nodes/core/SystemNode.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -11,15 +11,14 @@

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

import com.oracle.truffle.api.source.*;
import com.oracle.truffle.api.frame.*;
import org.jruby.truffle.nodes.*;
import org.jruby.truffle.runtime.*;
import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.hash.Entry;

/**
* Represents an expression that is evaluated by running it as a system command via forking and
Expand All @@ -45,7 +44,7 @@ public Object execute(VirtualFrame frame) {
final List<String> envp = new ArrayList<>();

// TODO(CS): cast
for (RubyHash.Entry entry : env.verySlowToEntries()) {
for (Entry entry : env.verySlowToEntries()) {
envp.add(entry.getKey().toString() + "=" + entry.getValue().toString());
}

Expand Down
5 changes: 3 additions & 2 deletions core/src/main/java/org/jruby/truffle/nodes/literal/HashLiteralNode.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18,6 +18,7 @@
import org.jruby.truffle.runtime.*;
import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.core.RubyString;
import org.jruby.truffle.runtime.hash.Entry;

import java.util.*;
Copy link
Copy Markdown
Contributor

@nirvdrum nirvdrum Dec 16, 2014

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Minor, but JRuby core prefers these be expanded.


Expand Down Expand Up @@ -126,12 +127,12 @@ public GenericHashLiteralNode(RubyContext context, SourceSection sourceSection,
public RubyHash executeRubyHash(VirtualFrame frame) {
notDesignedForCompilation();

final List<RubyHash.Entry> entries = new ArrayList<>();
final List<Entry> entries = new ArrayList<>();

for (int n = 0; n < keyValues.length; n += 2) {
final Object key = keyValues[n].execute(frame);
final Object value = keyValues[n + 1].execute(frame);
entries.add(new RubyHash.Entry(key, value));
entries.add(new Entry(key, value));
}

return RubyHash.verySlowFromEntries(getContext(), entries);
Expand Down
5 changes: 2 additions & 3 deletions core/src/main/java/org/jruby/truffle/nodes/methods/arguments/CheckArityNode.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -16,10 +16,9 @@
import org.jruby.truffle.runtime.*;
import org.jruby.truffle.runtime.control.RaiseException;
import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.hash.Entry;
import org.jruby.truffle.runtime.methods.*;

import java.util.Map;

/**
* Check arguments meet the arity of the method.
*/
Expand Down Expand Up @@ -50,7 +49,7 @@ public void executeVoid(VirtualFrame frame) {
}

if (!keywordsRest && arity.hasKeywords() && getKeywordsHash(frame) != null) {
for (RubyHash.Entry entry : getKeywordsHash(frame).verySlowToEntries()) {
for (Entry entry : getKeywordsHash(frame).verySlowToEntries()) {
for (String keyword : keywords) {
if (!keyword.toString().equals(entry.getKey().toString())) {
throw new RaiseException(getContext().getCoreLibrary().argumentError("unknown keyword: " + entry.getKey().toString(), this));
Expand Down
9 changes: 2 additions & 7 deletions core/src/main/java/org/jruby/truffle/nodes/methods/arguments/ReadKeywordArgumentNode.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -11,16 +11,11 @@

import com.oracle.truffle.api.frame.VirtualFrame;
import com.oracle.truffle.api.source.SourceSection;
import com.oracle.truffle.api.utilities.BranchProfile;
import org.jruby.truffle.nodes.RubyNode;
import org.jruby.truffle.nodes.RubyValueProfile;
import org.jruby.truffle.runtime.RubyArguments;
import org.jruby.truffle.runtime.RubyContext;
import org.jruby.truffle.runtime.UndefinedPlaceholder;
import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.core.RubyString;

import java.util.Map;
import org.jruby.truffle.runtime.hash.Entry;

public class ReadKeywordArgumentNode extends RubyNode {

Expand All @@ -47,7 +42,7 @@ public Object execute(VirtualFrame frame) {

Object value = null;

for (RubyHash.Entry entry : hash.verySlowToEntries()) {
for (Entry entry : hash.verySlowToEntries()) {
if (entry.getKey().toString().equals(name)) {
value = entry.getValue();
break;
Expand Down
7 changes: 4 additions & 3 deletions .../src/main/java/org/jruby/truffle/nodes/methods/arguments/ReadKeywordRestArgumentNode.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -15,6 +15,7 @@
import org.jruby.truffle.runtime.RubyArguments;
import org.jruby.truffle.runtime.RubyContext;
import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.hash.Entry;

import java.util.*;

Expand All @@ -39,16 +40,16 @@ public Object execute(VirtualFrame frame) {
return new RubyHash(getContext().getCoreLibrary().getHashClass(), null, null, null, 0, null);
}

final List<RubyHash.Entry> entries = new ArrayList<>();
final List<Entry> entries = new ArrayList<>();

outer: for (RubyHash.Entry entry : hash.verySlowToEntries()) {
outer: for (Entry entry : hash.verySlowToEntries()) {
for (String excludedKeyword : excludedKeywords) {
if (excludedKeyword.toString().equals(entry.getKey().toString())) {
continue outer;
}
}

entries.add(new RubyHash.Entry(entry.getKey(), entry.getValue()));
entries.add(new Entry(entry.getKey(), entry.getValue()));
}

return RubyHash.verySlowFromEntries(getContext(), entries);
Expand Down
Loading