четверг, 30 апреля 2009 г.

Вывод типов с помощью Fake функций

Рассмотрим один прием, помогающий выводить типы (на авторство не претендую) на примере мемоизации. В двух словах, если кто не вкурсе, мемоизация – это техника оптимизации (подвид кэширования), используемая для избежания вызовов функций с повторяющимися аргументами. Множество примеров реализации мемоизации на C# можно найти здесь. Оттолкнемся от мемоизации функции одного аргумента, описанного Wes Dyer-ом, одним из разработчиков компилятора C#.

public static Func<TKey, TResult> Memoize<TKey, TResult>(this Func<TKey, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var cache = new Dictionary<TKey, TResult>();
 TResult result;

 return key => (cache.TryGetValue(key, out result))
     ? result
     : (cache[key] = func(key));
}
Мой вариант отличается только тем, что я переменную result внес в замыкание вместо того, чтобы объявить ее внутри тела возвращаемой функции. Сделал я это только для того, чтобы не писать фигурные скобки в определении тела функции. Все красиво и наглядно, но допустим возникла необходимость мемоизации функции двух переменных.
Мемоизация функции двух аргументов
Решать можно по-разному. Например, модифицировать реализацию мемоизации функции одной переменной, т.е. фактически переписать ее заново:
public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var cache = new object[0].ToDictionary(
     x => new { k1 = default(T1), k2 = default(T2) },
     x => default(TResult));

 return (k1, k2) =>
 {
     TResult result;
     var key = new { k1, k2 };

     return (cache.TryGetValue(key, out result))
         ? result
         : (cache[key] = func(k1, k2));
 };
}
Здесь я воспользовался тем, что анонимный тип, который генерируется компилятором обладает всем необходимым для того, чтобы использовать его в качестве ключа словаря. Небольшая сложность заключалась в том, чтобы объявить переменную словаря с анонимным типом ключа, но выручил метод Enumerable.ToDictionary. Но душа захотела реюза описанного ранее метода мемоизации функции одного аргумента. Мне пока известно два способа сделать реюз:
  1. Применить последовательно мемоизацию к каждому аргументу, что привлечет к появлению множества экземпляров словарей (не интересно для дальнейшего обсуждения)
  2. Применить мемоизацию к методу, который принимает аргумент-комбинацию двух аргументов, а возвращает результат вызова метода func, полученный по соответствующей паре аргументов. Далее будем обсуждать метод этот вариант.
Итого, требуется применить мемоизацию к следующему методу (записанному условно):
Func<?, TResult> func2 = (? x) => func(x.t1, x.t2);
Проблема здесь в том, что комбинированный аргумент представлен анонимным типом, указать который проблематично. Стандартных Tuple-ов нет, да и неизвестно, будут ли они обладать теми же свойствами, что и анонимные типы, будет ли возможность использовать их в качестве ключа словаря?

Итого, есть метод с сигнатурой Func<?, TResult>, записать тело которого мы можем, но не можем сказать компилятору, что за тип кроется за знаком “?” (достаточно было бы указать тип хотя бы в одном из мест, отмеченных знаком “?” в определении анонимного метода).

Вот тут-то и выручит нас метод, который ничего не делает:
static Func<T, TResult> MakeFunc<T, TResult>(T _, Func<T, TResult> func)
{
 return func;
}
Метод MakeFunc абсолютно бесполезен во времени выполнения. Однако он помогает вывести тип “?”. Записать этот тип в коде мы все равно не сможем, но это и не требуется.

Вот как компилятор теперь может выявить тип метода: первым аргументом MakeFunc мы указываем экземпляр анонимного типа, а т.к. тип T первого аргумента совпадает с типом аргумента метода Func<T, TResult> второго аргумента метода MakeFunc, то компилятор теперь знает, что подразумевается под типом T в выражении Func<T, TResult>.

Теперь следующее выражение
var func2 = MakeFunc(
 new { A1 = default(T1), A2 = default(T2) },
 x => func(x.A1, x.A2));

