CODEWITHSUNDEEP
c#performancecollectionsdictionary
nawfal
nawfal

Reputation: 73253

Collection that lets access item by key but doesn't require duplicate checking on addition?

I'm asking for something that's a bit weird, but here is my requirement (which is all a bit computation intensive, which I couldn't find anywhere so far)..

I need a collection of <TKey, TValue> of about 30 items. But the collection is used in massively nested foreach loops that would iterate possibly almost up to a billion times, seriously. The operations on collection are trivial, something that would look like:

 Dictionary<Position, Value> _cells = new 


_cells.Clear();
_cells.Add(Position.p1, v1);
_cells.Add(Position.p2, v2);
//etc

In short, nothing more than addition of about 30 items and clearing of the collection. Also the values will be read from somewhere else at some point. I need this reading/retrieval by the key. So I need something along the lines of a Dictionary. Now since I'm trying to squeeze out every ounce from the CPU, I'm looking for some micro-optimizations as well. For one, I do not require the collection to check if a duplicate already exists while adding (this typically makes dictionary slower when compared to a List<T> for addition). I know I wont be passing duplicates as keys.

Since Add method would do some checks, I tried this instead:

_cells[Position.p1] = v1; 
_cells[Position.p2] = v2;
//etc

But this is still about 200 ms seconds slower for about 10k iterations than a typical List<T> implementation like this:

List<KeyValuePair<Position, Value>> _cells = new 


_cells.Add(new KeyValuePair<Position, Value>(Position.p1, v1));
_cells.Add(new KeyValuePair<Position, Value>(Position.p2, v2));
//etc

Now that could scale to a noticeable time after full iteration. Note that in the above case I have read item from list by index (which was ok for testing purposes). The problem with a regular List<T> for us are many, the main reason being not being able to access an item by key.

My question in short are:

  1. Is there a custom collection class that would let access item by key, yet bypass the duplicate checking while adding? Any 3rd party open source collection would do.

  2. Or else please point me to a good starter as to how to implement my custom collection class from IDictionary<TKey, TValue> interface

Update:

I went by MiMo's suggestion and List was still faster. Perhaps it has got to do with overhead of creating the dictionary.

Upvotes: 0

Views: 121

Answers (2)

MiMo
MiMo

Reputation: 11983

My suggestion would be to start with the source code of Dictionary<TKey, TValue> and change it to optimize for you specific situation.

You don't have to support removal of individual key/value pairs, this might help simplifying the code. There apppear to be also some check on the validity of keys etc. that you could get rid of.

Upvotes: 2

Jon Skeet
Jon Skeet

Reputation: 1502985

But this is still a few ms seconds slower for about ten iterations than a typical List implementation like this

A few milliseconds slower for ten iterations of adding just 30 values? I don't believe that. Adding just a few values should take microscopic amounts of time, unless your hashing/equality routines are very slow. (That can be a real problem. I've seen code improved massively by tweaking the key choice to be something that's hashed quickly.)

If it's really taking milliseconds longer, I'd urge you to check your diagnostics.

But it's not surprising that it's slower in general: it's doing more work. For a list, it just needs to check whether or not it needs to grow the buffer, then write to an array element, and increment the size. That's it. No hashing, no computation of the right bucket.

Is there a custom collection class that would let access item by key, yet bypass the duplicate checking while adding?

No. The very work you're trying to avoid is what makes it quick to access by key later.

When do you need to perform a lookup by key, however? Do you often use collections without ever looking up a key? How big is the collection by the time you perform a key lookup?

Perhaps you should build a list of key/value pairs, and only convert it into a dictionary when you've finished writing and are ready to start looking up.

Upvotes: 2

Related Questions