Asp Forum - Re: Is iterating in lock-step possible?

Roshan James

3/10/2005 1:18:00 PM

Brian, ts,

Generators - I did not know about them. I had a look at this -
http://www.ruby-doc.org/stdlib/libdoc/generator/rdoc/classes/G...
tml
It does not look like this is a good think to do at all, because all the
state-management that itertors do for free is lost at the cost of
creating another continuation around it. Admittedly this solves the
syntactic problem that I was looking for a solution to, but at a very
large cost to the runtime.

I found a terse description of zip() at
http://whytheluckystiff.net/articles/rubyOneEi...
Is there a better place I can read up about this? I want to know how
this works.

In my post, I chose the array.each only as an example. Its not arrays
for which I want to do this with - I want to solve the problem for
iterator calls. If zip() internally creates a list of values from both
iterations, then it does not help me. I want to be able to do the actual
computation of the iterator calls in lock-step.

Roshan

7 Answers

Robert Klemme

3/10/2005 3:11:00 PM

"Roshan James" <roshanj@microsoft.com> schrieb im Newsbeitrag
news:E8AA887D9A078F45B870125A37ED234701BC9573@APS-MSG-02.southpacific.corp.microsoft.com...
> Brian, ts,
>
> Generators - I did not know about them. I had a look at this -
> http://www.ruby-doc.org/stdlib/libdoc/generator/rdoc/classes/G...
> tml
> It does not look like this is a good think to do at all, because all the
> state-management that itertors do for free is lost at the cost of
> creating another continuation around it. Admittedly this solves the
> syntactic problem that I was looking for a solution to, but at a very
> large cost to the runtime.
>
> I found a terse description of zip() at
> http://whytheluckystiff.net/articles/rubyOneEi...
> Is there a better place I can read up about this? I want to know how
> this works.
>
> In my post, I chose the array.each only as an example. Its not arrays
> for which I want to do this with - I want to solve the problem for
> iterator calls. If zip() internally creates a list of values from both
> iterations, then it does not help me. I want to be able to do the actual
> computation of the iterator calls in lock-step.

Hm...

class Foo
include Enumerable
def initialize(i)
@enum = 1..i
end
def each(&b) @enum.each(&b) end
end

