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

Threaded vs Event driven

noreply@blogger.com (Евгений Лазин) — 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 (Евгений Лазин) — 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 (Евгений Лазин) — 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 (Евгений Лазин) — 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 (Евгений Лазин) — 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 (Евгений Лазин) — Sun, 29 May 2011 09:14:00 +0000

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

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

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

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

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

noreply@blogger.com (Евгений Лазин) — 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 (Евгений Лазин) — Tue, 26 Apr 2011 18:57:00 +0000

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

noreply@blogger.com (Евгений Лазин) — 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 (Евгений Лазин) — 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 (Евгений Лазин) — Sun, 05 Dec 2010 20:20:00 +0000

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

noreply@blogger.com (Евгений Лазин) — 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++ программист учится очень рациональному и прагматичному подходу к программированию, или терпит фиаско :)

Veracity – DVCS по новому.

noreply@blogger.com (Евгений Лазин) — Thu, 15 Jul 2010 19:45:00 +0000

Вчера произошло интересное событие, которое почему-то обошли вниманием в блогах. Эрик Синк (надеюсь я правильно пишу его имя), представил на конференции OSCON новую распределенную систему версионного контроля – Veracity. Она пока еще очень alpha и очень preview, но выглядит - очень интересно и многообещающе.

Для начала, небольшая предыстория. Главная фишка любой современной DVCS – хранение истории изменений в виде ненаправленного ацикличного графа (к слову, об этом хорошо написано в блоге автора – здесь и здесь). Это именно то, что делает таким простым процесс слияния, так как мы сливаем не рабочую копию и содержимое репозитория, как в SVN. Вместо этого мы merge-им содержимое двух changeset-ов(попросту говоря – двух разных наборов изменений, сделанных разными людьми). При этом информация о слиянии остается в репозитории и мы можем все повторить, если что-то пошло не так. Помимо этого, подобный способ хранения истории, позволяет сделать версионный контроль распределенным. Мы, пользователи DVCS – не имеем дела с версиями файлов, мы просто обмениваемся изменениями между собой, это очень круто :)

Однако, у медали есть и обратная сторона. Распределенные системы версионного контроля, такие как git, bazar и mercurial, при том, что они замечательно справляются со своей основной задачей – управлением изменениями, все же имеют один серьезный недостаток. Все существующие инструменты разработки - bug/issue/work item трэкеры и тому подобное - ориентированы на работу с линейной историей изменений. В результате, получается несколько странная картина – мы имеем распределенную историю изменений и.. централизованные wiki и bug трэкер. Разработчик может жить в распределенном мире ровно до тех пор, пока ему не потребуется как либо взаимодействовать со своими коллегами.

Теперь к делу. Господин Sink, анонсировал новую, распределенную систему управления версиями Veracity. Среди множества заявленных возможностей есть одна очень интересная – распределенная база данных. Это позволит хранить в истории изменений различную структурированную информацию, например, информацию о багах. Потенциально, это может привести к появлению таких вещей, как децентрализованный bug tracking. Выглядеть он может примерно так: вы работаете с коллегой Васей над одним проектом, при этом, у вас, в bug tracker-е заведено несколько багов. Пока вы занимаетесь реализацией какой-либо фичи, Вася работает над устранением одного из этих мерзких багов, чинит его, отдает тестировщикам, тестировщики закрывают баг, при этом в вашем репозитории, информации об этом нет, баг все еще открыт и воспроизводится, так как там еще нет и Васиных изменений, которые этот баг чинят. Спустя какое-то время, вы забираете изменения, сделанные Васей и сливаете со своими, после чего, обнаруживаете, что баг находится в закрытом состоянии и не воспроизводится, после чего всем становится хорошо :)

Особенно радует тот факт, что Veracity разрабатывается не кучкой народных умельцев, а достаточно серьезной софтверной компанией, которая планирует зарабатывать не на самой DVCS, а на продуктах, построенных на ее основе.

Google code jam. Qualification Round 2010.

