Деление на ноль, это отличная тема для троллинга, между прочим:

Есть такой стандарт — IEEE754, это стандарт на floating point вычисления. Согласно этому стандарту, при делении числа на 0, получается либо +, либо — бесконечность. Но это было сделано не потому что 1/0 = бесконечности, а для того, тобы упростить жизнь программистам. Начнем с того, что в этом стандарте существуют 3 нуля — 0, –0 и +0. Два последних получаются при underflow, при underflow нам не хватает точности для того, чтобы представить число, мы можем сохранить только знак.

Если теперь представить какое–нибудь вычисление, в котором какое–нибудь число делится на постоянно уменьшающееся значение, то при достаточном количестве итераций мы получим underflow, то есть, по сути — ноль. Если бы в FP вычислениях, при делении на ноль получалось бы NaN, как того требует здравый смысл, то мы получили бы NaN вместо результата вычисления. Но вместо этого мы получим Inf, что в данном случае верно и правильно, мало того, мы получим правильный знак у Inf, в зависимости от того, с какой стороны произошел underflow, мы получим либо +Inf либо –Inf, bingo!

И теперь внимание — большинство делений на 0 в реальных программах происходят именно в такой ситуации, как я описал — ноль получается в результате underflow, а не нормальных вычислений. Вычисления с плавающей точкой — это аппроксимация, они априори не точны. В данном случае, разработчики стандарта пожертвовали точностью в угоду корректности. Но из–за этого 90% программистов считают что 1/0 должно быть равно бесконечности :)

Читатель, учись делить на ноль правильно!

Restricted Transactional Memory в Haswell

Пожалуй я не сильно ошибусь, сказав что существует всего два механизма управления изменениями - пессимистичный и оптимистичный. Первый мы уже давно используем в своих программах в виде всевозможных мьютексов и семафоров. Второй механизм, до недавнего времени, применялся в различных СУБД.
Software transactional memory (STM) - реализация второго механизма управления изменениями, по сути это просто транзакции в коде. Вы помечаете участок кода, который должен выполняться в рамках одной транзакции. Во время выполнения, система запоминает все что вы читаете и записываете (поддерживает read set и write set). В случае, если произошел конфликт, несколько транзакций попытались изменить одни и те же переменные, происходит откат транзакции, система возвращается в исходное состояние, после чего транзакция выполняется повторно.

Существует множество реализаций STM на разных языках и платформах, тем не менее, это по прежнему экзотика. Про железные реализации я вообще молчу, не случившийся Rock и BlueGene/Q для суперкомпьютера IBM, но есть и повод для оптимизма.
Примерно год назад, Intel анонсировали новый процессор - Haswell, который будет поддерживать набор инструкций Transactional Synchronization Extensions (TSX). Restricted Transactional Memory (RTM) - это часть TSX, добавляющая поддержку транзакционной памяти. Как видно из названия - поддержку ограниченную.

Для программиста, RTM это четыре новых инструкции - XBEGIN, XEND, XABORT и XTEST.
XBEGIN - начинает транзакцию, XEND - ее фиксирует, XABORT - откатывает. Инструкция XTEST позволяет узнать, находимся мы сейчас в транзакции, или нет. В Visual Studio 2012 есть интринсики, с помощью которых можно удобно использовать эти инструкции. Называются они соответственно - _xbegin, _xend, _xabort и _xtest.

Работает это следующим образом, вы вызываете ф-ю _xbegin, которая возвращает статус транзакции. В случае, если ф-я вернула _XBEGIN_STARTED - транзакция была начата, в противном случае - произошел откат транзакции по какой-либо причине. В случае отката транзакции, управление возвращается в ее начало, то есть в _xbegin() и в этом случае, _xbegin вернет статус, отличный от _XBEGIN_STARTED. В конце транзакции вы должны вызвать ф-ю _xend, в этом случае произойдет фиксация транзакции. Ф-я _xabort прерывает выполняющуюся транзакцию, управление вернется в _xbegin. Разные биты статуса _xbegin позволяют определить причину отката транзакции, был это _xabort, конфликт записи или что-нибудь еще.

