Очень серьезный блог

Some obvious things about asynchronous network I/O

noreply@blogger.com (Anonymous) — Fri, 19 Dec 2014 22:37:00 +0000

Async IO and async API is a two different things that often confused. First is what we usually want, second is what we doomed to deal with all the time. But these are not the same thing. You can achieve asynchronicity using only synchronous API but at the same time you can fail to do this using asynchronous calls. This can be illustrated with this boost.asio example:
link to source
It is obvious (for somebody who knows boost.asio API) that this code uses async I/O, `async_read_some` and `async_write` is asynchronous calls. This is a part of the server code. Server reads some data from socket asynchronously first and then it asynchronously writes response to the socket. All input and all output in this program is non-blocking but anyway - this server is synchronous because server can't write data to the socket until it reads something from it!

Yes, this is echo server, it works that way, but this pattern can be found in many "asynchronous" applications. One example - RPC system. You "call" method and your RPC library wraps arguments in a packet and sends it to RPC server. Now server can perform some processing and return error code sending another packet back. In this case no matter what API you use - synchronous or asynchronous, interaction between single client and server will be synchronous anyway.

The worst thing is that performance of such system will be limited by the network latency and not by the network bandwidth. Because each RPC call will result in network round-trip.

So, what's the conclusion?

Don't be fulled by `async` buzzword, pay attention to system interaction (protocols), not to API being used to implement that interaction.
Design your protocol in such a way that can utilize high network bandwidth.
And finally - do the crazy things! For example, you can perform your RPC calls without waiting for responses assuming that no error was occurred but if this is not the case - you can rollback changes that was made under the wrong assumptions. Or if you know that client will request some data from server with 99.(9)% probability, you can send this data without waiting.

C++ Myths Debunking (part 1)

noreply@blogger.com (Anonymous) — Wed, 26 Nov 2014 19:01:00 +0000

It is well known that small object allocation in C ++ is slow. This is a quote from Andrey Alexandrescu book “Modern C++ Design”:

For occult reasons, the default allocator is notoriously slow. A possible reason is that it is usually implemented as a thin wrapper around the C heap allocator (malloc/realloc/free). The C heap allocator is not focused on optimizing small chunk allocations.

…
In addition to being slow, the genericity of the default C++ allocator makes it very space inefficient for small objects. The default allocator manages a pool of memory, and such management often requires some extra memory. Usually, the bookkeeping memory amounts to a few extra bytes (4 to 32) for each block allocated with new. If you allocate 1024-byte blocks, the per-block space overhead is insignificant (0.4% to 3%). If you allocate 8-byte objects, the per-object overhead becomes 50% to 400%, a figure big enough to make you worry if you allocate many such small objects.

Book states that memory allocation is in fact slow and more of that, it states that allocation of small objects using malloc and new can cause high memory fragmentation. As far as I understand this is a common knowledge beyond C++ programmers. Many of us believes that fancy allocators and manual memory management is a Good Thing. Maybe this was true when book was released first (more than ten years ago) but not now! Let’s check the facts.

I’ve created this gist to show the state of things - link. This code allocates one million small objects using simple segregated storage (boost.pool) frees memory and then allocates another million of small objects using jemalloc. Time and memory usage is tracked. Result can be surprising - link.

First - malloc is slower than memory pool but not drastically. On my machine it’s five times slower than memory pool if deallocation time was taken into account and only three times slower if it wasn’t (this is relevant for some applications). Second - using jemalloc to allocate memory for small objects actually saves some space! Memory pool have used 20Mb of RAM and jemalloc have managed to fit everything into 16Mb.

This isn’t surprising because jemalloc implements simple segregated storage under the hood. It manages memory better than most of the fancy handwritten memory allocation schemes on Earth. It is a better option than custom allocator most of the time because it’s stable, fast and it can give you some feedback. It can be beaten by some custom allocation scheme in synthetic tests but not in practice.

And finally you can always switch different allocators (jemalloc/tcmalloc/whatsoever) using LD_PRELOAD. This is not the case with custom hand-coded allocators - if you make mistake you can’t fix it without rewriting your code.

noreply@blogger.com (Anonymous) — Sat, 01 Nov 2014 08:36:00 +0000

Недавно я наконец зарелизил akumuli. Все что планировалось - сделано.Дальше я планирую улучшить компрессию для real значений, избавиться от зависимости из библиотеки boost, оставить только header-only библиотеки оттуда, чтобы упростить deployment. Ну и наконец допилить враппер для Golang.

Теперь о том, что будет дальше. Если кто-то внимательно изучил принцип работы моего движка для хранения данных, то этот человек мог заметить, что он организован не совсем так, как это обычно бывает. Обычно, такие вещи оптимизируются для запросов, возвращающих один временной ряд, чтобы иметь возможность быстро построить по нему график. Это здорово, но это могут делать graphite, influxedb, open tsdb, kairosdb, seriesly и тд. Но это не то что делает time series БД, по сути все вышеперечисленные решения, они не time-series а metrics databases. Они нужны в основном для devops применений, что хорошо, так как количество таких применений растет, но вот делать yet another metrics storage мне не очень интересно.

Akumuli не может быстро вернуть один временной ряд, это все выливается в полное сканирование тома. Это все именно так и задумывалось, потому что я пытаюсь построить TSDB, которая не предназначена для построения графиков, вместо этого, она должна уметь делать similarity search. Мой поинт в том, что чем больше time-series данных вы собираете, тем более бесполезными становятся обычные способы работы с ними ну и тем более бесполезным становится построение графиков по ним. Для того, чтобы работать с такими объемами информации, нужно уметь их эффективно майнить. Именно это akumuli и научится делать в ближайшем будущем. Для mining-а этих данных не нужны ни point-запросы ни способность быстро извлечь одну серию, для этого нужно уметь быстро строить индексы, а для этого нужны уметь быстро сканировать все данные.

Можно коротко описать принцип работы TSDB для майнинга следующим образом:

Собираем данные и записываем их на диск.
Делаем из длинных серий короткие с помощью sliding window.
Делаем dimensionality reduction, есть много методов основанных на преобразовании Фурье, wavelet transform и даже преобразовании в текст.
Индексируем то что получилось с помощью R-tree, VA-files или чего-нибудь еще.
Выполняем запросы с погрешностью используя полученные индексы, если нужно - читаем оригинальные данные.

Это все желательно уметь делать не на одной машине а на нескольких.

noreply@blogger.com (Anonymous) — Fri, 01 Aug 2014 22:20:00 +0000

