List<object> performance

Few days ago run into requirement to store about 500.000 objects in the List<object>. To store that amount of data in the list is not an issue.

list.Find(item => item.Arg1 == arg1 && item.Arg2== arg2 && item.Arg3 ==arg3 && item.arg4 == arg4);

While reading the line above, try to ask yourself, how much time your application will need to find a specific element defined by scalars { arg1, arg2, arg3, arg4 }?

To measure this I performed two different kind of calculations on processor: x64 Family 6 Model 15 Stepping 10 GenuineIntel ~2400 Mhz

First calculation one was the very simple average value, which resulted in 12 milliseconds. I learned at the university that the time is relative. I agree, but in information technology I experienced that the time is subjective too. So, 12 ms is pretty fast for half million of entries.

However if you search for entries in the list which are on the beginning of the list you will notice that the processor performs much better. Your program will not need even one second to lookup entries  on the beginning of the list. Unfortunately, to lookup entries on the end of the list the program will need about 30 milliseconds.

So I decided to calculate average time depending on the position in the list. For this experiment, I linearly sampled 10000 entries from the list of 500000 entries. The I created a kind of window of 100 samples and moved it over to whole interval. The result was average time for first 100 entries, then second hundred entries etc.

Here is the diagram which shows results for all interval:

 

Conclusion:
Without of performing exact analytical result, statistically it seems that the calculation time for looking up entries in the list linearly increases by moving to the end of the list. On the beginning of the list you can expect that looking up takes less than 1 ms. By entries on the position over 400.000 the time for looking is takes 25-30 ms. This is just to give you a feeling.