[Truffle] New implementation of non-small hashes #2328
Conversation
|
|
||
| @Specialization | ||
| public RubyArray uniq(RubyArray array) { | ||
| notDesignedForCompilation(); |
There was a problem hiding this comment.
MRI uses a temporary Hash to avoid O(n2) here.
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
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.
|
Looks good globally. I am slightly uncomfortable with the naming of Bucket for what is a "hashtable entry". |
| public static boolean isOtherObjectArray(RubyHash hash, RubyHash other) { | ||
| return other.getStore() instanceof Object[]; | ||
| // Arrays are covariant in Java! | ||
| return hash.getStore() instanceof Object[] && !(hash.getStore() instanceof Bucket[]); |
There was a problem hiding this comment.
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().
|
This needs to merge in the change from 7a4ab54. |
|
|
||
| for (int n = 0; n < RubyHash.HASHES_SMALL; n++) { | ||
| for (int n = 0; n < HashOperations.SMALL_HASH_SIZE; n++) { | ||
| if (n < size && eqlNode.call(frame, store[n * 2], "eql?", null, key)) { | ||
| return store[n * 2 + 1]; |
There was a problem hiding this comment.
This code was already here, but maybe it'd be easier to follow if KEY_OFFSET and VALUE_OFFSET constants were used.
There was a problem hiding this comment.
Good idea - I'll do that on the master branch later.
|
|
||
| import java.util.LinkedHashMap; | ||
| import java.util.*; |
There was a problem hiding this comment.
Minor, but JRuby core prefers these be expanded.
|
I'll have to check out the branch to navigate the code since I'm finding it too annoying in GItHub's web UI. But at first blush this looks pretty good. |
|
I renamed the buckets to entries and removed the backwards link in the bucket chain. |
…by covariance, just the negation of the other two.
[Truffle] New implementation of non-small hashes
@eregon @nirvdrum please review.
We've got two new things here. First of all we've got a proper implementation of hash where there are more than 3 key-value pairs. We have to have a custom data structure because we need to call Ruby methods for
hashandeql?with somewhere to store the state for the call site. We can't re-use JRuby's, for the usual reasons, and using the Truffle-style of storage strategies we don't want encapsulation - we want the logic to be in the nodes.Secondly I've also moved some of the logic of the hash into a node - the basic operation of finding the right bucket. That allows us to store the state and possibly do some branch profiling and value profiling but still provide a nice method call interface.
I've added a test to stress hash implementations.
We aren't doing any rebalancing for overloaded indices yet - we never grow the number of slots.