Предельная производительность: C#

Я поделюсь 30 практиками для достижения максимальной производительности приложений, которые этого требуют. Затем, я расскажу, как применил их для коммерческого продукта и добился небывалых результатов!
Приложение было написано на C# для платформы Windows, работающее с Microsoft SQL Server. Никаких профайлеров – содержание основывается на понимании работы различных технологий, поэтому многие топики пригодятся для других платформ и языков программирования.

Предисловие

Всё началось в далёком 2008 году – тогда я начал заниматься задачами сравнения и репликации реляционных баз данных. Такого рода приложения в первую очередь требуют высокого качества исполнения, т.к. потеря или порча данных может обернуться катастрофой. Во-вторых, размеры баз могут достигать сотни и тысячи гигабайт, поэтому от приложения требуется высокая производительность.
Основной упор делался на SQL Server, а так как Microsoft давно отказались от нормальной поддержки ODBC драйвера и предоставляют полный функционал только в ADO .NET provider, то приложение необходимо было писать на одном из языков для .NET Framework. Конечно сочетание High Performance Computing и платформа .NET как минимум вызывает улыбку, но не спешите с выводами.
Когда продукт был готов, результаты превзошли все ожидания, и производительность в разы превосходила лучшие решения на рынке. В данной статье я хочу поделиться с вами основными принципами, которых стоит придерживаться при написании высокопроизводительных приложений.

Принципы оптимизации

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

Начните с …

1. Хороший алгоритм.

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

2. План действий.

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

3. Микро-задержки.

Есть некая операция, время выполнения которой занимает F секунд. Если уменьшить это время всего на 1 микросекунду, то за 100 миллионов итераций вы получите выигрыш в 100 секунд! Такие частые операции – первый кандидат для оптимизации.

Ветвление кода

4. Не используйте «if», когда всё заранее известно.

Начнём с простого примера класса, в котором есть публичный метод, и его внутренняя реализация:

пример кода

class Example
{
    public void Print(String msg)
    {
        if (msg == null)
            throw new ArgumentNullException();
        PrintInternal(msg);
    }

    private void PrintInternal(String msg)
    {
        if (msg == null)
            throw new ArgumentNullException();
        ...
    }
}

В каждом из методов есть проверка аргумента на правильность значения. Это хорошо работает как «защита от дурака», но конструкция «if» – это в конечном итоге инструкции процессора, которые требуют время на выполнение. В данном примере метод «PrintInternal» вызывается только из метода «Print», где уже есть проверка. Это значит, что вторая такая же проверка не только не имеет смысла, но и негативно влияет на производительность. Это в какой-то мере пересекается с принципом YAGNI – зачем писать код, который никогда не используется?
Перейдём к примеру поинтереснее:

пример кода

void PrintValues(IDataReader dataReader)
{
    while (dataReader.Read())
    {
        for (int i = 0; i < dataReader.FieldCount; i++)
        {
            object value = dataReader.GetValue(i);
            PrintValue(value);
        }
    }
}

void PrintValue(object value)
{
    if (value is int)
        ...
    else if (value is long)
        ...
    else if (value is String)
        ...
    else if ...
}

В примере из некого IDataReader читаются записи и обрабатываются значения каждого поля. Если подумать, то зачем делать общий метод «Print», который проверяет тип значения и решает как его обработать? Ведь схема данных заранее известна, и доступна в методе GetSchemaTable. Тогда пример можно оптимизировать с использованием делегатов:

Оптимизированный код

delegate void PrintMethod(object value);

void PrintValues(IDataReader dataReader)
{
    PrintMethod[] printers = new PrintMethod[dataReader.FieldCount];
    for (int i = 0; i < printers.Length; i++)
    {
        Type fieldType = dataReader.GetFieldType(i);
        if (fieldType == typeof(int))
            printers[i] = PrintInt;
        else if (fieldType == typeof(long))
            printers[i] = PrintLong;
        else ...
    }

    while (dataReader.Read())
    {
        for (int i = 0; i < printers.Length; i++)
        {
            object value = dataReader.GetValue(i);
            printers[i](value);
        }
    }
}

Таким образом, мы проверяем типы данных в полях только один раз при инициализации, а не на каждой записи, что очень положительно отражается на производительности. К тому же, если какой-то тип данных не поддерживается вашим кодом, то вы получите ошибку сразу, а не после чтения миллионной записи. Думаю, про вредность Boxing / Unboxing в этом примере не стоит рассказывать, и надеюсь, вы догадываетесь как это исправить.

5. Вторая причина не использовать «if».

Любой современный процессор – это не «набор транзисторов», который тупо выполняют указанные команды. Процессор – это очень сложное технологическое устройство, в котором есть свои трюки для оптимизации выполнения инструкций.
Instruction Scheduling – один из видов оптимизации, который позволяет параллельно выполнять инструкции. Представьте код:

int x = a * b;
int y = c ^ d;
int z = x + y;
int w = z - y;

Инструкции, вроде как идут последовательно, но данные между первым и вторым выражением никак не связаны между собой. Это значит, что ещё на этапе компиляции можно задействовать все регистры общего назначения, при этом процессор сможет выполнить операции с этими регистрами практически параллельно. А вот третье и четвёртое выражения уже имеют зависимые данные, и тут оптимизировать не получится.
Польза от параллельности очевидна, и сейчас я объясню как это связано с «if». Дело в том, что когда процессор встречает условный переход, то он заранее не может знать выполнится ли условие или нет, поэтому об эффективности оптимизаций с выполнением инструкций параллельно можно забыть, не смотря на то, что есть такие техники как Branch prediction.
Вот вам задачка: как сравнить два байта без использования оператора «if»? Метод должен возвращать -1, 0, или 1, а его сигнатура: int CompareBytes(byte a, byte b)

Ответ

int CompareBytes(byte a, byte b)
{
    unchecked
    {
        int ab = (int)a - (int)b;
        int ba = (int)b - (int)a;
        return (ab >> 31) | (int)((uint)ba >> 31);
    }
}

Сам по себе этот подход работает быстрее, чем его аналог с двумя «if». Но для данного примера компилятор лучше оптимизирует программу в целом, если будет использоваться «if» с прямым вызовом метода (без делегатов и без виртуализации). Тем не менее, такого рода подход в определённых местах может сократить время выполнения программы.

Циклы

6. Эффективные циклы.

• Никаких «foreach» – эта конструкция может создать экземпляр класса, который реализует интерфейс IEnumerable (чем плохо, описано в принципах 16 и 23).
• Никогда не объявляйте переменные типами IList или IEnumerable, если вы знаете точный тип коллекции (см. принцип 24). Можно воспользоваться «var».
• По возможности, используйте встроенные массивы, а не класс List. Это связано с проверкой границ массива в индексаторе, которые сказываются на производительности. Единственный способ избежать этих проверок, написать «for» таким образом:
  

  for (int i = 0; i < a.Length; i++) {
      int e = a[i];
  }
  

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

  for (int i = 0; i < a.Count; i++) {
      int a = a[i];
      int b = a[i];
      int c = a[i];
  }
  

  
  
  
  

7. Разматывайте циклы.

Любой цикл – это та же конструкция «if». Если количество итераций небольшое, и их количество заранее известно, то иногда цикл лучше заменить на его тело, которое повторяется необходимое кол-во итераций (да, один раз Copy и N раз Paste).

Пример – возведение числа в 4-ю степень

int power4(int v)
{
    int r = 1;
    r *= v;
    r *= v;
    r *= v;
    r *= v;
    return r;
}

Если размотать цикл невозможно, то кол-во итераций N можно сократить в K раз, если N кратно K. Т.е. цикл можно представить как внешний из N/K итераций, и внутренний из K итераций. Таким образом, вы разворачиваете только внутренний цикл, и сокращаете изначальное кол-во итераций в K раз.

Пример на базе предыдущего

int power(int v, int N)
{
    int r = 1;
    // Reduce the number of iterations by 4 times.
    for (int loops = N >> 2; loops > 0; loops--)
    {
        r *= v;
        r *= v;
        r *= v;
        r *= v;
    }
    // Process the tail.
    for (int loops = N & 3; loops > 0; loops--)
    {
        r *= v;
    }
    return r;
} 

Этот метод может привести к ухудшению производительности в некоторых случаях, поэтому требует особой аккуратности. Советую почитать для начала «Loop unwinding» на Wikipedia.

Асинхронные задачи

8. Примитивы синхронизации.

Рассказывать про то, как правильно синхронизировать потоки, я не буду – об этом уже писали много раз. Просто хочу напомнить, что к примитивам синхронизации относятся критическая секция (класс Monitor или конструкция lock), события (например, ManualResetEvent), класс Interlocked, и можно ещё отнести переменные с модификатором volatile. Семафоры, мьютексы и пр. вряд ли вам понадобятся.
Здесь я хочу рассказать немного о «volatile», т.к. далеко не все понимают как это работает. Представьте целочисленную переменную, в которую вы записываете число, умножаете на что-то, вычитаете, и пр. – делаете подряд различные операции. В большинстве случаев, для вашей переменной отведено место в stack’е – т.е. в оперативной памяти. Практически для любой операции процессору необходимо вначале загрузить значение переменной в регистр, а потом он может выполнить операцию. После выполнения, можно записать значение переменной обратно в память. Однако, чтение и запись в память – очень дорогостоящая операция, поэтому по возможности все компиляторы генерируют такой код, что переменная один раз загружается в регистр, над ней выполняются все необходимые операции, и только в конце запись обратно в память. Т.е. это оптимизация на этапе компиляции.
Модификатор «volatile» – это не что иное, как указание компилятору не оптимизировать использование переменной, а постоянно читать её значение из памяти, а после выполнения операции – сразу записывать новое значение обратно в память. Таким образом гарантируется видимость изменения переменной другим потокам. В противном случае, если актуальное значение переменной будет постоянно «висеть» в регистре, то другой поток никогда не увидит этих изменений. Однако, в отличие от Interlocked, это не гарантирует взаимное исключение модификации переменной.
«Volatile» можно использовать, если одному потоку необходимо узнать значение, которое изменяется в другом, при этом погрешности актуальности значения не столь важны. Под это описание подходит сценарий с прогрессом асинхронной задачи.

Пример кода

class AsyncWorker
{
    volatile int progress;

    public int Progress
    {
        get
        {
            return progress;
        }
    }

    void DoWork()
    {
        for (this.progress = 0; this.progress < Count; this.progress++)
        {
            ...
        }
    }
}

В главном потоке программы можно создать таймер, который периодически опрашивает прогресс выполнения задачи и отображает его в UI. Если бы у переменной «progress» не было модификатора «volatile», то была бы вероятность, что актуальное её значение в итерациях цикла будет храниться только в регистре процессора и для главного потока она будет всегда 0. Такой подход к чтению прогресса избавляет от надобности синхронизации потоков, которая замедляет выполнение асинхронной задачи, и тем более от ужасной методики рассылки событий на каждое изменения значения прогресса.

9. Задачи и ресурсы.

Существует такой класс как ThreadPool, который является менеджером потоков, и вы с лёгкостью можете делегировать задачи без надобности постоянно создавать новые потоки, что в очередной раз хорошо для производительности. Здесь нельзя не согласиться, если речь идёт о простеньких приложениях, но если требуется серьёзная оптимизация – забудьте! Вам нужен либо свой менеджер асинхронных задач, либо готовые решения.
Представьте что у вас всего 2 ядра у процессора, и размер пула потоков тоже 2. Вы хотите выполнить 3 асинхронные задачи:

• первая считает общее количество бит в большом массиве данных в памяти
• вторая читает данные из сетевого протокола, и пишет на диск
• а третья шифрует небольшое значение с помощью AES-256

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

10. Пакетная обработка.

