Кэши

[ANDLL]

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

Итак, первым рассмотрим TimedCache

• Смысл. Часто в коде можно найти чтото вроде
  a=Func(b)
  Здесь мы вычисляем значение функции по указанному аргументу.
  Иногда нас может интересовать не вычислять результат каждый раз, а хранить его в некотором буфере. То есть вид функции должен иметь вид
  
  

  a=Buffer(b)
  Buffer(b):
    if(time_of_b(b)>XXX OR arr[b] is null)
      arr[b]=Func(b)
    return arr[b]
  (Не пугайтесь - это псевдокод, его мы будем постоянно использовать, в сущености ничего страшного в нем нет)
  Иными словами, наш кэш будет вычислять значение функции только в двух случаях
  • если она еще не вычисляла значение функции от этого аргумента
  • если она вычисляла значение функции от этого аргумента больше чем XXX минут(милисекунд\секунд\часов) назад
• Код
  
  

  using System;
  using System.Collections.Generic;
   
  namespace DANAsoft.Tools
  {
      public class TimedCahce<Key,Value>
      {
          TimeSpan timeOut;
          Function func;
          Dictionary<Key, Entry> dictionary=new Dictionary<Key, Entry>();
          Object lck = new Object();
   
          public TimedCahce(TimeSpan _timeout,Function f)
          {
              if (_timeout == null)
                  throw new ArgumentNullException("_timeout");
              if (f == null)
                  throw new ArgumentNullException("f");
              timeOut = _timeout;
              func = f;
          }
   
          public Value GetValue(Key x)
          {
              lock (lck)
              {
                  Entry v;
                  if (dictionary.TryGetValue(x, out v))
                      if ((DateTime.Now - v.time) < timeOut)
                          return v.value;
                  v = new Entry(DateTime.Now, func(x));
                  dictionary[x] = v;
                  return v.value;
              }
          }
   
          private class Entry
          {
              public DateTime time;
              public Value value;
   
              public Entry(DateTime s, Value t)
              {
                  time = s;
                  value = t;
              }
          }
   
          public delegate Value Function(Key k);
      }
  }
• Класс имеет два generic-параметра - тип аргумента и тип значения.
  Конструктор класса принимает два аргумента - время, через которое содержимое кэша считается неактуальным и должно обновлятся и функцию, которая по аргументу будет вычислять значение.
• Когда применять этот вид кэша?
  Тогда, когда память на вычисление объекта существенно больше чем память, которую может занимать кэш. Когда время на вычисление значения функции больше чем время на поиск в списке по ключу. Или когда функция обращается к внешнему объекту, имеющему существенное ограничение на возможное число вызовов в промежуток времени.
  Например - вам нужно хранить exhange rate двух произвольных валют, при этом сама валюта задается своим кодом.
  Что бы получить эту маленькую цифру нужно выполнить запрос к внешнему web-серверу(скажем к цбрф). Помимо того что это просто долго, есть еще ряд минусов, например сервер может вести лог запросов и автоматически отключить доступ, если число последних слишком велико. Это нормальная практика.
  В данной ситуации уместно использовать кэш вида
  
  

  TimedCahce<<KeyValuePair<string,string>,double> l;
  Соответсвенно в конструктор логично передавать параметры
  
  

  l=new TimedCahce<...>(new TimeSpan(1, 0, 0),Func)
  
  Где Func будет принимать в качестве параметра коды двух валют, вызывать web-сервис и прочее.
• Когда этот вид кэша не нужно применять?
  Во первых в тех случаях, когда число теоретическивозможных аргументов велико.
  Обратите внимание - кэш никогда не очищается. Это вполне логично в огромном количистве случаев - действительно, часто можно потратить n байт оперативной памяти в замен m милисекунд работы кода.
  Однако, в огромном количистве случаев это также и не логично.
  Если скажем Func() это числовая функция, которая скажем считает интеграл, или решает диффур, долгими итерационными методами, то, использовать здесь этот кэш нельзя. Просто потому что при достаточно долгом времени выполнении программы(а для серверных программ это актуально в n раз), число потребляемой ей памяти может вырасти до катострафических размеров.

По мере времени список будет пополнятся другими видами кэшев, с описанием и прочим. Enjoy

[Alexus]

Цитата ANDLL @ 18.02.08, 17:39

число потребляемой ей памяти может вырасти до катострафических размеров.

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

Ещё чисто-дотнетовская фича: в кеше (точнее, в Entry) хранить WeakReference.
Тоесть весь кэш будет подлежать сбору мусора. Тоесть, если нужна память - clr сама будет чистить кэш. (да, тоже минусы есть. опять же можно усложнить...)
Метод применим только если размер одной строки в словаре dictionary значительно меньше чем размер объекта типа Value

[GRIENDERS]

Я давно хотел спросить: а каков объем кэша?
Сколько данных в него можно запихнуть, чтобы было не в ущерб производительности (по аналогии с сессией)?

[Alexus]

Цитата GRIENDERS @ 19.02.08, 05:53

Сколько данных в него можно запихнуть, чтобы было не в ущерб производительности (по аналогии с сессией)?

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

Цитата ANDLL @ 18.02.08, 17:39

функция обращается к внешнему объекту, имеющему существенное ограничение на возможное число вызовов в промежуток времени.

Если есть ограничение на память - то нужно урезать кэш даже если выбирать из него значительно эффективнее чем получать.