Небольшой отчет о статусе akumuli. Итак, я реализовал всю основную функциональность.
Запись - работает, пропускную способность по записи я особо изощренно не тестировал, на моем старом ноутбуке, akumuli может прожевать порядка 3х миллионов insert-ов в секунду (и прочитать их потом назад, что немаловажно). На нормальном железе - заметно больше. Это все благодаря тому, что akumuli трансформирует случайную запись в последовательную запись, с которой у современных железок все очень хорошо и замечательно. В будущем производительность будет ниже, так как ей придется немного пожертвовать ради повышения отказоустойчивости. До сих пор не реализованы некоторые важные вещи, например синхронизация чтения и записи при перезаписи старых данных.
Поиск - тоже работает. Он требует оптимизаций (оптимизация с помощью mincore еще не реализована), но корректно ищет все что нужно. Возможно стоит реализовать простой планировщик запросов, например, на основе алгоритма FSCAN.
Я серьезно переработал in-memory индекс для данных, не вышедших за пределы sliding window. Теперь он основан не на B-tree, а на алгоритме patience sort. Подробно с алгоритмом можно ознакомиться в википедии. Если коротко, то все работает примерно так - в начале у нас есть пустой массив, элементами которого являются sorted runs - отсортированные в порядке увеличения меток времени массивы. Когда записывается первый элемент, в этот массив добавляется единственный sorted run из одного, только что добавленного, элемента. Далее, при записи следующего элемента, мы смотрим на его метку времени и, если она больше или равна метке времени предыдущего элемента, то этот элемент добавляется в тот же sorted run, если она меньше - то создается еще один sorted run. Далее, процесс повторяется для каждого последующего элемента, в результате чего, мы получаем набор отсортированных массивов. Их не может быть очень много, так как глубина записи ограничена sliding window. Эти массивы и есть индекс. Когда нужно слить всю информацию на диск (данные вышли за пределы sliding window), они сливаются с помощью простого k-way merge-а, очень быстро и эффективно. В этих массивах можно легко искать простым бинарным поиском, запись в такой индекс происходит быстрее чем запись в b-tree, даже на самых неудобных данных.
В ближайшее время я планирую реализовать синхронизацию между чтением и записью и оптимизировать поиск. После этого, возможно, у меня дойдут руки до whitepaper-а по системе.

noreply@blogger.com (Anonymous) — Wed, 11 Jun 2014 20:14:00 +0000

Как вы возможно помните, я пишу хранилище для временных рядов - akumuli. В данный момент я занят самим "движком" для хранения данных, однако планирую и frontend, который будет уметь записывать и считывать данные по сети. Для этого, мне нужен какой-нибудь механизм сериализации, само собой - он должен быть быстрым и эффективным, но самое главное - он должен быть безопасным. В идеале - сервер должен уметь торчать в интернет, с оговорками, вроде ограничения количества сообщений от одного клиента в time-frame.
И тут все очень плохо. Очень многие библиотеки сериализации проектировались без учета требований безопасности и позволяют положить сервис одним сообщением. За примерами далеко ходить не надо, вот, например, один товарищ с RSDN написал библиотеку сериализации - YAS (Yet Another Serializer) для С++. Это header only библиотека, умеющая сериализовать как стандартные контейнеры, так и контейнеры из boost и Qt. Можно также сериализовать пользовательские типы, интерфейс похож на boost::serialization. Библиотека YAS заявлена как drop-in replacement (correct me if I wrong) для boost::serialization, что хорошо, и работает заметно быстрее оного, что тоже хорошо. Что не хорошо, так это возможность уронить сервис одним сообщением:

Внимательно смотрим на 13-ю строку. Несложно догадаться, что нам достаточно передать вместо длины списка очень большое число, чтобы сервис упал или ушел в своп, при этом элементы списка можно не передавать вовсе! Вызов list.resize попытается создать нужное количество элементов, сделав столько аллокаций, сколько мы ему скажем, причем в выделенные участки памяти он будет писать, а значит память реально будет выделяться системой. При этом YAS не позволяет задать максимальный размер сообщения и ограничить максимальную длину списка. Этот фокус можно повторить для других типов, поддерживаемых этой библиотекой - deque, stable_vector из boost, может еще что-то.

Можно подумать, что это проблема только одной библиотеки, но на самом деле, такая фича у библиотек сериализации встречается часто (при том, что это самая очевидная ошибка из всех, что они могут сделать). Вот, например, cereal - второй по счету результат в выдаче на github по запросу serialization для языка С++.

Очень похоже, не правда ли? Я проверил, там нигде размер не проверяется.
А теперь внимание, простой вопрос - если настолько простая дыра в безопасности лежит на виду в проекте, у которого больше 300 лайков на github и за которым следят больше сорока человек, то сколько таких дыр будет в проекте попроще? :)
К слову, C++ реализация protocol buffers ничем подобным не страдает, там можно ограничить максимальный размер сообщения сверху (64Мб по умолчанию, но можно задать свое значение), а максимальная длина их base-128 variant-ов ограничена 64-мя битами.

Бывают примеры и посложнее, вот, например реализация message pack для Go, там, на 179-й строке есть функция unpack, которая вызывает сама себя рекурсивно, в зависимости от того, что встретит в потоке данных. Это нужно для того, чтобы парсить всякие вложенные структуры данных, вроде массива строк, т.е. глубина рекурсии зависит от входящих данных! Можно очень легко создать такое сообщение, которое заставит эту функцию вызвать себя очень много раз подряд и сожрать очень много памяти под стек, вообще сколько угодно памяти (в Go не получится переполнение стека из-за особенностей рантайма, но стек расти все равно будет). Если бы это было написано не на Go, а скажем, на Java, мы бы могли получить переполнение стека куда быстрее, чем сожрать всю память :)

В общем, нужно писать хороший и безопасный код и не писать плохой, а также стараться использовать поверенные решения и анализировать сторонний код, используемый в вашем приложении. Спасибо за внимание! :)

Про юнит-тесты

noreply@blogger.com (Anonymous) — Wed, 28 May 2014 22:07:00 +0000

В последнее время модно ругать юнит-тесты, по разным причинам. Сложность поддержки в актуальном состоянии системы юнит-тестов, отсутствие 100% гарантии корректности кода в случае, если тесты проходят, использование интеграционных тестов, очень многий код сложно тестировать с помощью юнит-тестов, существование практики написания тестов тупо ради покрытия и тд.
Я не собираюсь быть адвокатом какой-либо из сторон спора, вместо этого, я хочу показать, что юнит-тесты - вещь простая и естественная, вытекающая из нормальной практики программирования.
Итак, когда опытный программист пишет код функции с нетривиальной логикой, он думает в том числе и в терминах инвариантов. Практически любой код содержит кучу инвариантов (инварианты циклов, инварианты состояния объектов и тд) и желание зафиксировать их в коде - вполне естественно. Обычно, это делается с помощью assert-ов. Assert-ом удобно проверять, например, что счетчик ожидающих обработки элементов, после выполнения цикла, будет равен нулю, либо, что указатель находится внутри массива, перед выбрасыванием исключения можно проверять - не останется ли объект после этого в невалидном состоянии, и тд и тп.
Но более сложные инварианты с помощью assert-а проверить проблематично. Здесь уже программисты часто прибегают к условной компиляции, для того, чтобы вставить дополнительные проверки в отладочный билд.
Все эти проверки засоряют код, который помимо основной логики и логики обработки ошибок, содержит теперь и кучу отладочного кода, который заботливо вырезается компилятором в релизной версии. Если написать много такого кода, то обязательно появится следующая идея - "а почему бы не вынести все это в отдельное место, чтобы оно не мозолило глаза" и появляются юнит тесты. Вот и все :)

Akumuli: поиск и выборка данных

noreply@blogger.com (Anonymous) — Tue, 25 Feb 2014 22:24:00 +0000