У вас есть N элементов, с которыми необходимо выполнить некую операцию, причём все элементы не хранятся в памяти – у вас есть некий поставщик элементов. Элементов много, поэтому лучше было бы сделать это параллельно. Одна операция над элементом занимает F секунд, а синхронизация потоков для добавления элемента в очередь обработки занимает S секунд. Представьте, что F соизмеримо с S, или хуже того S больше F. В итоге, тот поток, который добавляет элементы в очередь обработки других потоков, тратит столько же времени (или больше) на синхронизацию потоков, сколько и само время обработки элементов (N x F <= N x S). Оптимизацией это не назовёшь, поэтому вы можете на этом остановиться и решить, что в распараллеливании нет никакого смысла.
Если объединить K элементов в «пакет», и ставить в очередь обработки не элементы, а пакеты, то вам не нужно будет так часто синхронизировать потоки, и общее время синхронизации уменьшится в K раз. Сделайте пакет в 1000 элементов, и оно пропорционально уменьшится в 1000 раз. Неплохо, да? Скажем, у вашего процессора 16 ядер, и в идеальном случае вы хотите снизить время обработки всех элементов до N x F / 16. А если F соизмеримо с S, то вы получите неравенство N x F / 16 > N x S / 1000. Т.е. теперь общее время синхронизации намного меньше, чем обработка элементов одним из 16 потоков. Для примера реализации приведу псевдокод:

Пример кода

void DoWork(ItemProvider provider)
{
    Batch batch = NextFreeBatch();

    while (true)
    {
        Item item = provider.GetNextItem();
        batch.AddItem(item);

        if (batch.IsFull)
        {
            EnqueueBatchForAsyncProcessing(batch);
            batch = NextFreeBatch();
        }
    }
}

void EnqueueBatchForAsyncProcessing(Batch batch)
{
    lock (this.batchQueue)
        this.batchQueue.Enqueue(batch);
}

void ThreadRoutine()
{
    while (true)
    {
        Batch batch = DequeueBatchForAsyncProcessing();

        foreach (Item item in batch)
            ProcessItem(item);

        RecycleBatch(batch);
    }
}

Batch DequeueBatchForAsyncProcessing()
{
    lock (this.batchQueue)
        return this.batchQueue.Dequeue();
}

Предупреждаю, код – нерабочий и содержит массу недочётов. Я специально сделал его максимально простым, чтобы просто пояснить суть принципа.

11. Переключение контекста.

Вы знаете, почему потоки могут работать «параллельно» даже, если у процессора всего одно ядро? Каждая программа имеет изолированную от других память (виртуальная память), но все они используют одни и те же регистры процессора для выполнения инструкций. Чтобы дать возможность использования регистров процессора «параллельно», придумали технику переключения контекста – сохранение состояния регистров в оперативную память при остановке выполнения программы, чтобы можно было их позже восстановить для продолжения выполнения. Т.е. система выполняет часть инструкций одной программы, сохраняет её состояние, потом загружает состояние другой программы, выполняет немного её инструкций, потом опять сохраняет состояние, и так далее. Таким образом, система много раз в секунду переключается с программы на программу, что даёт эффект «параллельности выполнения».
Переключение контекста – довольно тяжеловесная операция, поэтому слишком большое кол-во потоков ведёт к деградации производительности. Чем меньше приходится потоков на одно физическое ядро процессора, тем меньше происходит переключений контекста, тем быстрее работает система в целом.
Во избежание переключения контекста, можно привязать потоки к конкретным физическим ядрам/процессорам. Для процессов есть свойство Process.ProcessorAffinity (общая маска для всех потоков процесса), а для потоков можно использовать ProcessThread.ProcessorAffinity.
Для контроля выделения времени выполнения потоков есть приоритет – свойство Thread.Priority. Чем больше приоритет, тем больше выделяется процессорного времени на выполнение инструкций. Также есть приоритет у процессов в системе – Process.PriorityClass.

Дисковое хранилище и сети

12. Выравнивание по размеру кластера.

Каждый раз, когда происходит чтение или запись в файл с диска, то это происходит большими кусками, даже если вам нужен всего один байт. Так устроено, что минимальная физическая единица записи/чтения называется «сектор», стандартный размер которого 512 байт. Но при выборе файловой системы используется единица «кластер», размер которой кратен размеру сектора. При установке Windows, стандартный размер кластера – 4 KiB. Это значит, что если у вас есть файл размером 1 байт, то физически он будет занимать весь кластер. Соответственно при чтении/записи операционная система будет оперировать кластерами.
Из этого следует, что если записать в файл последовательно 2 KiB данных, а потом ещё 1 KiB, то на диск будет записано 4 KiB в первый раз, а потом 4 KiB второй раз. Чтобы избежать такой двойной записи в один и тот же кластер, достаточно объединить данные и скинуть их на диск за один раз. Также, если вы пытаетесь записать 2 KiB с позиции в файле 3 KiB, то первый KiB пойдёт в первый кластер, а второй KiB будет записан уже во второй кластер.
Похожая ситуация происходит при чтении. Если вы читаете сколь-угодно байт из файла, то будет прочитан весь кластер, а если данные пересекают границу двух кластеров – то два кластера. Хотя, стоит учесть, что все жёсткие диски и RAID контроллеры имеют внутренний кэш, который может существенно ускорить чтение и запись секторов.
Для избегания повторных операций чтения/записи, всегда оперируйте последовательными блоками памяти, размером в кластер. В этом поможет обычный класс FileStream, однако размер его внутреннего буфера по-умолчанию жёстко установлен в 4 KiB. Просто получите размер кластера, и передайте его в конструктор FileStream в качестве переменной bufferSize.

Пример кода получения размера кластера

[DllImport("kernel32.dll", CharSet = CharSet.Unicode, SetLastError = true, EntryPoint = "GetDiskFreeSpaceW")]
static extern bool GetDiskFreeSpace(string lpRootPathName, out int lpSectorsPerCluster, out int lpBytesPerSector, out int lpNumberOfFreeClusters, out int lpTotalNumberOfClusters);

// Each partition has its own cluster size.
public static int GetClusterSize(string path) {

	int sectorsPerCluster;
	int bytesPerSector;
	int freeClusters;
	int totalClusters;
	int clusterSize = 0;
	if (GetDiskFreeSpace(Path.GetPathRoot(path), out sectorsPerCluster, out bytesPerSector, out freeClusters, out totalClusters))
		clusterSize = bytesPerSector * sectorsPerCluster;
	return clusterSize;
}

В сетевых протоколах передачи данных используется термин MTU (Maximum Transmission Unit) для определения размера блока данных для передачи. Но ситуация обстоит несколько сложней и остаётся для самостоятельного изучения.

13. Асинхронная запись.

Кто же не писал код, в котором в Stream последовательно записываются байты… Что в этом плохого? Давайте рассмотрим, что происходит внутри. Если помнить, что FileStream использует внутреннюю буферизацию, то всё хорошо, пока буфер заполняется. Как только он заполнился, всё его содержимое скидывается на диск. Но кто сказал, что эта операция мгновенна? (особенно если это HDD на вэб-сервере.) Поэтому, поток программы останавливается, и ждёт завершения записи. И так каждый раз когда, когда буфер полностью заполняется.
Для устранения этих задержек достаточно создать свой класс Stream, который накапливает данные в буфер, а потом ставит его в очередь на запись в отдельном потоке. Пока первый буфер стоит в очереди и собственно записывается, можно уже наполнять второй буфер (см. принцип №9). Таким образом, ожидание окончания записи заменяется задержкой синхронизации потоков. И только при закрытии Stream остаётся дождаться окончания записи в другом потоке – это необходимо для обработки ошибок. А для конечного пользователя это будет тот же прозрачный интерфейс класса Stream. По-моему, отличный выигрыш! Только не стоит забывать, что это работает только для больших файлов. Если данные занимают пару кластеров, этот подход не имеет смысла.
Также подумайте о более существенных задержках, которые возникают при передаче данных по сети (например, с использованием NetworkStream).

14. Чтение наперёд.

Как и при записи (принцип №13), чтение кластера с диска занимает время. Если стоит задача прочитать большой файл последовательно от начала до конца, то можно аналогично организовать асинхронное чтение файла наперёд во внутренние буферы. Пока один из буферов используется, в следующий происходит чтение соседнего кластера. При этом так же сохраняется прозрачность интерфейса Stream.
И не забываем о насущности проблемы при чтении данных из сетевого интерфейса.

15. Сжатие данных.

Если данные большого объема, которыми вы оперируете, подлежат хорошему сжатию – сжимайте их. Вы потеряете часть процессорного времени для сжатия, но можете намного больше выиграть при записи и чтении. Производительность жёстких дисков характеризуется не только скоростью записи и чтения, а ещё и параметром IOPS (Input-Output Operations per Second) – максимальным количеством операций, выполняемых за секунду. Если данные сжаты, то:

• Необходимо записать/прочитать меньше байт. Линейное уравнение отношения объёма к скорости даёт меньшее время.
• Меньше данных = меньше кластеров = меньше IO операций

Прирост производительности особо заметен, если скорость работы жёсткого диска (или сети) является узким горлышком. Обычно, чтение сжатых данных и распаковка их в памяти всегда выигрывает у чтения несжатых данных.
Чтобы всё работало на практике, используйте легковесные алгоритмы сжатия, например какую-нибудь модификацию LZ (Lempel-Ziv), которую легко можно найти в интернете (только читайте лицензионное соглашение перед использованием готовых продуктов).

Управление памятью

16. Структуры, а не классы.

У структур есть ряд преимуществ перед классами, которые дают лучшую производительность приложения:

• Структуры занимают меньше места в памяти, т.к. у них нет заголовка описывающий тип данных, указателей на таблицы виртуальных методов, а так же другие поля, необходимые для синхронизации и сборки мусора.
• Структуры хранятся в stack’е (но в куче, если массив). Выделение памяти в stack’е происходит очень быстро: stack – заранее выделенный буфер памяти, в котором просто резервируется место по размеру структуры (в основном, на этапе компиляции) путём уменьшения значения в stack pointer (уменьшения, т.к. данные в stack’е хранятся задом-наперёд). Когда функция завершает свою работу, то «освобождение» всех переменных в stack’е происходит один махом путём увеличения указателя stack pointer на количество байт, необходимых для переменных. А выделение и освобождение памяти в куче – это огромное количество операций, в отличие от простого вычитания и суммирования.
• Из-за того, что структуры хранятся в stack’е, они не требуют сборки мусора. Это сильно разгружает сборщик мусора и избавляет от проблемы фрагментации памяти.
• Структуры, поля которых – только value types, легко сериализовать в массив байт и обратно.
  
  Пример кода сериализации

      MyStruct value;
      // Allocate memory buffer.
      byte[] buffer = new byte[Marshal.SizeOf(typeof(MyStruct))];
      fixed (byte* ptr = buffer)
      {
          // Serialize value.
          *((MyStruct*)ptr) = value;
          // Deserialize value;
          value = *((MyStruct*)ptr);
      }
  

  
  
  
  

Не забывайте, что reference types всегда передаются в метод по ссылке, а для структур достаточно дописать ключевое слово «ref».

17. Освобождение памяти.

Не смотря на автоматическое освобождение памяти в .NET Framework, не стоит забывать, как работает сборка мусора. Все объекты представляются как вершины графа, а ссылки на объекты – как его рёбра. Для простоты (хоть это не так), самой первой вершиной графа можно считать класс, который определяет точку входу в приложение (с функцией main). Как только некие рёбра графа всех объектов будут убраны так, что образуется два несвязанных графа, то объекты того, который не связан с точкой входа, можно удалить из памяти.
Поскольку рёбра графа представляются ссылками, то удаление рёбер можно считать установку ссылки в значение «null». Если вы забываете это делать, ваши объекты будут переживать сборку мусора и переходить из поколения в поколение, увеличивая общий расход памяти приложением.
Здесь можно вывести для себя очень простое правило – как только объект перестаёт быть нужным, обнулите ссылку на него.

18. Повторное использование памяти.