noreply@blogger.com (Евгений Лазин) — Sun, 09 May 2010 10:16:00 +0000

Решил вчера поучаствовать в отборочном раунде code jam. Раунд состоял из трех достаточно простых задач, мне хватило терпения только на первые две, хотя как решать третью я тоже понял :)

Первая задача, snaper chain – самая простая, достаточно понять, что состояние snapper-ов в цепочке после K щелчков, будет эквивалентно двоичному представлению числа K. Вот мое решение на F#:

open System
open System.IO

// read the input file
let args = Environment.GetCommandLineArgs()
let inputPath = args.[args.Length - 1]
let outputPath = Path.ChangeExtension(inputPath, ".out")

let inputStr = new StreamReader(inputPath)
let outputStr = new StreamWriter(outputPath)

let testsNum = int <| inputStr.ReadLine()

let inputSeq:seq<int*int> = seq {
    while inputStr.EndOfStream = false do
        let line = inputStr.ReadLine()
        let lst = line.Split(' ')
        yield int lst.[0], int lst.[1]
    }

// write the output file
let snapperState n k =
    let l = 2 <<< n - 1
    let m = k % l
    match l - 1 = m with
    | true  -> "ON"
    | false -> "OFF"

let mutable caseIx = 1
for n, k in inputSeq do
    let line = sprintf "Case #%d: %s" caseIx <| snapperState n k
    outputStr.WriteLine(line)
    caseIx <- caseIx + 1

outputStr.Close()
inputStr.Close()

Вторая задача, fair warning – намного сложнее. Суть задачи – в следующем, у нас есть набор чисел – t1, t2,.. tn. Нужно найти такое значение y, для которого справедливо условие – (Y + ti) mod T = 0, для любого i < n. Причем, T – должно быть максимально возможным. Помимо этого, исходные данные могут содержать большие числа, так и написано:

64 bits will not save you. You have been warned.

Я использовал следующий алгоритм – сначала массив чисел ti сортируется, затем – нормализуется (из каждого элемента вычитается значение минимального элемента); далее, вычисляется наибольший общий делитель элементов массива(функция gcdv), в результате чего мы получаем значение T, после чего достаточно легко рассчитать значение Y. Вот мое решение:

open System
open System.IO
open System.Numerics

// read the input file
let args = Environment.GetCommandLineArgs()
let inputPath = args.[args.Length - 1]
let outputPath = Path.ChangeExtension(inputPath, ".out")

let inputStr = new StreamReader(inputPath)
let outputStr = new StreamWriter(outputPath)

let testsNum = int <| inputStr.ReadLine()
printfn "N: %d" testsNum

let inputSeq = seq {
    while inputStr.EndOfStream = false do
        let line = inputStr.ReadLine()
        let strlst = line.Split(' ').[1..]
        let intlst = Array.map (fun x -> BigInteger.Parse(x)) strlst
        yield intlst
    }

let gcd a b = BigInteger.GreatestCommonDivisor(a, b)

let gcdv vals = Array.reduce gcd vals
            
let getDiff events = 
    if Array.length events < 2 then
        failwith "error in getDiff, events array is to small"
    Array.sortInPlace events
    let min = events.[0]
    min, Array.map (fun x -> x - min) events.[1..]

let (|Length|) arr = Array.length arr

let mutable caseIx = 1

for events in inputSeq do

    let result =
        match events with
        | Length 0
        | Length 1 -> 0I
        | _ -> 
            let min, diff = getDiff events 
            let factor = gcdv diff
            if min % factor = 0I then 0I
            else factor - (min % factor)

    let line = sprintf "Case #%d: %s" caseIx <| result.ToString()
    outputStr.WriteLine(line)
    caseIx <- caseIx + 1

outputStr.Close()
inputStr.Close()

Кстати, сразу после начала раунда я обнаружил что на моем домашнем компьютере нет ни Visual Studio, ни интерпретатора python-a, даже несчастного с++ компиялтора нет. Вышел из положения скачав F# CTP, код набирал в vim. F# interpreter – очень удобная штука, я его использовал в интерактивном режиме, в качестве REPL, а так-же для запуска своей писанины :)