в точности указывает компилятору, что func2 это метод, принимающий аргумент анонимного типа, и имеющий тело, которое возвращает TResult, обращаясь к оригинальному методу func, растаскивая анонимный тип на аргументы. Теперь к методу func2 можно применить мемоизацию:

public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var func2 = MakeFunc(
     new { A1 = default(T1), A2 = default(T2) },
     x => func(x.A1, x.A2));

 var func2m = func2.Memoize();

 return (t1, t2) => func2m(new { A1 = t1, A2 = t2 });
}
Здесь находится топик обсуждения мемоизации функции двух аргументов на RSDN (автор – я). Обратите внимание, как легко и изящно решается проблема на языке F#. Вышеописанный метод производит мемоизацию функции аргумента анонимного типа, затем возвращает метод, комбинирующий аргументы в анонимный тип, и передающий экземпляр анонимного типа в мемоизированную функцию.
Вообще говоря, я не думаю, что кому-то из читателей пригодится мемоизация функции двух и более аргументов… Пост немного о другом (как следует из его названия). Пост о том, как можно помочь компилятору вывести необходимый тип, в котором каким-то образом участвуют анонимные типы.
Потому еще один пример, где описанный мной прием может пригодитсья:
Вывод типа IEqualityComparer<?> для анонимного типа.
Преамбула проста: когда-то не так давно я решил, что если не заморачиваться на эффективности, то можно не писать классы компареров каждый раз, а создать адаптер, который бы принимал функции GetHashCode и Equals и представлял бы их экземпляром IEqualityComparer<T>. Выглядит это чудо так:
public static IEqualityComparer<T> CreateAdapter<T>(
 Func<T, T, bool> equals,
 Func<T, int> getHashCode)
{
 if (equals == null)
     throw new ArgumentNullException("equals");

 if (getHashCode == null)
     throw new ArgumentNullException("getHashCode");

 return new EqualityComparerAdapter<T>(equals, getHashCode);
}

class EqualityComparerAdapter<T> : IEqualityComparer<T>
{
 readonly Func<T, T, bool> _equals;
 readonly Func<T, int> _getHashCode;

 public EqualityComparerAdapter(Func<T, T, bool> equals, Func<T, int> getHashCode)
 {
     _equals = equals;
     _getHashCode = getHashCode;
 }

 public bool Equals(T x, T y)
 {
     return _equals(x, y);
 }

 public int GetHashCode(T obj)
 {
     return _getHashCode(obj);
 }
}
Между делом – довольно удобная штука, позволяющая экономить на описании класса, но не в случае когда тип T – анонимный. Вот такой вспомогательный метод
static IEqualityComparer<T> InferComparer<T>(
 T _,
 Func<T, T, bool> equals,
 Func<T, int> gethashCode)
{
 return CreateAdapter(equals, gethashCode);
}
позволяет вывести тип компарера для анонимного типа.
var pairComparer = InferComparer(
 pair,
 (x, y) => x.Key.SequenceEqual(y.Key),
 x => x.Key.Aggregate(0, (h, s) => h ^ s.GetHashCode()));
Эта конструкция создает IEqualityComparer для анонимного типа, свойство Key которого является коллекцией строк. Таким образом сравниваются экземпляры по совпадению коллекций строк, и хэшкод вычисляется по набору строк свойства Key анонимного типа. Далее этот компарер используется для построения словаря.

суббота, 11 апреля 2009 г.

Обобщение фундаментальных алгоритмов.

Иногда удивляюсь, насколько время меняет подходы к реализации и использованию фундаментальных алгоритмов, которым много лет!

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

Как решалась эта задача раньше (точнее как я ее решал в ВУЗ-е): брались классы-вершины и классы-ребра, и под них писался алгоритм. Я использовал алгоритм Дейкстры для случаев с неотрицательными весами (кстати, алгоритму 50 лет в этом году!). Естественно, что использование реализации алгоритма под конкретные типы невозможно для других типов вершин и ребер. О реюзе даже речи не идет.