Итак, в прошлом посте мы выяснили, что данные на диске хранятся очень просто - в больших, плоских файлах, отсортированными по возрастанию. Осталось только научиться в них искать. Самое очевидное решение - бинарный поиск. Представим для простоты, что мы ищем конкретные пары значений: метка времени + идентификатор и не занимаемся поиском диапазонов, выборкой срезов и тд, для простоты.

Все плохо

Допустим, мы храним простые, 4х байтовые значения, к которым akumuli добавит 20 байт заголовка - идентификатор параметра и метку времени. Том у нас имеет размер 4Гб, бинарный поиск делает log2(N) итераций в худшем случае, отсюда: log2(4GB/24B) = 27. Это значит, что нам потребуется до 27-ми итераций бинарного поиска. Причем первые итераций эдак 25, будут приводить к hard page fault (я использую отображаемые в память файлы для поиска), если поиск выполняется в первый раз. Если сравнить это с B-tree, для которого нам потребуется загрузить в худшем случае пять страниц (если размер страницы - 4КБ), то сразу станет понятно, почему так никто не делает. Бинарный поиск не является cache oblivious алгоритмом и будет работать не эффективно.

Поиск решения

К счастью, мы можем использовать специфику данных. Источники time series данных, очень часто бывают периодическими, например, это могут быть датчики, передающие показания с определенной частотой. Не обязательно, чтобы каждый источник был периодическим, так как параметров много, можно с высокой долей вероятности ожидать, что информация будет записываться примерно с одинаковой скоростью. А это как раз тот случай, когда можно использовать интерполирующий поиск. Принцип работы этого алгоритма крайне прост: мы знаем максимальную и минимальную метки времени, а также количество элементов в томе, мы делаем предположение о том, что метки времени всех данных распределены равномерно на этом промежутке времени, исходя из этого, мы можем приблизительно определить, где в томе может находиться искомое значение.

Интерполирующий поиск имеет сложность O(log log N), что уже сильно лучше бинарного поиска и близко к B-tree. В случае периодических источников, нам потребуется загрузить ровно столько же страниц, сколько в случае B-tree с размером страницы в 4КБ (выкладки пожалуй не буду приводить, но я считал, правда!). Но это нельзя считать решением, так как в реальности, даже с периодическими источниками можно получить неравномерное распределение, например в случае, если на какое-то время легла сеть и мы ничего не получали. В случае click-stream-ов мы будем наблюдать всякие суточные ритмы и тд. В общем, в реальности распределение может быть неравномерным. В этом случае, интерполирующий поиск будет ошибаться и делать больше итераций чем нужно (потенциально, даже больше чем бинарный поиск). Поэтому, мой алгоритм поиска делает ровно пять шагов интерполирующего поиска, а затем, откатывается на бинарный поиск. Почему именно пять? Это ровно столько, сколько нужно для того, чтобы найти результат в случае равномерного распределения.

Улучшения и оптимизации

Этим все не ограничивается. Алгоритм поиска старается на каждом этапе уменьшить область поиска. В самом начале область поиска равна всему тому, но на каждой итерации интерполирующего поиска одна из границ сдвигается ближе к искомому элементу. В случае, если область поиска сузилась до одной страницы, алгоритм откатывается на бинарный поиск, так как чем меньше масштаб, тем сильнее сказывается неравномерность распределения данных по меткам времени. Интерполирующий поиск старается сместить обе границы, если произошел overshoot, то на следующей итерации он постарается сделать undershoot. Это позволяет быстрее уменьшать область поиска.

Помимо этого, я планирую учитывать состояние страниц виртуальной памяти при поиске. Так как том мапится в память, одни страницы на момент поиска могут быть уже загружены с диска, а другие - еще нет. Мы можем получить эту информацию от операционной системы (системный вызов mincore в linux, в windows не помню как, но это тоже возможно). Во время поиска, мы можем использовать эту информацию для того, чтобы избежать page fault-ов, обращаясь только к загруженным в память страницам. Алгоритм поиска позволяет это делать, интерполирующий поиск может проверить не тот элемент, адрес которого он вычислил, а тот, который находится в ближайшей загруженной странице памяти. Бинарный поиск может проверить элемент не точно в середине области поиска, а ближайший из загруженных. Естественно, иногда все же придется обращаться к страницам, отсутствующим в памяти.

Open problem

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

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

Akumuli: запись и хранение данных

noreply@blogger.com (Anonymous) — Mon, 24 Feb 2014 22:19:00 +0000

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

Как известно, данные на диске можно хранить в различных B-деревьях, это такая структура данных, которая позволяет искать по ключу за логарифмическое время, но в тоже время - читая минимальное количество страниц памяти с диска. Для хранения time series данных, умные люди очень давно придумали TSB tree и некоторые другие структуры данных на основе B-tree.

Изначально, я планировал реализовать свой проект на основе TSB-tree, это вполне возможно и мне кажется, это и есть самый правильный дизайн. Но я попытался создать небольшой прототип на питоне и понял, что это не так просто, как кажется. Особенно, если хочется чтобы библиотека использовала фиксированное количество места на диске. Так как это персональный проект и я не могу тратить на него много времени, я решил отказаться от реализации TSB-tree, ведь помимо описанной мной проблемы тут есть проблемы синхронизации, проблемы целостности/восстановления данных, так как структура достаточно сложная.

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

Persistent storage

Итак, данные в akumuli хранятся в томах, размер каждого тома - 4Гб. Все тома создаются заранее, при создании хранилища, и образуют циклический список. В любой момент времени мы можем писать только в один том. При этом, метки времени в соседних томах могут пересекаться. На высоком уровне, алгоритм записи выглядит очень просто - мы пишем в открытый том до тех пор, пока он не заполнится, затем, открываем следующий и пишем в него. Если в следующем томе есть данные - они теряются. Вы уже наверное поняли, что глубина хранения данных определяется размером хранилища, новые данные просто перезатирают самые старые, также как в rrd-tool. Это осмысленное решение а не недостаток дизайна, оно не позволяет задавать глубину хранения для каждого параметра в отдельности, но зато, позволяет писать софт, который работает предсказуемо, не падая от нехватки места на диске.

Внутри тома все тоже устроено достаточно просто. Том, по сути, очень похож на узел B-tree, но только очень большой. Вначале тома располагается header с метаданными (количество добавленных элементов и тд), далее следует массив смещений, оставшееся место занято непосредственно данными. Каждый элемент данных начинается с заголовка - метки времени и идентификатора параметра, за которым следуют пользовательские данные переменной длины.

Данные записываются начиная с конца тома, в обратном направлении. На изображении, смещения увеличиваются слева направо, при этом элемент данных "А" был добавлен первым, "В" - вторым, а "С" - третьим. В массив смещений записываются смещения элементов данных (как неожиданно!). Причем смещения, как раз записываются в прямом порядке.
На изображении, элемент массива с индексом 0 содержит смещение элемента "А" и был добавлен первым. Запись в том заканчивается тогда, когда массив смещений и данные встречаются, т.е. между последним добавленным элементом массива данных и последним смещением не достаточно места для добавления следующего элемента данных.