Управление оперативной памятью – непростая задача, а постоянное её выделение и освобождение приводит к фрагментации и росту рабочего пространства процесса. Поэтому, не стоит просто полагаться на менеджера памяти, а как можно больше облегчить его задачу путём переиспользования фрагментов памяти (имеются в виду массивы byte[], int[], и пр.). Не нужно писать свой внутренний менеджер, который хранит ссылки на неиспользуемые блоки памяти и выдаёт их по требованию – будет ещё хуже. Среда выполнения очень эффективно справляется с переиспользованием памяти, если вовремя обнулять ссылки и создавать новые массивы с помощью оператора new такого же размера, как и освобождённые.
Самым хорошим примером такого переиспользуемого буфера памяти можно назвать stack. Память для stack’а выделяется один раз при старте потока (см. CreateThread), и используется для хранения стека вызовов функций, всех локальных переменных функций, входящих аргументов, и иногда для возвращаемых результатов.
Если вы всё же решили, скажем, повторно использовать массив байт для различных целей, и выделенного буфера вам не хватает, то не используйте Array.Resize. Как бы хорошо не звучало название метода, он просто создаёт новый массив и копирует туда содержимое старого. Новый массив вы и сами можете создать, а копирование содержимого для буфера не нужно (см. принцип 26).
И на последок хочу привести пример, как интерпретировать массив «byte» как массив «int» запрещённым способом:

Пример кода

internal static class ByteArrayReinterpreter
{
    private static IntPtr intArrayTypePtr;

    unsafe static ByteArrayReinterpreter()
    {
        int[] intArray = new int[1];
        fixed (int* ptr = intArray)
            intArrayTypePtr = *(IntPtr*)(((byte*)ptr) - (IntPtr.Size * 2));
        intArray = null;
    }

    public static unsafe int[] AsIntArray(this byte[] array)
    {
        if ((array.Length & 3) != 0)
            throw new ArgumentException("The array length must be multiple of 4.");

        object arrayObj = array;
        int newLength = array.Length >> 2;

        fixed (byte* ptr = array)
        {
            *(IntPtr*)(((byte*)ptr) - (IntPtr.Size * 2)) = intArrayTypePtr;
            *(int*)(((byte*)ptr) - IntPtr.Size) = newLength;
        }

        return (int[])arrayObj;
    }
}

Я не даю никаких гарантий – используйте этот код на свой страх и риск, и только если вы знаете что делаете, и если это действительно необходимо.

На уровень ниже

19. «unsafe» и указатели.

Код с пометкой «unsafe» позволяет в C# использовать указатели, и это открывает широкие возможности для оптимизации. Вы можете интерпретировать массив байт как угодно – как массив int или структур Guid, вы забываете про проверки границ массива, вы можете выравнивать адреса в памяти, и т.п. Без использования unsafe кода никак не получится максимально оптимизировать приложение, которое интенсивно работает с большими объёмами данных в памяти.

20. Компактное хранение.

При работе с большими массивами данных, стоит задуматься о структуре их хранения. Знаете сколько байт обычно занимает тип «bool»? 4 байта для 32-разрядного приложения и 8 – для 64-разрядного. Объявите в структуре несколько полей типа «bool» – и её размер вырастет до неимоверных размеров. Чтобы исправить этот недочёт, объявляйте переменную типа «byte», «ushort», «uint», или «ulong», и используйте её биты в качестве флагов (см. «enum»).
Если вы заранее знаете диапазон значений целочисленной переменной, то объявляйте поля соответствующего типа. Зачем объявлять поле типа «int», если диапазон значений от 0 до 10? Вам «byte» со свистом хватит.
Далее, если вы знаете, что диапазон значений занимает всего 20 бит (от 0 до 1048575) и вам нужен «int» (32 бита), то вы можете использовать оставшиеся 12 бит для других целей, например для неких флагов. Такое слияние полей неудобно для использования, но очень компактно. Правда, минус ещё в том, что такие поля плохо подлежат сжатию (алгоритмы сжатия работают с байтами, а не битами).

Пример кода

int field;
// Decouple numeric and flags
const int NumericMask = ((1 << 20) - 1);
int numeric = field & NumericMask;
MyFlags flags = (MyFlags)(field >> 20);
// Unite numeric and flags back
field = ((int)flags << 20) | numeric;

Очень часто структуры содержат данные, которые можно легко вычислить. Поэтому, стоит задуматься о балансе между вычислением значения поля «на лету» и использовании памяти для хранения значений таких полей в каждом элементе массива.
И, вдобавок, если много элементов массива имеют поле с абсолютно одинаковыми значениями, то можно сгруппировать такие элементы и хранить значение в группе, а не в поле каждого элемента.

21. Выравнивание в памяти.

Представьте себе структуру данных:

struct S
{
    byte a;
    short b;
    short c;
}

Общий её размер составляет 5 байт. Скажем, у вас есть массив S[], и некая функция в цикле что-то делает с полем «b». Предположим, что оператор «new» выделил кусок памяти для массива, и указатель на первый элемент равен 0x100000 – здесь я просто хочу подчеркнуть, что адрес является степенью двойки, или, по крайней мере, кратен 4 или 8. Теперь для первого элемента в массиве адрес для поля «b» будет 0x100001, для второго – 0x100006, третьего – 0x10000B, и т.д. Некоторые архитектуры процессоров требуют, чтобы адреса для чтения или записи были кратны размеру машинного слова – это и называется «выровненный адрес». Для архитектур x86 и x86-64 (где размер машинного слова 4 и 8 байт соответственно) таких требований нет, однако чтение и запись по выровненным адресам дают лучшую производительность.
Для выравнивания структур данных используется метод padding – добавление лишних байт, чтобы все размеры всех полей структуры были кратны указанному числу байт. Если выровнять нашу структуру на 4 байта, то получится:

вот такой код

struct S
{
    // offset: 0, size: 4
    byte a;
    byte __padding_byte_1;
    byte __padding_byte_2;
    byte __padding_byte_3;
    // offset: 4, size: 4
    short b;
    byte __padding_byte_4;
    byte __padding_byte_5;
    // offset: 8, size: 4
    short c;
    byte __padding_byte_6;
    byte __padding_byte_7;
    // total size: 12
}

Чтобы не писать всё это руками, в .NET Framework есть StructLayoutAttribute. Имейте в виду, выравнивание может очень негативно обернуться для производительности – добавляя лишние байты, размер данных может сильно увеличиться, что приводит к большему количеству обращений к памяти.
Тут есть и ещё интересная сторона. Практически все знают, что у процессоров есть внутренний кэш, да и ещё нескольких уровней. Но далеко не все знают, как он работает. Вкратце, есть так называемые cache lines – небольшие блоки памяти (например, 32 байта), в которые записываются данные из оперативной памяти по выровненному адресу (на размер кэш линии). Если взять наш пример со структурой «S» размером 5 байт, то процедура, которая в цикле последовательно обращается к данным элементов массива, будет на самом деле читать первые 6 элементов из кэша процессора (при размере кэш-линии в 32 байта; я имею в виду, что процессор это будет делать, кэш-то у него). Для седьмого элемента первые два байта структуры хранятся в последних двух байтах кэш-линии, а остальные три байта структуры – в физической памяти. При чтении происходит кэш-промах, и тогда процессору приходится читать данные из физической памяти, что намного медленнее чтения из кэша. Из этого следует, чем больше будет обращений к кэшированной памяти, тем быстрее будет работать приложение. В вопросе «PInvoke for GetLogicalProcessorInformation» на StackOverflow вы можете взять код для получения размера кэш линий.
Вторая, не менее интересная сторона, заключается в понимании как происходит выделение физической памяти. Каждый процесс имеет свою виртуальную память, которая неким образом соотносится с реальной физической памятью. В распространённой модели постраничной фрагментации памяти, где каждая страница памяти обычно занимает 4 KiB, последовательная виртуальная память размером 8 KiB может ссылаться на две НЕпоследовательные страницы физической памяти. Помните «файл подкачки»? Как вы думаете, какими кусками Windows записывает туда и считывает оттуда память? Так что выравнивание адресов в памяти на размер страницы иногда может быть большим плюсом.

22. Преимущества x86-64.

Если ваше приложение запущено в 64-разрядном процессе, то вам открывается доступ к 64-разрядным регистрам процессора RAX, RSP, и т.д. Конечно, не напрямую, а простым использованием типа «long» вместо «int». Представьте конвейерную ленту – сколь вы не положите на неё изделий (в пределах максимальной нагрузки), она всё равно будет двигаться с заданной скоростью. Точно так же и с регистрами – при использовании «int» вы всего лишь заполняете 8-байтный регистр наполовину, скорость выполнения операций остаётся постоянной.
Для примера возьмём структуру Guid. Она представлена 11 полями (int, 2 short, и 8 byte), которые в сумме занимают 16 байт. Метод, Equals в этой структуре выглядит так:

Код метода Equals

bool Equals(Guid g)
{
    return g._a == this._a && g._b == this._b && g._c == this._c && g._d == this._d
         && g._e == this._e && g._f == this._f && g._g == this._g && g._h == this._h
         && g._i == this._i && g._j == this._j && g._k == this._k;
}

Это 11 сравнений, которые мы можем заменить всего 4-мя, используя «unsafe»:

Оптимизированный код

unsafe bool Equals(Guid g)
{
    fixed (Guid* pg = &this)
    {
        int* p1 = (int*)pg;
        int* p2 = (int*)&g;
        return p1[0] == p2[0] && p1[1] == p2[1] && p1[2] == p2[2] && p1[3] == p2[3];
    }
}

Но используя преимущество x86-64, мы можем переписать этот код в два сравнения:

Оптимизированный код для x64

unsafe bool Equals(Guid g)
{
    fixed (Guid* pg = &this)
    {
        long* p1 = (long*)pg;
        long* p2 = (long*)&g;
        return p1[0] == p2[0] && p1[1] == p2[1];
    }
}

Две операции вместо 11 – по-моему, очень хорошо!

23. Вызов функций.

Есть практики, которые диктуют делать методы маленькими, а их названия должны быть самодостаточными, поэтому комментарии в коде даже не нужны. Это несомненно классно для, как минимум, понимания и поддержки кода, но очень негативно влияет на производительность. Разберёмся почему.
У процессора семейства x86 есть две инструкции CALL и RET (от «return»). Инструкция CALL вызывает метод по адресу в памяти, а инструкция RET возвращает управление вызывающему методу – продолжать выполнять инструкции, следующие за CALL. Т.е. и та и та инструкции схожи с JMP (от «jump») – переходят на выполнение инструкций по другому адресу. Так вот, чтобы это всё работало, инструкция CALL добавляет в stack адрес следующей за ней инструкции (из регистра IP) и делает JMP, а инструкция RET берёт этот адрес из stack’а и делает JMP обратно по этому адресу.
Далее, большинство методов принимают входящие параметры и что-то возвращают. Параметры можно передавать через регистры процессора, можно через stack, а можно и через то и другое. Есть различные соглашения вызовов методов. Чем больше параметров вы передаёте (и чем больше их размер в байтах), тем больше места нужно в stack’е, и тем больше требуется процессорного времени.
Итак, мы имеем:

• Безусловный переход по адресу в памяти.
• Запись и чтение адреса из stack’а для CALL/RET.
• Запись и чтение аргументов метода из stack’а.

А это ведёт к:

• Задержкам, связанным с обращением к памяти. А операции с регистрами выполняются намного быстрее.
• Невозможности эффективно использовать регистры процессора при компиляции IL в родной код.
• Отсутствию возможности для процессора проанализировать инструкции наперёд и выполнить их параллельно (из-за JMP-подобных инструкций).

Пример 1. Представьте функцию, которая сравнивает два Guid и объявлена так:

bool CompareGuids(Guid g1, Guid g2)

Если помнить, что структура Guid занимает 16 байт, то при вызове такого метода в stack будет записано 32 байта, чтобы передать аргументы g1 и g2. Вместо этого, вы можете написать:

bool CompareGuids(ref Guid g1, ref Guid g2)

И тогда, для каждого аргумента будет передан указатель на него, а не его значение, и это будет 4 байта для 32-разрадного процесса, и 8 байт для 64-разрадного процесса. Более того, появится вероятность, что адреса на аргументы будут переданы через регистры процессора, а не stack (в зависимости от соглашения вызова).
Пример 2. Тривиальный метод, который умножает два числа, и метод, который его вызывает:

пример кода

int Multiply(int a, int b)
{
    return a * b;
}

void Foo()
{
    int a = 4;
    int b = 5;
    int r = Multiply(a, b);
}