Но на самом деле все далеко не так радужно, как может показаться. Недаром в названии есть слово `Restricted`, существуют значительные ограничения на код, который может выполняться в транзакциях. Во первых, в транзакции можно выполнять только простые загрузки и сохранения, даже простое переключение контекста прервет транзакцию. Во вторых, размер write-set и read-set ограничен размером L1 кэша, если вы попытаетесь переписать в транзакции мегабайт памяти - ничего не получится. В третьих, RTM работает на уровне линий кэша, поэтому здесь возможен false sharing, в том случае, если разные переменные попадают на одну кэш линию.

Именно по этому, Intel не гарантирует, что транзакция вообще завершится когда-нибудь. Поэтому, код, использующий транзакции, должен следить за тем, сколько раз и по какой причине транзакция откатилась. Реализация должна предусматривать fallback механизм, например, если наша транзакция откатилась N раз, мы можем попытаться захватить соответствующую блокировку и выполнить тот же самый код без транзакции, используя эксклюзивный доступ к данным.

По этим причинам, код, выполняемый в транзакции, должен быть коротким, он не должен пытаться делать I/O или что-нибудь кроме простых загрузок и сохранений в память, он должен изменять и читать как можно меньше данных. Именно по этому, люди, ждущие от RTM чего-то похожего на STM из Haskell будут разочарованы.
На мой взгляд, RTM подходит для создания различных lock-free структур данных. Если без RTM написать lock-free очередь - было делом нетривиальным, то с RTM все станет намного проще. Вместо того, чтобы ломать себе голову над тем, как с помощью CAS реализовать ту или иную операцию, достаточно просто обернуть ее в транзакцию. Я уже молчу о более сложных структурах данных.

Для иллюстрации вышесказанного, я написал простой, lock-free двух-связный список. Элементы можно добавлять и удалять из любого конца списка.

Это всего лишь proof of concept, не более. Здесь не реализован fallback-механизм, поэтому в случае ошибки в коде, он может зациклиться. Помимо этого, данный код не будет работать на обычных процессорах. Он будет падать по `undefined instruction`. Запустить его можно только в эмуляторе:

sde -hsw -rtm-mode full -- appname.exe

На данный момент сложно судить о производительности. Я очень надеюсь на то, что RTM будет позволять писать код, который будет работать быстрее, чем аналогичный код, построенный на CAS. На это можно надеяться, так как транзакции все пишут в кэш, а для обнаружения конфликтов записи используется cache coherency протокол, который есть и сейчас. Насколько я понял, все операции записи внутри транзакции - неблокирующие, в отличии от xchg.

Ссылки:
Exploring Intel® Transactional Synchronization Extensions with Intel® Software Development Emulator
Intel® Software Development Emulator
Intel® Architecture Instruction Set Extensions Programming Reference (Chapter 8)

Singly resizable array

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

Естественно, операцию push_back в реальной жизни реализуют с помощью метода удвоения. Алгоритм, последовательно добавляющий множество элементов в массив методом удвоения, будет иметь линейную, амортизированую сложность. По памяти все тоже неплохо, в любой момент времени, наш динамический массив будет иметь capacity <= N*2, где N - количество элементов массива, а capacity - его вместительность.

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

Код, использующий один счетчик и InterlockedIncrement работает, в среднем, в три раза медленнее нежели код, исползующий класс ConcurrentCounter. Почему это происходит, должно быть достаточно очевидно. InterlockedIncrement блокирует шину памяти на время выполнения, т.е. по сути, все потоки получают доступ к переменной по очереди, синхронно.

• За какой асбракцией не пряталась бы инструкция lock xchg, знать что именно происходит на низком уровне все равно придется.
• Так же придется знать что такое TLB, write buffer, как происходит инвалидация кэша, что такое false sharing и тд.
• Загрузка процессора под 100% вовсе не означает что он используется эффективно.
• Хотелось бы все эти заботы переложить на плечи разработчиков библитек и инструменов разработки.

Threaded vs Event driven

Как правило, при создании сервера перед нами глобально стоит всегда один и тот же выбор - threaded или event driven.

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

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