Потом под веяниями ООП стали использовать абстрактные типы данных (вершин и ребер), либо их интерфейсы. Многие алгоритмы стало можно использовать многократно, стали появляться библиотеки для работы с теми же графами. ООП - хорошо, но что делать, если вершины моего графа - целые числа, либо классы, которые писал не я? Ну да, писать wrapper-адаптеры. Не всегда это удобно, требуется их кэшировать, чтобы не плодились, сравнивать, и т.д. Но у ООП найдется на все проблемы по решению.

Гораздо более гибким подходом было бы абстрагироваться не от типов данных (вершин и ребер), а от способа работы с ними. Это как Array.Sort(IComparer). В случае поиска на графах, плюс такого подхода еще и в том, что графы можно задавать как списками смежности, так и матрицами весов. Но для использования такого подхода все еще требуется реализация интерфейса, работающего с конкретными данными. Гибко, но не очень.

И тут приходят делегаты. Нет, не делегаты. Если рассматривать делегаты как аналог указателям на методы, то с приходом указателей на метод и делегатов в этом плане ничего не изменилось. А вот когда пришли (в .net) лексические замыкания в совокупности с анонимными методами, вот тогда, видимо, и наступил переломный момент. Наступил, но не все его заметили. Лямбда-выражения подлили масла в огонь, и теперь использовать обобщенные методы одно удовольствие (хотя сами лямбды в обобщении алгоритма участия не принимают):
var edjes = new[]
{
  new { s = 1, t = 2 },
  new { s = 2, t = 3 },
  new { s = 3, t = 4 },
  new { s = 4, t = 5 },
  new { s = 2, t = 4 },
  new { s = 2, t = 1 },
};

var pathes = Dijkstra.ComputePathes(
  1,
  v => edjes.Where(_ => _.s == v),
  (v, e) => e.t,
  e => 1);

CollectionAssert.AreEqual(
  new[] { new { s = 1, t = 2 } },
  pathes(2).ToArray());
Это фрагмент одного из тестов алгоритма нахождения кратчайших путей. Нетрудно заметить, что граф представлен набором направленных ребер-являющих собой переход от одной целой вершины к следующей. Первым аргументом задается исходная вершина, далее метод, возвращающий набор исходящих дуг для указанной вершины, далее функция перехода, которая по вершине и исходящей из нее дуге возвращает вершину, в которую ведет дуга. Последний аргумент - функция веса. Вполне можно было приписать к ребрам поле веса и возвращать его для каждого ребра. Обращаю внимание на то, что для использования алгоритма с конкретными (с дуба упавшими) типами данных практически ничего писать не пришлось!

Вот реализация алгоритма Дейкстры:
class Dijkstra
{
  public static Func<V, IEnumerable<E>> ComputePathes<V, E>(
      V s,
      Func<V, IEnumerable<E>> adjacentEdjes,
      Func<V, E, V> dest,
      Func<E, double> weight,
      IEqualityComparer<V> equalityComparer)
  {
      if (adjacentEdjes == null)
      {
          throw new ArgumentNullException("adjacentEdjes");
      }

      if (dest == null)
      {
          throw new ArgumentNullException("dest");
      }

      weight = weight ?? new Func<E, double>(_ => 1.0);
    
      equalityComparer = equalityComparer ?? EqualityComparer<V>.Default;

      var distancesFromS = new Dictionary<V, double>(equalityComparer) { { s, 0 } };

      // метод нахождения расстояния от указанной вершины до s.
      double tmp;
      Func<V, double> distanceFromS = v =>
          distancesFromS.TryGetValue(v, out tmp) ? tmp : double.PositiveInfinity;

      // запомненные пути (из какой вершины по какому ребру пришли в данную вершину).
      var sourceVertices = new[] { s }.ToDictionary(
          x => x,
          x => new { source = x, edje = default(E) },
          equalityComparer);

      // множество не вершин, кратчайший путь до которых не вычислен.
      var F = new HashSet<V> { s };

      while (F.Count > 0)
      {
          // Найти вершину с минимальным расстоянием от s
          var w = F.Aggregate(
              F.First(),
              (c, v) => distanceFromS(c) < distanceFromS(v) ? c : v);

          F.Remove(w);

          foreach (E e in adjacentEdjes(w))
          {
              V v = dest(w, e);
              double distanceToV = distanceFromS(w) + weight(e);
              if (distanceFromS(v) > distanceToV)
              {
                  // обновить расстояние.
                  distancesFromS[v] = distanceToV;
                  F.Add(v);
                  // запомнить откуда пришли.
                  sourceVertices[v] = new { source = w, edje = e };
              }
          }
      }

      // вернуть метод вычисления последовательности ребер.
      return x =>
      {
          var edges = new List<E>();

          while(sourceVertices.ContainsKey(x) && !equalityComparer.Equals(x, s))
          {
              var w = sourceVertices[x];
              edges.Add(w.edje);
              x = w.source;
          }

          edges.Reverse();
          return edges;
      };
  }
}
На удивление - это всего лишь один метод, который довольно хорошо коррелирует с псевдокодом по ссылке выше. Потому комментировать я его не буду за исключением нескольких моментов:

