4 ms·

It is actually very reasonable. Other alternative is that iterator returns an error if underlying collection was modified (fail fast iterators).

by qwerta 13y ago

kevingadd 13y ago
.NET's collections all fail fast for seemingly this reason - they can't really provide anything else without huge performance consequences (even the fail fast behavior comes with a cost, due to the check...)
antirez 13y ago
There are alternatives but all will cost something... especially memory :-) For example every element may have an epoch, and every time a new element is added the epoch is incremented. Then what you could do is to only remember elements with epoch <= the epoch at which you started iterating, so that all the new elements will not be returned. We tried to do our best with the state available, that is just a 64 bit counter the server does not even need to remember, but just to return back to the caller, and get as argument in the next iterator call.
- awj 13y ago
  > For example every element may have an epoch, and every time a new element is added the epoch is incremented. Then what you could do is to only remember elements with epoch <= the epoch at which you started iterating, so that all the new elements will not be returned. Do that and you will immediately have people wanting an equally transaction-like view of the iteration set in the face of updates. I think it's best to draw the line where you have and be specific about what this is or is not intended to support.
- qwerta 13y ago
  Is 64bit counter part of hash which points to current position in Hash Tree? I implemented something similar for HTreeMap, but in Java.
  - antirez 13y ago
    It's actually something like a counter that counts starting from the most significant bits first, in the article there is a link to a comment that explains the implementation.
    - qwerta 13y ago
      So it was hard because hash table could resize between calls? For HTreeMap I used expanding Hash Tree. There are 4 dir levels, each with 128 entries. If dir becomes full (or has too many collisions), it splits into another 128 dirs. Iterations is done by increasing counter. If dir at level 2 is not found, it is increased by 128^2. Writing iterators took single day.

It is actually very reasonable. Other alternative is that iterator returns an error if underlying collection was modified (fail fast iterators).

by qwerta 13y ago

It is actually very reasonable. Other alternative is that iterator returns an error if underlying collection was modified (fail fast iterators).

kevingadd 13y ago

.NET's collections all fail fast for seemingly this reason - they can't really provide anything else without huge performance consequences (even the fail fast behavior comes with a cost, due to the check...)

antirez 13y ago

There are alternatives but all will cost something... especially memory :-) For example every element may have an epoch, and every time a new element is added the epoch is incremented. Then what you could do is to only remember elements with epoch <= the epoch at which you started iterating, so that all the new elements will not be returned. We tried to do our best with the state available, that is just a 64 bit counter the server does not even need to remember, but just to return back to the caller, and get as argument in the next iterator call.

awj 13y ago
> For example every element may have an epoch, and every time a new element is added the epoch is incremented. Then what you could do is to only remember elements with epoch <= the epoch at which you started iterating, so that all the new elements will not be returned. Do that and you will immediately have people wanting an equally transaction-like view of the iteration set in the face of updates. I think it's best to draw the line where you have and be specific about what this is or is not intended to support.
qwerta 13y ago
Is 64bit counter part of hash which points to current position in Hash Tree? I implemented something similar for HTreeMap, but in Java.
- antirez 13y ago
  It's actually something like a counter that counts starting from the most significant bits first, in the article there is a link to a comment that explains the implementation.
  - qwerta 13y ago
    So it was hard because hash table could resize between calls? For HTreeMap I used expanding Hash Tree. There are 4 dir levels, each with 128 entries. If dir becomes full (or has too many collisions), it splits into another 128 dirs. Iterations is done by increasing counter. If dir at level 2 is not found, it is increased by 128^2. Writing iterators took single day.