[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Iterating a changing Hash under 1.9.1

Phrogz

2/15/2009 2:48:00 PM

The following code shows that Hash#each under 1.9.1p0 does not iterate
over keys added during iteration:
a = [ 1, 2, 3 ]; h = { 0=>0 }
h.each{ |k,v| h[a[k]] = a[k] }
p h
#=> {0=>0, 1=>1}

However, this code (on 1.9.1p0) results in a ruby process with
unending 100% CPU usage, presumably due to an unending loop that keeps
traversing newly-added items:
h = { 1=>nil, 2=>nil }
h.each{ |k,v| h.delete(k); h[k]=v }
(Credit to "tama" for posting this on the ramaze group.)

I'm assuming that one of these two are a bug, since they seem
contradictory. I'd like to think that the latter behavior is the bug,
and that hashes aren't supposed to iterate over keys added or moved
during iteration. Can anyone confirm or deny this?
15 Answers

David A. Black

2/15/2009 3:23:00 PM

0

Hi --

On Sun, 15 Feb 2009, Phrogz wrote:

> The following code shows that Hash#each under 1.9.1p0 does not iterate
> over keys added during iteration:
> a = [ 1, 2, 3 ]; h = { 0=>0 }
> h.each{ |k,v| h[a[k]] = a[k] }
> p h
> #=> {0=>0, 1=>1}
>
> However, this code (on 1.9.1p0) results in a ruby process with
> unending 100% CPU usage, presumably due to an unending loop that keeps
> traversing newly-added items:
> h = { 1=>nil, 2=>nil }
> h.each{ |k,v| h.delete(k); h[k]=v }
> (Credit to "tama" for posting this on the ramaze group.)
>
> I'm assuming that one of these two are a bug, since they seem
> contradictory. I'd like to think that the latter behavior is the bug,
> and that hashes aren't supposed to iterate over keys added or moved
> during iteration. Can anyone confirm or deny this?

I can only add what I think is another interesting example:

h = {1,2,3,4}

h.select {|k,v|
h[rand] = 1
v > 4
}

This exits in 1.8 but goes on forever in 1.9. I'm not sure whether
it's because of the override that Hash#select does of
Enumerable#select.


David

--
David A. Black / Ruby Power and Light, LLC
Ruby/Rails consulting & training: http://www.r...
Coming in 2009: The Well-Grounded Rubyist (http://manning....)

http://www.wis... => Independent, social wishlist management!

Pit Capitain

2/15/2009 3:36:00 PM

0

2009/2/15 David A. Black <dblack@rubypal.com>:
> On Sun, 15 Feb 2009, Phrogz wrote:
>> (...)

I think modifying a collection while iterating over it is undefined.

Regards,
Pit

Robert Klemme

2/15/2009 5:18:00 PM

0

On 15.02.2009 15:48, Phrogz wrote:
> The following code shows that Hash#each under 1.9.1p0 does not iterate
> over keys added during iteration:
> a = [ 1, 2, 3 ]; h = { 0=>0 }
> h.each{ |k,v| h[a[k]] = a[k] }
> p h
> #=> {0=>0, 1=>1}
>
> However, this code (on 1.9.1p0) results in a ruby process with
> unending 100% CPU usage, presumably due to an unending loop that keeps
> traversing newly-added items:
> h = { 1=>nil, 2=>nil }
> h.each{ |k,v| h.delete(k); h[k]=v }
> (Credit to "tama" for posting this on the ramaze group.)
>
> I'm assuming that one of these two are a bug, since they seem
> contradictory. I'd like to think that the latter behavior is the bug,
> and that hashes aren't supposed to iterate over keys added or moved
> during iteration. Can anyone confirm or deny this?

I agree to Pit: the bug is to iterate and modify a collection at the
same time.

Cheers

robert

William James

2/15/2009 8:11:00 PM

0

Pit Capitain wrote:

> 2009/2/15 David A. Black <dblack@rubypal.com>:
> > On Sun, 15 Feb 2009, Phrogz wrote:
> >> (...)
>
> I think modifying a collection while iterating over it is undefined.

+1

It seems a very poor practice to me.

Charles Oliver Nutter

2/15/2009 9:55:00 PM

0

Phrogz wrote:
> The following code shows that Hash#each under 1.9.1p0 does not iterate
> over keys added during iteration:
> a = [ 1, 2, 3 ]; h = { 0=>0 }
> h.each{ |k,v| h[a[k]] = a[k] }
> p h
> #=> {0=>0, 1=>1}

In this case, you're only reassigning the same keys over and over again.
Since they're just being reassigned, they don't get pushed to the end of
the iteration and you don't loop forever.

Lesson one: reassigning an existing key does not move it to the end of
iteration order.

> However, this code (on 1.9.1p0) results in a ruby process with
> unending 100% CPU usage, presumably due to an unending loop that keeps
> traversing newly-added items:
> h = { 1=>nil, 2=>nil }
> h.each{ |k,v| h.delete(k); h[k]=v }
> (Credit to "tama" for posting this on the ramaze group.)

Here, you are deleting the key before assigning it. That removes it from
the original order and re-adds it at the end. So the iteration runs
forever because there's always another key to walk...the one you've just
re-added.

Lesson two: Keys deleted and re-added or keys newly added appear at the
end of iteration order.

- Charlie

Phrogz

2/15/2009 11:04:00 PM

0

On Feb 15, 2:55 pm, Charles Oliver Nutter <charles.nut...@sun.com>
wrote:
> Phrogz wrote:
> > The following code shows that Hash#each under 1.9.1p0 does not iterate
> > over keys added during iteration:
> >   a = [ 1, 2, 3 ]; h = { 0=>0 }
> >   h.each{ |k,v| h[a[k]] = a[k] }
> >   p h
> >   #=> {0=>0, 1=>1}
>
> In this case, you're only reassigning the same keys over and over again.
> Since they're just being reassigned, they don't get pushed to the end of
> the iteration and you don't loop forever.

I think you're wrong.
Initial state: { 0=>0 }
First loop: k is 0, a[0] is 1, assign h[1]=>1
A brand new key/value has been inserted to the hash this point.
If #each then covered the next key/value pair:
Second loop: k is 1, a[1] is 2, assign h[2]=>2 (and so on)

Phrogz

2/15/2009 11:25:00 PM

0

On Feb 15, 8:35 am, Pit Capitain <pit.capit...@gmail.com> wrote:
> 2009/2/15 David A. Black <dbl...@rubypal.com>:
>
> > On Sun, 15 Feb 2009, Phrogz wrote:
> >> (...)
>
> I think modifying a collection while iterating over it is undefined.

Ah, doggone it, that was my third choice between "is it a bug or is it
not". And I kept saying to myself as I wrote that up "Remember, you
should never claim something is a bug unless you're really really
sure."

I'll accept this answer as reasonable, though it seems a bit of a
shame. Always relegating deletions to a delete_if or reject or
explicit calls while iterating a duplicate may be inefficient in some
cases where complex logic needs to happen and ideally happen in a
single pass through the data.

It's 'safest' to say "DON'T TRUST ANYTHING, EVER", but provides the
lest flexibility during coding. It's most dangerous to say "YOU CAN
EXPLOIT WHATEVER IMPLEMENTATION QUIRKS AND BUGS THE CURRENT VERSION
HAS, WE PROMISE TO KEEP THOSE IN FUTURE VERSIONS", but also may
provide for convenient or efficiency via 'tricky' coding. Somewhere in
between is (my) ideal.

Imagine if SQL said "Inserting multiple records use a select on the
table you are inserting into is undefined." Programmers everywhere
would nod their heads wisely and say "Good call". And some
implementations would allow it, some wouldn't, and some people would
accidentally rely on it, and others would be pissed to not be able to.

Before it seems like I'm taking a strong stand for modification during
iteration: In my opinion, the only problem in this situation is simply
that the documentation for Hash#each provides no information. "We've
gotta be able to get some kind of reading on that shield, up or down!"

Ideally, in my mind, we should document:

a) [Implementation] How each iterating method happens to behave
currently with respect to additions, modifications, and deletions
during traversal, and

b) [Design] What is intended to be true about the implementation for
(foreseeable) future versions, and may be relied upon.

