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 all commits
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
2 changes: 1 addition & 1 deletion core/src/main/java/org/jruby/RubyHash.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -314,7 +314,7 @@ private final void alloc(int buckets) {
* ============================
*/

private static final int MRI_PRIMES[] = {
public static final int MRI_PRIMES[] = {
8 + 3, 16 + 3, 32 + 5, 64 + 3, 128 + 3, 256 + 27, 512 + 9, 1024 + 9, 2048 + 5, 4096 + 3,
8192 + 27, 16384 + 43, 32768 + 3, 65536 + 45, 131072 + 29, 262144 + 3, 524288 + 21, 1048576 + 7,
2097152 + 17, 4194304 + 15, 8388608 + 9, 16777216 + 43, 33554432 + 35, 67108864 + 15,
Expand Down
2 changes: 1 addition & 1 deletion core/src/main/java/org/jruby/truffle/nodes/RubyNode.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -10,7 +10,6 @@
package org.jruby.truffle.nodes;

import com.oracle.truffle.api.CompilerAsserts;
import com.oracle.truffle.api.dsl.ImportGuards;
import com.oracle.truffle.api.source.SourceSection;
import com.oracle.truffle.api.dsl.TypeSystemReference;
import com.oracle.truffle.api.frame.VirtualFrame;
Expand All @@ -24,6 +23,7 @@
import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.core.RubyRange;
import org.jruby.truffle.runtime.core.RubyBasicObject;
import org.jruby.truffle.runtime.hash.HashSearchResult;
import org.jruby.truffle.runtime.rubinius.RubiniusByteArray;
import org.jruby.truffle.runtime.rubinius.RubiniusChannel;

Expand Down
2 changes: 1 addition & 1 deletion core/src/main/java/org/jruby/truffle/nodes/RubyTypes.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -9,7 +9,6 @@
*/
package org.jruby.truffle.nodes;

import com.oracle.truffle.api.dsl.ImplicitCast;
import com.oracle.truffle.api.dsl.TypeSystem;
import org.jruby.truffle.nodes.dispatch.Dispatch;
import org.jruby.truffle.runtime.UndefinedPlaceholder;
Expand All @@ -18,6 +17,7 @@
import org.jruby.truffle.runtime.core.RubyHash;
import org.jruby.truffle.runtime.core.RubyRange;
import org.jruby.truffle.runtime.core.RubyBasicObject;
import org.jruby.truffle.runtime.hash.HashSearchResult;
import org.jruby.truffle.runtime.rubinius.RubiniusByteArray;
import org.jruby.truffle.runtime.rubinius.RubiniusChannel;
import org.jruby.truffle.runtime.LexicalScope;
Expand Down
38 changes: 37 additions & 1 deletion core/src/main/java/org/jruby/truffle/nodes/core/ArrayNodes.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1110,7 +1110,6 @@ public ClearNode(ClearNode prev) {
@Specialization
public RubyArray clear(RubyArray array) {
notDesignedForCompilation();

array.setSize(0);
return array;
}
Expand Down Expand Up @@ -3551,6 +3550,43 @@ public RubyArray toA(RubyArray array) {

}

@CoreMethod(names = "uniq")
public abstract static class UniqNode extends CoreMethodNode {

public UniqNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
}

public UniqNode(UniqNode prev) {
super(prev);
}

@Specialization
public RubyArray uniq(RubyArray array) {
notDesignedForCompilation();

@eregon eregon Dec 16, 2014

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

MRI uses a temporary Hash to avoid O(n2) here.

@eregon eregon Dec 16, 2014

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

So maybe we could have an overload of notDesignedForCompilation() mapping to CompilerAsserts.neverPartOfCompilation(String message) so to keep track of what is not compilation ready when not obvious.

@chrisseaton chrisseaton Dec 16, 2014

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

Good idea - we can go through and add a reason for all the notDesigneds when we do a spring clean after 0.6 is released.


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

for (Object value : array.slowToArray()) {
boolean duplicate = false;

for (Object compare : uniq.slowToArray()) {
if ((boolean) DebugOperations.send(getContext(), value, "==", null, compare)) {
duplicate = true;
break;
}
}

if (!duplicate) {
uniq.slowPush(value);
}
}

return uniq;
}

}

@CoreMethod(names = "unshift", argumentsAsArray = true)
public abstract static class UnshiftNode extends CoreMethodNode {

Expand Down
23 changes: 3 additions & 20 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,33 +10,16 @@
package org.jruby.truffle.nodes.core;

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

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

public class HashGuards {

public static boolean isNull(RubyHash hash) {
return hash.getStore() == null;
}

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

public static boolean isObjectLinkedHashMap(RubyHash hash) {
return hash.getStore() instanceof LinkedHashMap<?, ?>;
}

public static boolean isOtherNull(RubyHash hash, RubyHash other) {
return other.getStore() == null;
}

public static boolean isOtherObjectArray(RubyHash hash, RubyHash other) {
return other.getStore() instanceof Object[];
}

public static boolean isOtherObjectLinkedHashMap(RubyHash hash, RubyHash other) {
return other.getStore() instanceof LinkedHashMap<?, ?>;
public static boolean isBuckets(RubyHash hash) {
return hash.getStore() instanceof Entry[];
}

}
Loading