www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - iterator stability for containers

reply ikod <igor.khasilev gmail.com> writes:
Hello,

I'd like to know if there are any iterator stability rules for 
dlang containers?
For example iterator over emsi containers unrolled list - does it 
provide any stability warranties?

Or any other containers?

Thanks!
Sep 21 2020
next sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 9/21/20 11:28 AM, ikod wrote:

 Hello,
 
 I'd like to know if there are any iterator stability rules for dlang 
 containers?
 For example iterator over emsi containers unrolled list - does it 
 provide any stability warranties?
 
 Or any other containers?


In dcollections (which is over 10 years past bitrotting), a major focus 
of mine was to ensure stability when possible.

Therefore, I had a few nice properties:

1. cursors were never invalidated by removal or addition of items.
2. ranges could be invalidated, but for certain containers, ranges would 
be invalidated only if the items being removed were the endpoints of the 
ranges.
3. Removing items from a hash based container wouldn't rehash (to avoid 
iteration issues).
4. All containers supported removal while iterating via a special 
foreach mechanism.

Honestly, my impetus for creating dcollections was to reproduce some of 
the nice features of iterators in C++, including removal while iterating.

-Steve
Sep 21 2020
next sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 9/21/20 11:52 AM, Steven Schveighoffer wrote:

 1. cursors were never invalidated by removal or addition of items.


This should say "by remove or addition of *other* items"

-Steve
Sep 21 2020
prev sibling parent reply ikod <igor.khasilev gmail.com> writes:
On Monday, 21 September 2020 at 15:52:03 UTC, Steven 
Schveighoffer wrote:

 On 9/21/20 11:28 AM, ikod wrote:

 Hello,
 
 I'd like to know if there are any iterator stability rules for 
 dlang containers?
 For example iterator over emsi containers unrolled list - does 
 it provide any stability warranties?
 
 Or any other containers?


 In dcollections (which is over 10 years past bitrotting), a 
 major focus of mine was to ensure stability when possible.


Sorry, do you mean - the sources were lost?


 Therefore, I had a few nice properties:

 1. cursors were never invalidated by removal or addition of 
 items.
 2. ranges could be invalidated, but for certain containers, 
 ranges would be invalidated only if the items being removed 
 were the endpoints of the ranges.
 3. Removing items from a hash based container wouldn't rehash 
 (to avoid iteration issues).


I don't know if my solution is correct but I solved this by 
creating "immutable" copy of hashmap buckets array at the moment 
when user decided to mutate hash table while iterator is active. 
Iterator continue to walk over this immutable copy and user is 
free to change main table. So this works like "copy on write" and 
provide stable byKey/Value/Pair ranges.


 4. All containers supported removal while iterating via a 
 special foreach mechanism.

 Honestly, my impetus for creating dcollections was to reproduce 
 some of the nice features of iterators in C++, including 
 removal while iterating.


Agree totally.

I have problems with stable and performant iterator over unrolled 
linked list, so I'm looking around for available solutions.


 -Steve
Sep 21 2020
next sibling parent reply Daniel Kozak <kozzi11 gmail.com> writes:
On Mon, Sep 21, 2020 at 11:05 PM ikod via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 Sorry, do you mean - the sources were lost?


http://www.dsource.org/projects/dcollections



 Honestly, my impetus for creating dcollections was to reproduce
 some of the nice features of iterators in C++, including
 removal while iterating.


 Agree totally.

 I have problems with stable and performant iterator over unrolled
 linked list, so I'm looking around for available solutions.



From my POV I`m ok even with containers where stability is not provide. But


it would be perfect to have containers when I can select between
performance or stability.
I hardly ever need stability from containers, so for me it would be ok to
not guarantee in favor of speed. But still would be nice to have a way to
say that in some cases I prefer stability
Sep 21 2020
parent ikod <igor.khasilev gmail.com> writes:
On Monday, 21 September 2020 at 21:27:38 UTC, Daniel Kozak wrote:

 On Mon, Sep 21, 2020 at 11:05 PM ikod via Digitalmars-d < 
 digitalmars-d puremagic.com> wrote:


 Sorry, do you mean - the sources were lost?


 http://www.dsource.org/projects/dcollections



 Honestly, my impetus for creating dcollections was to 
 reproduce some of the nice features of iterators in C++, 
 including removal while iterating.


 Agree totally.

 I have problems with stable and performant iterator over 
 unrolled linked list, so I'm looking around for available 
 solutions.


 From my POV I`m ok even with containers where stability is not 
 provide. But


Sometimes we need to operate on collection while we iterate over 
it, and it's pity if you have to collect this changes somewhere 
and then apply in separate action.


 it would be perfect to have containers when I can select between
 performance or stability.


Performance (in terms of execution speed) is also first priority 
for me.
I can give up some small part of speed in exchange for 
convenience only when user make some unusual and rare things 
(like updating collection while iterating over it)



 I hardly ever need stability from containers, so for me it 
 would be ok to
 not guarantee in favor of speed. But still would be nice to 
 have a way to
 say that in some cases I prefer stability


