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: 40291975e811
Choose a base ref
...
head repository: jruby/jruby
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: ff0d7359d1cc
Choose a head ref
  • 3 commits
  • 2 files changed
  • 1 contributor

Commits on May 27, 2016

  1. Copy the full SHA
    0b5fb7f View commit details
  2. Copy the full SHA
    13fead0 View commit details
  3. Copy the full SHA
    ff0d735 View commit details
Showing with 28 additions and 20 deletions.
  1. +2 −4 truffle/src/main/java/org/jruby/truffle/core/array/ArrayNodes.java
  2. +26 −16 truffle/src/main/ruby/core/array.rb
Original file line number Diff line number Diff line change
@@ -2069,8 +2069,7 @@ public DynamicObject sortVeryShort(VirtualFrame frame, DynamicObject array, NotP
public Object sortLargeArray(VirtualFrame frame, DynamicObject array, NotProvided block,
@Cached("new()") SnippetNode snippetNode) {
return snippetNode.execute(frame,
"sorted = dup; Truffle.privately { sorted.isort!(0, right) }; sorted",
"right", getSize(array));
"sorted = dup; Truffle.privately { sorted.mergesort! }; sorted");
}

@Specialization(guards = { "isObjectArray(array)" })
@@ -2095,8 +2094,7 @@ public int compare(Object a, Object b) {
public Object sortWithBlock(VirtualFrame frame, DynamicObject array, DynamicObject block,
@Cached("new()") SnippetNode snippet) {
return snippet.execute(frame,
"sorted = dup; Truffle.privately { sorted.isort_block!(0, right, block) }; sorted",
"right", getSize(array),
"sorted = dup; Truffle.privately { sorted.mergesort_block!(block) }; sorted",
"block", block);
}

42 changes: 26 additions & 16 deletions truffle/src/main/ruby/core/array.rb
Original file line number Diff line number Diff line change
@@ -2006,7 +2006,8 @@ def recursively_flatten(array, out, max_levels = -1)
# runs back together.
def mergesort!
width = 7
@scratch = Rubinius::Tuple.new size
source = self
scratch = Array.new(size, at(0))

# do a pre-loop to create a bunch of short sorted runs; isort on these
# 7-element sublists is more efficient than doing merge sort on 1-element
@@ -2035,30 +2036,34 @@ def mergesort!
last = left + (2 * width)
last = last < finish ? last : finish

bottom_up_merge(left, right, last)
bottom_up_merge(left, right, last, source, scratch)
left += 2 * width
end

@tuple, @scratch = @scratch, self
source, scratch = scratch, source
width *= 2
end

@scratch = nil
replace(source) if source != self

self
end
private :mergesort!

def bottom_up_merge(left, right, last)
def bottom_up_merge(left, right, last, source, scratch)
left_index = left
right_index = right
i = left

while i < last
if left_index < right && (right_index >= last || (at(left_index) <=> at(right_index)) <= 0)
@scratch[i] = at(left_index)
left_element = source.at(left_index)
right_element = source.at(right_index)

if left_index < right && (right_index >= last || (left_element <=> right_element) <= 0)
scratch[i] = left_element
left_index += 1
else
@scratch[i] = at(right_index)
scratch[i] = right_element
right_index += 1
end

@@ -2069,7 +2074,8 @@ def bottom_up_merge(left, right, last)

def mergesort_block!(block)
width = 7
@scratch = Rubinius::Tuple.new size
source = self
scratch = Array.new(size, at(0))

left = 0
finish = size
@@ -2094,30 +2100,34 @@ def mergesort_block!(block)
last = left + (2 * width)
last = last < finish ? last : finish

bottom_up_merge_block(left, right, last, block)
bottom_up_merge_block(left, right, last, source, scratch, block)
left += 2 * width
end

@tuple, @scratch = @scratch, self
source, scratch = scratch, source
width *= 2
end

@scratch = nil
replace(source) if source != self

self
end
private :mergesort_block!

def bottom_up_merge_block(left, right, last, block)
def bottom_up_merge_block(left, right, last, source, scratch, block)
left_index = left
right_index = right
i = left

while i < last
if left_index < right && (right_index >= last || block.call(at(left_index), at(right_index)) <= 0)
@scratch[i] = at(left_index)
left_element = source.at(left_index)
right_element = source.at(right_index)

if left_index < right && (right_index >= last || block.call(left_element, right_element) <= 0)
scratch[i] = left_element
left_index += 1
else
@scratch[i] = at(right_index)
scratch[i] = right_element
right_index += 1
end