F# и циклические зависимости.

noreply@blogger.com (Евгений Лазин) — Tue, 04 May 2010 19:08:00 +0000

Предметом разговора сегодня будет язык программирования F#, который вызвал у меня неслабую зависимость. Я не буду пока рассказывать чем именно, всему свое время. Вместо этого, я хочу обсудить некоторые “недостатки”.

Главный “недостаток” этого языка программирования, если конечно судить по записям в блогах и сообщениям на форумах – довольно странный для .NET разработчиков механизм компиляции. В C# или VB.NET, порядок компиляции не имеет значения, программист вообще не имеет возможности на него влиять. Мало того, эти языки позволяют с легкостью делать подобное:

class Foo
{  
  private Bar bar;  
  ...
}
class Bar
{  
  private Foo foo;
  ...
}

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

В случае F#, все не так просто. Во первых, файлы проекта компилируются в строго определенном порядке. И от этого порядка зависит – будет ли проект скомпилирован, или нет. Во вторых, этот порядок определяется программистом. В каком порядке следуют файлы в проекте, в том они и будут компилироваться, в этом порядке и будет работать вывод типов. Если класс Bar зависит от класса Foo, то файл, в котором определен класс Foo должен компилироваться раньше чем файл, в котором определен класс Bar. Предыдущий пример, на F# будет выглядеть так:

type Foo =
    val bar : Bar
    ...
and Bar =
    val foo : Foo
    ...

обратите внимание на ключевое слово and – с его помощью в F# определяются взаимно рекурсивные типы. При этом, оба класса должны находится в одном файле.

Естественно, это вызывает бурю гневных постов в блогах и на форумах, так-как очень далеко от подхода, используемого в C# и VB.NET.

Так вот, на самом деле – это очень круто! Круто, потому-что нам пришлось явным образом указать – какие классы являются взаимно рекурсивными. Это означает, что внести в код циклическую зависимость можно только специально.

Явный порядок компиляции – одна из моих любимых особенностей F#, так как она заставляет программиста заранее продумать архитектуру проекта. Допустим у нас есть большой проект, мы условно разделили его на два слоя – представление и бизнес логику. Классы из presentation слоя – используют классы из business layer-a, а тот в свою очередь – никак не зависит от представления. Если все это добро находится в одной сборке, то нам ничто не мешает использовать код из presentation слоя в бизнес логике. Это будет ошибкой проектирования, тем не менее, многие языки программирования позволяют с легкостью это сделать. С F# этот номер не пройдет, так как файлы слоя представления будут компилироваться позже файлов, содержащих бизнес логику.

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

Complexity and order

noreply@blogger.com (Евгений Лазин) — Sat, 20 Mar 2010 10:23:00 +0000

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

Принципы ООП

noreply@blogger.com (Евгений Лазин) — Sun, 28 Feb 2010 20:52:00 +0000

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

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

Инкапсуляция.

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

Наследование.

Всего лишь позволяет моделировать отношения между сущностями, не между самими объектами.

Полиморфизм.

Обычно его понимают как subtype полиморфизм - использование объекта производного класса, вместо объекта базового класса. Для нашей true OOP системы это не актуально, так как любому объекту, можно послать любое сообщение. Это актуально для тех языков программирования, в которых передача сообщения объекту реализована как вызов виртуального метода этого объекта.

В качестве примера true OOP системы программирования, можно привести совсем не ООП(по крайней мере в головах mainstream программистов) язык программирования - Erlang. Его процессы - классические объекты, конечно у процесса нет класса, свойств, методов, процессы не наследуются, и так далее. Но, erlang программа - это множество обменивающихся сообщениями процессов/объектов. Получив сообщение, процесс может изменить свое состояние - сделать что-нибудь. Поэтому, erlang - не менее объектно ориентированный, чем Java или Python :)