Если бы метод Foo просто делал умножения вместо вызова метода Multiply, тогда бы значения a и b просто были помещены в регистры процессора и умножены. Вместо этого мы заставляем компилятор генерировать лишний код, который делает кучу операций с памятью, да и ещё безусловный переход! А если метод вызывается миллионы раз в секунду? Вспомните про принцип №3.
Поэтому в таких языках, как C++ есть модификатор метода inline, который указывает компилятору, что тело метода необходимо вставить в вызывающий метод. Правда, и в .NET Framework только с версии 4.5 наконец-то можно делать inline методы (в предыдущих версиях невозможно было форсировано делать inline — только на усмотрение компилтора). А если говорить о микроконтроллерах, код для которых пишется на assembler, то там зачастую вообще запрещены вызовы функций. Хочешь выполнить код функции – делай Copy Paste.
Только не спешите переписывать код вашей программы в одну большую функцию – это приведёт к раздутию кода, которое сделает приложение ещё медленнее.

24. Виртуальные функции.

Чем могут быть плохи вызовы функций, мы выяснили. Виртуальные методы добавляют ещё один неприятный для производительности нюанс. Разберёмся на примере:

пример кода

class X
{
    virtual void A();
    virtual void B();
}

class Y : X
{
    override void B();
}

Есть два класса: X, и Y, который наследуется от X. Виртуальность методов обеспечивается таблицей виртуальных методов, в которой для класса X будет два метода: X.A и X.B, а для класса Y таблица будет содержать методы X.A и Y.B. Поэтому неважно как объявлена ваша переменная (тип X или Y), при вызове метода используется таблица.
Таблица – не что иное, как массив указателей на методы в памяти IntPtr[]. Таким образом, для того чтобы выполнить инструкцию CALL, вначале необходимо получить адрес функции в памяти из таблицы, а это – очередные задержки, связанные с обращением к памяти.
Чтобы избавиться от таких задержек, по возможности не используйте виртуальные функции. А если используете – пользуйтесь «sealed» и явным указанием типа переменной. Модификатор «sealed» говорит о том, у класса не может быть наследников, или метод не может быть переопределён в классе-наследнике. Вернёмся к примеру с классами X и Y:

пример кода

sealed class Y : X
{
    override void B();
}

void Slow(X x)
{
    x.B();
}

void Fast(Y y)
{
    y.B();
}

Мы сделали класс «Y» закрытым для наследования, и написали два метода, которые вызывают метод «B» класса «Y». В методе Slow мы объявляем тип переменной как «X», и при вызове метода «B» у экземпляра класса «Y» компилятор генерирует код обращения к виртуальной таблице, потому что класс «X» открыт для наследования.
Напротив, в методе Fast компилятор знает, что класс «Y» закрыт для наследования, а также он знает, что этот класс переопределят метод «B». И это говорит ему, что неоднозначных ситуаций здесь быть не может, есть только единственный метод «B» класса «Y», который будет вызван в таком случае. Поэтому, надобность в обращении к виртуальной таблице отпадает, не смотря на то, что метод «B» виртуальный. В таких случаях компилятор сгенерирует код прямого вызова метода «B», что положительно скажется на производительности.

Трюки и уловки

25. Reverse engineering.

Иногда производительность приложения упирается в третесторонние компоненты, на которые вы не можете никак повлиять. Или всё-таки можете...? Приведу реальный пример, SqlDataReader в методе GetValue для колонки с типом данных «xml» в конечном итоге вернёт вам String либо XmlReader. А задача состоит в том, чтобы сравнить два значения типа «xml» из двух разных источников. Вроде бы ничего особенного – взял да и сравнил две строки, да ещё можно использовать StringComparison.Oridnal чтоб вообще быстро было. Однако если копнуть глубже, и посмотреть в реализацию SqlDataReader, то можно узнать что на самом деле XML данные приходят клиенту в бинарном формате. Это значит, что конвертация таких данных в строку требует дополнительных ресурсных затрат, немалых затрат. Но если потрать время и покопаться в реализации, то можно заставить SqlDataReader думать (с помощью рефлексии), что вместо «xml» ему приходит обычный тип «varbinary». Таким образом, вам теперь просто необходимо проверить два массива байт на равенство, и никаких конвертаций. Конечно, если два массива отличаются, и вы хотите сравнить XML без учёта пробелов, комментариев, и регистра символов, то достаточно (с помощью той же рефлексии) создать два XmlReader на основе полученных байт, и сравнивать элементы XML.

26. Лишние действия.

Если вы играли в какую-нибудь 3D компьютерную игру, и случайно (или специально) попали за предел уровня, то вы, скорее всего, видели что пустое пространство ни чёрное и ни белое, а содержит мусор от предыдущих кадров. Этот эффект является результатом оптимизации игрового движка.
В 3D графике результат отрисовки 3D мира помещается в некий буфер кадра. Если вы загляните в любой туториал для начинающих, то там будет примерно такой код: залить буфер кадра белым или чёрным цветом, нарисовать 3D модель. В таких примерах заливка цветом служит просто фоном, на котором посередине вращается какая-нибудь фигура.
А теперь вспомните любую игру. Вы помните хоть где-то монотонный фон? Особенно, если действия разворачиваются в секретном бункере нацистов. Из этого следует, что перед отрисовкой сцены нет никакого смысла заливать буфер кадра каким-либо цветом, пусть там остаётся предыдущий кадр – всё равно весь кадр будет перетёрт новым изображением. А ведь Full HD (1920x1080) кадр с 32-битной глубиной цвета – это почти 8 MiB! И чтобы залить все однородным цветом, тоже нужно время. Хоть и небольшое, но нужно, причём делать это надо на каждом кадре (а их может быть около 100 в секунду). Таким образом, отсутствие элементарного бесполезного действия очень позитивно сказывается на FPS в игре.
Как это относится к .NET Framework? На самом деле, это относится к любой программе, написанной на любом языке. Вся операционная система просто кишит кучей бесполезных действий, которые выполняются тысячи раз в секунду. Но это отдельная тема, поэтому остановимся на тривиальном примере – оператор new. При создании нового экземпляра класса все его поля установлены в 0 или null, а в массиве все элементы тоже установлены в 0. Мы принимаем это как должное, и должен согласиться да – это очень удобно, и если бы значения были случайными, то это привело бы к множествам ошибок. На самом деле, на уровне системы память выделяется в таком виде, какой была освобождена – при освобождении никто не заботится об обнулении байт. Т.е. платформа .NET в пользу удобности делает действия, которые обычно лишние при выделении больших блоков памяти. Зачем инициализировать массив байт в ноль, если такой буфер будет заполнен данными с диска?
Решением могло бы стать использование GlobalAlloc (без флага GMEM_ZEROINIT) и GC.AddMemoryPressure, но при оптимальном подходе операция выделения памяти не будет слишком частой, поэтому инициализацией в 0 можно пренебречь. Речь в этом пункте, конечно же, не о памяти, а о выполнении бесполезных действий, так что суть вы уловили.

Изобретение велосипеда

27. Реализация «Format» и «ToString».

Не заставляйте программу искать куда и в каком виде вы хотите вставить строковое значение при использовании String.Format, если вы заранее знаете. Перепишите код на String.Concat или StringBuilder – будет быстрее. Лучше не представлять сколько действий выполняется, чтобы найти в строке “{0}” и подставить значение в указанном формате.
Для особого класса задач, можно и заняться реализацией ToString. Например, в разработанном приложении для формирования DML инструкций (INSERT/UPDATE/DELETE; во второй части статьи я объясню что к чему) были написаны свои методы для конвертации значений всех типов данных SQL Server в строку, которые конечно-же не создавали новый объект String. Такая оптимизация дала прирост производительности в 3 раза!

28. Слияние алгоритмов.

Другим примером велосипеда станет самодельный лексер для языка T-SQL, который необходим был для подсветки синтаксиса в текстовом редакторе. При получении очередного токена типа identifier необходимо определить, является ли он ключевым словом. Организовать список всех ключевых слов проще всего в Hashset. Тогда, чтоб проверить является ли токен ключевым словом, достаточно написать:

HashSet<string> keywords;
String tokenText;
bool isKeyword = keywords.Contains(tokenText.ToUpperInvariant());

Что плохого в такой реализации:

• Метод «ToUpperInvariant» создаёт новый экземпляр String.
• Метод «ToUpperInvariant» сам по себе очень тяжеловесный в реализации.
• При совпадении хэш кодов, сравниваются две строки. Хоть и побайтно, но сравниваются.

Все три пункта можно исправить. Заменим «keywords» на Hashset<int> и будем записывать туда не строки, а их хэш-код. Уверяю, для всех ключевых слов в T-SQL коллизий с использованием String.GetHashCode не будет. Таким образом, мы заменили сравнение строк сравнением 32-битных чисел. А с первыми двумя пунктами мы поступим хитро. Вспомните все ключевые слова из T-SQL, которые вы знаете. Особенность в том, что в них используются только латинские буквы, цифры, и символ подчёркивания, т.е. не выходят за пределы набора ASCII. А так как строки в .NET хранятся в UCS2/UTF16 кодировке, и по стандарту Unicode первые 127 code points совпадают с таблицей ASCII, то мы можем написать свою функцию ToUpper для ASCII, объединить её с вычислением хэш-кода строки, а также с проверкой на «keyword»!

Приблизительно так

