3

I need to modify all of the values in a Dictionary. Typically, modifying a Dictionary while enumerating it throws an exception. There are various ways to work around that, but all of the answers I've seen involve allocating temporary storage. See Editing dictionary values in a foreach loop for an example.

I would like to modify all the values without allocating any memory. Writing a custom struct enumerator the for the values that disregarded the dictionary version would be fine, but since all the important members of the dictionary are private, this seems impossible.

Community
  • 1
  • 1
Zachary Burns
  • 453
  • 2
  • 9
  • Any reason you don't want to use `ConcurrentDictionary`? Is your issue really the Exception for concurrent access or memory allocation? – Ian Mercer Dec 20 '16 at 20:22
  • 1
    The link you provided seems to indicate that calling Keys.ToList() on the dictionary and iterating over that list should work... No? – Chris Berger Dec 20 '16 at 20:23
  • 1
    @IanMercer: Although the question is very unclear. I believe the exception the OP is referring to is the one for modifying a collection while iterating it. It's not an issue with concurrent access. – Matt Burland Dec 20 '16 at 20:24
  • I guess maybe calling Keys.ToList() would count as allocating memory? If so, then I'm afraid the best solution might be to implement IDictionary on a custom class. – Chris Berger Dec 20 '16 at 20:26
  • I can think of a few possible approaches you might take, but they all have performance and behavior trade-offs. Do you understand why a Dictionary throws exceptions if it's modified while it's being iterated? Can you share how you would like it to behave if someone tries to iterate it and modify it at the same time? Why are you not willing to allocate more memory? Is concurrency an issue, or is this single-threaded? What's the specific use case you're trying to achieve? – StriplingWarrior Dec 20 '16 at 20:30
  • @IanMercer I am not using ConcurrentDictionary because elsewhere in the program I am locking access to this dictionary. Furthermore, I don't see how ConcurrentDictionary will allow me to modify all the values in the dictionary without allocation – Zachary Burns Dec 20 '16 at 20:33
  • @ChrisBerger Yes, that would work... but would allocate memory which is not sufficient for the performance constraints I have. – Zachary Burns Dec 20 '16 at 20:34
  • @StriplingWarrior Yes, I understand why it is implemented the way it is. Though, in the case where no resize is necessary I believe that the version increment for modifying an existing key is for consistency with the add+resize case. Access to this Dictionary is protected by a ReaderWriterLockSlim, so it's single threaded insofar as I'm concerned. – Zachary Burns Dec 20 '16 at 20:38
  • @ChrisBerger Also, FYI if you iterate over any implementation of IDictionary C# is forced to box the enumerator resulting in unwanted allocation (though admittedly that's much less allocation then a list copy of the keys). I agree with your general idea of implementing something *like* IDictionary though. – Zachary Burns Dec 20 '16 at 20:44
  • I'm not sure why the downvote. Can someone suggest an edit that would make the question more clear? – Zachary Burns Dec 20 '16 at 20:45
  • `dictionary[key] = new_value;` with `for` loop should do the trick. the indexer will create new entry if key does not exist other wise it updates the value referenced from entry. – M.kazem Akhgary Dec 20 '16 at 20:54
  • @M.kazemAkhgary: You'd have to show an example. What exactly is your `for` loop going to look like? I don't see how that can work without first allocating a separate list or array for the keys. – Jim Mischel Dec 20 '16 at 21:08
  • 1
    If the values are classes, you can modify them to your heart's content without modifying the dictionary at all. – Jeroen Mostert Dec 20 '16 at 21:11
  • 2
    @ZacharyBurns: I didn't down-vote, but I think if you were to add a small code sample to show an example of the kind of modification-during-iteration that you're trying to make, it would help a lot of people out. – StriplingWarrior Dec 20 '16 at 21:11
  • @JeroenMostert: I'm guessing if he's not willing to allocate space for all the dictionary keys, then he'd probably have a similar memory overhead issue with adding an object layer like that. – StriplingWarrior Dec 20 '16 at 21:12
  • @StriplingWarrior: my comment was a subtle nod to think outside the boxing. (Sorry, couldn't resist that one.) – Jeroen Mostert Dec 20 '16 at 21:18

1 Answers1

4

You're definitely getting into some nitty-gritty performance optimization here.

Based on the additional information you've given in the comments, it sounds like the best approach (short of upgrading your memory so you can handle a little more allocation) will probably be to take the Dictionary source code and make a new class specifically for this purpose, which doesn't increment the version field if it's only changing a value.

StriplingWarrior
  • 151,543
  • 27
  • 246
  • 315
  • I was afraid of that conclusion. You should probably update the link though to point to the .Net Core implementation, rather than reference source for licensing reasons. MIT License would allow modification if you follow some rules, whereas the MS-RSL license does not allow for hardly anything except 'referencing' the source. – Zachary Burns Dec 21 '16 at 14:35
  • In the end, this route worked out quite well. I ended up with a dictionary that you can iterate and replace values while iterating, or even delete keys while iterating as well. – Zachary Burns Dec 22 '16 at 15:33
  • I'm glad it worked out. I do *not* recommend deleting keys during iteration, though, because you could end up skipping over items if they happen to be placed in the same bucket as the one you delete. – StriplingWarrior Dec 22 '16 at 16:10
  • 1
    In this case deleting keys while iterating is ok. The new class only allows you to replace values or delete keys through the KeyValuePair, ensuring you are deleting the current item you are on. The way that the reference source Dictionary iteration works is that it doesn't iterate over the buckets, but instead it simply iterates the entries array. When deleting an item it zeroes out one entry from that array then heals the linked list from the bucket, so this does not become a problem. – Zachary Burns Dec 26 '16 at 14:02