Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: jruby/jruby
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: c093201270aa
Choose a base ref
...
head repository: jruby/jruby
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 2ff9a2484081
Choose a head ref
  • 2 commits
  • 2 files changed
  • 1 contributor

Commits on Apr 28, 2016

  1. Copy the full SHA
    2d3c114 View commit details
  2. [Truffle] Use ArrayStrategy in Array#sort and cleanup.

    * Make sure we do not touch the original array.
    eregon committed Apr 28, 2016
    Copy the full SHA
    2ff9a24 View commit details
Showing with 26 additions and 71 deletions.
  1. +4 −0 spec/ruby/core/array/sort_spec.rb
  2. +22 −71 truffle/src/main/java/org/jruby/truffle/core/array/ArrayNodes.java
4 changes: 4 additions & 0 deletions spec/ruby/core/array/sort_spec.rb
Original file line number Diff line number Diff line change
@@ -8,6 +8,10 @@
end

it "does not affect the original Array" do
a = [3, 1, 2]
a.sort.should == [1, 2, 3]
a.should == [3, 1, 2]

a = [0, 15, 2, 3, 4, 6, 14, 5, 7, 12, 8, 9, 1, 10, 11, 13]
b = a.sort
a.should == [0, 15, 2, 3, 4, 6, 14, 5, 7, 12, 8, 9, 1, 10, 11, 13]
93 changes: 22 additions & 71 deletions truffle/src/main/java/org/jruby/truffle/core/array/ArrayNodes.java
Original file line number Diff line number Diff line change
@@ -2018,7 +2018,7 @@ private int toInt(VirtualFrame frame, Object indexObject) {

}

@CoreMethod(names = {"size", "length"})
@CoreMethod(names = { "size", "length" })
public abstract static class SizeNode extends ArrayCoreMethodNode {

@Specialization
@@ -2046,107 +2046,58 @@ public DynamicObject sortNull(DynamicObject array, Object unusedBlock) {
}

@ExplodeLoop
@Specialization(guards = {"isIntArray(array)", "isSmall(array)"})
public DynamicObject sortVeryShortIntegerFixnum(VirtualFrame frame, DynamicObject array, NotProvided block) {
final int[] store = (int[]) getStore(array);
final int[] newStore = new int[store.length];

@Specialization(guards = { "!isNullArray(array)", "isSmall(array)", "strategy.matches(array)" }, limit = "ARRAY_STRATEGIES")
public DynamicObject sortVeryShort(VirtualFrame frame, DynamicObject array, NotProvided block,
@Cached("of(array)") ArrayStrategy strategy) {
final ArrayMirror originalStore = strategy.newMirror(array);
final ArrayMirror store = strategy.newArray(getContext().getOptions().ARRAY_SMALL);
final int size = getSize(array);

// Selection sort - written very carefully to allow PE
// Copy with a exploded loop for PE

for (int i = 0; i < getContext().getOptions().ARRAY_SMALL; i++) {
if (i < size) {
for (int j = i + 1; j < getContext().getOptions().ARRAY_SMALL; j++) {
if (j < size) {
if (castSortValue(compareDispatchNode.call(frame, store[j], "<=>", null, store[i])) < 0) {
final int temp = store[j];
store[j] = store[i];
store[i] = temp;
}
}
}
newStore[i] = store[i];
store.set(i, originalStore.get(i));
}
}

return createArray(getContext(), newStore, size);
}

@ExplodeLoop
@Specialization(guards = {"isLongArray(array)", "isSmall(array)"})
public DynamicObject sortVeryShortLongFixnum(VirtualFrame frame, DynamicObject array, NotProvided block) {
final long[] store = (long[]) getStore(array);
final long[] newStore = new long[store.length];

final int size = getSize(array);

// Selection sort - written very carefully to allow PE

for (int i = 0; i < getContext().getOptions().ARRAY_SMALL; i++) {
if (i < size) {
for (int j = i + 1; j < getContext().getOptions().ARRAY_SMALL; j++) {
if (j < size) {
if (castSortValue(compareDispatchNode.call(frame, store[j], "<=>", null, store[i])) < 0) {
final long temp = store[j];
store[j] = store[i];
store[i] = temp;
final Object a = store.get(i);
final Object b = store.get(j);
if (castSortValue(compareDispatchNode.call(frame, b, "<=>", null, a)) < 0) {
store.set(j, a);
store.set(i, b);
}
}
}
newStore[i] = store[i];
}
}

return createArray(getContext(), newStore, size);
return createArray(getContext(), store.getArray(), size);
}

@Specialization(guards = {"isObjectArray(array)", "isSmall(array)"})
public DynamicObject sortVeryShortObject(VirtualFrame frame, DynamicObject array, NotProvided block) {
final Object[] oldStore = (Object[]) getStore(array);
final Object[] store = ArrayUtils.copy(oldStore);

// Insertion sort

final int size = getSize(array);

for (int i = 1; i < size; i++) {
final Object x = store[i];
int j = i;
// TODO(CS): node for this cast
while (j > 0 && castSortValue(compareDispatchNode.call(frame, store[j - 1], "<=>", null, x)) > 0) {
store[j] = store[j - 1];
j--;
}
store[j] = x;
}

return createArray(getContext(), store, size);
@Specialization(guards = { "!isNullArray(array)", "!isSmall(array)" })
public Object sortLargeArray(VirtualFrame frame, DynamicObject array, NotProvided block,
@Cached("new()") SnippetNode snippetNode) {
return snippetNode.execute(frame,
"sorted = dup; Rubinius.privately { sorted.isort!(0, right) }; sorted",
"right", getSize(array));
}

@Specialization(guards = { "!isNullArray(array)" })
public Object sortUsingRubinius(
VirtualFrame frame,
DynamicObject array,
DynamicObject block,
public Object sortWithBlock(VirtualFrame frame, DynamicObject array, DynamicObject block,
@Cached("new()") SnippetNode snippet) {

return snippet.execute(
frame,
return snippet.execute(frame,
"sorted = dup; Rubinius.privately { sorted.isort_block!(0, right, block) }; sorted",
"right", getSize(array),
"block", block);
}

@Specialization(guards = { "!isNullArray(array)", "!isSmall(array)" })
public Object sortUsingRubinius(
VirtualFrame frame,
DynamicObject array,
NotProvided block,
@Cached("new()") SnippetNode snippetNode) {
return snippetNode.execute(frame, "sorted = dup; Rubinius.privately { sorted.isort!(0, right) }; sorted", "right", getSize(array));
}

private int castSortValue(Object value) {
if (value instanceof Integer) {
return (int) value;