Первое - то что отличает алгоритм от псевдокода: набора вершин нет. Это специфика той задачи, которую я решал с помощью алгоритма Дейкстры. В той задаче число вершин определяется комбинаторными законами, в то время как число допустимых переходов весьма ограничено. Потому вводить все вершины в алгоритм смысла нет. Алгоритм довольствуется только исходной вершиной и достижимыми из нее.

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

Третье - алгоритм вычисляет кратчайшие пути до всех достижимых вершин графа. Возвращать единственный путь не целесообразно, т.к. в этом случае для вычисления путей до нескольких вершин придется запускать поиск многократно. Вместо кратчайшего пути до указанной вершины алгоритм возвращает метод, который строит кратчайший путь до указанной методу вершины с помощью накопленной во время поиска информации о переходах. Еще кое-что: код
double tmp;
Func<V,double> distanceFromS = v =>
    distancesFromS.TryGetValue(v, out tmp) ? tmp : double.PositiveInfinity;
содержит потенциальный баг. А именно, переменная tmp должна быть объявлена внутри анонимного метода! Я же использовал замыкание переменной tmp только для того, чтобы сэкономить на фигурных скобках и ключевом слове return, которые пришлось бы добавить, помести я переменную в тело метода. Полагаю, что этот код не будет распараллеливаться.

