title: Removing items from a dictionary after a timeout in a CPU friendly way
body: <p>I have a usecase, in which I need to remove items from a dictionary either when a certain number of items are reached (so, like half of the oldest items in the dictionary will be removed), or when items have stayed in dictionary for lets say 10 seconds.</p>
  <p>New items are continuously added to the dictionary, and the reason why I am using a <code>ConcurrentDictionary</code> here is to have as much distinct set of items while also streaming.</p>
  <p>I have already accomplished this by using a setup like <code>ConcurrentDictionary&lt;string, (Message, DateTime)&gt;</code> where I am using message's key (which is like a small json with max 3 fields) as the key for dictionary and the message and the time stored as a tuple as the value for dictionary. I can now use the key to check for duplicates, have a spillover scenario which I handle like (not the actual code, writing this by memory)</p>
  <pre class="lang-cs prettyprint-override"><code>foreach (var item in dictionary.OrderByDescending(kvp =&gt; kvp.Value.Item2).Take(Threshold / 2))
  {
      dictionary.TryRemove(kvp.Key, out var _);
      // add to output queue
  }
  </code></pre>
  <p>and I check the old items by having a code like</p>
  <pre class="lang-cs prettyprint-override"><code>foreach (var kvpin dictionary)
  {
      if (DateTime.UtcNow.Subtract(kvp.Value.Item2) &gt;= TimeSpan.FromSeconds(10))
      {
          dictionary.TryRemove(distinctMessageKVP.Key, out var _)
          // do something with the removed item
      }
  }
  </code></pre>
  <p>And this works. Problem is, this is VERY CPU intensive. I plan to reduce CPU usage by switching to single thread dictionary access and using dictionary instead of concurrent dictionary. Then I also plan to increase the threshold, so we don't keep transferring items and wasting cycles there. I also suspect iterating through all the items for removing items from dictionary is an expensive process. If that's the case, is there any other way I can remove items from the dictionary? Is there any other data structure I can use which will help me solve the issue?</p>
  <p>EDIT : Right now, we have 5 tasks writing into the <code>ConcurrentDictionary</code>, and 1 task removing stuff from dictionary. If it's a better setup (to avoid locks), I will have the 5 tasks write into a <code>ConcurrentQueue</code>, then 1 task into <code>Dictionary</code> (not concurrent) and the same task to depopulate the dictionary as well.</p>
  <p>EDIT2 : We are looking at something like 1000 items going in and out of the dictionary per second.</p>