Такая схема позволяет, во первых, хранить данные переменной длины, во вторых, записывать данные в том очень быстро (запись линеаризуется, мы используем пропускную способность дисков по максимуму) и самое главное, эта схема позволяет очень быстро сортировать данные, для этого достаточно отсортировать массив смещений. Тот факт, что данные в томе могут быть отсортированы в порядке, отличном от порядка добавления также отражен на рисунке (элементы массива 1 и 2). Помимо этого, данная схема позволяет легко вводить избыточность, которая нужна для эффективного поиска редко обновляющихся данных. Можно добавить смещение старого элемента еще раз, чтобы алгоритму поиска не нужно было сканировать том глубоко (показано пунктирной линией).

Эта схема позволяет также хранить вместе с пользовательскими данными всякую вспомогательную информацию, сводки (rollups), хинты для алгоритма поиска и прочие метаданные.

In-memory cache

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

Кэш в памяти у меня построен на основе B-tree (реализация гугла), в качестве ключа используется кортеж из метки времени и ид-ра параметра, значение - смещение элемента в томе. Б-деревья выбраны не случайно, time-series данные имеют одну особенность, метка времени как правило возрастает, это значит, что данные в B-tree добавляются почти всегда в порядке возрастания, а это sweet spot для B-tree. Режим, в котором вставка в B-tree выполняется очень быстро.

Кэш организован следующим образом, данные хранятся в bucket-ах (штука, которая содержит внутри себя дерево и кое какую метаинформацию). Каждый такой bucket отвечает за небольшой интервал времени, кратный глубине окна записи, эти интервалы не пересекаются. Bucket-ы объединены в список, в хронологическом порядке. Устаревшие bucket-ы, запись в которые уже запрещена (они вышли за границу окна записи), извлекаются из конца списка по очереди, их содержимое перебирается в порядке возрастания и получившаяся последовательность смещений записывается в соответствующий сектор массива смещений тома. Future write приводит к созданию нового bucket-а (на самом деле не созданию, а извлечению готового из пула, zero allocation).

Concurrency

В кэш можно писать параллельно из нескольких потоков, чем больше потоков пишут в один bucket, тем больше lock contention и тем все медленнее. Чтобы решить эту проблему, bucket содержит не одно дерево, а несколько, по количеству процессоров/ядер. Каждый поток сначала выбирает свой экземпляр B-tree из bucket-а, лочит его, а затем - пишет в него. Это уменьшает contention и улучшает cache locality, в общем, все работает лучше. При сохранении последовательности смещений на диск, последовательности, полученные от отдельных деревьев сливаются в одну, а уже потом - записываются в том.

Comming soon

В следующей статье я постараюсь описать то, как выполняется поиск.

noreply@blogger.com (Anonymous) — Sun, 23 Feb 2014 23:07:00 +0000

Несколько месяцев назад, я начал работать над своим собственным open source проектом. Попробую рассказать почему я это все начал и чего хорошего хочу сделать.

Итак, все началось с того, что я не смог найти time-series БД, которая бы являлась продуктом с открытым исходным кодом и при этом нормально работала. Time-series данные, это любые данные снабженные меткой времени и идентификатором параметра (aka идентификатор метрики, aka идентификатор источника). Параметры могут соответствовать, например, разным сенсорам, разным измеряемым величинам, разным пользователям в click stream-е и тд.

Главная проблема time-series данных в том, что их всегда очень много. Представьте себе большой датацентр, в котором работают 10 000 машин, на каждой из которых специальный демон десять раз в секунду измеряет количество свободной памяти, загрузку CPU и отправляет это все в БД. Казалось бы, десять раз в секунду это не очень много, но это уже 100k операций записи в секунду, и это не пик, это sustained write rate, для данных, не помещающихся в память. А что, если потребуется измерять значения параметров не десять раз в секунду, а сто?

Самое известное решение этой проблемы - rrd-tool, де факто стандарт во многих областях, имеет жутко неэффективный формат хранения данных с огромным количеством недостатков. Для того, чтобы понять как плох rrd-tool (но в то же время хорош, для определенных применений), нужно понять как он хранит данные, я не буду вдаваться в подробности, скажу лишь, что точность хранения меток времени там ограничена, количество параметров там также ограничено, чем их больше, тем медленнее все работает. Запись в rrd файл это множество random writes. В общем, rrd подходит для чего-нибудь небольшого и не требовательного.

Представитель принципиально другого класса систем - open tsdb (и 100500 подражателей) тоже не слишком хорош, на мой взгляд. Во первых, оно зависит от hadoop и hbase. Hbase используется для хранения данных. Поэтому, open tsdb нельзя использовать в качестве embedded БД. Если вы пишете софт, который работает на каком нибудь промышленном ПК, собирающем данные от каких-нибудь датчиков, то вы open tsdb использовать не сможете. Помимо этого, open tsdb округляет метки времени. Для мониторинга серверов (задача, для которой open tsdb создавалась) это подходит. Для других применений - не всегда.

Самый главный недостаток всех этих систем - они игнорируют специфику данных. Как правило, они формируют некий ключ, комбинируя идентификатор параметра и метку времени, затем этот ключ используется для записи (в hbase, cassandra, leveldb etc). Для того, чтобы найти это значение, нужно использовать точно такой же ключ. По сути, эти БД работают с точечными данными. Отсюда все эти округления меток времени и тд. Главная задача той же open tsdb - построить сводки (rollups), а не поиск значения параметра X в момент времени Y.

В настоящей time series БД, операция записи создает не точку, а линию. Если мы записали значение параметра в момент времени T0, а затем ищем его значение в момент времени T1, причем T1 > T0, то мы должны найти ранее записанное значение. Это логично, ведь между моментами времени T0 и T1 значение параметра не менялось. К сожалению, большинству time series баз данных это неведомо.

В общем, я пришел к выводу, о необходимости создания специализированного бэкенда для таких данных. LevelDB, HBase и им подобные - не решают всех проблем. Собственно, я собираюсь заполнить данный пробел, создав быстрый и в тоже время "правильный" backend.

Цели пока такие:

Способность выдавать порядка миллиона операций записи в секунду на моем ноутбуке.
Использование фиксированного количества места на жестком диске (как rrd-tool).
Кэширование наиболее актуальных данных в памяти.
Хитрый алгоритм поиска, который я придумал, но еще не реализовал :)

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

Behold!

noreply@blogger.com (Anonymous) — Sun, 14 Apr 2013 10:21:00 +0000

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

Есть такой стандарт — 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

noreply@blogger.com (Anonymous) — Sun, 20 Jan 2013 12:04:00 +0000

Пожалуй я не сильно ошибусь, сказав что существует всего два механизма управления изменениями - пессимистичный и оптимистичный. Первый мы уже давно используем в своих программах в виде всевозможных мьютексов и семафоров. Второй механизм, до недавнего времени, применялся в различных СУБД.
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

noreply@blogger.com (Anonymous) — Wed, 13 Jun 2012 10:20:00 +0000

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

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

К сожалению, в реальности, все несколько хуже. Во первых, во время удвоения нам нужно выделить память под новый массив и скопировать в него содержимое старого, следовательно, расходы по памяти составят 3*N. Во вторых, постоянное пересоздание массива приводит к фрагментации памяти, так как для выделения памяти под массив при очередном удвоении размера, менеджер памяти не может использовать память, освобожденную динамическим массивом ранее. Именно по этому, во многих реализациях, массив увеличивают не в два раза, а в меньшее число раз, например в полтора. В третьих, данный алгоритм, даже имея сложность O(N), имеет достаточно большую коснтанту, так как периодически перезаписывает большие участки памяти.

