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

No-copy subarray iteration (Implements #3386) #3390

Closed
wants to merge 1 commit into from
Closed

No-copy subarray iteration (Implements #3386) #3390

wants to merge 1 commit into from

Conversation

cjgajard
Copy link
Contributor

@cjgajard cjgajard commented Oct 7, 2016

I first thought of not implementing Indexable#each_index(*, start : Int, count : Int) because feels redundat with (start...start+count).each, but it makes some boundary checks, so I think is not that useless.

A benchmark does not shows differences as big as I thougth it would be, but allows LLVM to inline unnecessary calls

$ bin/crystal tmp/benchmark.cr --release
Using compiled compiler at .build/crystal

NO INLINE:
  array[start, count].each   1.64M (± 8.48%)  1.55× slower
array.each(start:, count:)   2.53M (± 1.97%)  1.00× slower
       array.each(within:)   2.53M (± 1.42%)       fastest

INLINE:
  array[start, count].each   2.88M (±15.31%)  4.69× slower
array.each(start:, count:)  13.52M (± 2.62%)       fastest
       array.each(within:)   12.4M (± 1.97%)  1.09× slower

@RX14
Copy link
Contributor

RX14 commented Oct 7, 2016

If you use a larger array in your benchmark the difference should be much larger, especially when the copied array doesn't fit into the cache any more.

@lbguilherme
Copy link
Contributor

An alternative implementation/api:

a = (1..30).to_a
a.skip(20).limit(5).each do |x|
  p x # 21 .. 25
end

The good thing is that it would work with all other operations like map and so on. What do you think?

module Indexable(T)
  def skip(count)
    SkipIndexable.new(self, count)
  end

  def limit(count)
    LimitIndexable.new(self, {count, size}.min)
  end

  private class SkipIndexable(T)
    include Indexable(T)

    def initialize(@indexable : Indexable(T), @skip : Int32)
    end

    def size
      @indexable.size - @skip
    end

    def unsafe_at(index : Int)
      @indexable.unsafe_at(index + @skip)
    end
  end

  private class LimitIndexable(T)
    include Indexable(T)

    def initialize(@indexable : Indexable(T), @limit : Int32)
    end

    def size
      @limit
    end

    def unsafe_at(index : Int)
      @indexable.unsafe_at(index)
    end
  end
end

@chaniks
Copy link

chaniks commented Oct 7, 2016

@lbguilherme Wow.. I actually have a similar implementation, even with similar naming 😄

arr.each.limit(1..3) { |x| puts x }
arr.each.skip(1).limit(3) { |x| puts x }
arr.each.limit(2) { |x| puts x }

But mine still needs some work..
And to make it consistent, I have to change all methods in Iterator to take block.. (And maybe remove limit(n, &block) because first(n, &block) will do the same thing.)

However, yours don't have the problem and done much simpler! 😄

@asterite
Copy link
Member

asterite commented Oct 7, 2016

limit is first, so you can already do that (except provide a range). The "bad" thing is that creating iterators sometimes allocates a bit of memory, but it should be less memory than copying arrays.

@lbguilherme
Copy link
Contributor

Having this implemented in Iterable is bad because skip requires calling next several times. But on Indexable it is free.

@asterite
Copy link
Member

asterite commented Jun 4, 2017

I like this, and I like the use of the named arguments. 👍 from me.

@mverzilli
Copy link

@cjgajard are you around to resolve the conflicts? We can then merge.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

6 participants