Несколько произвольно возникших мыслей после беглого просмотра кода
— в Shrink избавиться от OrderBy, заменить на TopN
— нет ли случаем race condition между Shrink & TryGet, они симметричные проверки выполняют в разном порядке
— прочесть книгу Joe Duffy «Concurrent programming on Windows»
— interlocked операции могут воевать за кэш-линии процессора, зависит от того как у вас заполняется память
— попробуйте отделить процесс вычисления новых состояний пользователей от непосредственно применения их, имею в виду вычисление пусть происходит в многих потоках, но применение/обновление кэша — в одном, через очередь команд.
Несколько мыслей, возникших во вторую очередь
— у вас скорее всего основные тормоза приходятся не на бизнес-логику, а на garbage collector. Поставьте себе цель свести аллокацию в ноль или около нуля, кроме того избегайте хранения ссылок в словарях и временных переменных. Вместо ссылок храните индексы или числовые идентификаторы. Здесь дело в том, что garbage collector может тратить очень много времени и без всякой аллокации, просто на перетасовку метаданных из-за ваших копирований ссылок туда-сюда
— если в словаре много (больше миллиона) записей, прикрутить Intel TBB — их коллекции намного эффективнее. Я от ConcurrentDictionary в своё время был вынужден отказаться в пользу native-кода
По поводу TopN — не сортировать всё содержимое словаря, а выбрать первые N отсортированных ключей, которые вам собственно и нужны для удаления. Например здесь: stackoverflow.com/... from-an-array-of-length-n или здесь stevehanov.ca/blog/index.php?id=122
Намного дешевле, хотя вы его видимо запускаете редко, так что смысла нет.