bool IsKeyword(String tokenText)
{
    int hashCode = 0;

    for (int i = 0; i < tokenText.Length; i++)
    {
        int c = (int)tokenText[i];

        // check upper bound
        if (c > 'z')
            return false;

        // to upper case for Latin letters
        if (c >= 'a')
            c ^= 0x20;

        // a keyword must be of Latin letters, numbers, and underscore
        if ( ! ((c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_'))
            return false;

        // update hash code
        hashCode = hashCode <op> c;
    }

    return keywords.Contain(hashCode);
}

И никаких новых экземпляров строк, никакой сложной логики ToUpper для code points, которые не могут быть использованы в ключевых словах, да и хэш код сразу готов. На самом деле тут можно всё ещё намного круче оптимизировать, но это уже выходит за рамки данного пункта.

29. Изобретайте и экспериментируйте!

Не думайте что всё давным-давно изобретено. Много новшеств – это просто другой способ использования чего-то хорошо известного. Создайте новый язык программирования – на каком языке вы будете писать для него компилятор? И в конечном итоге, все, что было написано на новом языке, будет транслировано в инструкции процессора, как и для практически любого другого языка.
Была такая задача: сгенерировать T-SQL скрипт по неким данным и отобразить его в UI с подсветкой синтаксиса. Самый простой способ: сгенерировать скрипт в память или на диск, открыть его в текстовом редакторе, и добавить лексер для подсветки синтаксиса. Если учесть, что скрипт может занимать не одну сотню мегабайт, то такой подход съест огромное количество оперативной памяти и будет 3 больших задержки по времени: дождаться пока сгенерируется скрипт, дождаться пока текст загрузится в редактор, дождаться окончания лексического разбора скрипта. Поэтому было принято решение сделать так:

• Генерировать скрипт на диск, при этом делать индексный файл, который указывает на смещение от начала файла до каждой строки в тексте.
• Сделать свой компонент text view, который не грузит всё в память, а запрашивает конкретные строчки для отображения (для этого нужен индексный файл).
• Делать лексический разбор скрипта асинхронно, уже после того как первые строчки будут отображены в text view. О своём прогрессе лексер сообщает text view, который обновляет раскраску текста.
• Лексер обычно имеет состояние, которые выражается простым целочисленным числом «int». Зная это состояние и позицию в тексте можно продолжать синтаксический разбор с указанной позиции. А чтобы не хранить все токены для каждой строчки, которая сейчас не отображается на экране, достаточно хранить состояние лексера на начало строки. Как только строку необходимо будет отобразить на экране, необходимо сделать её лексический разбор, используя известное состояние. Это происходит очень быстро, и экономит огромное кол-во памяти. Поэтому, задача асинхронного лексера – разобрать весь текст и сохранить состояние для каждой строки в том же индексном файле, который используется для хранения смещений строк от начала текста. Таким образом, на каждую строку в индексном файле приходится 8 байт: 4 – смещение, 4 – состояние.

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

30. Вопреки всему.

Хочу отметить немаловажный факт, что приложение после серьёзной оптимизации может измениться в архитектуре некоторых компонентов, причём это зачастую противоречит многим известным вам шаблонам проектирования. Вот утрированный пример – класс, который перемножает числа:

class Multiplier
{
    public int a, b;
    public int Multiply() { return a * b; }
}

Во-первых, непонятно почему метод «Multiply» не принимает параметров, но возвращает некий результат умножения. Во-вторых, нарушена инкапсуляция. Именного такого рода, казалось бы, казусы могут иногда встречаться после тотальной оптимизации, причём они имеют серьёзную аргументацию. Хочу повторить, что этот пример просто показывает, как могут нарушаться понятия и принципы ООП, и не представляет особой ценности.
Если производительность крайне важна, не бойтесь изменять код до такой степени, что его можно назвать «вонючим». Однако имейте в виду, такие подходы очень плохо отражаются на простоте и понимании архитектуры, кода и его связанности, поддержки и развитию приложения, и зачастую ведут к большому кол-ву ошибок.

От слов к делу

Чтобы не быть голословным, я хочу показать, как применил все вышеописанные принципы (именно все, даже больше) при разработке движка сравнения и синхронизации, которая заняла у меня примерно 5 месяцев. К сожалению, я не могу рассказать обо всех секретах, раскрыть имя компании и имя продукта – статья не для рекламы. Чтобы не приводить просто цифры, вначале я хочу разъяснить для чего нужно такое приложение, и описать общий принцип его работы.

Сравнение и синхронизация баз

Представьте себе две базы. Вам необходимо сравнить их, найти различия, и перенести изменения (полностью или частично) из первой базы во вторую. Сценарии могут быть разными: есть staging база, данные которой нужно перенести в production; CMS для сайта, которая хранит содержание в БД – вы делаете копию базы, редактируете содержимое, а потом публикуете всё за один клик, применяя только изменения; частичное восстановление испорченных данных из резервной копии; и т.п.
Любую базу можно разделить на две логические части:

1. Модель, которая описывает поведение и содержимое базы (таблицы, представления, процедуры, и т.д.; назовём эту часть database schema)
2. Собственно данные базы, которые хранятся согласно модели (в основном, табличные данные; назовём эту часть database data)

Таким образом, весь процесс сравнения и синхронизации можно разделить на два этапа: сравнение и синхронизация схем, а затем – данных. Остановимся на втором этапе, так как обработка терабайт данных требует высокой производительности, хотя первый этап не менее сложный и интересный.

Общий алгоритм

Весь процесс от начала до конца можно разбить на 6 последовательных шагов:

1. Выбрать два источника данных для сравнения. В основном, источниками являются «живые» базы, однако это может быть и файл резервной копии, либо другой альтернативный источник.
2. Построить программную модель схемы из выбранных источников. Для сравнения, необходимо знать какие таблицы есть в базе, какие у них колонки, и какие типы данных там хранятся.
3. Настроить соответствие таблиц между двумя источниками. В каждой базе есть свой набор таблиц, и необходимо сравнивать таблицу Customers из первой базы с таблицей Customers из второй базы, таблицу Products – с таблицей Products, и так далее. Такое же соответствие необходимо установить между колонками в выбранных парах таблиц.
4. Сравнить данные таблиц. В основном, сравнение происходит по ключевым колонкам – они отвечают за уникальность записи в таблице. В результате такого сравнения мы можем получить 4 основных набора записей:
   • существующие только в первой таблице (нет схожих записей во второй)
   • существующие только во второй таблице
   • различные записи (данные отличаются в не-ключевых колонках)
   • идентичные записи (данные во всех колонках идентичны)
   Все эти записи (кроме идентичных), необходимо сохранить на локальный диск в некий кэш, который будет использован в следующих шагах.
5. Анализ сравнения, настройка синхронизации. На этом этапе пользователь может заняться анализом разницы, и выбрать таблицы и записи для частичной синхронизации, а также настроить различные опции для достижения желаемого результата. На этом этапе так же формируется план действий для синхронизации (удалить 10 записей там, обновить 5 записей тут, вставить 50 записей туда, и т.п.)
6. Выполнение синхронизации. По построенному плану и кэшу записей из предыдущих шагов, формируется SQL скрипт, который применяет изменения. Его можно выполнять на лету по мере формирования, либо просто сохранить на диск для отложенного выполнения.

Быстродействие в цифрах

После полного завершения продукта, можно было сравнить быстродействие с лидирующими конкурентами на рынке (заметьте, что неправильная реализация UI может свести на нет все ваши старания оптимизации back-end’а, поэтому я хочу подчеркнуть «полное завершение продукта»). Для данной статьи, в качестве конкурента я выберу только самое лучшее решение от самого известного производителя в этой области.
Все тесты я проводил на своём рабочем компьютере с вот такой конфигурацией:

• Intel i7-2630QM (4 cores @ 2GHz, 2.9GHz in Turbo, 8 logical threads)
• 12 Gb RAM DDR3 @ 1333 MHz (9-9-9-24)
• Intel SSD X25-M 120 Gb (250 Mb/s read, 35000 IOPS; 100Mb/s write, 8600 IOPS)
• Microsoft SQL Server 2008 R2 Developer Edition 64-bit
• Windows 7 Ultimate x64

Для шагов 2 и 3 общего алгоритма мы взяли базу с 22 тысячами таблиц, и вот что получили.

Описание теста	конкурент	мы	в % раз быстрее
Построение программной модели объектов базы данных (время, сек)	24 сек	6 сек	4
Автоматическое нахождение соответствий между объектами по именам (время, сек)	16 сек	2 сек	8

Для остальных шагов была выбрана, пожалуй, самая известная демо-база под названием «Adventure Works», которая занимает 185 MiB на диске, и в сумме имеет 761 тысячу записей с различными типами данных.

Описание теста и комментарии	конкурент	мы	в % раз быстрее
Сравнить базу саму с собой – измерить скорость движка сравнения данных (время, сек) В нашем случае все 8 ядер процессора загружены на 99.9% – это отличный показатель, который говорит, что ресурс «процессор» не простаивает без дела. Профайлер показал, что 75% процессорного времени уходит на SqlDataReader, а остальные 25% – на движок сравнения.	10 сек	2.2 сек	4.5
Сравнить базу с такой же схемой, но без данных – эффективность чтения данных из базы и скорость кэширования различных записей на диск (время, сек; размер кэша, MiB)	6 сек 125 MiB	1.8 сек 98 MiB	3.3 -
Повторить предыдущий тест, но с опцией сжатия кэша данных (время, сек; размер кэша, MiB) Благодаря компактному хранению данных, наш кэш намного меньше в размере. А параллельное сжатие данных и особый формат файла кэша дают незначительное приращение времени, хотя алгоритмы сжатия одинаковые.	12 сек 36 MiB	2.2 сек 24 MiB	5.4 -
После предыдущего теста сгенерировать T-SQL скрипт синхронизации – замерить скорость генерации, сравнить размер файлов (время, сек; размер, MiB) За 2 секунды прочитать 98 MiB кэша и записать 187 MiB на диск – это пиковая производительность используемого для тестов SSD	21 сек 245 MiB	2 сек 187 MiB	10.5 -
Генерировать T-SQL скрипт и выполнять на лету, без промежуточного файла (время, мин и сек) T-SQL тоже подлежит оптимизации, зная как работает SQL Server. Кроме того, код отсылки SQL запросов с помощью SqlCommand тоже можно оптимизировать.	2 мин 27 сек	1 мин 26 сек	1.7

Меня крайне порадовали такие результаты, как человека, который смог сам спроектировать и реализовать движок, и переплюнуть лучших конкурентов по всем параметрам. Хочу отметить, что разработка архитектуры велась сразу с учётом принципов оптимизации, а дальнейшая оптимизация всей программы велась путём построения предположений и проверки на практике (замер времени обычным QueryPerformanceCounter). Профайлер был использован только в конце ради интереса.
Напрашивается вопрос: «Может вы не всё учли? И поэтому конкуренты работают медленнее, но правильнее?». Мы учли всё, даже больше, чем конкуренты. И в этом заслуга команды QA, которая создала огромнейшее количество синтетических тестов для различных сценариев, которые наш продукт спокойно проходит, в отличие от других решений. Т.е. наше творение оказалось и самым надёжным, и самым быстрым.
P.S. Спасибо коллегам, которые усердно трудились над созданием приложения, и особенно компании, которая дала мне возможность проявить свой талант.

В итоге

Каждая задача требует индивидуального подхода, а оптимизация её решения включает комбинации различных концепций. Существует намного больше других принципов, которые не освещены в данной статье, некоторые из которых попросту не могут быть применимы к платформе .NET.
Есть много споров о сравнении быстродействия платформы .NET с приложениями, написанных на C++. За мою жизненную практику, в сложных алгоритмических задачах связка C++ и Assembler дают выигрыш от 1.5 до 2.5 раз по сравнению с C#. Это значит, что критические части можно выносить в unmanaged DLL. Однако на реальном примере я показал, что и на C# можно писать очень эффективный код.
И всё же не стоит досконально оптимизировать каждый кусок кода там, где это не требуется. Многие принципы ведут к усложнению архитектуры и понимания кода, а также поддержки и расширения вашего приложения, что выливается в кол-во потраченного времени. В данной статье я не призываю вернуться в каменный век, отказавшись от всех удобств платформы .NET, а просто хочу показать, как можно делать простые вещи сложно, но очень эффективно. Всегда вначале стоит определиться с целью приложения, требованиями к быстродействию и бюджетом, а потом решать как это реализовывать.
Очень хотелось по каждому из пунктов написать поподробнее, добавить кучу изображений и примеров для лучшего понимая, но тогда это получилась бы не статья, а книга. Тем не менее, я надеюсь, что она поможет в первую очередь тем, кто вообще не знает в какую сторону смотреть, если стоит задача оптимизации кода высокопроизводительного приложения.

---

Хочу ещё раз обратить ваши внимание, что статья не является:

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

Данная статья кратко освещает темы оптимизации:

• которые основываются на более глубоком понимании технологий
• на которые стоит обращать внимание для достижения максимальной производительности (выжать по максимуму)
• в которых стоит хорошо разобраться перед использованием (есть много «но», когда принцип не работает и делает только хуже)
• которые могут привести к усложнению архитектуры, кода, его поддержки и пр.
• которые стоит применять исходя из требований к приложению и из соображений здравого смысла

---

Специальное дополнение

В коментариях встретилось очень много критики, поэтому я решил привести пример реального кода оптимизации из принципа 28 (слияние алгоритмов), которую особые люди считают «ересью». Мне советуют использовать IEqualityComparer для HashSet и не будоражить умы аудитории. Хорошо, поробуем реализовать этот интерфейс. Поставим всего одно условие: ключевые слова SQL Server должны быть одинаковыми без учёта регистра. Например, «select» равно «SELECT» и равно «Select».
Метод GetHashCode. Начинать необходимо с него, т.к. HashSet вначале вычисляет хэш код, а потом только по совпадению вызывает Equals. Теперь стоит задача сгенерировать одинаковый хэш код для строк «select» и «SELECT». В этом, String.GetHashCode конечно же не поможет. Самый тупой способ решить проблему — сделать String.ToUpperInvariant и вычислить хэш код. Хорошо, будем умнее — берём класс StringComparer и его статический экземпляр OrdinalIgnoreCase. Тогда можно у него вызывать метод GetHashCode для нашей строки, и он будет возвращать хэш код без учёта регистра символов.
Метод Equals. Теперь можно заняться реализацией сравнения строк. Их тоже надо сравнивать без учёта регистра. В качестве IEqualityComparer будем продолжать использовать StringComparer.OrdinalIgnoreCase, и тогда гарантия равенства «select» и «SELECT» будет обеспечена. В итоге, в качестве IEqualityComparer для HashSet достаточно указать StringComparer.OrdinalIgnoreCase и все проблемы решены.
Что имеем?
1) Логика игнорирования регистра символов для инвариантной культуры при вызове GetHashCode. Как реализован этот метод — неизвестно, но варианта два: (а) либо делается что-то подобное ToUpperInvariant и вычисляется хэш код, либо (б) вызывается что-то типа CompareInfo.GetSortKey, и из байт в SortKey генерируется хэш код, что ещё хуже первого варианта (почему? смотрим Unicode Collation Algoritm).
2) Логика игнорирования регистра для инвариантной культуры при вызове Equals. Тут уже бесспорно работает что-то типа ToUpperInvariant, и два результата сравниваются побайтово (об этом говорит название «OrdinalIgnoreCase», где «IgnoreCase» делается с помощью инвариантной культуры, а «Ordinal» — побайтовое сравнение).
Чем это отличается от подхода с ToUpperInvariant?
• ToUpperInvariant теоритически намного хуже тем, что создаёт новый экземпляр String каждый раз.
• ToUpperInvariant выполняет всего один раз приведение к верхнему регистру, тогда как пункт (2) делает это два раза (для двух строк) и пункт (1) делает это один раз (либо работает через подобие SortKey). Т.е. 1 вызов против 3-х, где ToUpper (даже с Invariant) довольно таки тяжеловесная операция (можно это понять из Case Mappings). Тем не менне, это может не сравниться с проблемой создания нового экземпляра строки.
• Вычисление хэш кода и побайтовое сравнение одинаковы в обоих подходах (имеется ввиду по временным затратам).
Что всё же я предлагаю улучшить?
• Останавливать процедуру как только встечается символ, который не может быть использован в ключевом слове. Т.е. если строка будет «МояТаблица1», то всё закончится сразу на первом символе «М», и не нужно даже вычислять хэш код с игнорированием регистра символов (см. принцип 26 — Лишние действия).
• Выполнять очень легковесную процедуру приведения символов в верхний регистр, по сравнению с тяжеловесной Case Mappings в Unicode.
• Вычислять хэш код параллельно с выполнением ToUpperCase — не требуется два шага: вначале ToUpper, потом GetHashCode.
• Не сравнивать строки побайтово, а только их хэш коды. Сравнение Int32 однозначно быстрее сравнения массива байт в цикле.
• Слияние алгоритмов позволяет компилятору эффектовно оптимизировать использование регистров и памяти.
• Нет вызовов дополнительных методов (см. принцип 23 — Вызов функций, и 24 — Виртуальные функции)
От теории к практике
Для тестов я выбрал три подхода:
1) HashSet + ToUpperInvariant
2) HashSet + StringComparer.OrdinalIgnoreCase в качесте IEqualityComparer
3) Оптимизированный код — рабочий, а не демонстрационный как в статье.

