|
|
George, Your questions are pretty much great. You usually give good info, usually show some code, and you're definately polite....however some of your questions can be answered by just opening an IDE and trying things out. Thats how you learn and how you learn to not need help.
Just my 0.02
|
|
|
|
|
|
Yes, you're absolutely correct.
The only thing I'd like to add to your list of things we cannot do is: changing the order of the elements (by changing the key or whatever the elements are sorted on).
Everything else is fine.
Notes:
1. It is possible for someone to create an enumerable class (such as a dictionary) that supports all these operations from within a foreach loop. It all depends on how the enumerator and the rest of the class is implemented.
2. For performance reasons, enumerable classes are generally not thread-safe (unless the docs say they are). This means you have to think about not only what you do in the foreach loop, but also what other threads may be doing.
3. Testing this in the IDE (as someone suggested) may not help you much. It may work sometimes, and sometimes not, depending on how the dictionary is implemented, what it contains and exactly what you do. So the results may fool you.
Peter the small turnip
(1) It Has To Work. --RFC 1925[^]
|
|
|
|
|
Thanks PeterTheSwede,
Your reply is really great! I have a further question, why in current design of Dictionary, it is not allowed to add/remove elements or change the value of key (reorder factor is key)?
regards,
George
|
|
|
|
|
George_George wrote: why in current design of Dictionary, it is not allowed to add/remove elements
You can not change the dictionary while you are looping through it. If the dictionary would be able to handle that, it would have to be a lot more complex.
George_George wrote: or change the value of key
You can't change a key of an entry, as the key decides where the entry is stored. To store a value under a different key, you have to remove the entry and add the value using the new key.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Thanks Guffa,
I totally agree with you. Sorry I have not made myself understood. My question is, how Dictionary is designed internally so that we do not allow to insert/remove elements during foreach loop?
I want to know the basic idea about why the design of Dictionary is restricted to such operation.
regards,
George
|
|
|
|
|
There are some things that would be complicated, impractical, or even impossible, to handle correctly if a dictionary would allow adding and removing items during enumeration. For example:
If the dictionary would allow adding of items, it would have to always add the items at the end of the collection, so that the new items would always be handled at the end of the loop. This means that the dictionary can not reuse any previously released entries.
The enumerator contains a reference to the current item. If that item would be removed, the reference would point to an item that no longer is a part of the collection.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Thanks Guffa,
I have understood why there is such restriction. 
regards,
George
|
|
|
|
|
What Guffa said, plus some further clarifications (I hope):
The reason behind all this is that it is usually expensive (in terms of performance or memory) for an enumerator (see below) to handle additions/deletions/reordering during its lifetime.
An enumerator is the object (implementing the interfaces IEnumerator and possibly IEnumerator<T>) that handles the foreach loop. It is returned by the GetEnumerator method on the IEnumerable or IEnumerable<T> interface, which gets called behind the scenes by the foreach statement (in C# this is hidden - the GetEnumerator body can be thought of as the enumerator object).
As the enumerator has to know where it is and where it is going in the collection, handling inserts, deletes and reordering would force it to - for example - copy a reference for each element into a temporary array when it is created (when the loop starts), and then step through that array. Depending on the number of elements, this could take a lot of time (and space). And it's usually considered unwise to let something that looks simple (foreach) actually be complex behind the scenes (because that would fool programmers and make them write slow code by mistake).
Any clearer? See the docs (under System.Collections and System.Collections.Generic, respectively) for details on the interfaces I mention.
One more point: It is sometimes possible to figure out (or even obvious) exactly how a particular collection is implemented and exactly what happens in the enumerator. Knowing that, it's perfectly possible to perform deletions, additions and/or reorderings from within a foreach loop, as long as you take care and handle the consequences correctly (such as never seeing the item after an item getting deleted - which is true in index-based collections). But... it is normally not a good idea to do this - as the implementation may change in a newer version of the library defining the collection.
Also, I would consider it bad style to do inserts, deletions or reordering in a foreach loop even if a collection explicitly supports it (in its documentation, version-independently) - simply because it is confusing. Not everyone reading the foreach loop may have access to the docs, and would therefore assume the behaviour to be a bug.
Peter the small turnip
(1) It Has To Work. --RFC 1925[^]
|
|
|
|
|
Thanks PeterTheSwede!
Great reply! I am interested to discuss further with you.
I am very interested in two statements you mentioned before,
---------------------
1.
The reason behind all this is that it is usually expensive (in terms of performance or memory) for an enumerator (see below) to handle additions/deletions/reordering during its lifetime.
2.
As the enumerator has to know where it is and where it is going in the collection, handling inserts, deletes and reordering would force it to - for example - copy a reference for each element into a temporary array when it is created (when the loop starts), and then step through that array.
---------------------
Especially for item 2, I think it is the reason why add/remove/reorder during foreach is expensive, but my question is I can not figure out why from the implmentation level it is expensive, for example, why do we need to "copy a reference for each element into a temporary array when it is created"? Could you clarify or give more description please?
The reason why I am confused is, for example, delete during foreach is not hard to implement and should not be expensive,
(suppose we are using linked list to store a list of key collections of a Dictinoary)
1. if delete an element which is already iterated, just remove and step next in next iteration;
2. if delete an element which is not iterated yet, just remove and step next in next iteration;
3. if delete an element which is the element which is currently iterated now, just remove the current and step to next iteration.
regards,
George
|
|
|
|
|
George_George wrote: ...delete during foreach is not hard to implement and should not be expensive
You are perfectly right - there are scenarios where this isn't expensive - a linked list is a perfect example. A lazy-loading collection class that behaves like an ADO recordset would be another.
The point, however, is that this isn't always the case - it depends on how the collection class is implemented internally.
Look at this example (not tested, may have typos):
private List<SomeType> myList = new List<SomeType>
public System.Collections.Generic.IEnumerator<SomeType> GetEnumerator()
{
for (int i = 0; i < myList.Length; i++)
{
yield return myList[i];
}
}
public System.Collections.Generic.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
This is probably what most custom collection classes look like (at least mine do). Since I know that people don't mess with my collection from within a foreach loop, I don't even have to think about what happens if elements get deleted. As you can see, I will miss the next element in that case - if you delete element 2 in {1, 2, 3, 4}, the next element yielded will be 4, not 3. Also, if someone tried to optimize it by storing myList.Length in a variable (which would be quite possible), the for loop would even throw an exception (index out of range) before finishing the loop.
If you look at it for a while, you see that there is no really simple way to fix this (allow deletes) without using something that isn't a List. And let's say - for the sake of argument - that I have to use a list (perhaps because I get the list from some internal class that only returns a list, and a conversion would be costly).
So... although you could see the "rules" as more of recommendations, they are generally accepted, so you can never assume that they don't apply. Also, you will cause confusion among your peers if you violate them, even if the collection class you're using explicitly permits it (unless you make that very clear in a comment).
Peter the small turnip
(1) It Has To Work. --RFC 1925[^]
|
|
|
|
|
Thanks Peter,
Your reply is so great! One question, you mentioned -- "custom collection classes", do you mean the class like List/Dictionary or the class like SomeType in your sample?
regards,
George
|
|
|
|
|
Thanks. And sorry - the word "custom" usually means "not standard", so yes, I meant the class SomeType in my example. Or any other collection class not in the .NET framework.
Then again, what I say is probably true even for the "standard" classes (the ones in the framework), unless the documentation explicitly tells you otherwise.
Peter the small turnip
(1) It Has To Work. --RFC 1925[^]
|
|
|
|
|
Great Peter!
Question answered.
regards,
George
|
|
|
|
|
If you look at it for a while, you see that there is no really simple way to fix this (allow deletes) without using something that isn't a List.
Actually, there would be. Provide a means of indicating an object is no longer meaningful (e.g. for an array-based dictionary, set the key to nothing), and make the 'add' routine (which may not be run during an enumeration) perform the actual deletions. Note that this would not only allow for convenient deletion of objects from within an enumerator--it would also allow the consolidation of multiple deletions that are performed without an intervening addition.
|
|
|
|
|
George_George wrote: for example, why do we need to "copy a reference for each element into a temporary array when it is created"? Could you clarify or give more description please?
Expanding on my previous example:
private List<SomeType> myList = new List<SomeType>
public System.Collections.Generic.IEnumerator<SomeType> GetEnumerator()
{
SomeType[] elems = myList.ToArray();
for (int i = 0; i < elems.Length; i++)
{
yield return elems[i];
}
}
public System.Collections.Generic.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
With the ToArray() call (which is a memory allocation and a shallow copy of the list - an expensive operation if the list is large), I am now totally immune to any changes of the list during the foreach.
And... without spending more time on it than I would like when building my own collection class, I can't think of a cheaper way to solve this (again assuming that I must use a list internally, and cannot use a linked list, for example). And again... the purpose of the rule (to not mess with the contents of a collection from within a foreach loop) is that I shouldn't have to spend time thinking about this when building an enumerator...
Any clearer?
Peter the small turnip
(1) It Has To Work. --RFC 1925[^]
|
|
|
|
|
Hello everyone,
I have not found any support document about whether the operation of reference variable assignment is atomic or not.
For example, foo1 and foo2 are both reference variable of type Foo. Is foo1 = foo2 atomic? Any support documents?
thanks in advance,
George
|
|
|
|
|
Yes, assigning a reference is an atomic operation.
ECMA-334 C# Language Specification:
"12.5 Atomicity of variable references
Reads and writes of the following data types shall be atomic: bool, char, byte, sbyte, short, ushort, uint, int, float, and reference types. In addition, reads and writes of enum types with an underlying type in the previous list shall also be atomic. Reads and writes of other types, including long, ulong, double, and decimal, as well as user-defined types, need not be atomic. Aside from the library functions designed for that purpose, there is no guarantee of atomic read-modify-write, such as in the case of increment or decrement."
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Great Guffa!
Question answered.
regards,
George
|
|
|
|
|
Guffa wrote: Yes, assigning a reference is an atomic operation.
DANGER WILL ROBINSON! DANGER WILL ROBINSON!
An assignment of a reference type consists of an atomic read followed by an atomic write. The assignment as a whole is not atomic.
Assume var2 starts == 1.
Thread 1:
var1 = var2;
Thread2:
var2 = 2;
var1 = 3; If assignments were atomic, var1 might end up equal to 2 or 3, but it could not possibly end up equal to anything else (such as 1). Since they are not atomic, however, thead 1 decomposes as "temp = var2; var1 = temp;". The operations could thus be sequenced as "temp = var2 [1]; var2 = 2; var1 = 3; var1 = temp [1];"
It would be possible to write a generic class to support true atomic assignments. Given the existence of Interlocked.CompareExchange it could even be done without locks or spin-waits(*) in such a way that the total time required for any number of operations would be bounded (the time required for any particular operation would only be bounded if the number of other operations was limited).
(*) A thread may have to retry an operation up to 'n' times if other threads perform 'n' operations during its execution; it is never necessary, however, for a thread to wait for another thread to do something.
I don't know if there are any nice algorithms to synthesize atomic assignment given atomic compare-and-exchange. The best lock-free approach I can come up with is pretty nasty, but it would work.
|
|
|
|
|
supercat9 wrote: An assignment of a reference type consists of an atomic read followed by an atomic write.
No, it doesn't. An assignment is only a write operation.
What you are talking about is a complete statement, which in this case is the evaluation of an expression and the assignment of the result. The complete statement is of course not an atomic operation.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Guffa wrote: No, it doesn't. An assignment is only a write operation.
The original question was Is foo1 = foo2 atomic?. You answered in the affirmative, without giving any indication that "foo1 = foo2" represents two operations.
Guffa wrote: The complete statement is of course not an atomic operation.
Whether the complete statement is atomic or not depends on the implementation. Some microprocessors and microcontrollers do allow atomic memory-to-memory moves, at least in non-paged implementations (the 68020-68040 even allow it in paged implementations, though I doubt any compiler would use the CAS2 instruction for a normal assignment). Your statement could reasonably have been taken to suggest that the processors that run Windows will perform a statement like "foo1 = foo2" atomically. I think it's very important to point out clearly and unambiguously that they will not.
|
|
|
|
|
As an addition to what Guffa said if you take for example:
Foo foo = new Foo();
you should know that first the right side of the assignment is evaluated. So that first the Foo object is constructed entirely and then assigned to foo. So this is also an atomic operation.
|
|
|
|
|
Great Zoltan!
Question answered.
regards,
George
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
