Skip to content
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.

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

Optimize slice reverse #5401

Merged
merged 1 commit into from Dec 18, 2017
Merged

Conversation

larubujo
Copy link
Contributor

current slice reverse uses offsets. then each step need to compute new offset. faster if use just pointers and move pointers. less math. benchmark:

require "benchmark"

struct Slice
  def new_reverse!
    check_writable

    p = @pointer
    q = @pointer + size - 1

    while p < q
      p.value, q.value = q.value, p.value
      p += 1
      q -= 1
    end

    self
  end
end

bytes = Bytes[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]

Benchmark.ips do |x|
  x.report("old") do
    bytes.reverse!
  end
  x.report("new") do
    bytes.new_reverse!
  end
end

output:

old   34.7M ( 28.82ns) (± 4.03%)  1.43× slower
new  49.52M ( 20.19ns) (± 4.44%)       fastest

@sdogruyol
Copy link
Member

Welcome and congratulations for your first PR @larubujo 🎉

@RX14
Copy link
Contributor

RX14 commented Dec 18, 2017

I would have thought that LLVM would easily be able to convert this indexing into a pointer, it's a fairly basic optimization. But this is clearly faster so lets merge it.

I did some testing and it appears to be faster for all arrays, even large ones (even 1GiB where I thought instruction differences would pale in comparison to memory bandwidth showed a 5% speedup).

@RX14 RX14 merged commit c74c0bd into crystal-lang:master Dec 18, 2017
@RX14 RX14 modified the milestones: Next, 0.24.1 Dec 18, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

5 participants