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

performanceЯ поделюсь 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, которые не такие уж и частые.
• И самое главное, процетирую самого себя:
я просто хочу показать, как можно делать простые вещи сложно, но очень эффективно

Никто вас не заставляет следовать перечисленным правилам, да и вообще они не нужны для большинства приложений (неоднократно упоминаю «оптимизации для высокопроизводительных приложений, которые этого требуют»). Если вы не работали в области высокопроизводительных приложений, не надо бить себя в грудь заявляя что материал — «ересь», а уж тем более что компилиятор или ОС знает все алгоритмы и оптимизации на все случае жизни, и сделает всё за вас.
Поделиться публикацией
Ммм, длинные выходные!
Самое время просмотреть заказы на Фрилансим.
Мне повезёт!
Реклама
Комментарии 289
  • +8
    Пункт 5 про if для простых арифметических операций некорректен.

    Точнее, когда-то давно всё было действительно так, но тот же x86 давно поддерживает инструкции CMOVxx (conditional move), которые не приводят к сбрасыванию конвейера, в отличие от инструкций переходов, и выполняются быстро. В результате, например, конструкция условного вида max(a, b) { if (a > b) { return a } else { return b } } выполняется примерно вдвое быстрее её аналога без if. Хотя раньше подобная оптимизация имела бы смысл. Не далее как вчера это проверял :)
    • +3
      Не могу не согласится насчёт CMOVxx, но не забывайте что статья про C# — здесь код компилируется в IL, а потом в инструкции (причём JIT должен делать это быстро). Будет ли там CMOV — нужно смотреть от случая к случаю.
      Насчёт примера «int CompareBytes(byte a, byte b)», я проверял на практике при написании статьи — на моей машине работало ровно в 2 раза быстрее, не обманываю :) А если с CMOV — ещё раз этак в 2,5 быстрее (точно уже не помню). Поэтому и написал «определённых местах может», а не «всегда будет лучше» :)
      • +2
        Это говорит не в пользу C# :) Я это проверял на JVM и просто на коде на Си и в обоих случаях всё заканчивалось именно CMOVxx. Причём, с точки зрения разработки компилятора (в том числе и JIT) оптимизация короткого if'а в CMOVxx есть куда более тривиальная задача, чем оптимизация арифметического аналога.
      • 0
        Линус считает, что CMOV не очень хорош.
      • 0
        «в % раз быстрее» — это как? Оо
        • 0
          Вместо "%" подставляете число в колонке. Это лучшее сокращение, которое я мог придумать для названия :)
          • 0
            Как насчет X?
            • +5
              Ну вы уже знаете, что такое "%", зачем вам «Х»? :)
              • 0
                Что бы те, кто ещё не до читал до комментов, не перечитывали по три раза заголовок столбца, например?
                • –3
                  Надо устроить опрос «Кому понятно что такое % ?». Неужели «X» внесёт ясность? :)
                  • +3
                    Ясность внесёт «во сколько раз быстрее». X, по крайней мере, не напоминает о процентах.
        • +17
          >Никаких «foreach»
          Неверно, foreach для массивов генерирует такой IL который потом 100% оптимизируется GIT копилятором. Можно написать такой код руками, но многие ли знают условия при которых сработает оптимизатор?

          >эта конструкция создаёт экземпляр класса, который реализует интерфейс IEnumerable
          И это тоже не верно. Он создает объект/структуру который возвращает метод GetEnumerator, и это не обязательно должен быть класс реализующий IEnumerable. Только с аналогичной сигнатурой. Такой вот duck typing.

          >Единственный способ избежать этих проверок, написать «for» таким образом
          И опять неправильный пример. Переменная с массивом должна быть локальной и неизменяемой.

          >volatile
          igoro.com/archive/volatile-keyword-in-c-memory-model-explained/

          >Структуры, поля которых – только value types, легко сериализовать в массив байт и обратно.
          Так делать нельзя по двум причинам:
          а) это валидно только для blittable типов
          б) разное выравнивание структур на разных архитектурах

          в остальном у вас хорошие, годные советы.
          • –4
            >Никаких «foreach»
            Зачем надеятся на оптимизацию при каких-то условиях, если можно руками чётко написать именно то, что хочешь. Тем более, JIT compiler может быть разный (для Windows, XBox, Linux, и пр.) от разных производителей. Кто сказал что все они одинаково работают?

            >эта конструкция создаёт экземпляр класса, который реализует интерфейс IEnumerable
            Вы неправильно поняли пункт. Это уже уточнения как можно использовать «foreach». Смысл в том, что в итоге у вас всё-равно 2 метода: MoveNext и Current. Именно об вызове методов я писал, ссылаясь на пункт 23 (я в тексте ссылаюсь на 24, сейчас исправлю, простите).

            >Единственный способ избежать этих проверок, написать «for» таким образом
            Вы ссылку смотрели на блог от Microsoft на словах «таким образом»? Там детально объясняется как можно. Что ж здесь неверного?

            >volatile
            Это детальное разъяснение к описанию? Не совсем понял.

            >Структуры, поля которых – только value types, легко сериализовать в массив байт и обратно.
            Почему нельзя? Туда можно ещё приписать Big/Little Endian, но всё это проблемы характерные для конкретных задач, о которых не шла речь. Если использовать такой подход для какого-нибудь временного кэша, то почему нельзя?

            Я везде пытался как можно проще и короче пояснить основную суть, не вдаваясь в детали (а их очень много), о чём честно предупредил в начале статьи :)
            • +8
              Зачем надеятся на оптимизацию при каких-то условиях, если можно руками чётко написать именно то, что хочешь

              Но ваше «руками чётко написать», будет почти всегда хуже того кода который генерирует компилятор foreach по массиву, и всегда хуже по читабельности. И в довесок сгенерированный компилятором код будет оптимизирован в .NET Framework, скорее всего и в моно.
              Итого, foreach это не всегда зло, что противоположно вашему «Никаких foreach»

              MoveNext и Current

              Они не виртуальные и могут принадлежать структуре. т.е. нет будет замусоривания GC и лишней нагрузки от виртуальных методов. Единственный оверхед который можно учитывать это слежение за версией коллекции. Что может быть и плюсом.

              Вы ссылку смотрели на блог от Microsoft на словах «таким образом»

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

              Это детальное разъяснение к описанию?

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

              Почему нельзя?

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

          • +4
            А можно не рассказывать про foreach такие страшилки про IEnumerable. Оно там ни разу не объязательное.
            Это разжевывалось много раз. Вот еще один разок stackoverflow.com/questions/3679805/how-does-foreach-call-getenumerator-via-ienumerable-reference-or-via.

            • +2
              Иногда код упрощается не от незнания или неумения, а для простоты чтения и восприятия разработчиками. В общем, везде должен быть баланс, углубляться в в совсем уж жесткую оптимизацию и канонические правила разработки может привести к тому, что кд станет просто нк читабельным. Тем более, что благо сейчас системы мощные и часто выигрыш в производительности не всегда оправдывается затраченным на его цену временем разработчика.
            • +36
              Начните с … 1. Хороший алгоритм.

              Нет, начинать надо с того, что определить, где именно у вас боттлнек (и есть ли он вообще).

              В данном примере метод «PrintInternal» вызывается только из метода «Print», где уже есть проверка. Это значит, что вторая такая же проверка не только не имеет смысла, но и негативно влияет на производительность.

              Вторая такая проверка имеет смысл, потому что один и тот же код регулярно пишут разные люди. Другое дело, что, поскольку это находится внутри безопасной зоны, это должен быть не if, а Debug.Assert, который по очевидным причинам не влияет на скорость релизного кода. Более общий случай — все покрыть Code Contracts, а в рерайтере для релизной версии оставить проверки только на public surface.

              Никаких «foreach» – эта конструкция создаёт экземпляр класса, который реализует интерфейс IEnumerable (чем плохо, описано в принципах 16 и 24).

              Во-первых, «никаких foreach» — это уже смешно, большая часть кода внутри BCL построена на foreach, особенно в части доступа к данным. А уж весь LINQ без этого просто невозможен.

              Во-вторых, смотрим в принципы 16 («Структуры, а не классы») и 24 («Виртуальные функции»). Не знаю, при чем тут виртуальные функции, а вот в части принципа 16 вы не правы. Во-первых, экземпляр IEnumerable не создается, а используется. Наверное, вы имели в виду IEnumerator? Так нет, это тоже не так, потому что это не обязан быть класс, а может быть и структура (что регулярно используется внутри BCL), и она не обязана реализовывать IEnumerator. Так что оба ваших принципа тут не при чем. Подробности — у Липперта.

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

              Вы про TPL слышали?

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


              … а про Producer/Consumer и TPL Dataflow?

              Для устранения этих задержек достаточно создать свой класс Stream, который накапливает данные в буфер, а потом ставит его в очередь на запись в отдельном потоке. [...] А для конечного пользователя это будет тот же прозрачный интерфейс класса Stream.

              Извините, но у Stream есть сразу два интерфейса — синхронный и асинхронный. И «прозрачно» подменять синхронный асинхронным нельзя, потому что сразу появляются неожиданные ошибки.

              У структур есть ряд преимуществ перед классами

              Во-первых, не все они корректны (в частности, структура не обязательно хранится на стеке). Во-вторых, давно уже написано: используйте структуры только в том случае, если вы очень хорошо понимаете, что делаете. В частности, не используйте mutable struct (как и вообще mutable value types), потому что это приводит к трудно отлавливаемым багам. Собственно, вот хороший ответ про это.

              Поэтому в таких языках, как C++ есть модификатор метода inline, который указывает компилятору, что тело метода необходимо вставить в вызывающий метод. Правда, и в .NET Framework только с версии 4.5 наконец-то можно делать inline методы.

              А вы не в курсе, что в .net компилятор сам делает инлайнинг методов, если это возможно? И существенно раньше, чем в 4.5?

              Приведу реальный пример, SqlDataReader в методе GetValue для колонки с типом данных «xml» в конечном итоге вернёт вам String либо XmlReader. А задача состоит в том, чтобы сравнить два значения типа «xml» из двух разных источников. Вроде бы ничего особенного – взял да и сравнил две строки, да ещё можно использовать StringComparison.Oridnal чтоб вообще быстро было.

              Ну вообще — нет. xml нельзя сравнивать как строки, у него свои алгоритмы нормализации и каноникализации. И уж тем более — как байтовые массивы, которые приходят из БД. Не надо нарушать семантику.

              Организовать список всех ключевых слов проще всего в Hashset. Тогда, чтоб проверить является ли токен ключевым словом, достаточно написать:

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

              Про new HashSet<T>(IEqualityComparer<T>) вы не в курсе?

              Ну и так далее.

              В общем, возвращаясь к началу: сначала надо найти боттлнек. Потом оптимизировать его стандартными средствами платформы. И только потом заниматься битьем в бубен.
              • –21
                Можете рассуждать сколь угодно в рамках своих познаний, но всё работает на практике, причём есть реальное приложение, которое работает лучше всех. Всё было кропотливо проверено за 3 года работы в этой области. А вы лично проверяли то, о чём сейчас написали? Есть доказательства высокопроизводительных приложений?
                • +18
                  есть реальное приложение, которое работает лучше всех

                  Не «лучше всех», а в лучшем случае «быстрее всех». Да и то не факт.

                  Всё было кропотливо проверено за 3 года работы в этой области.

                  Утверждение с новым экземпляром IEnumerable — тоже? А доказать вы его можете? Для любого использования foreach?

                  А вы лично проверяли то, о чём сейчас написали?

                  Да.

                  PS Сперва добейся?
                  • +2
                    Ну вообще, у lair есть кое-какая репутация на хабре.
                    И в добавок я могу подтвердить его пост.
                    Есть доказательства высокопроизводительных приложений?

                    senchadotnet.codeplex.com
                    там есть JSON сериализатор, tip ревизия делает популярный JSON.NET на 15-20% по производительности. Тест внутренний, но довольно простой: сериализуется один и тот же большой объект, сериализатору дают генератор(yield) и пишет он в Null поток. В этом проекте полно оптимизаций, вплоть до генерации IL для сериализации конктретных объектов.

                    Причем как и написал lair в первую очередь был запущен профайлер, и потом уже пошли фиксы.
                  • 0
                    Хочу не согласиться про XML. Поскольку речь идет о синхронизации/клонировании/репликации данных, то побайтовое сравнение перед полным сравнением имеет смысл. Контекст использования определяет валидность этой оптимизации. На основе этого сравнения можно сделать очень быстрый вывод о равенстве. А для вывода о неравенстве уже полное сравнение. Кстати это сравнение схоже со сравнением хэша во всяких HashSet, HashTable и т.п., только там наоборот, сравнение хэша может дать вывод неравенства, а для вывода равенства нужна полная проверка.
                    Мне больше интересно, почему никто на «поверьте, коллизий не будет» не обращает внимания. Вот это точно оптимизация за гранью приличий. Что тем более с применением оптимизаций с индексированием и асинхронным разбором теряет смысл.
                    • +2
                      Хочу не согласиться про XML. Поскольку речь идет о синхронизации/клонировании/репликации данных, то побайтовое сравнение перед полным сравнением имеет смысл

                      Нет. Потому что байтовое представление xml внутри колонки соответствующего типа — это личное дело SQL Server, и оно имеет право отличаться между двумя инстансами.

                      Сравнивать нужно именно семантическое представление данных. Если мы храним данные как xml (т.е., разобранное), значит, нам интересно именно дерево (более того, SQL может возвращать разные варианты строкового представления этого дерева в разных случаях); а если бы нам было интересно именно строковое представление (например, для некоторых видов ЭЦП), то надо было бы хранить nvarchar.

                      Мне больше интересно, почему никто на «поверьте, коллизий не будет» не обращает внимания.

                      Я обратил. Но поскольку я вообще всю эту оптимизацию считаю ересью (а делать надо через свою реализацию сравнения), я не стал на этом заострять.
                      • –3
                        Нет. Потому что байтовое представление xml внутри колонки соответствующего типа — это личное дело SQL Server, и оно имеет право отличаться между двумя инстансами.

                        Т.е. вы утверждаете, что два одинаковых массива байт могут представлять различные XML данные? Вот это новость!

                        Но поскольку я вообще всю эту оптимизацию считаю ересью...

                        Мне нечего сказать, кроме как «Статья явно не для Вас». Вы даже не проверяли ни капли сказанного (ну и не будете — зачем это вам надо), а заявляете что это ересь. Ваши выводы основываются на субъективной оценке, и не несут никакой пользы.
                        • +4
                          Т.е. вы утверждаете, что два одинаковых массива байт могут представлять различные XML данные?

                          Нет, я утверждаю, что два разных массива байт могут представлять одни и те же xml-данные.

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

                          Во-первых, вы не можете доказать, что я проверял, а что нет (равно как и не можете доказать своих собственных слов, смотри пример с экземпляром IEnumerable). А во-вторых, это вы зачем-то предлагаете в качестве бейзлайна вариант с string.ToUpperInvariant (и расписываете его недостатки), хотя любому грамотному программисту известно, что использовать надо вариант со своим компарером (в котором могут быть любые оптимизации, в том числе и ваш код). И только если это окажется медленно, надо брать ваш вариант и сравнивать производительность.

                          Вот это — объективно.
                          • –1
                            Нет, я утверждаю, что два разных массива байт могут представлять одни и те же xml-данные.

                            Хорошо, значит, два идентичных массива байт представляют один и тот же XML. Почему тогда нельзя сравнивать два массива байт? Объясните?
                            Ну а если массивы разные — то будет сравниваться структура XML — об этом написано в статье. Вы думаете о чём пишете?

                            хотя любому грамотному программисту известно, что использовать надо вариант со своим компарером

                            Да будет известно грамотному программисту, что перечисление StringComparison содержит 6 значений, и у каждого есть своё применение. А то что вы пишете «использовать надо вариант» — за это надо наказывать программистов, если они лепят это везде. И если вы ознакомитесь со стандартом Unicode, сравнением строк (string collation algorithm), то тогда вы поймёте о чём всё же я писал…
                            • 0
                              Ну а если массивы разные — то будет сравниваться структура XML — об этом написано в статье. Вы думаете о чём пишете?

                              Да, думаю. Во-первых, я не уверен, что это предложение изначально было в статье. Но даже если было — вы тем самым делаете два сравнения вместо одного, что очень выгодно на xml в пару десятков мегабайт.

                              Да будет известно грамотному программисту, что перечисление StringComparison содержит 6 значений

                              А при чем тут вообще StringComparison, если я говорю о компарерах? Я ведь не зря привел сигнатуру конструктора (new HashSet<T>(IEqualityComparer<T>)). Что характерно, там есть и сам алгоритм сравнения объектов (где можно ничего нового не создавать и использовать произвольную математику), и алгоритм расчета хэш-кодов. И именно так реализуются «нестандартные» хэшсеты, а не написанием своего внешнего метода — программист продолжать видеть, что он работает с привычным ему хэшсетом, но логика сравнения внутри оптимизируется.

                              Это как раз пример типичного велосипедостроения без желания внимательно прочитать документацию (даже в исходники лезть не надо).
                              • 0
                                Два сравнения вместо одного, это да, несомненно. Также, как и при поиске объектов в хэшсете, сначала сравнивается хэш, потом сам объект, сравнения тоже два.
                                Побайтовое сравнение этак в десяток раз быстрее, чем полное(навскидку).
                                Если есть 1000 пар xml-ек, из которых сотня была изменена со времени последней синхронизации, то вместо 1000 единиц времени, мы получим, что 900, оставшись неизменными, ускорились в 10 раз, то есть 90 условных единиц времени, а 100 оставшихся замедлились на 10%, то есть итого 200 единиц времени вместо 1000.
                                Плюс к этому, в изменившихся xml файлах вероятность того, что изменился и размер тоже — почти 100%, то есть побайтовая проверка займет околонулевое время, и перейдет сразу к полной проверке.
                                Итого худший случай — замедление на 10%, лучший случай — ускорение в 10 раз. Как мне кажется все же такая оптимизация имеет смысл. Правда, конечно же, надо сделать замеры на средневзятой xml-ке, чтобы вместо 10ки получить реальный коэффициент.
                                • 0
                                  мы получим, что 900, оставшись неизменными, ускорились в 10 раз

                                  Кто вам это сказал? Вы исходите из того, что бинарное представление, в котором xml передается от сервера в IDataReader одинаково для одинакового xml — а с чего вы это взяли?
                                  • 0
                                    Предположение тут такое, что если взять xml из одной базы(1) и положить в другую, и потом извлечь ее(2), то (1) и (2), будут до байта cовпадать.
                                    Автор конечно обманывает себя и других, говоря что оптимизирует что то «зная как это работает». Так и в данном случае это чисто практическая оптимизация без доли теории. Но мне кажется, что это работает. Проверять, если честно, уже лень.
                                    • 0
                                      Что будет до байта совпадать, транспортное представление xml внутри SqlDataReader? А почему?
                                      • +1
                                        Предположу, что потому что версии SQL Server одинаковые, они одинаково обрабатывают входящие данные.

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

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

                                        Эта статья про то, как одни безрукие программисты тягались с другими безрукими программистами, тем не менее, я считаю, что спор про сравнение массивов вы проиграли =)
                                        • 0
                                          Предположу, что потому что версии SQL Server одинаковые, они одинаково обрабатывают входящие данные.

                                          А почему версии одинаковые? А ничего, что это для них не входящие, а исходящие данные, а обрабатывает их клиентский код?

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

                                          С этим никто не спорит. Но только надо понимать, в каких граничных условиях этим можно пользоваться. Если бы речь шла о файлах на диске, я бы вопросов не задавал.
                                          • 0
                                            Одинаковые, потому что уверен, что они не ставили разные версии для тестирования =) Замеры на базе в 200 метров, а в предисловии про терабайтные базы — думаю, что разные версии серверов не такой забавный челлендж будет, как проблема локальности, когда продукт конкурентов перестанет отставать =)

                                            Про сравнение массивов — они просто в начале пути, я полагаю =) Про понимать — это нужно обычно везде ;)
                                            • 0
                                              Одинаковые, потому что уверен, что они не ставили разные версии для тестирования

                                              Это означает, что результаты в тестовой среде и в продуктивной могут приятно удивить.

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

                                              Я тоже так думаю.
                                              • 0
                                                уверен, что они не ставили разные версии для тестирования

                                                Воспринимаю как плохой отзыв обо мне и моих коллегах — вы сильно наc недооцениваете. Мы занимаемся минрацией баз данных с различными версиями серверов.

                                                А на самом деле, достаточно заглянуть в код SqlDataReader — там есть метод, который десериализует массив байт в XML, и он одинаков для всех версий SQL Server.

                                                И сразу в этом комменте допишу, что при сравнении баз обычно отношение изменишевся данных к идентичным составляет маленький процент, поэтому побайтовое сравнение даёт существенный прирост производительности.
                                                • 0
                                                  Да нормально я вас оцениваю =) Вы выложили тесты на базе 200 мегабайтов, это не очень разумно, слишком мало данных.

                                                  Одинаковые версии серверов это не самое страшное, я бы для первичного тестирования сделал то же самое.

                                                  Со сравнения массивов я и начал переписку с вашим оппонентом, считаю, что в этом споре он неправ.
                                                  • 0
                                                    Со сравнения массивов я и начал переписку с вашим оппонентом, считаю, что в этом споре он неправ.

                                                    Спасибо, я заметил. Я просто решил все мысли в одном коментарии написать, это был не упрёк в вашу сторону =)
                            • 0
                              Но эта «оптимизация» действительно ересь. Во первых при сравнении строк, начиная с фреймворка 3.5 строки побайтово не сравниваются. Сравнение строк эквивалентно сравнению ссылок, и по времени оно занимает столько же, сколько и сравнение хэш кодов. То есть сравнение строк все равно присутствует, но на тот момент, когда мы пишем a==b или mySet.Contains CLR это сравнение уже сделал. Кроме этого, я не понял, зачем вообще приводить к верхнему регистру? SQL код же генерится своим же приложением, почему бы сразу в нем все ключевые слова не сделать в верхнем регистре? Лишнее действие оптимизировать можно в зародыше. И последнее, собственно почему это ересь — допустим между SELECT и INSERT совпадений хэша не будет, но как можно довериться тому, что совпадений не будет в произвольном тексте, извлеченном из бд? Рано или поздно лексер подсветит какое нибудь левое слово, да еще с опечаткой(чтоб ваш тест со словарем обойти), как будто оно ключевое.
                              • –1
                                Вас нужно тыкнуть носом?
                                код из mscorlib
                                class String {
                                    public bool Equals(string value)
                                    {
                                    	if (this == null)
                                	{
                                		throw new NullReferenceException();
                                	}
                                	return value != null && (object.ReferenceEquals(this, value) || (this.Length == value.Length && string.EqualsHelper(this, value)));
                                    }
                                }
                                
                                private unsafe static bool EqualsHelper(string strA, string strB)
                                {
                                	int i = strA.Length;
                                	if (i != strB.Length)
                                	{
                                		return false;
                                	}
                                	char* ptr = &strA.m_firstChar;
                                	char* ptr2 = &strB.m_firstChar;
                                	bool result;
                                	while (i >= 12)
                                	{
                                		if (*(long*)ptr != *(long*)ptr2)
                                		{
                                			result = false;
                                		}
                                		else
                                		{
                                			if (*(long*)(ptr + (IntPtr)8 / 2) != *(long*)(ptr2 + (IntPtr)8 / 2))
                                			{
                                				result = false;
                                			}
                                			else
                                			{
                                				if (*(long*)(ptr + (IntPtr)16 / 2) == *(long*)(ptr2 + (IntPtr)16 / 2))
                                				{
                                					ptr += (IntPtr)24 / 2;
                                					ptr2 += (IntPtr)24 / 2;
                                					i -= 12;
                                					continue;
                                				}
                                				result = false;
                                			}
                                		}
                                		return result;
                                	}
                                	while (i > 0 && *(int*)ptr == *(int*)ptr2)
                                	{
                                		ptr += (IntPtr)4 / 2;
                                		ptr2 += (IntPtr)4 / 2;
                                		i -= 2;
                                	}
                                	result = (i <= 0);
                                	return result;
                                }
                                


                                • 0
                                  Осталось сказать, в каких именно случаях (а) вызывается Equals (в частности, вызывается ли он внутри HashSet) и (б) неверно условие object.ReferenceEquals(this, value).
                                  • 0
                                    Вместо тысячи слов
                                    static void Main(string[] args)
                                            {
                                                string[] z = 
                                                new string[] { "abc"//воткнуть любой набор строк  };
                                                Stopwatch watch1 = new Stopwatch();
                                                Stopwatch watch2 = new Stopwatch();
                                    
                                                HashSet<String> str = new HashSet<String>();
                                                HashSet<int> dig = new HashSet<int>();
                                                foreach (var s in z)
                                                {
                                                    str.Add(s);
                                                    dig.Add(s.GetHashCode());
                                                }
                                                int a = 7;
                                                watch2.Start();
                                                for (int n = 0; n < 10000000; n++)
                                                    if (dig.Contains(z[0].GetHashCode()))
                                                        a--;
                                                watch2.Stop();
                                                watch1.Start();            
                                                for(int n =0;n<10000000;n++)
                                                    if (str.Contains(z[0]))                
                                                        a++;
                                                watch1.Stop();
                                     
                                    
                                                Console.Write(string.Format("str {0} int {1} a {2}",watch1.Elapsed,watch2.Elapsed,a));
                                                Console.ReadKey();
                                            }
                                    
                                    


                                    Профайлер это еще полбеды, но замеры «до» и «после» все же надо делать?
                                    • 0
                                      Только ваш код не решает никакой задачи. Вы не верно понимаете условия реального test case: при разборе текста лексер возвращает новые объекты String, поэтому Object.ReferenceEquals никогда не вернёт true.
                                      • 0
                                        Я предлагаю вписать нужный набор строк, в т.ч. в .Contains() и убедиться, что это не так.

                                        Подсказать что вернет этот код?
                                        ReferenceEquals("abcd","ab"+"cd"); 
                                        

                                        • 0
                                          Разверну ответ немного. Вписать предполагается «SELECT», «INSERT» ну и еще что то до кучи
                                          • 0
                                            Подсказать что вернет этот код?
                                            ReferenceEquals(«abcd»,«ab»+«cd»);

                                            Подсказать почему?
                                            • 0
                                              Этот пример некорректен, потому что он опирается на string interning, который работает на этапе компиляции.

                                              Другое дело, что в лексерах как раз надо делать интернинг, просто вручную, благо это просто.
                                              • 0
                                                да вас бы убили за такой код :)
                                                представьте скрипт с данными размер несколько сотен MiB. Вы будете для каждого токена делать Intern, чтобы просто сработал Object.ReferenceEquals?
                                                • 0
                                                  Не, для того, чтобы уменьшить бессмысленную нагрузку на память.

                                                  Новообще, конечно, я бы сначала написал в лоб, а потом уже смотрел.
                                                • 0
                                                  Тоже сперва так подумал, но потом запустил код и увидел немного другой результат :)
                                                  Проблема в том что при поиске по числу (хешкоду от строки) Вам придется сначала его рассчитать, а потом уже искать по нему. В случае же поиска по строке точно тоже самое за вас сделает HashSet. По-этому оба варианта почти одинаковы.
                                                  • 0
                                                    Вы точно не ошиблись с тем, куда написали свой комментарий?
                                                    • 0
                                                      Этот пример некорректен, потому что он опирается на string interning, который работает на этапе компиляции.

                                                      Вроде нет.

                                                      Интернирование он конечно использует но не в этом дело.
                                                      • 0
                                                        Теперь посмотрите на код примера:

                                                        ReferenceEquals("abcd","ab"+"cd"); 
                                                        


                                                        Где здесь хэшсет?
                                                        • 0
                                                          Да, пожалуй я все таки потерял мысль треда. Мне почему то показалось что ваш комментарий относится к этому.
                                                    • 0
                                                      Если искать по строке, то верно что будет расчитан hash code, однако при совпадении этого кода переданная строка будет сравниваться побайтого с той, которая лежит в HashSet (потому что Object.ReferenceEquals вернёт false).
                                                      Если искать сразу по hash code, то HashSet для расчёта hash code ключа типа int будет использовать само значени ключа типа int, и сравнивать строки не нужно — будут сравниваться значения типа int. Т.е. что-то типа такого:
                                                      int key = 12345; // pre-computed hash code for a string
                                                      
                                                      bool Contains<T>(T key) { // where "T" is "int"
                                                        int hashCode = key; // get hash code for "T" type, when it's "int"
                                                        int bucketIndex = hashCode % bucketCount;
                                                        int itemIndex = buckets[bucketIndex];
                                                      @loop:
                                                        Item item = itemArray[itemIndex];
                                                        if (item.Key == key) // Call operator '==' for 'T' type.
                                                          return true;
                                                        itemIndex = item.NextItemIndex;
                                                        if (itemIndex >= 0)
                                                          goto loop;
                                                        return false;
                                                      }
                                                      
                                                      • 0
                                                        Не побайтно (сравниваться), а так, как задано в компарере.
                                                        • 0
                                                          Имелось в виду при использовании HashSet<T> без своего IEqualityComparer. А в GenericEqualityComparer как раз и вызываются стандартные методы Equals и GetHashCode.

                                                          Вы — самый настоящий тролль. В вашем коментарии я вижу всего один умысел — поумничать. Придраться можно абсолютно бесконечно к любой мелочи, чем собственно вы и занимаетесь. Вы бы ещё добавили, что Object.ReferenceEquals может вернуть true; что хэш коды на самом деле не сравниваются, что остатки от их деления являются индексами в массиве; что пример кода неправильный, там «if» не в том месте, и что bucketIndex может быть отрицательным; и т.д. и пр.

                                                          Прочитайте раздел «Специальное дополнение», которое я добавил в конец статьи. Может тогда вы станете добрее… :)
                                                          • 0
                                                            Имелось в виду при использовании HashSet без своего IEqualityComparer.
                                                            А зачем использовать решение, заведомо не подходящее к задаче?

                                                            Прочитайте раздел «Специальное дополнение», которое я добавил в конец статьи.

                                                            habrahabr.ru/post/165729/#comment_5742425
                                                  • +1
                                                    Выражение:
                                                    ReferenceEquals(«abcd»,«ab»+«cd»); // true

                                                    Компилируется в:
                                                    L_0001: ldstr «abcd»
                                                    L_0006: ldstr «abcd»
                                                    L_000b: call bool [mscorlib]System.Object::ReferenceEquals(object, object)

                                                    Так что правильнее:
                                                    ReferenceEquals(«abcd», string.Concat(«ab», «cd»)); // false
                                              • 0
                                                Просто преступно создавать подобный код, в то время как даже у 8086 уже была хардверная команда CMPS для сравнения строк! (потом появились команды CMPSD и CMPSQ для сравнения 32-битными и 64-битными блоками соответственно, что ускорит сравнение мегабайтных строк).
                                                Подобный код — ответ на вопрос, почему процессоры становятся мощнее, а толку — нет.
                                              • 0
                                                что совпадений не будет в произвольном тексте

                                                Здесь согласен, в статье приведён код, который специально написан для неё. К тому же, он вырван из контекста, поэтому логично сделать такое предположение. Эта проблема решена очень просто. Я не хотел писать лишний код в статье, чтобы он не мешал чтение основного. Тем не менее, это не отменяет саму суть оптимизации.
                                      • +34
                                        Превентивная оптимизация да ещё и без профайлинга? Выводы об эффективности «оптимизации» на базе black-box замеров двух разных систем? Да вы шутите. Вот не дай бог начинающие программисты начитаются подобных «советов».
                                        • –15
                                          > black-box замеров двух разных систем
                                          Откуда такие сведения? Я точно знаю по какому алгоритму работает конкурентная сисетма. У меня было достаточно времени чтоб ознакомится с исходным кодом с помощью .NET Reflector.

                                          > Да вы шутите
                                          Out-of-box thinking ;)
                                        • +6
                                          13. Асинхронная запись.
                                          А как же BeginRead и BeginWrite в FileStream или Socket? Эти операции выполняются асинхронно на уровне ОС.
                                          • –8
                                            Опять же, вы можете рассуждать сколь угодно. На практике проверяли? Думаете я просто так об этом всё писал, чисто из-за незнания .NET Framework?
                                            • +9
                                              Я не рассуждаю. А сообщаю информацию, почерпнутую из достоверных источников, коим я считаю и Рихтера, который рекомендует пользоваться асинхронными операциями для FileStream, NetworkStream и Ко. В статье же, на мой взгляд, предлагается создать свой велосипед и бороться с ветряными мельницами. Вы, наверное, очень много и долго писали ранее на С++ =)
                                              • –3
                                                На самом деле многие серъёзные компании изобретают велосипеды, даже если есть уже что-то готовое и отлично спавляющееся с задачами, и тут скрывается много причин. Они готовы переходить с .NET или Java на С/С++ ради достижения наивысшего качества продукта.
                                                Я, конечно же, не собираюсь учить программированию на C#, просто хочу показать как можно писать на С++ используя C# :) Если бы была возможность, я бы написал программу на С++.
                                                • +10
                                                  Не спорю. Но прежде чем приступать к разработке продукта, необходимо выбрать инструмент, соответствующий задаче. Если стоит задача обрабатывать гигабайты данных в реальном времени, то имеет смысл продумать путь каждого байта. Выбрать минимально необходимые размеры структур, избежать копирования, внедрить быстрые алгоритмы и озаботиться вопросами оптимизации при компиляции. Да что тут говорить — иногда внедрение asm кода, значительно увеличивает производительность приложения. А что из этого следует? Что в качестве инструмента нужно сразу выбирать С++, и не пытаться ставить профессиональные трековые покрышки на любительский велосипед.

                                                  «Далее, если вы знаете, что диапазон значений занимает всего 20 бит (от 0 до 1048575) и вам нужен «int» (32 бита), то вы можете использовать оставшиеся 12 бит для других целей, например для неких флагов.» — уместно в контексте программирования микроконтроллеров, но для шарпа, это просто аморально, на мой взгляд :). На шарпе можно оперативно писать код, который достаточно быстро работает в 99% случаев. И, главное то, что язык и платформа толкают к написанию кода для людей. «Не стоит стачивать лопату до маникюрной пилки.» =)
                                                • 0
                                                  Когда у вас много параллельных чтений, нагрузка распределяется сама собой и никакого выигрыша от предложенной в статье «асинхронности» не будет. А когда читаете в один поток, разница будет зависеть от времени обработки — чем больше время обработки, тем больше разница, но не более, чем в два раза. Если вы читаете и пишете одновременно, разница будет до 4 раз.
                                            • +10
                                              В ту же копилку:

                                              И никогда, никогда не пишите в таком стиле
                                              for (int i = 0; i < a.Count; i++) {
                                                  int a = a[i];
                                                  int b = a[i];
                                                  int c = a[i];
                                              }
                                              


                                              Цитируем ту же статью, на которую ссылается сам автор поста (выделение мое):

                                              In the method:

                                              
                                                  static void Test_SimpleRedundant(int[] a, int i) {
                                                      k = a[i];
                                                      k = k + a[i];
                                                  }
                                              


                                              bounds-check code is generated for the first instance of “a[i]”, but not the second. In fact, the x86 JIT treats it as a common subexpression, and the first result is re-used.


                                              Не надо пытаться быть умнее компилятора.
                                              • –5
                                                Вы не поняли пункт. Я говорил об обращении к памяти.
                                                также избежите лишних проверок границ массива (если таковые имеют место)
                                                • +5
                                                  А что обращения к памяти? Вы (специально для вас выделенную) фразу про использование одного и того же первого результата не заметили?
                                                  • –4
                                                    Вы говорите про частный случай с типом int[]
                                                    Я нигде не указывал в своём коде, что переменная «а» — именно этого типа. Если это будет IList, или что угодно ещё, правило «the first result is re-used» уже может не работать.
                                                    • +8
                                                      Если это будет IList, или что угодно ещё, правило «the first result is re-used» уже может не работать.

                                                      А вы не задумывались о том, что в случае «что угодно еще» там и результат может быть разный, и поведение кода

                                                      int a = a[i];
                                                      int b = a[i];
                                                      int c = a[i];
                                                      


                                                      может отличаться от

                                                      int t = a[i]
                                                      int a = t;
                                                      int b = t;
                                                      int c = t;
                                                      


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

                                                      Пламенный привет МакКоннелу и intention-revealing code.
                                              • +5
                                                И там же:

                                                Arrays implement the IEnumerable interface, which raises a reasonable question: if you enumerate over the elements of an array using C#’s foreach construct, do you get bounds checks? For example:

                                                static int Test_Foreach(int[] ia) {
                                                        int sum = 0;
                                                        foreach (int i in ia) {
                                                            sum += i;
                                                        }
                                                        return sum;
                                                    }
                                                

                                                Happily, we do eliminate the bounds checks in this case.


                                                Привет «единственному способу избежать проверок».
                                              • +6
                                                Скорее всего 95% прироста производительности вашей программы обеспечены 1-2 оптимизациями. Кроме того, зачем вообще упираться с оптимизацией этапов, которые заведомо работают пару секунд (что можно было понять по программе конкурента еще до начала разработки), если другие занимают пару минут.
                                                • –1
                                                  Это ж на примере демобазы. В реальных базах конкурент справлялся с задачей где-то за 40 часов, а мы за 1 час 40 мин! Теперь разницу чувствуете?
                                                  • +6
                                                    Что это меняет? Было бы интересно, если бы вы подробнее рассказали про самое горячее место в программе, которое сделало эту разницу, с сравнением реализаций конкурента и вашей.
                                                    • –1
                                                      Для конечных пользователей это много чего меняет :) Собственно, я для этого и написал основных 30 пунктов. Каждый из них привнёс в производительность свою долю. Я упоминал, что разработка велась сразу с учётом оптимизации, поэтому сложно говорить о самых горячих местах. Да, после первой реализации программа была уже быстрее конкурентов, а дальнейшая оптимизация была что-то вроде «надо выжать по максимуму».
                                                      • +2
                                                        Да возьмите же уже профайлер наконец и посмотрите. Тормоза, как правила, оказываются совсем не в том месте и по совсем не очевидной причине.
                                                        • –2
                                                          Зачем? Какие тормоза? Вы читали статью? Программа «летает» по сравнению со всеми конкурентами.
                                                          • +3
                                                            Сейчас уже незачем. А вот если бы вы это (профилирование) сделали в начале разработки, то, возможно, разработка и поддержка обошлись бы вам дешевле.
                                                            • –3
                                                              Вы советуете мне как распоряжаться средствами компании?
                                                              Вы знаете требования к приложению?
                                                              В начале разработки профилировать ничего не было — ведь кода ещё не было :)
                                                              • +1
                                                                Вы советуете мне как распоряжаться средствами компании?

                                                                Я советую вам (да и всем читающим) вести разработку в «правильном» порядке.

                                                                В начале разработки профилировать ничего не было — ведь кода ещё не было

                                                                Окей, я был неправ. Не «в начале разработки», а «на первом этапе разработки», т.е. после построения вертикального прототипа, проверяющего работоспособность алгоритма.
                                                                • 0
                                                                  Зачем вы сводите до абсурда обсуждение, если прекрасно понимаете, о чем идет речь? Это как не тру. Кроме того вы имеете тенденцию задавать вопросы «о знании требований к приложению» даже когда это никак не влияет на суть темы. Если в требованиях была «скорость работы», то туда вы были тем более обязаны посмотреть.
                                                              • –3
                                                                Просто статья получилась в духе «да здравствует premature optimization!!!»
                                                                Скорее всего применительно к (тормозному по умолчанию) .NET ваши советы действительно имеют смысл, но не дай бог вам сказать такое применительно к C++ или Delphi, вас просто освистают, т.к. все эти действия ничтожны по сравнению с полезными действиями, которые производит программа (читает/пишет данные на диск, передает данные по сети, общается с SQL-сервером (даже если MS SQL стоит на той же машине, что и программа, межпроцессное взаимодействие на порядок тормознее любых операций со строками в памяти вашей программы)).
                                                                Вы даже не представляете, сколько действий выполняется, чтобы найти в вашей строке “{0}” и подставить значение в указанном формате.

                                                                А вы представляете, сколько действий выполняется, когда вы отправляете один единственный (неподготовленный) SQL-запрос SQL-серверу? От количества этих действий просто с ума сойти можно (парсинг, построение и выбор оптимального плана выполнения, само выполнение, связанное, возможно, с обращением к диску), а ведь SQL-сервер выполняет сотни и тысячи запросов в секунду и ничего, как-то справляется.
                                                                • +1
                                                                  Скорее всего применительно к (тормозному по умолчанию) .NET


                                                                  Не надо, .NET не такой уж и тормознутый :)
                                                                  • 0
                                                                    Вот-вот. Всего лишь сотни и тысячи запросов.
                                                                    Вместо десятков тысяч на MongoDB, например.

                                                                    Конкатенация раз в 50-100 примерно быстрее форматной строки для записи в журнал.
                                                                    А если писать в журнал сразу байтики, без конкатенации, то будет быстрее в 1000 раз, чем с конкатенацией =)

                                                                    Чтобы не писать бреда, который вы написали, надо получить опыт, а не прочитать где-то про плохую раннюю оптимизацию. С опытом приходит тайное знание, где оптимизация нужна, а где можно отложить на потом и доработать профайлером.
                                                        • 0
                                                          > Скорее всего 95% прироста производительности вашей программы обеспечены 1-2 оптимизациями
                                                          Это не так. Мы много смотрели в код конкурентов, и знаем что мы используем практически идентичные алгоритмы, просто для задачи сравнения данных в базе других особо нет. Насчёт асинхронности — да, тут есть хороший выигрыш, но даже без неё программа всё-равно в разы быстрее, благодаря остальным оптимизациям.
                                                        • +1
                                                          Пункт 9 — менеджер задач уже встроен в ядро ОС. Если у вас много IO операций — либо делайте больше потоков, чем ядер, либо используйте асинхронное IO (что, суть, одно и то же). Писать свой менеджер задач в большинстве случаев не стоит.

                                                          Вторая половина пункта 11 тоже спорная, современные ОС умеют распределять процессы с учётом множества факторов.

                                                          Пункты 12-14 — опять же, в современных ОС есть readahead, writeback, pagecache… Не стоит советовать переписывать их. Лучше поставить в сервер побольше памяти :)
                                                          • 0
                                                            Не спорю. Я тоже говорю, что стоит вначале определится с требованиями к приложению, а только в самых необходимых случаях прибегать к хардкорным оптимизациям :)
                                                            • 0
                                                              Самый быстрый способ работы с файлами это memory mapping.

                                                              Readahead, например, из вашего рассказа, это магия, недоступная простым смертным. Эту прекрасную неотключаемую «фичу» в ядре Линукса мы обычно закручиваем до минимума, потому что она упарывает производительность БД на ровном месте.
                                                              Когда поработаете с десятками гигабайтов данных, почувствуете «эффективность» и остальных перечисленных «фич». Статья про максимальную производительность, а не про лабораторные работы в школе.
                                                              • 0
                                                                Readahead — это магия, которую уже сделали, просто пользуйтесь fadvise для указания профиля работы с данными. Мы юзаем и работает это хорошо. Если какая-то БД умеет работать с диском лучше, то пусть флашки указывает, или в документации пишут, как закрутить readahead. Если она только считает, что может работать лучше — то тут ещё непонятно, кто виноват в смерти диска по io.

                                                                Про десятки гигабайт данных — это вы мне написали, или автору статьи?
                                                                • 0
                                                                  Вызов fadvise завершается успешно, но ядро на это не обращает внимания.
                                                                  MongoDB ничего не считает, просто использует memory mapping с соответствующим вызовом madvise. Виновата магия readahead, которую я не могу понять с давнишних времён первой встречи на рейд-контроллерах.

                                                                  Писал вам, естественно =) Последний абзац указывает на то, что вы верите в магию. Что поможет readahead или там больше памяти. Это верно очень недолго, или на десктопных приложениях, когда постоянной нагрузки нет.
                                                                  Суть затеи в том, если много писать просто так, в Windows заканчивается оперативная память. Гигабайты в час имелись в виду, а не вообще.

                                                                  Написал и понял, что мы в разных мирах живём. В обсуждении статьи про ПО, тестируемое на 200 метрах данных вполне нормально давать советы поставить больше оперативки. Извините, что влез со своим представлением о высокой нагрузке.
                                                                  • 0
                                                                    Наверное, в разных, да. И у нас почему-то readahead в линуксе работает хорошо. Может, потому, что мы не монгу используем? Надо только хорошо понимать, когда он хорош, а когда плох, когда надо как можно агрессивнее забивать pagecache данными, а что лучше не помещать туда, как расположить данные на диске, чтобы они быстрее считывались. Под заканчивающейся памятью вы что имеете в виду? А под гигабайтами в час — это запись на диск, или чтение? Какой размер каждой записи? Как именно они располагаются на диске?

                                                                    Вы точно хотите меряться представлениями о высокой нагрузке?
                                                                    • 0
                                                                      Они RA отключают, не помогает, только если его на всю систему закрутить до минимума, жить можно.

                                                                      Под заканчивающейся памятью имею в виду именно заканчивающуюся доступную память, а что ещё можно иметь в виду? ;) Гигабайты записи просто файлов. В Windows. Как расположены, по барабану, это просто такая «оптимизация» для SMB, фиг отключишь. Writeback, который «решает все проблемы» =)

                                                                      «Меряться представлениями» это прекрасно =)
                                                                      • 0
                                                                        Идея readahead проста:
                                                                        — прочитать с диска (обычного крутящегося, не SSD) несколько секторов занимает практически столько же времени, сколько и прочитать 1 сектор
                                                                        — чаще всего данные читают последовательно

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

                                                                        Если какое-то приложение плохо работает с readahead — то это означает либо то, что оно плохо работает с диском, либо оптимизировано для работы с SSD.

                                                                        А зачем вам на машине свободная память? Они же не обязательно все грязные, большинство сразу сбрасывается на диск. Когда память понадобится — быстренько освободится. Во всяком случае, в линуксе так. Free памяти на сервере быть совсем немного, на десктопе можно побольше, но тоже нечего ей простаивать.

                                                                        Вот, правдоподобные хорошие цифры (не мои, из интернетов):
                                                                        $ free -m
                                                                                     total       used       free     shared    buffers     cached
                                                                        Mem:         96730      96418        311          0         71      93120
                                                                        -/+ buffers/cache:       3227      93502
                                                                        Swap:        21000         51      20949

                                                                        Вы правда считаете, что это плохо?
                                                                        • 0
                                                                          Про RA — диски шпиндельные, с секторами по 4к. В теории наверное да, несколько секторов прочитать времени занимает столько же, в реальности нет.

                                                                          На практике, знаете ли, в здравом уме не читают последовательно блоками по 1 сектору, читают мегабайтами обычно. И пишут тоже. Есть нормальные понятные технологии, типа NCQ, чтобы ускорять доступ к диску. RA это магия.

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

                                                                          Когда память понадобится — быстренько освободится.

                                                                          В теории так, да =) Пока не столкнулся с этим, тоже так думал. В Linux свои «оптимизации», про доступную память при активной записи я говорил в Windows. В Task manager есть счётчик доступной памяти (Available), это чистые страницы или готовые в любой момент к возврату пользователю, грубо говоря, кэш чтения. Кэш записи просто так на диск не сбросить, особенно в контексте «поставить больше оперативки», когда скинуть на диск надо 90 гигабайтов. Free без разницы, какое значение имеет.

                                                                          Конечно, я считаю, что это очень плохо, когда система всю свою оперативку использует под «грязные» страницы. Это плохо во всех отношениях, и пропадание питания чревато потерей очень большого количества данных, и доступной оперативки для приложений нет, и кэша чтения тоже нет.
                                                                          • 0
                                                                            Начнём с того, что магия — это технология, которую вы не понимаете.

                                                                            Итак, практика: 100 IOPS random read дадут вам 3 мб/с, 100 IOPS последовательных чтений дадут 30 мб/с при сравнимой latency. Что это говорит? Что время чтения 1 сектора сильно меньше времени позиционирования головки. У вас другая реальность? NCQ, кстати, замедляет доступ к диску, зато даёт возможность сделать больше IO операций в секунду. Latency при включении NCQ растёт, т.к. появляется ещё одна очередь запросов.

                                                                            Читают и пишут обычно так, как удобно. Единственное, если читать по 100 байт — то количество сисколов будет слишком большим, и тормозить будет уже из-за этого. Но читать с диска сразу мегабайты/гигабайты, как-то кешировать внутри своей системы, следить за этим — это переписывать pagecache операционной системы. Особенно когда у вас индексы для данных перестают помещаться в память, ну очень нетривиальный код будет. Попахивает велосипедизмом.

                                                                            Кстати, я разве где-то писал, что pagecache = writeback cache? Если какая-то из подсистем windows держит огроменный writeback cache — это, конечно, не всегда хорошо. Но обычно в pagecache мало грязных страниц, даже если вы интенсивно пишете на диск. Вот вам пример с реальной машинки:
                                                                            $ free -m
                                                                                         total       used       free     shared    buffers     cached
                                                                            Mem:         64557      64232        324          0        227      57165
                                                                            -/+ buffers/cache:       6838      57718
                                                                            Swap:         4093          6       4087

                                                                            sync делается каждые 30 секунд, так что там практически нету грязных страниц.

                                                                            На другой машинке похожая картина:
                                                                            $ free -m
                                                                                         total       used       free     shared    buffers     cached
                                                                            Mem:        193831     193037        794          0       1783      97128
                                                                            -/+ buffers/cache:      94125      99706
                                                                            Swap:         4102          0       4102

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

                                                                            Мне кажется, что очень даже хорошо — память используется, данные кешируются, и всё это делает ОС для меня. Коллега, linux kernel hacker, тоже считает, что надо по-максимуму использовать то, что даёт сама операционная система, и что её писали далеко не глупые люди. Но тем не менее регулярно находятся господа, которые пишут свой «TCP» поверх UDP, и в некоторых тестах их реализация работает действительно лучше TCP. Правда в других — сильно сливает, и именно поэтому стоит использовать TCP вместо своих велосипедов.

                                                                            Кстати, на счёт вашего выпада в первом посте про десятки гигабайт… У меня обычно по полсотни терабайт данных на сервер. И по несколько сотен тебарайт на кластер.
                                                                            • 0
                                                                              Магия это технология, которая не работает, как анонсируется. Конечно же, я знаю, как readahead работает. Последовательное чтение на серверах читают мегабайтами, а не как удобно. «Как удобно» делают только когда скорость не имеет значения.

                                                                              Итак, практика: 100 IOPS random read дадут вам 3 мб/с, 100 IOPS последовательных чтений дадут 30 мб/с при сравнимой latency. Что это говорит? Что время чтения 1 сектора сильно меньше времени позиционирования головки. У вас другая реальность?

                                                                              Это практика чего? Синтетического теста? У меня реальность другая, да. Чтения никогда не бывают без записей, такие нюансы придают бодрости на первой встрече с реальностью. Вы написали очевидный факт, непонятно зачем. Я утверждал исключительно о том, что readahead на сервере только вредит. В следующий раз, когда захотите блеснуть эрудицией, упомяните ещё промахи позиционирования головки, на современных дисках с ростом плотности актуальность всё больше.

                                                                              NCQ, кстати, замедляет доступ к диску, зато даёт возможность сделать больше IO операций в секунду. Latency при включении NCQ растёт, т.к. появляется ещё одна очередь запросов.

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

                                                                              Но читать с диска сразу мегабайты/гигабайты, как-то кешировать внутри своей системы, следить за этим — это переписывать pagecache операционной системы.

                                                                              Последовательное чтение мегабайтами используется для последовательной обработки данных. Не надо ничего переписывать. Вы рассуждаете про общие теории ни о чём. Я утверждаю, что когда может помочь readahead, он не имеет смысла. И утверждаю, что вы агитируете за использование магии, потому что нет опыта её применения. Ни один из ваших «советов» нельзя применить к опыту, описанному в статье, потому что опыт на Windows и говорить «а вот у меня в Линуксе много пишется и с памятью всё хорошо» демагогия.

                                                                              Особенно когда у вас индексы для данных перестают помещаться в память, ну очень нетривиальный код будет.

                                                                              Когда у нас индексы перестанут помещаться в память, всё встанет колом =) Тем не менее, ручным кэшированием обычно заниматься, ясное дело, неразумно.

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

                                                                              Без деталей это данные ни о чём. Запросы к БД должны измеряться тысячами в секунду, обращения к просто файлам измеряться десятками килобайтов хотя бы (иначе зачем файлы?). Описанная вами ситуация ни рыба, ни мясо.

                                                                              Коллега, linux kernel hacker, тоже считает, что надо по-максимуму использовать то, что даёт сама операционная система, и что её писали далеко не глупые люди.

                                                                              Невероятное знание! =)
                                                                              IO-шедулер в серверной Убунте по умолчанию стоит десктопный, для единообразия. Дураков хватает везде. Тем не менее, я уважаю авторов Линукса, потому что в целом достойный результат.

                                                                              Кстати, на счёт вашего выпада в первом посте про десятки гигабайт… У меня обычно по полсотни терабайт данных на сервер. И по несколько сотен тебарайт на кластер.

                                                                              Там был нюанс «в час». Либо вы в юношеском задоре пропустили этот нюанс, либо я сильно устарел и не в курсе, что уже можно писать по 15 гигабайтов в секунду на один сервер. Напомню ещё, что это было про Windows, который используется в обсуждаемом материале.
                                                                              • 0
                                                                                Ну раз вы начали рассуждать про записи и чтения — то давайте начнём с того, как именно у вас хранятся данные на диске, без этого рассуждать о том, что readahead всегда вредит как-то странно. А вот про описанную ситуацию — это вы зря, она более чем реальна. Надо хранить много (по 2 млрд на машину) объектов размером в несколько килобайт (средний размер пусть будет 3кб). Ваши варианты, как это положить на диск?

                                                                                Далее у вас началась последовательная обработка данных. Как часто она случается в MongoDB? Можно ли в принципе так положить данные, к которым производится произвольный более-менее равномерный доступ, на диск так, чтобы их можно было последовательно считывать большими кусками? Кстати, про шедулер: какой шедулер стоит при этом применять и почему, какой при этом будет профит?

                                                                                Про нюанс «в час» — можете сами посчитать, а могу сразу сказать: на систему, которая была второй в предыдущем посте, постоянно льётся 3-5гб/ч, в пиках — больше. Но там маленькие записи, дискам сложно переваривать бОльшие объёмы из-за IO. В других местах, где записи по несколько мегабайт — конечно гигабайты в час легко получаются, когда начинают контент заливать.

                                                                                А в Windows то вы с заканчивающейся памятью на диск писали или в сеть? В оригинальной статье всё же шёл разговор о работе с диском. В то, что в Windows хреново написан file cache, простите, не верю. Вот если кто-то накрутил настройки lazy write — тогда вполне возможны проблемы с большим количеством грязных страниц. В любом случае, настраивать надо периодичность flush, а не отключать writeback. А диски — они одинаковые, проблемы при работе с ними слабо зависят от операционной системы.
                                                                                • 0
                                                                                  Как хранит данные MongoDB, можно почитать в интернетах.
                                                                                  О том, что RA вредит случайному доступу, очевидно и ребёнку, о том, что RA не помогает, я вам написал несколько раз — при линейном чтении от RA никакого толка, потому что линейно всегда читается большими блоками.

                                                                                  Файловая система не предназначена для хранения большого количества мелких экземпляров. Во-первых, оверхеад, во-вторых, скорость низкая, в-третьих, репликация это ужас. Есть несколько ФС, решающих часть проблем (btrfs, например, или gfs), но они нестабильны просто или в плане скорости.
                                                                                  Мы храним в MongoDB файлы даже по 500кб. Есть нюансы, конечно, но как решение в целом на данный момент эффективность максимальная.

                                                                                  Последовательное чтение используется для парсера лога, например. Естественно, писать надо так, чтобы потом быстро читать. В MongoDB последовательная обработка тоже возможна, но есть нюансы.

                                                                                  Кстати, про шедулер: какой шедулер стоит при этом применять и почему, какой при этом будет профит?

                                                                                  Я не справочное бюро =) А так для линейного чтения в один поток по фигу, что за шедулер.

                                                                                  Про нюанс «в час» — можете сами посчитать

                                                                                  Не могу! Вы написали конечный объём в 50 терабайтов, за день это или за год, у меня данных нет. Но это всё равно про Линукс, написал уже два или три раза, что проблемы записи в Windows, используемом автором статьи.

                                                                                  А в Windows то вы с заканчивающейся памятью на диск писали или в сеть?

                                                                                  Диск.

                                                                                  В то, что в Windows хреново написан file cache, простите, не верю.

                                                                                  Об этом я написал в самом начале, вера опыт не заменяет. Скопируйте образ BR диска, например, и посмотрите, что будет с системой происходить. Чтобы два раза не вставать, советую смотреть счётчик Available для памяти в Task manager.

                                                                                  Про отключение writeback занятная теория (отключение WB, сюрприз!, не помогает), есть способ лучше =) O_DIRECT.
                                                                                  • 0
                                                                                    Как хранит данные MongoDB, можно почитать в интернетах.
                                                                                    Это переводится как «я не знаю»?

                                                                                    О том, что RA вредит случайному доступу, очевидно и ребёнку, о том, что RA не помогает, я вам написал несколько раз — при линейном чтении от RA никакого толка, потому что линейно всегда читается большими блоками.

                                                                                    You can always use POSIX_FADVISE_RANDOM to disable it, but it's seldom
                                                                                    something that people do. And there are real loads that have random
                                                                                    components to them without being _entirely_ random, so in an optimal world
                                                                                    we should just have heuristics that work well.

                                                                                    ©Linux Torvalds

                                                                                    sendfile, кстати, через readahead работает. Примеры, когда readahead будет хорошо работать: вычитывание b-tree индекса, подгрузка какой нибудь игрой ресурсов из большого ресурсного файла. В обоих случаях доступ рандомный, да не совсем.

                                                                                    Файловая система не предназначена для хранения большого количества мелких экземпляров. Во-первых, оверхеад, во-вторых, скорость низкая, в-третьих, репликация это ужас. Есть несколько ФС, решающих часть проблем (btrfs, например, или gfs), но они нестабильны просто или в плане скорости.
                                                                                    Кто вам сказал, что я храню 2 млрд файлов на файловой системе?

                                                                                    Мы храним в MongoDB файлы даже по 500кб. Есть нюансы, конечно, но как решение в целом на данный момент эффективность максимальная.
                                                                                    Вы в монгу сможете положить 2млрд записей по 3 кб?

                                                                                    Последовательное чтение используется для парсера лога, например. Естественно, писать надо так, чтобы потом быстро читать. В MongoDB последовательная обработка тоже возможна, но есть нюансы.

                                                                                    Чаще всего если данные надо хранить в большом объёме — то доступ к ним будет случайный. А если чтения всё равно не получится оптимизировать — то надо оптимизировать хотя бы запись, делая её линейной.

                                                                                    Не могу! Вы написали конечный объём в 50 терабайтов, за день это или за год, у меня данных нет. Но это всё равно про Линукс, написал уже два или три раза, что проблемы записи в Windows, используемом автором статьи.
                                                                                    Монгу вы под линуксом запускаете или под виндой?

                                                                                    Об этом я написал в самом начале, вера опыт не заменяет. Скопируйте образ BR диска, например, и посмотрите, что будет с системой происходить. Чтобы два раза не вставать, советую смотреть счётчик Available для памяти в Task manager.

                                                                                    Про отключение writeback занятная теория (отключение WB, сюрприз!, не помогает), есть способ лучше =) O_DIRECT.
                                                                                    Вы отключаете writeback и у вас всё равно остаётся много грязных страниц? Видимо, как-то не так отключаете. Вы случаем не во временный файл писали? Если проблема действительно есть — то дайте ссылку, мне сходу ни одной не попалось.
                                                                                    • 0
                                                                                      Это переводится как «я не знаю»?

                                                                                      Нам бессмысленно продолжать дискуссию. Спорить с детьми я могу и без интернетов, дома. Хинт — не надо общаться вопросами, надо общаться утверждениями, вероятность ошибки значительно выше, это отличный показатель ответственности за свои слова.

                                                                                      Спасибо за новую шутку. Раньше мне нравилась «Стив Джобс сказал, что вам это не надо», теперь к ней будет «Линукс Торвальдс сказал, что это работает» =) Кроме самой прекрасной фразы вы ещё подсказали, что и имя можно написать с ошибкой для пущего эффекта ;)

                                                                                      Не смог удержаться =) Вместо поиска информации про MongoDB (и расширения кругозора) вы стали искать информацию про простой и понятный для повторения пример. Не получилось.

                                                                                      social.technet.microsoft.com/Forums/ru/sqlru/thread/7721af71-6eaa-48a0-85c1-b231ef23b85e
                                                                                      social.technet.microsoft.com/Forums/ru/ws2008r2ru/thread/1bef70b4-932e-4104-996e-1fadb1fda9d2
                                                                                      social.technet.microsoft.com/Forums/ru-RU/ws2008r2ru/thread/cd60a4a5-4bb4-4ad9-b498-457bdf141c89
                                                                                      social.technet.microsoft.com/Forums/ru-RU/ws2008r2ru/thread/3fc0a8be-8d32-4ab5-be93-de51dc82128b
                                                                                      social.technet.microsoft.com/Forums/ru/sqlru/thread/7721af71-6eaa-48a0-85c1-b231ef23b85e
                                                                                      Часть примеров про SQL Server, так как он отличный индикатор описанной проблемы.

                                                                                      MongoDB, к слову, на Windows работает для галочки, как только начинается серьёзная запись, сервер умирает.

                                                                                      Ответов больше не будет, не обессудьте.
                                                                                      • 0
                                                                                        Да, вы уже сделали пару необоснованных заявлений, типа «readahead плохо, потому что MongoDB с ним работает плохо» и «Windows не скидывает страницы на диск, в итоге Allocated стремится к нулю после записи больших файлов».

                                                                                        Специально сейчас на Win7 скопировал с сетевой шары на локальный диск 400мб файл, ближе к концу копирования действительно было мало Allocated памяти, но через минуту после копирования Allocated = Cached + Free, то есть грязных страниц не осталось. Все ссылки, что вы привели — про то, что File Cache занимает весь доступный объём ОЗУ и приложениям, которые предварительно резервировали себе память, ничего не достаётся и они даже в файл подкачки вытесняются. Ну так это же нормально, оно так и должно работать! Файловый кэш выедает всю свободную память, чтобы она не простаивала, для ускорения операции записи. Если не нравится — уменьшайте объём памяти, который готовы выделять под буферы, делайте синк на диск чаще, инструменты то есть для этого.

                                                                                        Вы готовы привести другие ссылки, где будет написано про большое количество грязных страниц в памяти после окончания процесса копирования? Или, может быть, готовы показать ссылку, где будет описано, что страницы не сбрасываются на диск, когда вызывается sync? Мне такие не попадались.

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

                                                                                        Можете не отвечать, но советую всё же разобраться с «магией», которую применяют во всех современных операционных системах много лет, и с которой успешно работают миллионы программистов по всему миру. Расширьте кругозор. И не стоит учиться этому у разработчиков MongoDB, это далеко не самая лучшая база данных.
                                                                                        • 0
                                                                                          ближе к концу копирования действительно было мало Allocated памяти, но через минуту после копирования Allocated = Cached + Free, то есть грязных страниц не осталось

                                                                                          На сервере не бывает «через минуту», пишется непрерывно.
                                                                                          • 0
                                                                                            Так делайте sync чтобы страницы на диск сбросить, в чём проблема то?
                                                                                            • 0
                                                                                              Уже несколько раз написал — в том, что не работает =)
                                                                                              Точнее, лишь позволяет отсрочить смерть, а помогает от захламления памяти только O_DIRECT.
                                                                    • 0
                                                                      Кстати, мы тестировали сравнение реальных баз размером около 100 GiB, и получили такую картину:
                                                                      конкурент — 40 часов
                                                                      мы — 1 час 40 мин
                                                                      Так что пример с демобазой на 200 MiB наверно не самый удачный :)
                                                                      • 0
                                                                        Дык, и приводили бы этот пример. С какими-нибудь нюансами, типа количества таблиц, максимального количества строк в таблицах или ещё чего-нибудь интересного на абзац текста.
                                                                        Выглядело бы значительно ближе к реальности.
                                                              • +3
                                                                «1. Хороший алгоритм.»

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

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

                                                                UPD Сорри, не увидел.
                                                                • –1
                                                                  Сколько людей — столько и мнений. Если вы, например, скажете на собеседовании в Microsoft, что алгоритм — не главное, то скорее всего вы его не пройдёте. Там алгоритмам уделяется особое внимание, и слова «Хороший алгоритм» я брал не с потолка :) Если один алгоритм решает задачу за O(N*logN), а второй за O(logN), то выбор очевиден.

                                                                  в каких задачах из дотнетовского скоупа могут понадобиться такие оптимизации?

                                                                  Это уже вам решать, надо вам это или не надо. Задачи всегда найдутся, поверьте :)
                                                                  • +6
                                                                    Если один алгоритм решает задачу за O(N*logN), а второй за O(logN), то выбор очевиден.

                                                                    Нет, не очевиден. Потому что если первый требует n памяти, а второй — n3 памяти, то мы имеем балансировку между одним и другим.
                                                                    • +2
                                                                      Поддержу. Более того, благодаря скрытым константам даже и требование по памяти не нужно. Да и вообще куча причин есть, по которой первый алгоритм может быть предпочтительнее.
                                                                    • +2
                                                                      Алгоритм прямо вытекает из структур данных. Поиск по линейному списку, по бинарному дереву и по хэш-таблице — дадут вам как раз таки разную вычислительную сложность. Ну и как написал lair, есть еще требования к памяти.

                                                                      Прекрасно описано вот в этой книжке, например — www.ozon.ru/context/detail/id/4788523/ и в аналогичной книжке от Вирта.

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