>> f1=Foo.new 10
=> #<Foo:0x10177298 @enum=1..10>
>> f2=Foo.new 10
=> #<Foo:0x10172498 @enum=1..10>
>> f1.zip(f2) {|*a| p a}
TypeError: cannot convert Foo into Array
from (irb):10:in `zip'
from (irb):10

class Foo
include Enumerable
def initialize(i)
@enum = 1..i
end
def each(&b) @enum.each(&b) end
alias :to_ary :to_a
end

>> f1=Foo.new 10
=> #<Foo:0x101a0080 @enum=1..10>
>> f2=Foo.new 10
=> #<Foo:0x1019a0c8 @enum=1..10>
>> f1.zip(f2) {|*a| p a}
[[1, 1]]
[[2, 2]]
[[3, 3]]
[[4, 4]]
[[5, 5]]
[[6, 6]]
[[7, 7]]
[[8, 8]]
[[9, 9]]
[[10, 10]]
=> nil

Fixed but at the cost of one enum converted to an array. I guess the
generator approach is the only feasible solution for the general case.

Regards

robert

William Morgan

3/10/2005 3:42:00 PM

Excerpts from Roshan James's mail of 10 Mar 2005 (EST):
> Generators - I did not know about them. I had a look at this -
> http://www.ruby-doc.org/stdlib/libdoc/generator/rdoc/classes/Gene...
>
> It does not look like this is a good think to do at all, because all the
> state-management that itertors do for free is lost at the cost of
> creating another continuation around it.

I'm not sure what you mean by that, but:

> Admittedly this solves the syntactic problem that I was looking for a
> solution to, but at a very large cost to the runtime.

There's a definite cost to using generators. Of course, you've already
incurred a huge performance penalty by using Ruby in the first place. Is
the further cost of generators really too much?

I see about a factor of ten slow-down in the following toy example.
It'd be interesting to do more datapoints and see if this is a linear
relationship or what.

ruby -rgenerator -rbenchmark -e 'a=(1..100000).map{|x|x};g=Generator.new(a);[
lambda { a.each { |x| x } },
lambda { while g.next?; g.next; end },
].each {|pr| puts Benchmark.measure(&pr) }'
0.030000 0.000000 0.030000 ( 0.027388)
10.380000 1.190000 11.570000 ( 11.612888)

> I found a terse description of zip() at
> http://whytheluckystiff.net/articles/rubyOneEi...
> Is there a better place I can read up about this? I want to know how
> this works.

Unfortunately not, other than the Ruby source code itself.

> In my post, I chose the array.each only as an example. Its not arrays
> for which I want to do this with - I want to solve the problem for
> iterator calls. If zip() internally creates a list of values from both
> iterations, then it does not help me. I want to be able to do the actual
> computation of the iterator calls in lock-step.

Enum#zip internally turns everything into arrays.

Unless you can deal with the original objects as external (i.e.
Python-style) iterators, this is the price you pay for the niceness of
interal iterators.

--
William <wmorgan-ruby-talk@masanjin.net>

William Morgan

3/10/2005 5:25:00 PM

Excerpts from William Morgan's mail of 10 Mar 2005 (EST):
> I see about a factor of ten slow-down in the following toy example.

Um that would be, 1000. Not ten. 1000.

In the following experiments I see factors of anywhere between 200 and
950, so three orders of magnitude seems reasonable.

ruby -rgenerator -rbenchmark -e 'Benchmark.bm(7) do |b|
(14 .. 19).each do |level|
size = 2 ** level
a = (0 ... size).to_a
g = Generator.new a
b.report("arr #{level}") { a.each { |x| x } }
b.report("gen #{level}") { while g.next?; g.next; end }
end
end'

arr 14 0.010000 0.000000 0.010000 ( 0.007526)
gen 14 2.280000 0.600000 2.880000 ( 2.912238)
arr 15 0.010000 0.000000 0.010000 ( 0.017132)
gen 15 5.270000 0.030000 5.300000 ( 5.302015)
arr 16 0.040000 0.000000 0.040000 ( 0.030965)
gen 16 11.520000 0.660000 12.180000 ( 12.204337)
arr 17 0.040000 0.000000 0.040000 ( 0.044533)
gen 17 25.030000 3.370000 28.400000 ( 28.563181)
arr 18 0.070000 0.000000 0.070000 ( 0.070832)
gen 18 61.730000 0.500000 62.230000 ( 62.321825)
arr 19 0.150000 0.000000 0.150000 ( 0.151578)
gen 19 142.200000 10.050000 152.250000 (159.363150)

Looks kinda super-linear. Anyways, just entertaining myself.

--
William <wmorgan-ruby-talk@masanjin.net>

Jonathan Paisley

3/11/2005 10:05:00 AM

On Fri, 11 Mar 2005 02:25:12 +0900, William Morgan wrote:

> Excerpts from William Morgan's mail of 10 Mar 2005 (EST):
>> I see about a factor of ten slow-down in the following toy example.
>
> Um that would be, 1000. Not ten. 1000.
>
> In the following experiments I see factors of anywhere between 200 and
> 950, so three orders of magnitude seems reasonable.

Anyone got any idea how the performance and memory cost would compare by
using threads to do the parallel internal iteration (using each) instead
of the continuations that Generator uses?

What I'm thinking of is creating a thread for each Enumerable that needs
to be iterated, and having each of these threads pass the yielded values
to the calling thread which can then yield appropriately.

I get the impression that Generator generates (hoho) lots of continuations
and therefore causes extra headache for the garbage collector. Minimising
this might provide a performance boost?

ts

3/11/2005 10:42:00 AM

>>>>> "J" == Jonathan Paisley <jp-www@dcs.gla.ac.uk> writes:

J> Anyone got any idea how the performance and memory cost would compare by
J> using threads to do the parallel internal iteration (using each) instead
J> of the continuations that Generator uses?

Internally a continuation is implemented by a thread.

--

Guy Decoux

Jonathan Paisley

3/11/2005 1:11:00 PM

On Fri, 11 Mar 2005 11:41:42 +0100, ts wrote:

>>>>>> "J" == Jonathan Paisley <jp-www@dcs.gla.ac.uk> writes:
>
> J> Anyone got any idea how the performance and memory cost would compare by
> J> using threads to do the parallel internal iteration (using each) instead
> J> of the continuations that Generator uses?
>
> Internally a continuation is implemented by a thread.

Ahah! The difference then would be that Generator creates many
continuations (and therefore threads?) as each value is yielded, whereas
the approach I was thinking about involves creating one thread for each
Enumerable.

I wonder what the tradeoffs are then between creating and invoking
continuations, and locking and context switching between threads.

Cs. Henk

3/11/2005 5:33:00 PM

On Fri, Mar 11, 2005 at 12:41:33AM +0900, William Morgan wrote:
> ruby -rgenerator -rbenchmark -e 'a=(1..100000).map{|x|x};g=Generator.new(a);[
> lambda { a.each { |x| x } },
> lambda { while g.next?; g.next; end },
> ].each {|pr| puts Benchmark.measure(&pr) }'
> 0.030000 0.000000 0.030000 ( 0.027388)
> 10.380000 1.190000 11.570000 ( 11.612888)

It's a bit faster if you do

begin
while g.next; end
rescue EOFError
end

Not with magnitudes, tho.

Csaba

comp.lang.ruby

Re: Is iterating in lock-step possible?

Roshan James

Robert Klemme

William Morgan

William Morgan

Jonathan Paisley

ts

Jonathan Paisley

Cs. Henk

x Login to ForumsZone