Итак, введем следующие обозначения:

T - пропускная способность сервера, количество запросов в секунду.

C - время, затрачиваемое процессором на выполнение запроса (CPU time).

I - время, затрачиваемое потоком на синхронное выполнение операций ввода/вывода (I/O time).

N - количество процессоров.

M - количество потоков.
Я считаю что мы пишем сервер, который выполняет запросы, каждый запрос выполняется фиксированное время, часть времени тратится на выполнение операций ввода вывода - I, а часть на обработку - C.

Максимальная пропускная способность event driven сервера - T = N/C. Это должно быть интуитивно понятно, пропускная способность максимальна тогда, когда процессор загружен обработкой запросов на 100%.
Пропускная способность многопоточного сервера - T = M/(I + C). Последняя формула справедлива только в том случае, если процессор загружен не полностью, иначе, увеличение M не будет приводить к увеличению пропускной способности сервера. Если эта зависимость кажется вам не очевидной, представьте что у нас есть однопоточный сервер (М = 1), его пропускная способность должна быть обратно пропорциональна сумме I + C, так как весь ввод/вывод выполняется синхронно и блокирует поток.
Наша задача состоит в том, что-бы определить такое количество потоков, при котором пропускная способность многопоточного сервера является максимальной. Очевидно, она будет равна максимально пропускной способности event driven сервера:

T = N/C = M/(I + C);
M = N (I/C + 1);

Как это можно использовать на практике? Очень просто, допустим, выполнение запроса у нас занимает 1мкс, а операции ввода вывода - 1мс. При N = 1, подставляем значения в формулу - M = 0.001/0.000001 + 1 = 1001, ровно столько потоков нам нужно для того, чтобы полностью загрузить один процессор. Очевидно, что в данном случае лучше использовать event driven архитектуру.

Другой пример, время обработки С = 100мкс, время выполнения ввода/вывода I = 1мс, M = 11. В данном случае можно обойтись threaded архитектурой сервера.

У вас может возникнуть следующий вопрос, что будет, если во втором примере к серверу подключится множество клиентов, намного больше одиннадцати и не лучше ли выбрать в этом случае event driven подход? Ответ - а черт его знает, в режиме перегрузки обе архитектуры работают плохо, в рамках event driven подхода будет увеличиваться среднее время обработки отдельного запроса и объем используемой памяти. Ровно тоже самое будет происходить с threaded сервером, который запустит слишком много потоков. Возможно, event driven сервер будет работать в режиме сильной перегрузки немного лучше, но это вовсе не обязательно и вообще зависит от конкретной реализации.

Disruptor

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

Представим себе некую сложную систему из очередей и потоков, у нас есть N потоков, которые связаны N + 1 очередями. Пускай очереди реализованы на основе массивов. У нас есть множество массивов, каждое сообщение N + 1 раз записывается в массив и N + 1 раз читается из массива, при этом происходит N + 1 изменений переменных head и tail разных очередей. Даже если все очереди, это SPSC очереди, это несколько избыточно. Для решения этой проблемы, разработчики LMAX создали библиотеку Disruptor для java. Помимо этого, уже существуют .NET и С++ порты, примеры в этой статье будут использовать .NET порт.

Очереди сообщений

Я хотел написать пост о библиотеке disruptor, начал писать введение и, совершенно случайно, написал целый пост :)
Итак, очереди бывают разными, бывают очереди, с помощью которых реализуют обход графа в ширину, а бывают такие очереди, с помощью которых можно передавать сообщения от одного потока к другому, этот пост именно о них.
Для начала договоримся, что очередь, это структура данных, поддерживающая две операции - enqueue и dequeue, добавление и извлечение элемента данных из очереди. Элементы извлекаются из очереди в FIFO порядке.
Когда речь заходит о распараллеливании каких либо вычислений, то многим на ум сразу приходит параллелизм на уровне данных, то бишь одну половину массива мы обрабатываем в одном потоке, а вторую в другом, в простейшем случае. Либо как нибудь еще разбиваем задачу на независимые части, обрабатываем их на разных процессорах и затем объединяем результаты.