Существует множество способов решения этих проблем. Один из этих способов очень похож на метод удвоения: вместо того, чтобы хранить элеметы в одном большом массиве, можно хранить их в последовательности массивов меньшего размера, при этом первый подмассив должен хранить один элемент, а каждый следующий - в два раза больше чем предыдущий. Для поиска i-го элемента массива нам нужно выполнить две операции: определить позицию старшего бита индекса - k и вычислить значение b, равное значению индекса без старшего бита. При этом значение k будет номером подмассива, а b - индексом элемента в этом подмассиве. Алгоритм добавления элемента в такой динамический массив достаточно очевиден, поэтому я его не буду описывать. Данный подход решает две проблемы из трех. Он не переписывает кучу памяти и не вызывает фрагментацию, но он по прежнему приводит к потерям памяти порядка O(N). В простыне кода в конце поста, данный алгоритм реализован в классе ResizableArray.

Существует еще один алгоритм, позволяющий решить все три проблемы, он хорошо описан в этой статье - http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf. Это по сути дальнейшее развитие предыдущего алгоритма, подмассивы(суперблоки) мы делим на множество блоков, каждый из которых имеет размер Sqrt(N), где N - размер суперблока, причем в каждом суперблоке у нас будет Squrt(N) блоков. Подобная схема позволяет сократить потери памяти до O(Sqrt(N)), при этом операции добавления и поиска элемента по индексу, будут иметь сложность O(1), как и прежде. Данный алгоритм реализован в классе ResizableArrayV2.

Класс ResizableArray примерно в 2.5 раза быстрее нежели std::vector при добавлении большого количества элементов, в 3.5 раза медленнее вектора при чтении и имеет ровно такие же потери памяти. Класс ResizableArrayV2 примерно в полтора раза быстрее вектора при добавлении элементов, в 4.5 раза медленнее при чтении, но зато он обеспечивает очень низкий, по сравнению с вектором, уровень потерь памяти. Нужно также добавить, что код практически не оптимизирован (я только цикл для вычисления индекса старшего бита равзернул), так-что ситуация может быть несколько лучше.

Вот собственно сам код (ни разу не production качества, имейте ввиду):

noreply@blogger.com (Anonymous) — Fri, 01 Jun 2012 09:09:00 +0000

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

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

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

Threaded vs Event driven

noreply@blogger.com (Anonymous) — Tue, 15 Nov 2011 19:32:00 +0000

Как правило, при создании сервера перед нами глобально стоит всегда один и тот же выбор - 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

noreply@blogger.com (Anonymous) — Sun, 02 Oct 2011 16:15:00 +0000

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

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

В общем, disruptor это один большой кольцевой буфер, с помощью которого можно заменить целый огород из очередей. Во время создания, кольцевому буферу передается его размер и фабрика для создания объектов. Помимо этого, буфер можно немного настроить, он может использовать разные механизмы ожидания, блокирующий, yield (передает управление другому потоку) и spin wait. Буфер заполняется созданными фабрикой объектами, которые из него никогда не удаляются.

  var ringBuffer = new RingBuffer<ValueEntry>(
    () => new ValueEntry(),
    100 * 1024,
    ClaimStrategyFactory.ClaimStrategyOption.SingleThreaded,
    WaitStrategyFactory.WaitStrategyOption.Yielding);

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

  var cons = new ValueConsumer(COUNT);
  ringBuffer

    .ConsumeWith(new Incrementer())
    .Then(new Incrementer(), new Decrementer())
    .Then(cons);

В данном примере мы создаем конвейер из трех этапов, на пером этапе каждое сообщение будет обработано одним потребителем Incrementer, на втором двумя(Incrementer и Decrementer), и на третьем - одним потребителем типа ValueConsumer. При этом сообщение останется в массиве после того, как все потребители его обработают, в дальнейшем его перезапишет производитель. Потребители, это объекты, реализующие интерфейс IBatchHandler<T>:

  class Incrementer : IBatchHandler<ValueEntry>
  {
    public void OnAvailable(long sequence, ValueEntry data) {
      data.Value++;
    }

    public void OnEndOfBatch() {
    }
  }

Хочу обратить внимание на то, что потребитель изменяет параметр data, параметр data, это элемент кольцевого буфера, sequence - номер сообщения. После этого, пользователь библиотеки должен создать producer barrier - объект, с помощью которого он будет добавлять новые сообщения. Producer barrier может быть многопоточным, тогда внутри себя он будет использовать атомарные операции, либо однопоточным, тогда он будет работать немного быстрее в случае, если вызывается из одного потока.

  var pbarrier = ringBuffer.CreateProducerBarrier();
  ringBuffer.StartConsumers();

После того, как вы все это сделали, нужно вызвать метод StartConsumers, который запустит по одному потоку на каждого потребителя. Добавление нового сообщения выглядит следующим образом:

  ValueEntry data;
  var seq = barrier.NextEntry(out data);
  data.Value = i;
  barrier.Commit(seq);

мы должны в первую очередь вызвать метод NextEntry, который выделит в массиве место под наш новый элемент. При этом не происходит выделение памяти, элемент массива был создан заранее. Барьер использует claim factory для получения номера очередного сообщения (параметр claim factory конструктора) именно его и возвращает метод NextEntry. Далее, нужно изменить объект, ссылку на который мы получили вызвав NextEntry, например записав в него наше сообщение и затем, вызвать метод Commit, передав в него номер сообщения.
Такой хитрый метод записи позволяет добавлять элементы в буфер сразу из нескольких потоков без блокировок и синхронизации.Далее, будут вызываться методы OnAvailable всех потребителей в том порядке, который мы задали во время конфигурирования буфера. В этот метод также передается номер обрабатываемого сообщения, который можно использовать например для того, что-бы организовать обработку сообщений в round-robin манере, несколькими параллельными consumer-ами.

Обработчики содержат внутри себя свою текущую позицию и специальный объект, который создается с помощью wait factory, с помощью которого он может ждать появления доступных для обработки сообщений. Также, все обработчики знают о своих зависимостях и после обработки очередного сообщения "сигналят" следующему обработчику. Текущая позиция обработчика изменяется только из одного потока - потока этого обработчика, при этом генерируется write barrier. Перед тем как прочитать элемент, обработчик должен быть "разбужен" producer barrier-ом или другим обработчиком, он должен прочитать значение текущей позиции разбудившего (генерируется read barrier) и решить, сколько сообщений он может прочитать. Затем, для каждого из доступных сообщений будет вызван метод OnAvailable, а затем OnEndOfBatch.

OnEndOfBatch - позволяет обрабатывать сообщения не по оному а пачками, т.н. batch processing. Если ваш обработчик выполняет какой либо I/O, то лучше в методе OnAvailable формировать буфер для отправки(либо просто запомнить номера первого и последнего сообщений между вызовами OnEndOfBatch), а в OnEndOfBatch - непосредственно выполнять I/O.

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

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using System.Diagnostics;
using System.Collections.Concurrent;
using Disruptor;
 
namespace QueueTest
{
	class ValueEntry
	{
		public int Value { get; set; }
	}
 
	class Incrementer : IBatchHandler<ValueEntry>
	{
		public void OnAvailable(long sequence, ValueEntry data) {
			data.Value++;
		}
 