If the documentation for Hash#each said that inserting new entries
during traversal might cause an infinite loop, I never would have even
started this topic. And (possibly) the real-world bugs that happened
to exist in Ramaze that caused it to hang when moving from 1.8 to 1.9
would never have been coded.

I'll take this to ruby-core and see if I can gather details on Design
for a variety of methods, and offer up a doc patch. If anyone here can
provide any details about either Implementation or (for sure) Design,
I'd be happy to hear it.

Charles Oliver Nutter

2/16/2009 12:08:00 AM

0

Phrogz wrote:
> I think you're wrong.
> Initial state: { 0=>0 }
> First loop: k is 0, a[0] is 1, assign h[1]=>1
> A brand new key/value has been inserted to the hash this point.
> If #each then covered the next key/value pair:
> Second loop: k is 1, a[1] is 2, assign h[2]=>2 (and so on)

There are a maximum of four keys possible and you never remove any. The
second time through you're reassigning keys that are already there from
the first time.

- Charlie

Charles Oliver Nutter

2/16/2009 12:55:00 AM

0

Charles Oliver Nutter wrote:
> Phrogz wrote:
>> I think you're wrong.
>> Initial state: { 0=>0 }
>> First loop: k is 0, a[0] is 1, assign h[1]=>1
>> A brand new key/value has been inserted to the hash this point.
>> If #each then covered the next key/value pair:
>> Second loop: k is 1, a[1] is 2, assign h[2]=>2 (and so on)
>
> There are a maximum of four keys possible and you never remove any. The
> second time through you're reassigning keys that are already there from
> the first time.

Actually it looks like 1.9 is slightly different then what I described
(which was what I know of ordered hash iteration in JRuby. Ruby 1.9
appears to 'each' only once, since it's already at the end of the list.
In JRuby, we continue to iterate as long as you keep adding new keys:

a = [ 1, 2, 3 ]; h = { 0=>0 }
h.each{ |k,v| p [k,v]; p a[k]; h[a[k]] = a[k] }
p h

JRuby:

[0, 0]
1
[1, 1]
2
[2, 2]
3
[3, 3]
nil
[nil, nil]

Ruby 1.9.1:

[0, 0]
1
{0=>0, 1=>1}

Could be just a minor difference or a bug in one or the other.

- Charlie

Phrogz

2/16/2009 12:55:00 AM

0

On Feb 15, 5:07 pm, Charles Oliver Nutter <charles.nut...@sun.com>
wrote:
> Phrogz wrote:
> > I think you're wrong.
> > Initial state: { 0=>0 }
> > First loop: k is 0, a[0] is 1, assign h[1]=>1
> > A brand new key/value has been inserted to the hash this point.
> > If #each then covered the next key/value pair:
> > Second loop: k is 1, a[1] is 2, assign h[2]=>2 (and so on)
>
> There are a maximum of four keys possible and you never remove any. The
> second time through you're reassigning keys that are already there from
> the first time.

I'm confused. As far as I can tell, the hash starts with 1 key, and
ends up with 2. What 'first time' are the keys being set?