Overengineering

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

that is the question :)

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

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

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

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

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

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

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

Читать далее...

Code Jam

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

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

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

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

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

исходник

Читать далее...

C++Next

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

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

Читать далее...

Boost.Preprocessor

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

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

Читать далее...

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

Как известно, одно из главных требований к модульным тестам, это повторяемость. Очень сложно искать ошибку, которая воспроизводится через раз. А с кодом, использующим асинхронный ввод вывод, все обычно так и обстоит, как как обработчики различных событий, обычно, выполняются в неопределенном порядке, к тому-же из разных потоков. Но, если вы используете 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
}

Читать далее...