program code

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.InteropServices;

namespace ConsoleApplication1
{
    partial class Program
    {
        #region Keywords 1 - ToUpperInvariant

        static HashSet<String> keywords1;

        static void InitKeywords1()
        {
            keywords1 = new HashSet<string>();
            keywords1.Add("ABSOLUTE");
            keywords1.Add("ACTION");
            keywords1.Add("ADA");
            keywords1.Add("ADD");
            keywords1.Add("ADMIN");
            keywords1.Add("AFTER");
            keywords1.Add("AGGREGATE");
            keywords1.Add("ALIAS");
            keywords1.Add("ALL");
            keywords1.Add("ALLOCATE");
            keywords1.Add("ALTER");
            keywords1.Add("AND");
            keywords1.Add("ANY");
            keywords1.Add("ARE");
            keywords1.Add("ARRAY");
            keywords1.Add("AS");
            keywords1.Add("ASC");
            keywords1.Add("ASENSITIVE");
            keywords1.Add("ASSERTION");
            keywords1.Add("ASYMMETRIC");
            keywords1.Add("AT");
            keywords1.Add("ATOMIC");
            keywords1.Add("AUTHORIZATION");
            keywords1.Add("AVG");
            keywords1.Add("BACKUP");
            keywords1.Add("BEFORE");
            keywords1.Add("BEGIN");
            keywords1.Add("BETWEEN");
            keywords1.Add("BIGINT");
            keywords1.Add("BINARY");
            keywords1.Add("BIT");
            keywords1.Add("BIT_LENGTH");
            keywords1.Add("BLOB");
            keywords1.Add("BOOLEAN");
            keywords1.Add("BOTH");
            keywords1.Add("BREADTH");
            keywords1.Add("BREAK");
            keywords1.Add("BROWSE");
            keywords1.Add("BULK");
            keywords1.Add("BY");
            keywords1.Add("CALL");
            keywords1.Add("CALLED");
            keywords1.Add("CARDINALITY");
            keywords1.Add("CASCADE");
            keywords1.Add("CASCADED");
            keywords1.Add("CASE");
            keywords1.Add("CAST");
            keywords1.Add("CATALOG");
            keywords1.Add("CHAR");
            keywords1.Add("CHAR_LENGTH");
            keywords1.Add("CHARACTER");
            keywords1.Add("CHARACTER_LENGTH");
            keywords1.Add("CHECK");
            keywords1.Add("CHECKPOINT");
            keywords1.Add("CLASS");
            keywords1.Add("CLOB");
            keywords1.Add("CLOSE");
            keywords1.Add("CLUSTERED");
            keywords1.Add("COALESCE");
            keywords1.Add("COLLATE");
            keywords1.Add("COLLATION");
            keywords1.Add("COLLECT");
            keywords1.Add("COLUMN");
            keywords1.Add("COMMIT");
            keywords1.Add("COMPLETION");
            keywords1.Add("COMPUTE");
            keywords1.Add("CONDITION");
            keywords1.Add("CONNECT");
            keywords1.Add("CONNECTION");
            keywords1.Add("CONSTRAINT");
            keywords1.Add("CONSTRAINTS");
            keywords1.Add("CONSTRUCTOR");
            keywords1.Add("CONTAINS");
            keywords1.Add("CONTAINSTABLE");
            keywords1.Add("CONTINUE");
            keywords1.Add("CONVERT");
            keywords1.Add("CORR");
            keywords1.Add("CORRESPONDING");
            keywords1.Add("COUNT");
            keywords1.Add("COVAR_POP");
            keywords1.Add("COVAR_SAMP");
            keywords1.Add("CREATE");
            keywords1.Add("CROSS");
            keywords1.Add("CUBE");
            keywords1.Add("CUME_DIST");
            keywords1.Add("CURRENT");
            keywords1.Add("CURRENT_CATALOG");
            keywords1.Add("CURRENT_DATE");
            keywords1.Add("CURRENT_DEFAULT_TRANSFORM_GROUP");
            keywords1.Add("CURRENT_PATH");
            keywords1.Add("CURRENT_ROLE");
            keywords1.Add("CURRENT_SCHEMA");
            keywords1.Add("CURRENT_TIME");
            keywords1.Add("CURRENT_TIMESTAMP");
            keywords1.Add("CURRENT_TRANSFORM_GROUP_FOR_TYPE");
            keywords1.Add("CURRENT_USER");
            keywords1.Add("CURSOR");
            keywords1.Add("CYCLE");
            keywords1.Add("DATA");
            keywords1.Add("DATABASE");
            keywords1.Add("DATE");
            keywords1.Add("DATETIME");
            keywords1.Add("DATETIME2");
            keywords1.Add("DATETIMEOFFSET");
            keywords1.Add("DAY");
            keywords1.Add("DBCC");
            keywords1.Add("DEALLOCATE");
            keywords1.Add("DEC");
            keywords1.Add("DECIMAL");
            keywords1.Add("DECLARE");
            keywords1.Add("DEFAULT");
            keywords1.Add("DEFERRABLE");
            keywords1.Add("DEFERRED");
            keywords1.Add("DELETE");
            keywords1.Add("DENY");
            keywords1.Add("DEPTH");
            keywords1.Add("DEREF");
            keywords1.Add("DESC");
            keywords1.Add("DESCRIBE");
            keywords1.Add("DESCRIPTOR");
            keywords1.Add("DESTROY");
            keywords1.Add("DESTRUCTOR");
            keywords1.Add("DETERMINISTIC");
            keywords1.Add("DIAGNOSTICS");
            keywords1.Add("DICTIONARY");
            keywords1.Add("DISCONNECT");
            keywords1.Add("DISK");
            keywords1.Add("DISTINCT");
            keywords1.Add("DISTRIBUTED");
            keywords1.Add("DOMAIN");
            keywords1.Add("DOUBLE");
            keywords1.Add("DROP");
            keywords1.Add("DUMP");
            keywords1.Add("DYNAMIC");
            keywords1.Add("EACH");
            keywords1.Add("ELEMENT");
            keywords1.Add("ELSE");
            keywords1.Add("END");
            keywords1.Add("END-EXEC");
            keywords1.Add("EQUALS");
            keywords1.Add("ERRLVL");
            keywords1.Add("ESCAPE");
            keywords1.Add("EVERY");
            keywords1.Add("EXCEPT");
            keywords1.Add("EXCEPTION");
            keywords1.Add("EXEC");
            keywords1.Add("EXECUTE");
            keywords1.Add("EXISTS");
            keywords1.Add("EXIT");
            keywords1.Add("EXTERNAL");
            keywords1.Add("EXTRACT");
            keywords1.Add("FALSE");
            keywords1.Add("FETCH");
            keywords1.Add("FILE");
            keywords1.Add("FILLFACTOR");
            keywords1.Add("FILTER");
            keywords1.Add("FIRST");
            keywords1.Add("FLOAT");
            keywords1.Add("FOR");
            keywords1.Add("FOREIGN");
            keywords1.Add("FORTRAN");
            keywords1.Add("FOUND");
            keywords1.Add("FREE");
            keywords1.Add("FREETEXT");
            keywords1.Add("FREETEXTTABLE");
            keywords1.Add("FROM");
            keywords1.Add("FULL");
            keywords1.Add("FULLTEXTTABLE");
            keywords1.Add("FUNCTION");
            keywords1.Add("FUSION");
            keywords1.Add("GENERAL");
            keywords1.Add("GEOGRAPHY");
            keywords1.Add("GEOMETRY");
            keywords1.Add("GET");
            keywords1.Add("GLOBAL");
            keywords1.Add("GO");
            keywords1.Add("GOTO");
            keywords1.Add("GRANT");
            keywords1.Add("GROUP");
            keywords1.Add("GROUPING");
            keywords1.Add("HAVING");
            keywords1.Add("HIERACHYID");
            keywords1.Add("HOLD");
            keywords1.Add("HOLDLOCK");
            keywords1.Add("HOST");
            keywords1.Add("HOUR");
            keywords1.Add("IDENTITY");
            keywords1.Add("IDENTITY_INSERT");
            keywords1.Add("IDENTITYCOL");
            keywords1.Add("IF");
            keywords1.Add("IGNORE");
            keywords1.Add("IMAGE");
            keywords1.Add("IMMEDIATE");
            keywords1.Add("IN");
            keywords1.Add("INCLUDE");
            keywords1.Add("INDEX");
            keywords1.Add("INDICATOR");
            keywords1.Add("INITIALIZE");
            keywords1.Add("INITIALLY");
            keywords1.Add("INNER");
            keywords1.Add("INOUT");
            keywords1.Add("INPUT");
            keywords1.Add("INSENSITIVE");
            keywords1.Add("INSERT");
            keywords1.Add("INT");
            keywords1.Add("INTEGER");
            keywords1.Add("INTERSECT");
            keywords1.Add("INTERSECTION");
            keywords1.Add("INTERVAL");
            keywords1.Add("INTO");
            keywords1.Add("IS");
            keywords1.Add("ISOLATION");
            keywords1.Add("ITERATE");
            keywords1.Add("JOIN");
            keywords1.Add("KEY");
            keywords1.Add("KILL");
            keywords1.Add("LANGUAGE");
            keywords1.Add("LARGE");
            keywords1.Add("LAST");
            keywords1.Add("LATERAL");
            keywords1.Add("LEADING");
            keywords1.Add("LEFT");
            keywords1.Add("LESS");
            keywords1.Add("LEVEL");
            keywords1.Add("LIKE");
            keywords1.Add("LIKE_REGEX");
            keywords1.Add("LIMIT");
            keywords1.Add("LINENO");
            keywords1.Add("LN");
            keywords1.Add("LOAD");
            keywords1.Add("LOCAL");
            keywords1.Add("LOCALTIME");
            keywords1.Add("LOCALTIMESTAMP");
            keywords1.Add("LOCATOR");
            keywords1.Add("LOWER");
            keywords1.Add("MAP");
            keywords1.Add("MATCH");
            keywords1.Add("MAX");
            keywords1.Add("MEMBER");
            keywords1.Add("MERGE");
            keywords1.Add("METHOD");
            keywords1.Add("MIN");
            keywords1.Add("MINUTE");
            keywords1.Add("MOD");
            keywords1.Add("MODIFIES");
            keywords1.Add("MODIFY");
            keywords1.Add("MODULE");
            keywords1.Add("MONEY");
            keywords1.Add("MONTH");
            keywords1.Add("MULTISET");
            keywords1.Add("NAMES");
            keywords1.Add("NATIONAL");
            keywords1.Add("NATURAL");
            keywords1.Add("NCHAR");
            keywords1.Add("NCLOB");
            keywords1.Add("NEW");
            keywords1.Add("NEXT");
            keywords1.Add("NO");
            keywords1.Add("NOCHECK");
            keywords1.Add("NOCOUNT");
            keywords1.Add("NONCLUSTERED");
            keywords1.Add("NONE");
            keywords1.Add("NORMALIZE");
            keywords1.Add("NOT");
            keywords1.Add("NTEXT");
            keywords1.Add("NULL");
            keywords1.Add("NULLIF");
            keywords1.Add("NUMERIC");
            keywords1.Add("NVARCHAR");
            keywords1.Add("OBJECT");
            keywords1.Add("OCCURRENCES_REGEX");
            keywords1.Add("OCTET_LENGTH");
            keywords1.Add("OF");
            keywords1.Add("OFF");
            keywords1.Add("OFFSETS");
            keywords1.Add("OLD");
            keywords1.Add("ON");
            keywords1.Add("ONLY");
            keywords1.Add("OPEN");
            keywords1.Add("OPENDATASOURCE");
            keywords1.Add("OPENQUERY");
            keywords1.Add("OPENROWSET");
            keywords1.Add("OPENXML");
            keywords1.Add("OPERATION");
            keywords1.Add("OPTION");
            keywords1.Add("OR");
            keywords1.Add("ORDER");
            keywords1.Add("ORDINALITY");
            keywords1.Add("OUT");
            keywords1.Add("OUTER");
            keywords1.Add("OUTPUT");
            keywords1.Add("OVER");
            keywords1.Add("OVERLAPS");
            keywords1.Add("OVERLAY");
            keywords1.Add("PAD");
            keywords1.Add("PARAMETER");
            keywords1.Add("PARAMETERS");
            keywords1.Add("PARTIAL");
            keywords1.Add("PARTITION");
            keywords1.Add("PASCAL");
            keywords1.Add("PATH");
            keywords1.Add("PERCENT");
            keywords1.Add("PERCENT_RANK");
            keywords1.Add("PERCENTILE_CONT");
            keywords1.Add("PERCENTILE_DISC");
            keywords1.Add("PIVOT");
            keywords1.Add("PLAN");
            keywords1.Add("POSITION");
            keywords1.Add("POSITION_REGEX");
            keywords1.Add("POSTFIX");
            keywords1.Add("PRECISION");
            keywords1.Add("PREFIX");
            keywords1.Add("PREORDER");
            keywords1.Add("PREPARE");
            keywords1.Add("PRESERVE");
            keywords1.Add("PRIMARY");
            keywords1.Add("PRINT");
            keywords1.Add("PRIOR");
            keywords1.Add("PRIVILEGES");
            keywords1.Add("PROC");
            keywords1.Add("PROCEDURE");
            keywords1.Add("PUBLIC");
            keywords1.Add("RAISERROR");
            keywords1.Add("RANGE");
            keywords1.Add("READ");
            keywords1.Add("READS");
            keywords1.Add("READTEXT");
            keywords1.Add("REAL");
            keywords1.Add("RECONFIGURE");
            keywords1.Add("RECURSIVE");
            keywords1.Add("REF");
            keywords1.Add("REFERENCES");
            keywords1.Add("REFERENCING");
            keywords1.Add("REGR_AVGX");
            keywords1.Add("REGR_AVGY");
            keywords1.Add("REGR_COUNT");
            keywords1.Add("REGR_INTERCEPT");
            keywords1.Add("REGR_R2");
            keywords1.Add("REGR_SLOPE");
            keywords1.Add("REGR_SXX");
            keywords1.Add("REGR_SXY");
            keywords1.Add("REGR_SYY");
            keywords1.Add("RELATIVE");
            keywords1.Add("RELEASE");
            keywords1.Add("REPLICATION");
            keywords1.Add("RESTORE");
            keywords1.Add("RESTRICT");
            keywords1.Add("RESULT");
            keywords1.Add("RETURN");
            keywords1.Add("RETURNS");
            keywords1.Add("REVERT");
            keywords1.Add("REVOKE");
            keywords1.Add("RIGHT");
            keywords1.Add("ROLE");
            keywords1.Add("ROLLBACK");
            keywords1.Add("ROLLUP");
            keywords1.Add("ROUTINE");
            keywords1.Add("ROW");
            keywords1.Add("ROWCOUNT");
            keywords1.Add("ROWGUIDCOL");
            keywords1.Add("ROWS");
            keywords1.Add("ROWVERSION");
            keywords1.Add("RULE");
            keywords1.Add("SAVE");
            keywords1.Add("SAVEPOINT");
            keywords1.Add("SCHEMA");
            keywords1.Add("SCOPE");
            keywords1.Add("SCROLL");
            keywords1.Add("SEARCH");
            keywords1.Add("SECOND");
            keywords1.Add("SECTION");
            keywords1.Add("SECURITYAUDIT");
            keywords1.Add("SELECT");
            keywords1.Add("SENSITIVE");
            keywords1.Add("SEQUENCE");
            keywords1.Add("SESSION");
            keywords1.Add("SESSION_USER");
            keywords1.Add("SET");
            keywords1.Add("SETS");
            keywords1.Add("SETUSER");
            keywords1.Add("SHUTDOWN");
            keywords1.Add("SIMILAR");
            keywords1.Add("SIZE");
            keywords1.Add("SMALLDATETIME");
            keywords1.Add("SMALLINT");
            keywords1.Add("SMALLMONEY");
            keywords1.Add("SOME");
            keywords1.Add("SPACE");
            keywords1.Add("SPECIFIC");
            keywords1.Add("SPECIFICTYPE");
            keywords1.Add("SQL");
            keywords1.Add("SQL_VARIANT");
            keywords1.Add("SQLCA");
            keywords1.Add("SQLCODE");
            keywords1.Add("SQLERROR");
            keywords1.Add("SQLEXCEPTION");
            keywords1.Add("SQLSTATE");
            keywords1.Add("SQLWARNING");
            keywords1.Add("START");
            keywords1.Add("STATE");
            keywords1.Add("STATEMENT");
            keywords1.Add("STATIC");
            keywords1.Add("STATISTICS");
            keywords1.Add("STDDEV_POP");
            keywords1.Add("STDDEV_SAMP");
            keywords1.Add("STRUCTURE");
            keywords1.Add("SUBMULTISET");
            keywords1.Add("SUBSTRING");
            keywords1.Add("SUBSTRING_REGEX");
            keywords1.Add("SUM");
            keywords1.Add("SYMMETRIC");
            keywords1.Add("SYSNAME");
            keywords1.Add("SYSTEM");
            keywords1.Add("SYSTEM_USER");
            keywords1.Add("TABLE");
            keywords1.Add("TABLESAMPLE");
            keywords1.Add("TEMPORARY");
            keywords1.Add("TERMINATE");
            keywords1.Add("TEXT");
            keywords1.Add("TEXTSIZE");
            keywords1.Add("THAN");
            keywords1.Add("THEN");
            keywords1.Add("TIME");
            keywords1.Add("TIMESTAMP");
            keywords1.Add("TIMEZONE_HOUR");
            keywords1.Add("TIMEZONE_MINUTE");
            keywords1.Add("TINYINT");
            keywords1.Add("TO");
            keywords1.Add("TOP");
            keywords1.Add("TRAILING");
            keywords1.Add("TRAN");
            keywords1.Add("TRANSACTION");
            keywords1.Add("TRANSLATE");
            keywords1.Add("TRANSLATE_REGEX");
            keywords1.Add("TRANSLATION");
            keywords1.Add("TREAT");
            keywords1.Add("TRIGGER");
            keywords1.Add("TRIM");
            keywords1.Add("TRUE");
            keywords1.Add("TRUNCATE");
            keywords1.Add("TSEQUAL");
            keywords1.Add("UESCAPE");
            keywords1.Add("UNDER");
            keywords1.Add("UNION");
            keywords1.Add("UNIQUE");
            keywords1.Add("UNIQUEIDENTIFIER");
            keywords1.Add("UNKNOWN");
            keywords1.Add("UNNEST");
            keywords1.Add("UNPIVOT");
            keywords1.Add("UPDATE");
            keywords1.Add("UPDATETEXT");
            keywords1.Add("UPPER");
            keywords1.Add("USAGE");
            keywords1.Add("USE");
            keywords1.Add("USER");
            keywords1.Add("USING");
            keywords1.Add("VALUE");
            keywords1.Add("VALUES");
            keywords1.Add("VAR_POP");
            keywords1.Add("VAR_SAMP");
            keywords1.Add("VARBINARY");
            keywords1.Add("VARCHAR");
            keywords1.Add("VARIABLE");
            keywords1.Add("VARYING");
            keywords1.Add("VIEW");
            keywords1.Add("WAITFOR");
            keywords1.Add("WHEN");
            keywords1.Add("WHENEVER");
            keywords1.Add("WHERE");
            keywords1.Add("WHILE");
            keywords1.Add("WIDTH_BUCKET");
            keywords1.Add("WINDOW");
            keywords1.Add("WITH");
            keywords1.Add("WITHIN");
            keywords1.Add("WITHOUT");
            keywords1.Add("WORK");
            keywords1.Add("WRITE");
            keywords1.Add("WRITETEXT");
            keywords1.Add("XML");
            keywords1.Add("XMLAGG");
            keywords1.Add("XMLATTRIBUTES");
            keywords1.Add("XMLBINARY");
            keywords1.Add("XMLCAST");
            keywords1.Add("XMLCOMMENT");
            keywords1.Add("XMLCONCAT");
            keywords1.Add("XMLDOCUMENT");
            keywords1.Add("XMLELEMENT");
            keywords1.Add("XMLEXISTS");
            keywords1.Add("XMLFOREST");
            keywords1.Add("XMLITERATE");
            keywords1.Add("XMLNAMESPACES");
            keywords1.Add("XMLPARSE");
            keywords1.Add("XMLPI");
            keywords1.Add("XMLQUERY");
            keywords1.Add("XMLSERIALIZE");
            keywords1.Add("XMLTABLE");
            keywords1.Add("XMLTEXT");
            keywords1.Add("XMLVALIDATE");
            keywords1.Add("YEAR");
            keywords1.Add("ZONE");
        }