P.S.

Этим постом я не пытаюсь сказать, что использовать mainstream языки программирования - плохо и что всем нужно срочно переходить на Erlang. Просто мысли вслух :)

Dynamic Languages Strike Back

noreply@blogger.com (Евгений Лазин) — Thu, 07 Jan 2010 09:40:00 +0000

I went to the University of Washington and [then] I got hired by this company called Geoworks, doing assembly-language programming, and I did it for five years. To us, the Geoworkers, we wrote a whole operating system, the libraries, drivers, apps, you know: a desktop operating system in assembly. 8086 assembly! It wasn't even good assembly! We had four registers! [Plus the] si [register] if you counted, you know, if you counted 386, right? It washorrible.
I mean, actually we kind of liked it. It was Object-Oriented Assembly. It's amazing what you can talk yourself into liking, which is the real irony of all this. And to us, C++ was the ultimate in Roman decadence. I mean, it was equivalent to going and vomiting so you could eat more. They had IF! We had jump CX zero! Right? They had "Objects". Well we did too, but I mean they had syntax for it, right? I mean it was all just such weeniness. And we knew that we could outperform any compiler out there because at the time, we could!
So what happened? Well, they went bankrupt. Why? Now I'm probably disagreeing – I know for a fact that I'm disagreeing with every Geoworker out there. I'm the only one that holds this belief. But it's because we wrote fifteen million lines of 8086 assembly language. We had really good tools, world class tools: trust me, you need 'em. But at some point, man...
The problem is, picture an ant walking across your garage floor, trying to make a straight line of it. It ain't gonna make a straight line. And you know this because you have perspective. You can see the ant walking around, going hee hee hee, look at him locally optimize for that rock, and now he's going off this way, right?
This is what we were, when we were writing this giant assembly-language system. Because what happened was, Microsoft eventually released a platform for mobile devices that was much faster than ours. OK? And I started going in with my debugger, going, what? What is up with this? This rendering is just really slow, it's like sluggish, you know. And I went in and found out that some title bar was getting rendered 140 times every time you refreshed the screen. It wasn't just the title bar. Everything was getting called multiple times.
Because we couldn't see how the system worked anymore!
Small systems are not only easier to optimize, they're possible to optimize. And I mean globally optimize.
So when we talk about performance, it's all crap. The most important thing is that you have a small system. And then the performance will just fall out of it naturally.

Отсюда: Stevey's blog rants - Dynamic Languages Strike Back.

Overengineering

noreply@blogger.com (Евгений Лазин) — Fri, 20 Nov 2009 07:49:00 +0000

Здравствуй дорогой дневник. Дело в том, что в фирме, в которой я работаю, принят общий стандарт для параметров командной строки. Поэтому, у каждого разработчика есть своя маленькая библиотека для превращения argc и argv в осмысленный набор данных. Велосипедостроение - наше все, поэтому я решил не отставать от остальных и сделать свою библиотеку, с преферансом и блудницами :) Но просто взять и написать - не спортивно, поэтому я решил использовать Boost.Spirit. Сказано - сделано, есть видимость того, что все работает, но тут возникают проблемы... Сначала на тестовых серверах, мои приложения отказываются понимать параметры, содержащие символы кириллицы, в процессе исправления этого бага, оказалось, что spirit-у нельзя подсунуть произвольную локаль. Затем, выясняется, что одно мое приложение должно запускаться неким сторонним приложением, в которое намертво зашита командная строка для запуска, причем она самую малость не соответствует нашему внутреннему стандарту и изменить это стороннее приложение нет никакой возможности. Потом, оказалось, что библиотека должна поддерживать не только именованные, но и позиционные параметры, что-то вроде этого: "C:\> program_name.exe positional arguments /Named:parameter", и даже логические параметры: "C:\> program_name.exe /FlagName". В итоге, я посмотрел на плод трудов тяжких и понял, что разобраться в этом через месяц будет очень сложно, после чего взял и переписал все заново :) У меня ушло 20 минут, на то, что-бы написать самый скучный и неинтересный код в моей жизни, если в двух словах, то там есть один большой switch, в каждом case-e которого есть еще один switch :D И вот этот "быдло-код" ушел в production, прекрасно работает, с ним не было никаких проблем. Неисповедимы пути твои, Господи :D