		public void OnEndOfBatch() {
		}
	}
 
	class Decrementer : IBatchHandler<ValueEntry>
	{
		public void OnAvailable(long sequence, ValueEntry data) {
			data.Value--;
		}
 
		public void OnEndOfBatch() {
		}
	}
 
	class ValueProducer
	{
		int count;
		IProducerBarrier<ValueEntry> barrier;
 
		public ValueProducer(int num, IProducerBarrier<ValueEntry> pbarrier) {
			count = num;
			barrier = pbarrier;
		}
 
		public void Run() {
			for (int i = 0; i < count; i++) {
				ValueEntry data;
				var seq = barrier.NextEntry(out data);
				data.Value = i;
				barrier.Commit(seq);
			}
		}
	}
 
	class ValueConsumer : IBatchHandler<ValueEntry>
	{
		int iter = 0;
		int count;
		AutoResetEvent evt;
 
		public ValueConsumer(int cnt) {
			count = cnt;
			evt = new AutoResetEvent(false);
		}
 
		public void OnAvailable(long sequence, ValueEntry data) {
			if (sequence == count - 1)
				evt.Set();
			if (data.Value != sequence + 1)
				Console.WriteLine("Error at {0}", iter - 1);
		}
 
		public void OnEndOfBatch() {
		}
 
		public void WaitForAll() {
			evt.WaitOne();
		}
	}
 
	class Program
	{
		const int COUNT = 100 * 1000;
		static void Main(string[] args) {
			var ringBuffer = new RingBuffer<ValueEntry>(
				() => new ValueEntry(),
				100 * 1024,
				ClaimStrategyFactory.ClaimStrategyOption.SingleThreaded,
				WaitStrategyFactory.WaitStrategyOption.Yielding);
 
			var cons = new ValueConsumer(COUNT);
			ringBuffer
				.ConsumeWith(new Incrementer())
				.Then(new Incrementer(), new Decrementer())
				.Then(cons);
			var pbarrier = ringBuffer.CreateProducerBarrier();
			var prod = new ValueProducer(COUNT, pbarrier);
			ringBuffer.StartConsumers();
			var sw = new Stopwatch();
			sw.Start();
			prod.Run();
			cons.WaitForAll();
			sw.Stop();
			Console.WriteLine("Disruptor: {0}ms", sw.ElapsedMilliseconds);
		}
	}
}

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

noreply@blogger.com (Anonymous) — Sun, 02 Oct 2011 14:58:00 +0000

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

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

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

Мы можем использовать на одном из этапов обработки несколько потоков, если эта операция требует больше вычислительных ресурсов. Для этого мы должны на стороне производителя в round-robin порядке выбрать очередь, в которую будем записывать, а на стороне потребителя, в том же самом порядке выбрать очередь из которой сообщение будет извлечено и помещено в следующую очередь(это если нам нужно сохранить порядок сообщений, если не нужно, то можно сделать проще). Для этого нам нужны два счетчика, изначально их значения должны быть равны, прежде чем добавлять элемент, мы вычисляем индекс очереди как i mod N, где i - значение счетчика, N - количество очередей, добавляем элемент - queues[i mod N].enqueue(X), после этого мы увеличиваем i на единицу.

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

Естественно, для решения этой задачи нельзя использовать std::queue, System.Collection.Generics.Queue, java.util.Queue или то, что есть в вашем любимом языке программирования. Эти структуры данных не потокобезопасны, доступ к ним придется синхронизировать, а это означает что два потока не смогут одновременно добавить и извлечь элемент из очереди.
Помимо этого, операции на стороне потребителя и производителя часто выполняются с разной скоростью, в случае, если производитель работает быстрее чем потребитель, достаточно долго, программа просто вылетит по OOM, так как в очередь будет помещено слишком много элементов.
Для решения всех этих проблем были созданы специальные очереди. Их можно классифицировать следующим образом: блокирующие - неблокирующие; ограниченные - неограниченные. Так же очереди классифицируют по уровню concurrency - single producer/single consumer(SPSC), single producer/multiple consumers(SPMC), multiple producers/single consumer(MPSC), multiple producers/multiple consumers(MPMC). При этом данные характеристики могут сочетаться произвольным образом, например single producer/multiple consumers очередь может быть ограниченной и неблокирующей одновременно.

Блокирующая очередь, это очередь, операции над которой могут заблокировать вызывающий поток до тех пор, пока состояние очереди не изменится. Например, в случае ограниченной очереди, попытка добавления элемента(enqueue) в переполненную очередь может быть заблокирована до тех пор, пока какой либо другой поток не извлечет элемент и не освободит место для нового элемента. Попытка извлечения элемента из пустой блокирующей очереди так же может заблокировать вызывающий поток до тех пор, пока в очередь не будет добавлен элемент. Обычно, для блокирующей очереди реализуют способ сообщить потоку потребителю, извлекающему сообщения из очереди, что производитель уже завершил работу. Данные свойства делают блокирующие очереди очень простым в использовании инструментом для организации совместной работы множества потоков.
Неблокирующие очереди, как правило просто возвращают признак того, была операция выполнена, или нет. Их преимущество, перед блокирующими очередями, состоит в том, что они могут быть реализованы без использования мьютексов, семафоров и прочих condintion variables, которые обычно применяются в блокирующих очередях для реализации ожидания.

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

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

Теперь о типах очередей с точки зрения concurrency.

SPSC - самая простая и быстрая очередь, она может быть реализована вообще без использования атомарных (команды с префиксом lock, блокирующие шину памяти на время выполнения) операций, достаточно двух барьеров памяти. Мало того, операции enqueue и dequeue могут быть реализованы как wait free операции (естественно, wait free гарантия здесь условна, так как в случае списка, нужно выделить память под новый элемент, в случае массива wait free гарантия может выполняться только тогда, когда есть место в массиве).

SPMC и MPSC очереди немного сложнее и медленнее, так как в данном случае несколько потоков могут бороться за head либо за tail указатели. По этой причине, данные очереди могут быть реализованы только с применением атомарных операций. Для такой очереди нужна как минимум одна CAS операция, с одной из сторон, для MPSC - со стороны производителя, для SPMC - со стороны потребителя.
MPMC - наиболее универсальная и наименее эффективная очередь. Она требует использования двух атомарных CAS операций, одной при добавлении элементов и одной при извлечении.

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

noreply@blogger.com (Anonymous) — Wed, 03 Aug 2011 09:16:00 +0000

Мне часто доводилось встречать на разных форумах и блогах такое мнение - если вы пишете приложение, критичное к скорости выполнения, то виртуальные функции не для вас. Обычно, в таких случаях советуют применять статический полиморфизм или еще что-то подобное.
На самом деле, с косвенными вызовами в общем и с виртуальными функциями/методами в частности - все хорошо. Современные процессоры умеют предсказывать ветвления даже в случае непрямого вызова, это может свести на нет все накладные расходы, связанные с вызовом виртуальной функции.
Проблема в другом. Часто, виртуальные функции используют следующим образом: создают массив/список указателей на базовый класс, обходят все элементы массива и вызывают виртуальный метод. Это приводит к тому, что количество L1 кэш промахов заметно увеличивается(виртуальный метод может быть переопределен и при каждом новом вызове процессор, в худшем случае, будет выполнять новый код). Помимо этого, такой подход уменьшает вероятность успешного предсказания ветвления.
Я написал небольшой тест, демонстрирующий эти эффекты. Сначала, в список добавляются все элементы одного класса, затем другого и тд. После этого, для каждого элемента списка вызывается виртуальный метод. На моей машине это происходит примерно за 300 миллисекунд. Далее, элементы списка перемешиваются случайным образом, что увеличивает время обхода списка с вызовом метода втрое! И в конце я вызываю, в точно таком же цикле, обычный, не виртуальный метод, который делает ровно тоже самое что и виртуальные методы. Это занимает все те же 300 миллисекунд. Делайте выводы :)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
 