        static bool IsKeyword1(String tokenText)
        {
            return keywords1.Contains(tokenText.ToUpperInvariant());
        }

        #endregion

        #region Keywords 2 - StringComparer

        static HashSet<String> keywords2;

        static void InitKeywords2()
        {
            keywords2 = new HashSet<string>(keywords1, StringComparer.OrdinalIgnoreCase);
        }

        static bool IsKeyword2(String tokenText)
        {
            return keywords2.Contains(tokenText);
        }

        #endregion

        #region Keywords 3 - Good optimized

        static IntPtr gpCaseMapping;
        static IntPtr gpKeywords3;

        unsafe static void InitKeywords3()
        {
            gpKeywords3 = Marshal.AllocCoTaskMem(1293 * 4 * 4);
            int* pHashset3 = (int*)gpKeywords3;
            for (int i = 0; i < 1293 * 4; i++)
                pHashset3[i] = 0;
            foreach (String keyword in keywords1)
            {
                fixed (char* pKeyword = keyword)
                {
                    int hashCode = keyword.GetHashCode();
                    int index = (int)(((uint)hashCode % 1293) << 2);
                    if (pHashset3[index] != 0)
                        index += 2;
                    if (pHashset3[index] != 0)
                        throw new Exception("Solve the collision.");
                    pHashset3[index] = hashCode;
                    pHashset3[index + 1] = (int)pKeyword[0] | ((int)pKeyword[1] << 8) | ((int)pKeyword[2] << 16) | ((int)pKeyword[3] << 24);
                }
            }

            gpCaseMapping = Marshal.AllocCoTaskMem(65536);
            byte* pCaseMapping = (byte*)gpCaseMapping;
            for (int i = 0; i < 65536; i++)
                pCaseMapping[i] = 0;
            for (int i = 'A'; i <= 'Z'; i++)
                pCaseMapping[i] = (byte)i;
            for (int i = 'a'; i <= 'z'; i++)
                pCaseMapping[i] = (byte)(i ^ 0x20);
            pCaseMapping['2'] = (byte)'2';
            pCaseMapping['-'] = (byte)'-';
            pCaseMapping['_'] = (byte)'_';
        }