GC or not GC

noreply@blogger.com (Евгений Лазин) — Sat, 31 Oct 2009 22:24:00 +0000

that is the question :)

Мне часто приходилось встречаться с таким мнением, мол в С++ нет сборки мусора, но она и не нужна, так-как есть умные указатели, с помощью которых можно так-же легко управлять памятью используя подсчет ссылок. Так вот, я думаю, что все это ерунда и попробую сейчас объяснить почему, в качестве примера умного указателя считающего ссылки, буду использовать boost::shared_ptr, под сборщиком мусора, я собираюсь понимать сборщик мусора CLR. :)

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

Операции над указателями: в случае GC, мы просто копируем их, в случае not GC, копирование указателя приводит к изменению счетчика ссылок объекта. Копирование, передача в качестве параметра в функцию, удаление умного указателя, приводят к генерации барьера и изменению счетчика ссылок. К тому-же, сам указатель и его счетчик ссылок, могут находится далеко друг от друга в памяти, а это означает плохую локальность.

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

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

Итак, подведу итог. Если использовать в качестве критерия сложность, то получается следующее: сам по себе, алгоритм подсчета ссылок очень прост, алгоритм работы современного сборщика мусора значительно сложнее. Но с точки зрения разработчика все наоборот. Сложности, связанные со сборкой мусора, берет на себя рантайм, а с подсчетом ссылок должен управляться сам программист. Он должен следить за тем, что-бы не возникали циклические ссылки, что-бы у одного объекта всегда был только один счетчик ссылок и так далее. В случае использования GC, нужно просто стараться не создавать для него лишнюю работу. Ну и самое главное – архитектура становится проще.

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

Code Jam

noreply@blogger.com (Евгений Лазин) — Wed, 09 Sep 2009 08:27:00 +0000

Недавно прошел первый квалификационный раунд конкурса Google Code Jam. Я в нем не участвовал, но, ради развлечения, решил одну из задач - alien language. Суть задачи такова: у нас есть две последовательности строк. Первая, состоит из N разных строк одинаковой длины(abc, cda, ...). Вторая - из М строк вида: (abc)cd, где в скобках перечислены все возможные значения, которые являются шаблонами для поиска в первой последовательности. К примеру, шаблону (abc)cd, будут соответствовать три строки - acd, bcd и ccd. Цель - посчитать количество строк из первой последовательности, которые соответствуют каждому из шаблонов из второй последовательности.

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

Не трудно понять, что уже при достаточно небольшой длине строки, мы получим комбинаторный взрыв. Количество вариантов, которые нужно проверить будет огромным. Самое простое решение задачи - преобразовать каждый из шаблонов в регулярное выражение, а затем посчитать количество совпадений. Но, это совсем не интересно :) Вместо этого, я построил свой алгоритм, который не перебирает все возможные строки, подходящие к шаблону. Он ищет(и считает) совпадения в дереве, каждый узел которого может содержать до 26-ти потомков(на рисунке). Каждый из потомков соответствует одному из символов английского алфавита. Первому уровню дерева(узел показан зеленым цветом) соответствуют первые символы всех строк входной последовательности. Второму уровню(показан синим) - вторые символы, и так далее... Соответственно, что-бы проверить, есть-ли строка "abc" среди входных данных, нужно проверить, есть-ли в корневом узле дерева, поддерево, соответствующее символу 'a', затем, рекурсивно, найти в этом поддереве потомка, соответствующего символу 'b' и тд. Затем, если мы прошли ветвь дерева, соответствующую строке "abc", мы легко можем перейти к ветви, соответствующей подстроке "abd" либо "abb". В общем, алгоритм обхода дерева достаточно очевиден.