namespace L1CacheMissDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            var lst = new List<Base>();
 
            for (int i = 0; i < 1000000; i++)
                lst.Add(new Derived1());
            for (int i = 0; i < 1000000; i++)
                lst.Add(new Derived2());
            for (int i = 0; i < 1000000; i++)
                lst.Add(new Derived3());
            for (int i = 0; i < 1000000; i++)
                lst.Add(new Derived4());
 
            var s = new Stopwatch();
            s.Start();
            foreach (var x in lst)
                x.Process();
            s.Stop();
 
            Console.WriteLine("Case 1: {0}", s.ElapsedMilliseconds);
 
            // shuffle elements
            var r = new Random(Guid.NewGuid().GetHashCode());
            for (int i = 0; i < lst.Count; i++)
            {
                var j = r.Next(i, lst.Count);
                var t = lst[i];
                lst[i] = lst[j];
                lst[j] = t;
            }
 
            s.Restart();
            foreach (var x in lst)
                x.Process();
            s.Stop();
 
            Console.WriteLine("Case 2: {0}", s.ElapsedMilliseconds);
 
            var p = new Program();
            s.Restart();
            foreach(var _ in lst)
                p.Process();
            s.Stop();
 
            Console.WriteLine("Case 3: {0}", s.ElapsedMilliseconds);
        }
 
        void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
 
    abstract class Base
    {
        public abstract void Process();
    }
 
    class Derived1 : Base
    {
        public override void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
 
    class Derived2 : Base
    {
        public override void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
 
    class Derived3 : Base
    {
        public override void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
 
    class Derived4 : Base
    {
        public override void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
}

noreply@blogger.com (Anonymous) — Sun, 19 Jun 2011 10:18:00 +0000

Чтение чужого кода - весьма полезное занятие, можно узнать много интересного, хотя все конечно зависит от того, кем этот код написан. В этом плане, код создателя Clojure - Ричарда Хикки, просто эльдорадо какое-то :)

Вот один интересный прием использованный в Clojure - допустим у нас есть объект - массив фиксированной длины содержащий до 32-х элементов. Массив заполнен не полностью, некоторые элементы равны null, некоторые содержат полезные данные. Доступ к элементам осуществляется обычным образом, по индексу.

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

Вот как это сделано в clojure - объект содержит массив и маску (32 бита). Массив содержит только полезные данные, то есть, если в массиве 4 элемента, и 28 null-ов, то будет создан массив из 4-х элементов. Маска служит индексом, если i-й элемент массива равен null, то i-й бит маски будет сброшен, а в противном случае - установлен.

Самое интересное в этом - поиск элемента в массиве по индексу. Допусти мы хотим получить значение i-го элемента массива. Для этого, нам нужно выполнить сравнение:

int bit = 1 << i;

if (mask & bit == 0) return null;

в противном случае, элемент не равен null и нам нужно найти его смещение в массиве. Допустим, array - наш массив, он имеет размер - от 0 до 32х. Для получения индекса i-го элемента в массиве, мы должны выполнить следующие операции:

int index = numberOfSetBits(mask & (bit - 1));

return array[index];

где numberOfSetBits - функция, возвращающая количество не нулевых битов числа. Это вычисляется за несколько тактов процессора :)
Представим, что у нас есть массив из 4-х элементов. Допустим, 0-й, 3-й, 6-й и 7-й элементы не равны null. В этом случае, маска будет выглядеть так - 11001001. Младший бит соответствует первому элементу массива, а старший - последнему. Теперь, вычислим индекс последнего элемента массива - i = 7, bit = 1 << 7 = 10000000. Поскольку bit - степень двойки, то bit - 1 будет равно 1111111. Если мы побитово сравним это значение с маской, то мы получим все те же биты, что и в маске, кроме старшего - 11001001 & 1111111 = 1001001. Теперь, если мы посчитаем биты в этом числе, то получим число не null элементов индекс которых меньше нашего i, а именно 3. Именно это число и будет индексом в нашем массиве, не включающем null значения.
Все эти битовые операции выполняются за считанные такты процессора и код в целом работает быстрее. Вообще, мне очень нравятся такие не очевидные решения :)

Рукибыпоотрывал пост

noreply@blogger.com (Anonymous) — Sun, 29 May 2011 09:14:00 +0000

Решил я сегодня попробовать Apache Etch. Это такая штука, которая позволяет описать набор сервисов и сообщений, на специальном IDL, скомпилировать это все специальным компилятором, получив на выходе набор исходников, добавить их в свой проект и наслаждаться жизнью. Этот проект привлек меня тем, что он более функциональный, нежели Thrift, позволяет делать больше. В частности, наследовать сообщения. Ну и Cisco тоже внушает некоторое доверие.

Так вот, у меня не заработал простой hello world, который я взял с официального сайта. Не заработал он вот из-за чего:

Дело в том, что сообщения об ошибках зависят от локализации, а разработчик Etch использует эти сообщения не для отображения, он строит на них логику! За это нужно отрывать руки по самый локоть, ибо даже в MSDN сказано что так делать нельзя.

В общем, до свиданья apache etch :D

В интернете кто-то снова не прав!

noreply@blogger.com (Anonymous) — Mon, 09 May 2011 10:14:00 +0000

Точнее, в оплоте создателей стартапов и специалистов по натягиванию шаблонов на wordpress - хабрахабре :)

Некий юзер, взялся переводить статьи о lock-free алгоритмах на великий и могучий, за что ему спасибо конечно. Но к несчастью для себя, он покусился на святое! По своему перевел термин lock-free на русский язык! Идея, на мой взгляд, крайне неудачная, особенно в свете того, что уже давно прижился перевод - "без блокировок".

Почему lock-free неправильно переводить как "беззамочный"? Все очень просто, в информатике нет "замков", зато есть блокировки. Здесь даже говорить не о чем.

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

Гарантия lock-freredom означает, что в каждый момент времени, один из потоков совершает прогресс. Полезным на практике следствием соблюдения lock-freredom гарантии является то, что мы можем прибить любой из потоков, выполняющих наш lock-free алгоритм и у нас гарантированно не возникнет dead-lock. Если гарантия lock-freedom не соблюдается, то один из потоков может сделать нечто такое, что заставит другие потоки его ждать. Например, захватить мьютекс. Если мы этот поток прибьем, то возникнет dead-lock.

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

Поэтому, я считаю термин "беззахватный" крайне неудачным, не отражающим сути.

P.S.

Я несколько раз написал о том, что поток может быть "прибит". В Windows это может быть сделано функцией TerminateThread, например. Так вот, прибивать потоки, не в коем случае не нужно. Это может привести к непредсказуемым последствиям. Если вы используете эту функцию, то у меня для вас плохие новости!