        unsafe static bool IsKeyword3(String tokenText)
        {
            unchecked
            {
                fixed (char* pString = tokenText)
                {
                    byte* pCaseMapping = (byte*)gpCaseMapping;

                    int num1 = 5381;
                    int num2 = num1;
                    int c1;
                    int c2;
                    char* ptr = pString;
                    int seq = 0;

                    if (tokenText.Length >= 4)
                    {
                        c1 = (int)(*(ushort*)ptr);
                        c2 = (int)(*(ushort*)(ptr + 1));
                        c1 = pCaseMapping[c1];
                        c2 = pCaseMapping[c2];
                        if (c1 == 0 || c2 == 0)
                            return false;
                        seq = (c2 << 8) | c1;
                        num1 = ((num1 << 5) + num1 ^ c1);
                        num2 = ((num2 << 5) + num2 ^ c2);
                        ptr += 2;

                        c1 = (int)(*(ushort*)ptr);
                        c2 = (int)(*(ushort*)(ptr + 1));
                        c1 = pCaseMapping[c1];
                        c2 = pCaseMapping[c2];
                        if (c1 == 0 || c2 == 0)
                            return false;
                        seq |= (c2 << 24) | (c1 << 16);
                        num1 = ((num1 << 5) + num1 ^ c1);
                        num2 = ((num2 << 5) + num2 ^ c2);
                        ptr += 2;

                        for (int loops = (tokenText.Length >> 1) - 2; loops > 0; loops--, ptr += 2)
                        {
                            c1 = (int)(*(ushort*)ptr);
                            c2 = (int)(*(ushort*)(ptr + 1));
                            c1 = pCaseMapping[c1];
                            c2 = pCaseMapping[c2];
                            if (c1 == 0 || c2 == 0)
                                return false;
                            num1 = ((num1 << 5) + num1 ^ c1);
                            num2 = ((num2 << 5) + num2 ^ c2);
                        }

                        if ((tokenText.Length & 1) != 0)
                        {
                            c1 = (int)(*(ushort*)ptr);
                            c1 = pCaseMapping[c1];
                            if (c1 == 0)
                                return false;
                            num1 = ((num1 << 5) + num1 ^ c1);
                        }
                    }
                    else if (tokenText.Length == 3)
                    {
                        c1 = (int)(*(ushort*)ptr);
                        c2 = (int)(*(ushort*)(ptr + 1));
                        c1 = pCaseMapping[c1];
                        c2 = pCaseMapping[c2];
                        if (c1 == 0 || c2 == 0)
                            return false;
                        seq = (c2 << 8) | c1;
                        num1 = ((num1 << 5) + num1 ^ c1);
                        num2 = ((num2 << 5) + num2 ^ c2);

                        c1 = (int)(*(ushort*)(ptr + 2));
                        c1 = pCaseMapping[c1];
                        if (c1 == 0)
                            return false;
                        seq |= (c1 << 16);
                        num1 = ((num1 << 5) + num1 ^ c1);
                    }
                    else if (tokenText.Length == 2)
                    {
                        c1 = (int)(*(ushort*)ptr);
                        c2 = (int)(*(ushort*)(ptr + 1));
                        c1 = pCaseMapping[c1];
                        c2 = pCaseMapping[c2];
                        if (c1 == 0 || c2 == 0)
                            return false;
                        seq = (c2 << 8) | c1;
                        num1 = ((num1 << 5) + num1 ^ c1);
                        num2 = ((num2 << 5) + num2 ^ c2);
                        ptr += 2;
                    }
                    else
                    {
                        return false;
                    }

                    int hashCode = num1 + num2 * 1566083941;
                    int index = (int)(((uint)hashCode % 1293) << 2);
                    int* pHashset3 = (int*)gpKeywords3;
                    return (pHashset3[index + 0] == hashCode && pHashset3[index + 1] == seq)
                        || (pHashset3[index + 2] == hashCode && pHashset3[index + 3] == seq);
                }
            }
        }

        #endregion

        #region Test Data

        static String[] TestTokens = new String[] {
"DECLARE", "@lang", "sysname",
"SELECT", "TOP", "@lang", "Alias", "FROM", "sys", "syslanguages", "WHERE", "lcid",
"IF", "@lang", "IS", "NOT", "NULL", "SET", "LANGUAGE", "@lang",
"SET", "ARITHABORT", "ANSI_PADDING", "ANSI_WARNINGS", "QUOTED_IDENTIFIER",
"NOCOUNT", "CONCAT_NULL_YIELDS_NULL", "ANSI_NULLS", "ON",
"SET", "NUMERIC_ROUNDABORT", "IMPLICIT_TRANSACTIONS", "XACT_ABORT", "OFF",
"SET", "DATEFORMAT", "dmy",
"USE", "AdventureWorks2008R2",
"GO",
"INSERT", "Sales", "SalesOrderHeader", "SalesOrderID", "RevisionNumber", "OrderDate", "DueDate", "ShipDate",
"Status", "OnlineOrderFlag", "PurchaseOrderNumber", "AccountNumber", "CustomerID", "SalesPersonID", "TerritoryID",
"BillToAddressID", "ShipToAddressID", "ShipMethodID", "CreditCardID", "CreditCardApprovalCode", "CurrencyRateID",
"SubTotal", "TaxAmt", "Freight", "Comment", "rowguid", "ModifiedDate", "VALUES",
"ALTER", "TABLE", "dbo", "DatabaseLog", "ADD", "CONSTRAINT", "PK_DatabaseLog_DatabaseLogID", "PRIMARY", "KEY", "NONCLUSTERED",
"DatabaseLogID", "ASC", "WITH", "DATA_COMPRESSION", "NONE",
"EXEC", "sp_addextendedproperty", "dbo", "DatabaseLog", "PK_DatabaseLog_DatabaseLogID",
"GO", "IF", "@@ERROR", "OR", "TRANCOUNT", "BEGIN", "IF", "@@TRANCOUNT", "ROLLBACK", "SET", "NOEXEC", "ON", "END",
"GO", "DBCC", "CHECKIDENT", "RESEED", "GO", "IF", "@@ERROR", "@@TRANCOUNT", "BEGIN", "IF", "@@TRANCOUNT", "ROLLBACK", "SET", "NOEXEC", "ON", "END", "GO"
            };

        #endregion

        #region Timing

        static long _timestamp;

        static void StartTiming()
        {
            _timestamp = Stopwatch.GetTimestamp();
        }

        static double EndTiming()
        {
            return (double)(Stopwatch.GetTimestamp() - _timestamp) / (double)Stopwatch.Frequency;
        }

        #endregion

        unsafe static void DoLexerTests()
        {
            int testCount = 100000;
            int matchCount = 0;
            double time;

            // Test 1
            InitKeywords1();
            StartTiming();
            for (int t = testCount; t > 0; t--)
            {
                matchCount = 0;
                for (int i = 0; i < TestTokens.Length; i++)
                {
                    String identifier = TestTokens[i];
                    if (IsKeyword1(identifier))
                        matchCount++;
                }
            }
            time = EndTiming();
            Console.WriteLine("Test 1 - ToUpper");
            Console.WriteLine("Time:    " + time);
            Console.WriteLine("Matches: " + matchCount);
            Console.WriteLine();

            // Test 2
            InitKeywords2();
            StartTiming();
            for (int t = testCount; t > 0; t--)
            {
                matchCount = 0;
                for (int i = 0; i < TestTokens.Length; i++)
                {
                    String identifier = TestTokens[i];
                    if (IsKeyword2(identifier))
                        matchCount++;
                }
            }
            time = EndTiming();
            Console.WriteLine("Test 2 - StringComparer");
            Console.WriteLine("Time:    " + time);
            Console.WriteLine("Matches: " + matchCount);
            Console.WriteLine();

            // Test 3
            InitKeywords3();
            StartTiming();
            for (int t = testCount; t > 0; t--)
            {
                matchCount = 0;
                for (int i = 0; i < TestTokens.Length; i++)
                {
                    String identifier = TestTokens[i];
                    if (IsKeyword3(identifier))
                        matchCount++;
                }
            }
            time = EndTiming();
            Console.WriteLine("Test 3 - Optimized Code");
            Console.WriteLine("Time:    " + time);
            Console.WriteLine("Matches: " + matchCount);
            Console.WriteLine();
        }
    }
}

Запускаем, и получаем такие результаты по времени выполнения (на моей машине):

Имя подхода	Время выполнения
ToUpperInvariant	2330 мс
IEqualityComparer	661 мс
Оптимизированный код	239 мс

Вывод
C ToUpperInvariant я действительно погорячился, представляя его в статье — метод действительно оказался очень отвратным, но это можно было проверить только опытным путём. И это в очередной раз подтверждает вредность создания новых объектов и неиспользования слияния алгоритмов, которое с большой вероятностью есть в недрах .NET Framework (или Windows).
А вот оптимизированный код работает почти в 3 раза быстрее, чем StringComparer, что доказывает эффективность принципов оптимизации. И стоит учесть, что потроха StringComparer'а написаны на C++, а не C#, что даёт большое преимущество в производительности. Вы можете начать закидывать меня гнилыми помидорами, опираясь на то, что код вообще нечитабелен и непонятен, да разница в 400 миллисекунд никому не нужна. Но у меня есть контраргументы:
• Принцип N3 — микрозадержки. В основном, все берут интервал для профилирования очень короткий. Думайте глобальнее — если функция экономит 400мс в час, то это будет экономия одного часа в год. И это всего одна функция. Возьмите десять подобных функций — это уже 10 часов. Любое ПО состоит далеко не из 10 функций, и масштаб сэкономленного времени может быть колоссальный.
• Как следствие из предыдущего пункта, чем быстрее работает ПО, тем меньше оно требует энергии. А это это может сильно продлить жизнь аккумулятора мобильного устройства.
• Есть некоторые вещи, которые требуют быстрого отклика. Когда вы печатаете текст, или водите польцем по тач-скрину, вы ожидаете мгновенного отклика. А если он будет слишком большой, в несколько десятков миллисекунд, то вас это может начать раздражать. В таких местах крайне важно хорошо оптимизировать код, чтобы дать пользователь почувствовал «отзывчивый интерфейс». Особо хорошо замечают этот эффект профессиональные геймеры и спортсмены, у которых выше зрительная и моторная реакция, чем у среднестатистического человека. Синтаксический разбор кода как раз относится к таким задачам, например для IntelliSense. Также все не любят ждать, пока проект скомпилируется, но вначале код программы необходимо синтаксически разобрать…
• Насчёт поддержки и развития кода — насколько часто прийдётся менять функцию проверки токена на ключевое слово? Скорее всего, прийдётся просто добавлять новые ключевые слова с выходом новых версий SQL Server, которые не такие уж и частые.
• И самое главное, процетирую самого себя:

я просто хочу показать, как можно делать простые вещи сложно, но очень эффективно

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