Работает это правильно и достаточно шустро. Я не измерял время работы, но по ощущениям, большой набор данных, был обработан не больше чем за две секунды :)

исходник

C++Next

noreply@blogger.com (Евгений Лазин) — Sun, 16 Aug 2009 16:14:00 +0000

Пару недель назад Дэвид Абрамс и Дуг Грегор начали вести блог - C++Next. На данный момент там только две статьи, надеюсь, что это не надолго :)

В общем, очень рекомендую, будет интересно!

Boost.Preprocessor

noreply@blogger.com (Евгений Лазин) — Sat, 02 May 2009 12:46:00 +0000

Препроцессор - штука достаточно неодназначная, что-бы это понять, достаточно поднять дискуссию на эту тему на каком-нибудь формуе, и опасная, так-как он вообще не в курсе синтаксиса языка программирования С++, ничего не знает о пространствах имен, шаблонах и тд. Лучше всего ограничить его применение условной компиляцией а так-же не забывать использовать #undef. Но, если не следовать этой рекомендации, то с его помощью можно делать очень интересные вещи :) Это можно продемонстрировать на примере списков типов, которые описаны в книге Александресску - "Современное проектирование на С++". Вот реализация такого списка

struct empty_t {};

template<class Head, class Tail>
struct cons
{
    typedef Head head;
    typedef Tail tail;
};

а использовать его можно так:

typedef cons< int, cons<long, cons< double, empty_t > > > tl_first;

Но это совсем не удобно, что-бы это исправить, нужен более простой способ объявления списков типов. Самый простой способ это сделать - макросы a-la Александресску:

#define TYPE_LIST_1(t) cons< t, empty_t >
#define TYPE_LIST_2(t1, t2) cons< t1, TYPE_LIST_1(t2) >
#define TYPE_LIST_3(t1, t2, t3) cons< t1, TYPE_LIST_2(t2, t3) >
typedef TYPE_LIST_3(int, long, double) tl_second;

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

template<class T1, class T2 = empty_t, class T3 = empty_t, class T4 = empty_t>
struct make_typelist;


template<class T1>
struct make_typelist<T1, empty_t, empty_t, empty_t>
{
    typedef cons<T1, empty_t> type;
};

template<class T1, class T2>
struct make_typelist<T1, T2, empty_t, empty_t>
{
    typedef cons<T1, cons<T2, empty_t> > type;
};

template<class T1, class T2, class T3>
struct make_typelist<T1, T2, T3, empty_t>
{
    typedef cons<T1, cons<T2, cons<T3, empty_t> > > type;
};

теперь достаточно написать:

typedef make_typelist<int, long, double>::type tl_third;

и у нас есть список типов. В этом коде мы сталкиваемся с одним из недостатков языка С++ - отсутствием шаблонов с переменным числом параметров, поэтому приходится описывать все необходимые специализации. Страшно представить, что будет, если нам потребуется создать список хотя-бы из десяти элементов. И вот здесь нам может помочь библиотека boost.preprocessor. С ее помощью можно написать вот такой ~~нечитаемый~~ код:

#include <boost/preprocessor/repetition.hpp>
//boost preprocessor
#define MAX_TYPELIST_SIZE 4

template< BOOST_PP_ENUM_PARAMS_WITH_A_DEFAULT(MAX_TYPELIST_SIZE, class T, empty_t)>
struct make_typelist;

#define TUPLE_PRINT(n, i, data) data
#define GEN_MAKETYPELIST(n, i, unused)                                  \
template< BOOST_PP_ENUM_PARAMS(i, class T) >                            \
struct make_typelist<                                                   \
      BOOST_PP_ENUM_PARAMS(i,T)                                         \
      BOOST_PP_COMMA_IF(i)                                              \
      BOOST_PP_ENUM(                                                    \
          BOOST_PP_SUB(MAX_TYPELIST_SIZE,i), TUPLE_PRINT, empty_t) >    \
{                                                                       \
    typedef BOOST_PP_ENUM_PARAMS(i, cons<T), empty_t                    \
            BOOST_PP_REPEAT(i, TUPLE_PRINT, > ) type;                   \
};

