Fastest way to add and extract items from a 2 level KeyValuePair in FIFO configuration

Question

I'm working on creating a List which has the following structure

Item 1
  Key:Value
  Key:Value
  Key:Value
  ... (between 100 to 1000 pairs)
Item 2
  Key:Value
  Key:Value
  Key:Value
  ... (between 10 to 1000 pairs)
Item 3
... (upto about 300,000 items)

I started by using the following

Dictionary<string, SortedList<string, string>>

The problem was after adding about 10,000 items it started slowing down exponentially.

Then I moved to List<Tuple<string, SortedList<string, string>>>

This worked upto about 20,000 entries and then started slowing down, by 40,000 items it was exponentially slow

I'm trying to figure out what's the fastest way to add create a list of the items structure I pointed out above.

I'm only want to preserve order insertion, I'm only looking at inserting and reading back the data in FIFO order. No modifications to any data elements once inserted.

Given the simple FIFO needs would be the fastest way to store and retrieve the data?

I can't find any definitive comparisons between List, Dictionary, Sorted List, Tuple etc for FIFO. Or is there some other Class I should be using?

I can change the way the data is accessed, i.e. dictionary not required, the ONLY requirement is sequential insertion and reading back (FIFO) for all items AND KeyValue pairs

UPDATE: Here is the outline of the code

I also tried a Queue<KeyValuePair<string, Dictionary<string, string>>> but again it slowed down after inserting about 25,000 items.

CREATING THE LIST:

Dictionary<string, Dictionary<string, string>> retVal = new Dictionary<string, Dictionary<string, string>>();
List<string> fileNames = GetNames();
foreach (string filePath in fileNames)
{
    Dictionary<string, string> entries = GetKeyValuePairs(filePath);
    if (!retVal.ContainsKey(filePath))
        retVal.Add(filePath, entries);
}

return retVal

READING BACK:

foreach (string filePath in retVal)
{
    Dictionary<string, string> entries = retVal[filePath];
    foreach (string key in entries.Keys)
    { ... }
}

How you are retrieving it by item as a key or by item as key than key as second index — BRAHIM Kamel, Jul 20 '17 at 20:59
Updated the question showing the code outline of how it's created and read back. I can change the way the data is accessed, i.e. dictionary not required, the ONLY requirement is sequential insertion and reading back (FIFO) for all items AND KeyValue pairs — rboy, Jul 20 '17 at 21:11
@DStanley are you saying that Queue is the fastest data structure to use for my requirements? Should I be using a KeyValuePair with the queue? I have two levels of KeyValuePairs. You marked the question as duplicate but it doesn't answer my question. What's the fastest way to access a 2 level KeyValuePair in FIFO configuration? — rboy, Jul 20 '17 at 21:15
@DStanley, a Queue and what? It's 2 levels of keys and pairs. Should I use a SortedList with a Queue, a Dictionary with a Queue or a KeyValue pair or a Queue within the Queue? Fastest is very objective, I've provided the needs quite clearly. Sequential inserting and reading back of 2 levels of keys/values. No searching, no reordering nothing else. — rboy, Jul 20 '17 at 21:21
Okay tried that, it's showing down exponentially after 25000 entries, just like List or Sorted List or Dictionary. The adding to the queue/dictionary etc is slowing down, the retrieval is pretty fast. — rboy, Jul 20 '17 at 21:31
Since you've marked this a duplicate (which it isn't, I can't have folks answer it). Anyways here's some data I found but hopefully someone has insight into multi level KeyValuePairs. http://blog.bodurov.com/Performance-SortedList-SortedDictionary-Dictionary-Hashtable/ — rboy, Jul 20 '17 at 21:34
@DStanley I think you should reopen the question isn't a duplicate it's exposing a different issue I have voted to reopen it — BRAHIM Kamel, Jul 20 '17 at 21:38
the best way to know what is the best approach to use for this is to try a different ways and then measure them using a framework like the Benchmark.net — BRAHIM Kamel, Jul 20 '17 at 21:54
@rboy You didn't tell which exact part is slowing down exponentially. Neither of the *shown* parts should be slow, I suspect the `GetKeyValuePairs` is the culprit, could you show it? And please note that neither hash not order based dictionary data structures are FIFO. — Ivan Stoev, Jul 21 '17 at 09:38
I don't think the GetKeyValuePair is slowing it down. For the purposes of test it contains only 5 pairs for each iteration. For the main loop it adds 10,000 items in about 10 seconds and then taken another 20 seconds for the next 10,000 and takes almost 2 minutes minute for the next 20,000. Same things on the reading back it takes almost 2 minutes to read back all the values. I did find that using Queue for the main outer loop is faster than Dictionary by almost 30%. But between SortedLoop and Dictionary I didn't find much difference. — rboy, Jul 21 '17 at 11:19
Sorry, but this more and more sounds like XY problem. Adding 10K items cannot take 10 seconds. Take the code snippet from https://pastebin.com/gYbCpnV1, paste it into a new console project and run it. Adding 20K items takes less than second. Apparently you have an issue, but we can't help w/o [mcve]. — Ivan Stoev, Jul 21 '17 at 19:22

Fastest way to add and extract items from a 2 level KeyValuePair in FIFO configuration

0 Answers0