За все время работы, мне лишь однажды пришлось столкнуться с этой проблемой. Я написал библиотеку, клиент которой часто вызывал TerminateThread. Это иногда приводило к неприятным последствиям. Поэтому, мне пришлось предоставить этому клиенту lock-free интерфейс.

GC и латентность

noreply@blogger.com (Anonymous) — Tue, 26 Apr 2011 18:57:00 +0000

Пояснение. Это скриншот тестовой утилиты, которая измеряет производительность одного нашего продукта (работающего под .NET Framework 4). По оси абсцисс - номер запроса, по оси ординат - время получения ответа на запрос. Запросы не отличаются друг от друга. В среднем, один запрос выполняется меньше чем за 5 миллисекунд. Но один, выполняется в 50 раз медленнее. Это происходит из-за того, что выполнение запроса приостанавливается для того, что-бы сборщик мусора смог сделать свою работу.

noreply@blogger.com (Anonymous) — Sat, 16 Apr 2011 13:28:00 +0000

Прочитал вчера вот эту статью: http://easy-coding.blogspot.com/2011/04/go.html

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

и не впечатлился. Эта программа реализует простую вещь - Master/Worker pattern. Каких-либо особых преимуществ языка Go в этом нелегком деле я не заметил. Для написания этой программы, язык программирования вообще не важен, он должен позволять запускать потоки и использовать блокирующие очереди, вот и все. Все тоже самое может быть написано на C++, с использованием класса tbb::concurrent_queue, или на C#, с использованием класса BlockingCollection. Код будет выглядеть так же просто.
Мало того, на шарпе, можно написать как-то так:

using(var tar = new TarReader(tarname))
{
var files = tar.NewReader(tmpdir);

Parallel.ForEach(files, file => Compiler.Run(file, params));
}

(далее, имена всех классов и методов вымышлены, все совпадения - случайны)
Допустим, tar - объект, читающий tar архив, метод NewReader(tmpdir) - возвращает IEnumerable, при обходе которого на диске, в каталоге tmpdir, будут создаваться новые файлы, а итератор будет возвращать их имена. При вызове tar.Dispose() - все временные файлы должны быть удалены.

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

Вот собственно и все. TPL не будет создавать 100500 потоков, количество выполняемых параллельно задач будет зависеть от количества процессоров. Возиться с очередями и балансировкой нагрузки - не нужно. Обработка ошибок - проще некуда.

Возникает логичный вопрос - зачем этот Go вообще нужен? :)

noreply@blogger.com (Anonymous) — Tue, 04 Jan 2011 15:42:00 +0000

Вдогонку к предыдущему посту. Мы всегда, неосознанно, ищем во всем связи, даже если никакой связи на самом деле нет. Проявляется это по разному, например, многие хоккеисты во время плей-офф не бреются, а тренеры не меняют рубашки :) Программисты в этом деле - впереди планеты всей, ведь у нас есть специальный инструмент для внесения в код подобных заблуждений - наследование! Если между сущностями есть связь - то их можно объединить в иерархию наследования. Пожалуй, самый яркий пример подобного заблуждения встречается в литературе, в качестве примера объектно ориентированного программирования - иерархия фигур в векторном графическом редакторе, знаменитый Shape и его наследники - Line, Rectangle и прочие. (Справедливости ради стоит отметить, что автор этих строк, когда-то давно, написал простой векторный граф. редактор используя именно такой подход :D) Итак, у нас есть базовый абстрактный класс - Shape, у которого есть набор виртуальных методов для: вывода себя на экран/графический контекст; получения bounding box-а объекта; трансформации объекта... Далее, программист должен реализовать классы - наследники Shape, которые специализируют все операции для определенной фигуры. Плюсы этого подхода - кажущаяся простота кода, вроде все в одном месте, а также повторное использование кода, к примеру, класс Circle может быть наследником класса Ellipse. Минусы несколько менее очевидны: сложность внесения изменений - на каждую новую фигуру нам потребуется реализовать новый класс - наследник Shape и реализовать соответствующие вирт. методы, а если мы хотим добавить новую операцию, для которой нужен еще один вирт. метод, то нам придется реализовать его для каждого существующего класса - наследника Shape; не очень хорошая производительность - у нас целых два уровня косвенности - указатель на объект и виртуальный метод этого объекта. И самый главный недостаток этого подхода - нам не нужно знать о том, что та или иная фигура является окружностью или линией, это не имеет значения, так зачем же нам поддерживать иерархию наследования? Иногда самый простой и очевидный способ решения проблемы - самый правильный. Однако, в данном случае, наиболее простой и эффективный метод решения достаточно не очевиден и даже контр-интуитивен. Представим, что у нас есть два массива - массив точек и массив метаданных. Массив точек содержит координаты всех точек чертежа: начало и конец каждой линии; начало, конец и контрольные точки каждого спалйна, точки заливки... Массив метаданных должен содержать информацию о том, к чему относится та или иная точка, а также прочую информацию об объекте: начало линии, конец линии, начало сплайна, конец сплайна, изменить цвет линии, изменить цвет заливки и тд. В этом случае, для того, что-бы отобразить все на экране, нам потребуются два индекса/указателя на текущую позицию в каждом из массивов, далее, в цикле мы будем выбирать поочередно метаданные и соответствующие им точки. К примеру, если в текущей позиции массива метаданных находится команда LINE, то, начиная с текущей позиции массива точек, должны быть выбраны две точки - координаты начала и конца линии и, используя текущий цвет фигуры, нарисована линия; если мы встретили в метаданных команду FLOOD_FILL, то из массива точек следует выбрать одну точку и выполнить заливку текущим цветом фона из этой точки. Минусы этого подхода - ну очень непонятно для поклонников GoF, Грэди Буча и Скотта Мейерса. Плюсы: очень легко изменять код - набор изначальных примитивов очень ограничен и не меняется, операции реализуются для примитивов, не для фигур, один раз; эффективность - нет никаких указателей, смарт-поинтеров, виртуальных методов, многие операции могут быть реализованы очень просто, например, для поворота всего чертежа, достаточно умножить каждую точку массива на соответствующую матрицу поворота. Конечно, это не означает, что наследование это плохо, или, что следует отказаться от ООП, просто следует помнить о том, что то, что у вас в голове выстраивается в иерархию, на самом деле иерархией может и не быть. Фигуры чертежа состоят из примитивов - линий, сплайнов. То, что из этих линий и сплайнов можно создать более сложные фигуры, которые могут быть объединены в иерархию - может быть совсем не важно для решения задачи.

noreply@blogger.com (Anonymous) — Sun, 05 Dec 2010 20:20:00 +0000

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

noreply@blogger.com (Anonymous) — Sun, 18 Jul 2010 06:48:00 +0000

Увидел сегодня следующее:

Everyone should program in C++ for a few years so they learn memory management, project compilation strategies, decoupling, and a host of other professional activities that are needed to program in C++. But when they go back to the more convenient languages they will realize how much they enjoy programming again.

Я в общем-то тоже считаю, что умение программировать на С++ – очень полезный навык. Рано или поздно, C++ программист учится очень рациональному и прагматичному подходу к программированию, или терпит фиаско :)