На работе в программе часто создаются строки. При большой нагрузке - сотни тысяч в секунду. Основной источник - десериализация входящих сообщений. Несколько программ обмениваются сообщениями, в сообщениях есть текстовые идентификаторы. С одними и теми же идентификаторами бегают до нескольких десятков сообщений. Короче, не все создаваемые строки уникальны, много раз содаётся строка с одним и тем же содержимым. Возникает желание кэшировать строки для повторного использования. Перед созданием новой строки сначала поискать аналогичную в кэше и, если она там есть, вернуть указатель на неё.

Возникает проблема какой размер выбрать для кэша и как его чистить.

Сначала я сделал сложный кэш фиксированного размера в виде хэштаблицы и "приоритетного" списка. Когда строка находилась в хэштаблице она перемещалась в начало "приоритетного" списка. Если строка по хэштаблице не находилась и фиксированный размер был достигнут, то из кэша удалялась строка стоящая в хвосте "приоритетного" списка, а новая строка добавлялась.

Преимущества:
1) Часто используемые строки останутся в таком кэше практически навсегда, а редкоиспользуемые будут удаляться при достижении фиксированного размера.

Недостатки:
1) При больших нагрузках какой бы разумный предел на размер кэша я ни ставил его всё равно оказывалось мало. Но когда размер кэша мал, то смысла в нём почти нет, зато есть вред (тратить время на поиск, тратить память на хранение).

2) Когда какая-то строчка используется в последний раз, то она тоже ставится в голову приоритетного списка и далее лежит мертвым грузом в памяти до тех пор пока не дотащится до самого конца приоритетного списка.

В конце концов пришлось признать, что недостатки перевешивают и лучше вообще без кэша чем с таким.

* * *

Тогда я изобрёл другой строковый кэш.

Я использовал "одноячеистую" хештаблицу. То есть взял большой массив указателей на строки. Когда нужно создать из массива байтов строчку, я просто вычисляю её хэшкод и по нему индексируюсь в этом массиве. Если в нём по этому индексу уже есть указатель на строку с тем же самым содержимым, то возвращаю этот указатель. Если там нуль или же указатель на другую строку, то создаю новую строчку с нужным содержимым и помещаю указатель на неё в эту ячейку массива затирая предыдущий указатель. Обратите внимание, что это можно делать из нескольких потоков одновременно, то есть никаких блокировок делать не нужно (для операций с приоритетным списком блокировка была необходима).

Если такой кэш никогда не чистить, то он растёт (в байтах занимаемой памяти) асимптотически до некоторого максимума, затем рост останавливается (новые строки замещают старые, старые удаляются сборщиком мусора).

Чтобы одноячеистый кэш был эффективен размер массива надо брать как можно больше. Фактически у меня он равен примерно десяти миллионам (точнее NextPrime[10*1024*1024] = 10485767 штук). При среднем размере строки в 100 байт при полном заполнении будет израсходовано примерно один гигабайт памяти. Гигабайт памяти на кэширование текста жалко. Поэтому чистить надо. Кроме того, хочется, чтобы при уменьшении нагрузки программа уменьшала и расход памяти, а при полном отсутствии нагрузки, чтобы опустошала кэш полностью.

Возникает противоречие. С одной стороны кэш чистить нельзя, а то будет медленно работать и смысла в нём не будет. И кэш чистить нужно, а то он много памяти израсходует.

Решение есть. Просто один раз в минуту я обнуляю десять процентов ячеек. Для этого последовательно по кругу ездит обнуляющий "каток". Один раз в минуту он прокатывается вперёд на 10% от размера массива. Указатели на строки в ячейках лежат случано (хэш всё таки), так что удаляются случайные строки.

Выгоды:
1) Работает "со скоростью света" да ещё и без блокировок (многопоточность).
2) При кратковременных высоких нагрузках размер кэша может (и должен) быть очень большой (у меня до гигабайта).
3) При уменьшении нагрузки кэш уменьшается. При полном отсутствии нагрузки кэш полностью обнуляется через десять минут.