Forum: Ruby Iterating a changing Hash under 1.9.1

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
852a62a28f1de229dc861ce903b07a60?d=identicon&s=25 Gavin Kistner (phrogz)
on 2009-02-15 15:50
(Received via mailing list)
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?
F53b05cdbdf561cfe141f69b421244f3?d=identicon&s=25 David A. Black (Guest)
on 2009-02-15 16:24
(Received via mailing list)
Hi --

On Sun, 15 Feb 2009, Phrogz wrote:

>  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.rubypal.com
Coming in 2009: The Well-Grounded Rubyist (http://manning.com/black2)

http://www.wishsight.com => Independent, social wishlist management!
50b2daf0e7666574579b9edaf8f2b69a?d=identicon&s=25 Pit Capitain (Guest)
on 2009-02-15 16:37
(Received via mailing list)
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
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2009-02-15 18:20
(Received via mailing list)
On 15.02.2009 15:48, Phrogz wrote:
>   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
2ee1a7960cc761a6e92efb5000c0f2c9?d=identicon&s=25 William James (Guest)
on 2009-02-15 21:17
(Received via mailing list)
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.
Ede2aa10c6462f1d825143879be59e38?d=identicon&s=25 Charles Oliver Nutter (Guest)
on 2009-02-15 22:57
(Received via mailing list)
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
852a62a28f1de229dc861ce903b07a60?d=identicon&s=25 Gavin Kistner (phrogz)
on 2009-02-16 00:05
(Received via mailing list)
On Feb 15, 2:55 pm, Charles Oliver Nutter <charles.nut...@sun.com>
wrote:
> 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)
852a62a28f1de229dc861ce903b07a60?d=identicon&s=25 Gavin Kistner (phrogz)
on 2009-02-16 00:36
(Received via mailing list)
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.
Ede2aa10c6462f1d825143879be59e38?d=identicon&s=25 Charles Oliver Nutter (Guest)
on 2009-02-16 01:10
(Received via mailing list)
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
Ede2aa10c6462f1d825143879be59e38?d=identicon&s=25 Charles Oliver Nutter (Guest)
on 2009-02-16 01:58
(Received via mailing list)
Charles Oliver Nutter wrote:
> 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
852a62a28f1de229dc861ce903b07a60?d=identicon&s=25 Gavin Kistner (phrogz)
on 2009-02-16 01:59
(Received via mailing list)
On Feb 15, 5:07 pm, Charles Oliver Nutter <charles.nut...@sun.com>
wrote:
> 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?
F1d6cc2b735bfd82c8773172da2aeab9?d=identicon&s=25 Nobuyoshi Nakada (nobu)
on 2009-02-16 02:26
(Received via mailing list)
Hi,

At Mon, 16 Feb 2009 09:54:44 +0900,
Charles Oliver Nutter wrote in [ruby-talk:328324]:
> 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.

It's a bug fixed already in the trunk.
2ee1a7960cc761a6e92efb5000c0f2c9?d=identicon&s=25 William James (Guest)
on 2009-02-16 03:55
(Received via mailing list)
Phrogz wrote:

> 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.

h={:b,22, :c,33, :d,44, :e,55}
    ==>{:b=>22, :c=>33, :e=>55, :d=>44}
h.merge( {:b,202, :e,505, :f,66} )
    ==>{:b=>202, :c=>33, :f=>66, :e=>505, :d=>44}
Ede2aa10c6462f1d825143879be59e38?d=identicon&s=25 Charles Oliver Nutter (Guest)
on 2009-02-16 05:04
(Received via mailing list)
Phrogz wrote:
> 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?

I mean the first time passing through the set of keys, in comparison to
some additional times you see in the repeating case (example #2 in your
original email).

Note Nobu's response to my other email also. The JRuby behavior appears
to be the correct one, and ends up with five keys for 0-3 plus nil.

- Charlie
9b905791cbdbb1af35b65e02c3217e23?d=identicon&s=25 Tom Link (Guest)
on 2009-02-16 06:28
(Received via mailing list)
> > I think modifying a collection while iterating over it is undefined.
> It seems a very poor practice to me.

It shouldn't go into an infinite loop though. IMHO an exception
("modification during iteration" or something like that) would be
nice.
0ec4920185b657a03edf01fff96b4e9b?d=identicon&s=25 Yukihiro Matsumoto (Guest)
on 2009-02-16 07:34
(Received via mailing list)
Hi,

In message "Re: Iterating a changing Hash under 1.9.1"
    on Mon, 16 Feb 2009 14:28:07 +0900, Tom Link <micathom@gmail.com>
writes:

|It shouldn't go into an infinite loop though. IMHO an exception
|("modification during iteration" or something like that) would be
|nice.

Do you think speed decrease for normal case is acceptable?

              matz.
47b1910084592eb77a032bc7d8d1a84e?d=identicon&s=25 Joel VanderWerf (Guest)
on 2009-02-16 07:40
(Received via mailing list)
Yukihiro Matsumoto wrote:
>
>               matz.

It's also worrying that there is no clear definition of "during
iteration", bearing in mind that any method which yields is an iterator,
of sorts. Or would this only apply to a fixed set of core methods?
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2009-02-16 09:30
(Received via mailing list)
2009/2/16 Phrogz <phrogz@mac.com>:
> 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.

I think you left out plenty of options here.  Of course, it depends on
the issue at hand but you can do at least these

1. Iterate through keys only

hash.keys.each {|k| ... }

This is safe for inserts and deletions because Hash#keys creates a
new, unrelated Array.  This fits well your original example since you
are using keys only anway.

2. Using delete_if directly

hash.delete_if {|k,v| ...}

This method iterates all entries as well as safely deleting particular
items.

3. storing keys prepared for deletion separately

del = []
hash.each {|k,v| .... del << k if ...}
del.each {|k| hash.delete k}

> 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.

If changing during iteration is yields undefined results it is
perfectly ok to in one case endlessly loop and in the other do
something else.  Code which does something forbidden is never safe.

> 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.

IMHO SQL is a bad language for an example because it has a dramatic
different nature than Ruby: SQL is declarative while Ruby is
procedural.  Apart from that there is a SQL standard which defines
legal and illegal constructs.

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

I agree, this should be documented.  OTOH it is very common for
programming languages to not allow modifications of at least some
types of collections during iteration.  So I personally do not expect
it to work unless explicitly stated - especially for hash based
structures which can change dramatically with the insertion of a
single entry just because of the way hash tables work.

> 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.

AFAIK modification during iteration with #each is never safe for
Array, Hash (and thus also Set).

Kind regards

robert
This topic is locked and can not be replied to.