Вернемся к обсуждению прелестей обобщенных реализаций алгоритмов.
  • Отсутствие каких либо ограничений на типы данных позволяет оперировать вершинами V и ребрами E, ничего не требуя от них. Это здорово! Вершинами может быть все: числа, строки, сайты, города... Это позволяет тестировать реализацию алгоритма на элементарных типах данных. Задача, под которую я писал эту реализацию, обладает довольно сложновообразимыми типами данных. Тесты алгоритма на этих типах очень непрозрачны и нелаконичны. Обобщение позволило мне писать простые и понятные тесты (часть теста в начале поста). В качестве бонуса для себя я получил возможность реюза этого алгоритма тут же не отходя от кассы, при решении сопутствующей задачи анализа возможностей переходов по ребрам из первой задачи. Во втором случае не требовался кратчайший путь, достаточно было лишь установления факта существования пути на других типах данных, но писать специальный алгоритм для решения этой задачи стимула небыло.
  • Отсутствие ограничений на типы позволило так же сконцентрироваться именно на реализации фундаментального алгоритма, а не на его поведении в рамках конкретной системы. Создание вершин, перебор ребер-переходов, вычисление весов - все это осталось за бортом. Реализация алгоритма приобрела вид, очень близкий к псевдокоду на википедии. Если кому-то придется поддерживать этот алгоритм, он без труда это сделает, даже не вникая в задачу, в рамках которой используется этот алгоритм.
  • Задание управляющих методов делегатами позволяет гибко настраивать работу алгоритма, позволяет использовать преимущества лексических замыканий при обращении к алгоритму (делегаты тут и не причем, я хотел сказать функциональные типы, но в C# за них делегаты).
  • Анонимные типы и лексические замыкания позволили вернуть накопленные в ходе расчета данные в удобном для использования виде. Не потребовалось описывать дополнительные типы для хранения результатов счета.
P.S. И кто сказал, что библиотеки для работы с графами должны быть Объектно-Ориентированными?

пятница, 10 апреля 2009 г.

Comparer с обобщенными методами

Последнее время часто использую методы с обобщенными аргументами. Довольно часто приходится сравнивать значения обобщенных типов между собой, сравнивать с default(T). Конструкции типа
while (!EqualityComparer<T>.Default.Equals(t, default(t))
{
    // do something
}
довольно сильно утомляют глаз. Следующий класс здорово облегчает жизнь:
public static class Comparer
{
    public static int Compare<T>(T a, T b)
    {
        return Comparer<T>.Default.Compare(a, b);
    }

    public static bool Equals<T>(T a, T b)
    {
        return EqualityComparer<T>.Default.Equals(a, b);
    }

    public static bool IsNullOrDefault<T>(T value)
    {
        return Equals(default(T), value);
    }
}
Теперь можно писать так:
while (!Comparer.Equals(t, default(t))
{
    // do something
}
И даже так:
while (!Comparer.IsNullOrDefault(t))
{
    // do something
}
Естественно, это имеет смысл только для сравнения компарером по-умолчанию.

Хранилище записей фиксированной длины (часть IV)

Хранилище записей фиксированной длины
Хранилище записей фиксированной длины (часть II)
Хранилище записей фиксированной длины (часть III)

Давно обещанное сравнение производительности хранилища с SQLite. Если честно, вся эта эпопея с хранилищем утомила меня. Делов на копейку, а растянул уже на полгода. Смысл теста незатейлив. Требуется сохранить много-много пар {Guid, int}, а потом произвести некоторое количество запросов записи по Guid ключу, и сверить соответствующий ему int. Поиски делаются из разных потоков.

Для тестирования пресловутого хранилища и SQLite базы данных используется один и тот же код, который работает со следующим интерфейсом:
interface IStorage : IDisposable
{
   void StoreGuidsAndInts(Guid[] guids);

   void InitStorage();

   int GetInt32FromRecordByKey(Guid id);
}
Вот, собственно, код теста:
private const int RecordCount = 200000;
private static readonly int SearchCount = Math.Min(100000, RecordCount);

private static Guid[] GenereateGuids()
{
    var ids = new Guid[RecordCount];

    for (int i = 0; i < ids.Length; i++)
    {
        ids[i] = Guid.NewGuid();
    }
    return ids;
}

static void StressStorageTest(IStorage storage)
{
    Guid[] ids = GenereateGuids();

    Stopwatch sw1 = Stopwatch.StartNew();

    storage.StoreGuidsAndInts(ids);

    Console.WriteLine(
        "Быстрая вставка новых записей ({0} штук) - {1}", 
        RecordCount, 
        sw1.Elapsed);


    Stopwatch swInit = Stopwatch.StartNew();

    storage.InitStorage();

    Console.WriteLine("Инициализация индексированного хранилища - {0}", swInit.Elapsed);

    int searchCount = SearchCount;
    var syncRoot = new object();

    var rnd = new Random();

    var callbacks = new List<WaitCallback>(searchCount);

    for (int i = 0; i < searchCount; i++)
    {
        int index = rnd.Next(RecordCount);

        callbacks.Add(
            _ =>
            {
                int value = storage.GetInt32FromRecordByKey(ids[index]);
                Assert.AreEqual(index, value);
                if (Interlocked.Decrement(ref searchCount) == 0)
                {
                    lock (syncRoot)
                    {
                        Monitor.Pulse(syncRoot);
                    }
                }
            });
    }

    var sw2 = Stopwatch.StartNew();

    foreach (var callback in callbacks)
    {
        ThreadPool.QueueUserWorkItem(callback);
    }

    lock (syncRoot)
    {
        Monitor.Wait(syncRoot);
    }

    Console.WriteLine("Проверка индекса ({0} поисков - {1}", SearchCount, sw2.Elapsed);
}
Извиняюсь, долго не медитировал над кодом, хотя суть должна быть понятна. Заряжаем хранилища набором Guid-ов, создаем список делегатов, которые берут Guid по случайному индексу, просят хранилище вернуть индекс идентификатора, сравнивают индексы. Закидываем список делегатов (вот так вот грубо) в пул потоков и ждем когда декрементируется счетчик поисков. Хранилище, основанное на хранилище записей, не сильно сложно (относительно хранилища на SQLite).

Пришлось, правда, подтюнинговать метод записи пар. Его производительность меня волновала только в плане комфортного запуска тестов. Уж слишком долгая операция перераспределения места в файле, потому добавление записей через само хранилище безобразно долгое. Писал пары прямо в стрим данных, благо формат прозрачный.
class IndexedTestStorage : IndexedStorage<TestHeader, TestRow, Guid>, IStorage
{
    private Stream _bufferedStream;
    private BinaryWriter _writer;

    public IndexedTestStorage(Stream stream)
        : base(
            stream,
            Encoding.Default,
            TestRow.IdColumn,
            new DictionaryIndex<Guid>())
    {
    }

    public void StoreGuidsAndInts(Guid[] guids)
    {
        _bufferedStream = new BufferedStream(Stream);
        _writer = new BinaryWriter(_bufferedStream);
        for (int i = 0; i < guids.Length; i++)
        {
            _writer.Write(guids[i].ToByteArray());
            _writer.Write(i);
        }

        _bufferedStream.Flush();
    }

    public void InitStorage()
    {
        base.Initialize();
    }

    public int GetInt32FromRecordByKey(Guid id)
    {
        return GetRow(id).Int32Value;
    }

    public override void Dispose()
    {
        base.Dispose();
        _bufferedStream.Dispose();
        _writer.Close();
    }

    public TestRow GetRow(Guid id)
    {
        return GetRow(GetIndex(id));
    }

    public TestRow AddNewRow(Guid id)
    {
        return InsertRow(id);
    }
}
С вариантом реализации через SQLite пришлось повозиться. Открытие и закрытие соединения - слишком дорогая операция. Делать открытие и закрытие соединения на каждое обращение - непозволительная роскошь. Пришлось пойти окружными путями и использовать соединение из разных тредов, обеспечивая самостоятельно гарантию того, что соединение не будет использовано из разных тредов одновременно. Фактически пришлось организовать пул открытых соединений (это довольно безопасно, пока нет одновременной записи).

Вот код:
class SQLiteStorage: IStorage
{
    private readonly string _path;
    private readonly Stack<SQLiteConnection> _connectionPool = new Stack<SQLiteConnection>();
    private readonly object _syncRoot = new object();

    public SQLiteStorage()
    {
        string path1 = Path.GetFullPath(@"..\..\StreamStorage\sqlitedb.s3db");

        _path = Path.GetFullPath("sqlitedb.s3db");
        if (File.Exists(_path))
        {
            File.Delete(_path);
        }

        File.Copy(path1, _path);
    }

    private SQLiteConnection GetConnection()
    {
        lock (_syncRoot)
        {
            if (_connectionPool.Count > 0)
            {
                return _connectionPool.Pop();
            }
        }

        var result = new SQLiteConnection("Data Source=" + _path);
        result.Open();
        return result;
    }

    private void ReturnToPool(SQLiteConnection connection)
    {
        lock(_syncRoot)
        {
            _connectionPool.Push(connection);
        }
    }

    public void Dispose()
    {
        foreach(var connection in _connectionPool)
        {
            connection.Dispose();
        }
        _connectionPool.Clear();
    }

    public void StoreGuidsAndInts(Guid[] guids)
    {
        var connection = GetConnection();
        Action<string> simpleCommand = text =>
        {
            using (var cmd = new SQLiteCommand(text, connection))
                cmd.ExecuteNonQuery();
        };
        var insertCommand = new SQLiteCommand(connection)
        {
            CommandText =
                "INSERT INTO [TestTable] ([Id], [IntValue]) VALUES (@Id, @Value)"
        };
        var valueParameter = insertCommand.Parameters.Add("@Value", System.Data.DbType.Int32);
        var id1Parameter = insertCommand.Parameters.Add("@Id", System.Data.DbType.Guid);

        //connection.Open();
        simpleCommand("BEGIN");

        try
        {
            for (int i = 0; i < guids.Length; i++)
            {
                id1Parameter.Value = guids[i];
                valueParameter.Value = i;
                insertCommand.ExecuteNonQuery();
            }

            simpleCommand("COMMIT");
        }
        finally
        {
            //connection.Close();
            ReturnToPool(connection);
        }
    }

    public void InitStorage()
    {
    }

    public int GetInt32FromRecordByKey(Guid id)
    {
        var connection = GetConnection();
        var getIntValueCommand = new SQLiteCommand(connection)
        {
            CommandText = "SELECT [IntValue] FROM [TestTable] WHERE [Id] = @Id"
        };
        var idParameter = getIntValueCommand.Parameters.Add("@Id", System.Data.DbType.Guid);

        idParameter.Value = id;

        //connection.Open();
        object obj = getIntValueCommand.ExecuteScalar();
        //connection.Close();
        ReturnToPool(connection);
        return Convert.ToInt32(obj);
    }
}
Места, где я поначалу пытался открывать и закрывать соединения, остались закомментированы. Сами тесты:
[Test]
public void StressIndexedStorageTest()
{
    using(var stream = new FileStream(
        "Storage.tmp",
        FileMode.Create,
        FileAccess.ReadWrite,
        FileShare.None,
        128,
        FileOptions.RandomAccess))
    using (var storage = new IndexedTestStorage(stream))
    {
        StressStorageTest(storage);
    }
}

[Test]
public void StressSQLiteTest()
{
    using (var storage = new SQLiteStorage())
    {
        StressStorageTest(storage);
    }
}
Ну и наконец, результаты:
 
StressIndexedStorageTest
Быстрая вставка новых записей (200000 штук) - 00:00:00.0763303
Инициализация индексированного хранилища - 00:00:00.1788403  
Проверка индекса (100000 поисков) - 00:00:01.4525583
 
StressSQLiteTest
Быстрая вставка новых записей (200000 штук) - 00:00:10.6895979
Инициализация индексированного хранилища - 00:00:00.0000385  
Проверка индекса (100000 поисков) - 00:00:12.0554961

При открытии и закрытии соединения на каждый запрос по индексу, время SQLite составило больше минуты на 100000 запросов. Должен признать, SQLite с пулом открытых соединений оказался достаточно быстр для нужд проекта! Но он слил. Ни в коем случае не испытываю радости по этому поводу. Описанный мной тест не может претендовать на объективность. Слишком специфичны условия (одиночные обращения к хранилищу из разных потоков)... В защиту SQLite тот факт, что он хранит индекс в файле, в то время, как мое хранилище использует словарь в памяти.

При тестировании варианта хранилища с индексом в файле, разница в производительности между SQLite и моим хранилищем тает (SQLite уступает лишь в 2 раза). Безусловно, SQLite годится на гораздо большее, чем хранилище записей фиксированной длины. Однако, предпочтение было отдано хранилищу записей по ряду причин: В основном, из-за прозрачной организации файла. Еще одна причина - ощутимо более быстрое добавление записей, чем в таблицу SQLite. Последняя: к моменту обсуждения возможности использования SQLite (начало ноября) времени на переделку не было, хотя много времени и не требовалось. Надо как-то подытожить 4 длинных поста на тему хранилища: Велосипеды - вещь в себе, особенно узкоспециализированные. Они могут дать неплохое преимущество перед инструментами широкого профиля. Но, время потраченное на исследование доступных инструментов, вполне может окупить время, потраченное на написание велосипеда. Данный велосипед безусловно порвал SQLite по производительности, хотя производительность SQLite-а (с пулом открытых соединений) вполне могла удовлетворить требованиям задачи.

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