It is possible to make stability configurable.
Sep 23 2020
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 9/21/20 5:01 PM, ikod wrote:

 On Monday, 21 September 2020 at 15:52:03 UTC, Steven Schveighoffer wrote:

 On 9/21/20 11:28 AM, ikod wrote:

 Hello,

 I'd like to know if there are any iterator stability rules for dlang 
 containers?
 For example iterator over emsi containers unrolled list - does it 
 provide any stability warranties?

 Or any other containers?


 In dcollections (which is over 10 years past bitrotting), a major 
 focus of mine was to ensure stability when possible.


 
 Sorry, do you mean - the sources were lost?


No, they are still there. Last commit was 2011 (meaningful commit), so I 
guess not yet 10 years.

https://github.com/schveiguy/dcollections

What I meant was simply that I haven't touched it in a long time, and it 
likely would be a bit of work to get it working again. For sure there is 
no dub file.


 

 Therefore, I had a few nice properties:

 1. cursors were never invalidated by removal or addition of items.
 2. ranges could be invalidated, but for certain containers, ranges 
 would be invalidated only if the items being removed were the 
 endpoints of the ranges.
 3. Removing items from a hash based container wouldn't rehash (to 
 avoid iteration issues).


 
 I don't know if my solution is correct but I solved this by creating 
 "immutable" copy of hashmap buckets array at the moment when user 
 decided to mutate hash table while iterator is active. Iterator continue 
 to walk over this immutable copy and user is free to change main table. 
 So this works like "copy on write" and provide stable byKey/Value/Pair 
 ranges.


This requires a lot of recordkeeping, but is a reasonable solution. I 
wanted to avoid too much of this. I provided a primitive that you can 
always check if a cursor or range belongs to a container.

I *think* I had experimented at one point with keeping a revision count, 
and throwing if you tried to iterate something that was no longer at the 
same revision. But I don't remember if that ever made it into any 
versions. Maybe that was a different project...


 4. All containers supported removal while iterating via a special 
 foreach mechanism.

 Honestly, my impetus for creating dcollections was to reproduce some 
 of the nice features of iterators in C++, including removal while 
 iterating.


 
 Agree totally.
 
 I have problems with stable and performant iterator over unrolled linked 
 list, so I'm looking around for available solutions.


Technically, dcollections doesn't have unrolled linked lists. But the 
default allocator allocates a page-worth of nodes, which are assigned in 
order from the block, so it should be pretty cache friendly.

If there is any interest, I can accept PRs to resurrect it or put it 
into code.dlang.org.

-Steve
Sep 21 2020
parent reply ikod <igor.khasilev gmail.com> writes:
On Monday, 21 September 2020 at 22:00:36 UTC, Steven 
Schveighoffer wrote:

 On 9/21/20 5:01 PM, ikod wrote:

 On Monday, 21 September 2020 at 15:52:03 UTC, Steven 
 Schveighoffer wrote:

 On 9/21/20 11:28 AM, ikod wrote:







 No, they are still there. Last commit was 2011 (meaningful 
 commit), so I guess not yet 10 years.

 https://github.com/schveiguy/dcollections


Oh, sorry for confusion )


 Technically, dcollections doesn't have unrolled linked lists. 
 But the default allocator allocates a page-worth of nodes, 
 which are assigned in order from the block, so it should be 
 pretty cache friendly.


Thanks, I'll check it. If dcollections support fast nogc list - 
that's all what I need. optionally I need stability.


 If there is any interest, I can accept PRs to resurrect it or 
 put it into code.dlang.org.

 -Steve
Sep 23 2020
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 9/23/20 3:21 AM, ikod wrote:

 On Monday, 21 September 2020 at 22:00:36 UTC, Steven Schveighoffer wrote:

 Technically, dcollections doesn't have unrolled linked lists. But the 
 default allocator allocates a page-worth of nodes, which are assigned 
 in order from the block, so it should be pretty cache friendly.


 
 Thanks, I'll check it. If dcollections support fast nogc list - that's 
 all what I need. optionally I need stability.


Oh, nogc. that's probably not in the cards for dcollections. 
Technically, it might be possible, as dcollections used my own design of 
allocators (stdx.allocators wasn't around), but unfortunately 
dcollections is based on classes. I suppose you could use scope objects 
and C malloc allocators. But it's not implemented currently.

-Steve
Sep 23 2020
prev sibling parent reply Brian Schott <briancschott gmail.com> writes:
On Monday, 21 September 2020 at 15:28:24 UTC, ikod wrote:

 For example iterator over emsi containers unrolled list - does 
 it provide any stability warranties?


No. It also doesn't specify stability or instability, so I should 
probably improve the documentation for that.
Sep 22 2020
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/22/20 6:05 PM, Brian Schott wrote:

 On Monday, 21 September 2020 at 15:28:24 UTC, ikod wrote:

 For example iterator over emsi containers unrolled list - does it 
 provide any stability warranties?


 
 No. It also doesn't specify stability or instability, so I should 
 probably improve the documentation for that.


Thanks. Problem is, I wrote the code in this manner hoping to get rid of 
the braces (it had the condition reverse). But not a biggie.
Sep 22 2020