BOOST_PP_REPEAT_FROM_TO(1, MAX_TYPELIST_SIZE, GEN_MAKETYPELIST, ~)

typedef make_typelist<int, long, double>::type tl_third;

#undef TUPLE_PRINT
#undef GEN_MAKETYPELIST

В этом примере, препроцессор создаст точно такой-же код как и в предидущем примере. Но теперь, в случае если нам потребуется увеличить максимальный размер списка типов для make_typelist, достаточно изменить MAX_TYPELIST_SIZE. Многие библиотеки boost используют подобную технику для эмуляции шаблонов с переменным количеством параметров, например boost.tuple. В данном конкретном случае, макрос GEN_MAKETYPELIST создает одну из специализаций шаблонного класса make_typelist, в качестве параметров он получает максимальный размер списка типов(n), и количество параметров шаблона(i). Этот макрос используется в BOOST_PP_REPEAT_FROM_TO, для генерации всех необходимых специализаций шаблона. Сама библиотека boost.preprocessor - достаточно простая. Начать ее использовать очень легко, главное знать, для чего она может быть полезна.

PEP-374

noreply@blogger.com (Евгений Лазин) — Tue, 31 Mar 2009 09:05:00 +0000

Сегодня GvR объявил о том, что python переходит на mercurial. По ссылке неплохой обзор трех DVCS и SVN.

Unit тестирование и boost::asio

noreply@blogger.com (Евгений Лазин) — Tue, 24 Mar 2009 13:03:00 +0000

Как известно, одно из главных требований к модульным тестам, это повторяемость. Очень сложно искать ошибку, которая воспроизводится через раз. А с кодом, использующим асинхронный ввод вывод, все обычно так и обстоит, как как обработчики различных событий, обычно, выполняются в неопределенном порядке, к тому-же из разных потоков. Но, если вы используете boost::asio, то все не так плохо. Эта библиотека спроектирована так, что-бы её можно было легко испоьзовать в модульных тестах. Представим, что у нас есть два класса, клиент и сервер, оба используют boost::asio для асинхронного IO. Для того, что-бы написать для них тест, нам нужно создать два io_service-a, так-как в они будут работать независимо. Далее, мы можем вызывать различные функции, которые начинают асинхронные операции, например запись данных в сокет, или ожидание подключения клиента. Но, вместо того, что-бы вызывать метод io_service::run, мы можем вызвать метод io_service::run_one, который выполняет обработчик только одного события. Благодаря этому, асинхронный код можно превратить в линейный и протестировать таким образом логику наших классов.

TEST(MyTest, test_async_connect)
{
    boost::io_service client_io, server_io;

    my_client client(client_io);
    my_server server(server_io);
    
    EXPECT_FALSE(client.connected());//connected возвращает false, если клиент не подключен к серверу
    EXPECT_EQ(server.clients_count(), 0);//к серверу не подключен ни один клиент
    server.start_accept();//начинаем принимать подключения
    client.async_connect("localhost", my_port);//метод async_connect, 
    //начинает асинхронную операцию подключения к серверу,
    //в коде my_client, это может быть реализовано примерно так:
    //  boost::asio::async_connect(thsi->socket_, &my_client::on_connect);
    //естественно, метод on_connect, должен изменить состояние клиента
    server_io.run_one();//во время этого вызова, сервер дожен принять подключение,
    //обработать сообветствующее событие и изменить свое состояние
    EXPECT_EQ(server.clients_count(), 1);//теперь клиент подключен к серверу
    EXPECT_FALSE(client.connected());//но сам еще не знает об этом
    client_io.run_one();//что-бы он об этом узнал, нужно что-бы выполнился обработчик собыитя on_connect
    EXPECT_TRUE(client.connected());//done
}