*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

четверг, 28 апреля 2011 г.

p4-git - работа в Perforce через git

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

  • CVS - все понятно, система не для автоматизации разработки, где все меняется каждую минуту, а для "публикации истории изменений"
  • SVN - все более менее ничего, когда в разработке есть выделенный trunk, иначе после нескольких массивных слияний веток в разных направлениях хочется застрелиться
  • RTC (Rational Team Concert) - монструозная система, удобная когда все и везде написано только на Java, и неудобный клиент в командной строке
  • ClearCase - кроме шуток, пользователям надо выдавать травы и водки, чтобы понять, как это система работает

На фоне всего этого Perforce - это реальный рай. Регулярно делаю слияния между ветками команд разработчиков, интеграцией и релизами - удобно. Также смотря с позиции ежедневных нужд разработчика - также все удобно. Только одна вещь нас немного мучала - это невозможность перебрасывать changeset'ы между физическими машинами перед commit'ом. У нас в разработке шесть основных платформ, включая Windows, поэтому каждый commit приходится проверять на всех платформах. Моя утилита p4patch решала проблему более менее, но в последних версиях появилась волшебная команда p4 shelve, которая решает эту проблему на корню.

Но что ни говори, для локальной работы, когда утопаешь в экспериментах, тестовых данных, временных копиях и т.д. - наличие распределенной системы типа git, hg, bazaar или fossil, когда можно плодить ветки по каждому чиху, сливать, удалять и т.д., реально упрощает жизнь.

Как рекоммендуют сами Perforce'овцы, можно в некотором роде срастить оба подхода, например, через git.

p4-git - скрипт, которым локальные файлы, находящиеся под контролем Perforce, дополнительно можно взять под git.

Я все настроил, как сказано. Теперь у меня в git есть ветка master, являющаяся зеркалом из репозитория Perforce, и пяток-десяток локальных веток, из которых я сливаю в master. Изменения, которые я внес через git, автоматически заливаются в Perforce командой "git p4 submit". Комадной же "git p4 rebase" можно синхронизировать ветку master с ее оригиналом в Perforce.

Кстати, я уже потерял счет тем разам, когда в hg или fossil'e я влеплял ошибку в команде комита - либо просто опечатка в сообщении, что еще можно пережить, или при повторении команд из буфера командой строки вместо diff залепишь старый комит и все. Потом приходится либо как-то хитро merge'ить, либо просто откатывать изменения, делая новый комит. А в git можно просто сказать "git commit --amend" для исправления опечатки в только что сделанном комите, или "git reset HEAD^1" для удаления последнего комита вообще. А меняя 1 на 2, 3 и т.д., можно удалить сколько угодно комитов назад.

А самое важное, что даже неверная команда "git reset HEAD^n", которая якобы удаляет n последних комитов - это не конец света. И ее можно откатить через "git reset <commit_id>", где <commit_id> - это идентификатор удаленного комита. При всех тех возможностях по работе с репозиторием, которые дает git, и которые принято считать "опасными", очень мало команд, которые реально имеют необратимые последствия. Пока вы не сделали сборку мусора командой "git repack" объекты физически не удаляются, а только меняются указатели на них, а значит практически всегда можно вернуть назад, когда напортачил.

вторник, 26 апреля 2011 г.

Работа в компании Hex-Rays

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

Характерный пример - компания Hex-Rays.

Их главный продукт - интерактивный дизассемблер IDA Pro. Хотя сейчас это уже не просто дизассемблер, а еще и отладчик и декомпилятор.

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

IDA уникален по функциональности, удобству и количеству поддерживаемых архитектур. А его декомпилятор, превращающий ассемблерный код в псевдокод на С, вообще не имеет себе аналогов. Рекомендую посмотреть видео с демонстрацией работы декомпилятора. Это впечатляет.

Неделю назад в блоге компании появилось объявление о поиске разработчиков, желающих присоединиться к их небольшой, но очень продуктивной команде. Компания базируется в Бельгии, но скорее всего варианты сотрудничества могут быть весьма гибкими, от переезда в Бельгию до удаленной работы. В компании, кстати, также говорят по-русски.

Итак, любите reverse engineering и ассемблер, и при этом умеете грамотно писать на С++ - не пропустите.

P.S. Предвосхищу вопросы на тему какой-либо моей личной финансовой заинтересованности в публикации данной информации, что пост никак официально не связан с компанией Hex-Rays и является лишь моим личным мнением, высказанным только из-за многолетней привязанности к продукту IDA.

пятница, 22 апреля 2011 г.

Почему на интервью принято дрючить

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

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

Ладно, тут можно много спорить. Желающие прочтут в книге сами.

Сейчас не об этом. Я тут подумал, что жесткие процедуры интервьюирования отчасти работают по такому же принципу. Пройдя подобный отбор, кто в душе не будет говорить себе: "Да! Я прошел! Теперь я член этой классной команды!"?

Возразите мне...

вторник, 19 апреля 2011 г.

re2c - компилятор регулярных выражений

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

Например, flex - это один из таких анализаторов. Старый, но проверенный годами.

Я много пользовался flex'ом, он имеет и плохие и хорошие стороны, но по большому счету, жаловаться не приходилось.

Но вчера наткнулся на интересный проект - re2c. По сути, на этой штуке можно писать лексические анализаторы прямо на коленке за несколько минут.

Сразу рассмотрим пример.

Допустим, вам нужно из строки выделять некоторые команды, целые и дробные числа. Можно расчехлить flex, а можно написать так:

#include <stdio.h>
#include <stdlib.h>

enum {
  CMD, INT, FLOAT, SPACE, END
};

int scan(char** p, char** lex)
{
    char* marker;
    if (lex) *lex = *p;
/*!re2c
        re2c:define:YYCTYPE  = "unsigned char";
        re2c:define:YYCURSOR = *p;
        re2c:define:YYMARKER = marker;
        re2c:yyfill:enable   = 0;
        re2c:yych:conversion = 1;
        re2c:indent:top      = 1;
        "GET"|"PUT"|"EXIT" { return CMD; }
        [0-9]+             { return INT; }
        [0-9]+ '.' [0-9]*  { return FLOAT; }
        [ \t]+             { return SPACE; }
        [^]                { return END; }
*/
}

int main(int argc, char* argv[]) {
  char *p, *last;
  int token;
  if (argc < 2) return 1;

  p = argv[1];
  while ((token = scan(&p, &last)) != END) {
    int sz = p - last;
    switch (token) {
      case CMD: printf("Command: '%.*s'\n", sz, last); break;
      case INT: printf("Number: '%.*s'\n", sz, last); break;
      case FLOAT: printf("Float: '%.*s'\n", sz, last); break;
    }
  }

  return 0;
}

И все!

Понятно, что вся магия происходит в функции "scan()" между строками, ограниченных комментариями "/*!re2c" и "*/".

Итак, re2c - это компилятор регулярных выражений, который встраивает код прямо в текст программы.

Если прогнать наш исходник через re2c:

re2c.exe -is test.re2c >test.c

То получим вот такое:

/* Generated by re2c 0.13.5 on Tue Apr 19 21:08:57 2011 */
#include <stdio.h>
#include <stdlib.h>

enum {
  CMD, INT, FLOAT, SPACE, END
};

int scan(char** p, char** lex)
{
    char* marker;
    if (lex) *lex = *p;

    {
        unsigned char yych;

        yych = (unsigned char)**p;
        if (yych <= '9') {
            if (yych <= 0x1F) {
                if (yych == '\t') goto yy8;
                goto yy10;
            } else {
                if (yych <= ' ') goto yy8;
                if (yych <= '/') goto yy10;
                goto yy6;
            }
        } else {
            if (yych <= 'F') {
                if (yych == 'E') goto yy5;
                goto yy10;
            } else {
                if (yych <= 'G') goto yy2;
                if (yych == 'P') goto yy4;
                goto yy10;
            }
        }
yy2:
        yych = (unsigned char)*(marker = ++*p);
        if (yych == 'E') goto yy24;
yy3:
        { return END; }
yy4:
        yych = (unsigned char)*(marker = ++*p);
        if (yych == 'U') goto yy23;
        goto yy3;
yy5:
        yych = (unsigned char)*(marker = ++*p);
        if (yych == 'X') goto yy18;
        goto yy3;
yy6:
        ++*p;
        if ((yych = (unsigned char)**p) == '.') goto yy13;
        if (yych <= '/') goto yy7;
        if (yych <= '9') goto yy16;
yy7:
        { return INT; }
yy8:
        ++*p;
        yych = (unsigned char)**p;
        goto yy12;
yy9:
        { return SPACE; }
yy10:
        yych = (unsigned char)*++*p;
        goto yy3;
yy11:
        ++*p;
        yych = (unsigned char)**p;
yy12:
        if (yych == '\t') goto yy11;
        if (yych == ' ') goto yy11;
        goto yy9;
yy13:
        ++*p;
        yych = (unsigned char)**p;
        if (yych <= '/') goto yy15;
        if (yych <= '9') goto yy13;
yy15:
        { return FLOAT; }
yy16:
        ++*p;
        yych = (unsigned char)**p;
        if (yych == '.') goto yy13;
        if (yych <= '/') goto yy7;
        if (yych <= '9') goto yy16;
        goto yy7;
yy18:
        yych = (unsigned char)*++*p;
        if (yych == 'I') goto yy20;
yy19:
        *p = marker;
        goto yy3;
yy20:
        yych = (unsigned char)*++*p;
        if (yych != 'T') goto yy19;
yy21:
        ++*p;
        { return CMD; }
yy23:
        yych = (unsigned char)*++*p;
        if (yych == 'T') goto yy21;
        goto yy19;
yy24:
        ++*p;
        if ((yych = (unsigned char)**p) == 'T') goto yy21;
        goto yy19;
    }

}

int main(int argc, char* argv[]) {
  char *p, *last;
  int token;
  if (argc < 2) return 1;

  p = argv[1];
  while ((token = scan(&p, &last)) != END) {
    int sz = p - last;
    switch (token) {
      case CMD: printf("Command: '%.*s'\n", sz, last); break;
      case INT: printf("Number: '%.*s'\n", sz, last); break;
      case FLOAT: printf("Float: '%.*s'\n", sz, last); break;
    }
  }

  return 0;
}

Страшно? Да, код не для ручной правки, но это и не требуется.

Компилируем:

re2c.exe -is test.re2c >test.c && cl test.c

Запускаем:

test "GET 123.0 12344 PUT 10."

Результат:

Command: 'GET'
Float: '123.0'
Number: '12344'
Command: 'PUT'
Float: '10.'

Как говориться, быстро, дешево и сердито. Чтобы полностью овладеть re2c надо прочитать одну и единственную страничку документации.

Кстати, простота работы с re2c не означает, что на нем нельзя делать сложных анализаторов. В дистрибутиве есть примеры для грамматики токенов языков C и Rexx.

Если поиграться с флагами re2c, то можно вместо "if/else" генерировать код на основе "switch/case". Выбор стоит сделать на основе понимания, какой код ваш компилятор лучше оптимизирует.

Как я понимаю, анализатор, сгенерированный re2c должен быть весьма быстр, даже очень быстр. Хотя было бы интересно померить его против того же flex'а, ANTLR'а или Spirit'a.

Посты почти по теме:

понедельник, 18 апреля 2011 г.

Google Test 1.6.0

Только что вышла новая версия отличной библиотеки для unit-тестирования на С++ - Google C++ Testing Framework.

Вот список изменений:

  • New feature: ADD_FAILURE_AT() for reporting a test failure at the
    given source location -- useful for writing testing utilities.
  • New feature: the universal value printer is moved from Google Mock
    to Google Test.
  • New feature: type parameters and value parameters are reported in
    the XML report now.
  • A gtest_disable_pthreads CMake option.
  • Colored output works in GNU Screen sessions now.
  • Parameters of value-parameterized tests are now printed in the
    textual output.
  • Failures from ad hoc test assertions run before RUN_ALL_TESTS() are
    now correctly reported.
  • Arguments of ASSERT_XY and EXPECT_XY no longer need to support << to
    ostream.
  • More complete handling of exceptions.
  • GTEST_ASSERT_XY can be used instead of ASSERT_XY in case the latter
    name is already used by another library.
  • --gtest_catch_exceptions is now true by default, allowing a test
    program to continue after an exception is thrown.
  • Value-parameterized test fixtures can now derive from Test and
    WithParamInterface<T> separately, easing conversion of legacy tests.
  • Death test messages are clearly marked to make them more
    distinguishable from other messages.
  • Compatibility fixes for Android, Google Native Client, MinGW, HP UX,
    PowerPC, Lucid autotools, libCStd, Sun C++, Borland C++ Builder (Code Gear),
    IBM XL C++ (Visual Age C++), and C++0x.
  • Bug fixes and implementation clean-ups.
  • Potentially incompatible changes: disables the harmful 'make install'
    command in autotools.

Полная история версий.

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

Лично я очень ждал исправления мелких, но неприятных несовместимостей с компиляторами HP-UX, Sun и AIX.

Посты по теме и почти по теме:

UPDATE:

По ходу вышел еще и Google Mock 1.6.0.

Что нового тут:

  • Compilation is much faster and uses much less memory, especially
    when the constructor and destructor of a mock class are moved out of
    the class body.
  • New matchers: Pointwise(), Each().
  • New actions: ReturnPointee() and ReturnRefOfCopy().
  • CMake support.
  • Project files for Visual Studio 2010.
  • AllOf() and AnyOf() can handle up-to 10 arguments now.
  • Google Mock doctor understands Clang error messages now.
  • SetArgPointee<> now accepts string literals.
  • gmock_gen.py handles storage specifier macros and template return
    types now.
  • Compatibility fixes.
  • Bug fixes and implementation clean-ups.
  • Potentially incompatible changes: disables the harmful 'make install'
    command in autotools.

Полная история.

Потоки в C++ против потоков в Go

После поста про потоки в Go я прочитал другое мнение про общую целесообразность Go в плане продвинутости в многопоточном программировании.

Признаюсь, я не боец в бусте и новом C++, но благодаря предоставленному примеру, было очевидно, что и на С++ решение получается весьма изящное.

Интересно было сравнить производительнось потоков во обоих языках в плане скорости из создания и назначения им работы. Как я понял, это битва между pthreads и системой Go-рутин, которые не являются потоками операционной системы. Как сказано в документации:

Goroutines are multiplexed onto multiple OS threads so if one should block, such as while waiting for I/O, others continue to run. Their design hides many of the complexities of thread creation and management.

Я взял последний boost, и на той же восьми процессорной машине провел эксперимент.

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

Итак, программа на Go:

package main

import (
        "flag"
        "fmt"
)

var jobs *int = flag.Int("jobs", 8, "number of concurrent jobs")
var n *int = flag.Int("tasks", 1000000, "number of tasks")

func main() {
        flag.Parse()

        fmt.Printf("- running %d concurrent job(s)\n", *jobs)
        fmt.Printf("- running %d tasks\n", *n)
        tasks := make(chan int, *jobs)
        done := make(chan bool)

        for i := 0; i < *jobs; i++ {
                go runner(tasks, done)
        }

        for i := 1; i <= *n; i++ {
                tasks <- i
        }

        for i := 0; i < *jobs; i++ {
                tasks <- 0
                <- done
        }
}

func runner(tasks chan int, done chan bool) {
        for {
                if arg := <- tasks; arg == 0 {
                        break
                }
                worker()
        }
        done <- true
}

func worker() int {
        return 0
}

Makefile для прогона по серии параметров:

target = go_threading

all: build

build:
        6g $(target).go
        6l -o $(target) $(target).6

run:
        (time -p ./$(target) -tasks=$(args) \
                1>/dev/null) 2>&1 | head -1 | awk '{ print $$2 }'

n = \
10000 \
100000 \
1000000 \
10000000 \
100000000

test:
        @for i in $(n); do \
                echo "`printf '% 10d' $$i`" `$(MAKE) args=$$i run`; \
        done

Программа на C++:

#include <iostream>
#include <boost/thread.hpp>
#include <boost/bind.hpp>
#include <queue>
#include <string>
#include <sstream>

class thread_pool {

  typedef boost::function0<void> worker;

  boost::thread_group threads_;
  std::queue<worker> queue_;
  boost::mutex mutex_;
  boost::condition_variable cv_;
  bool done_;

 public:

  thread_pool() : done_(false) {
    for(int i = 0; i < boost::thread::hardware_concurrency(); ++i)
      threads_.create_thread(boost::bind(&thread_pool::run, this));
  }

  void join() {
    threads_.join_all();
  }

  void run() {
    while (true) {
      worker job;
      {
        boost::mutex::scoped_lock lock(mutex_);
        while (queue_.empty() && !done_)
          cv_.wait(lock);

        if (queue_.empty() && done_) return;

        job = queue_.front();
        queue_.pop();
      }
      execute(job);
    }
  }

  void execute(const worker& job) {
    job();
  }

  void add(const worker& job) {
    boost::mutex::scoped_lock lock(mutex_);
    queue_.push(job);
    cv_.notify_one();
  }

  void finish() {
    boost::mutex::scoped_lock lock(mutex_);
    done_ = true;
    cv_.notify_all();
  }
};

void task() {
  volatile int r = 0;
}

int main(int argc, char* argv[]) {
  thread_pool pool;
  int n = argc > 1 ? std::atoi(argv[1]) : 10000;

  int threads = boost::thread::hardware_concurrency();
  std::cout << "- executing " << threads << " concurrent job(s)" << std::endl;
  std::cout << "- running " << n << " tasks" << std::endl;
  for (int i = 0; i < n; ++i) {
    pool.add(task);
  }

  pool.finish();
  pool.join();

  return 0;
}

Makefile:

BOOST = ~/opt/boost-1.46.1

target = boost_threading

build:
        g++ -O2 -I $(BOOST) -o $(target) \
                -lpthread \
                -lboost_thread \
                 -L $(BOOST)/stage/lib \
                $(target).cpp

run:
        (time -p LD_LIBRARY_PATH=$(BOOST)/stage/lib ./$(target) $(args) \
                1>/dev/null) 2>&1 | head -1 | awk '{ print $$2 }'

n = \
10000 \
100000 \
1000000 \
10000000 \
100000000

test:
        @for i in $(n); do \
                echo "`printf '% 10d' $$i`" `$(MAKE) args=$$i run`; \
        done

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

Запускаем программу на C++:

make && make -s test

g++ -O2 -I ~/opt/boost-1.46.1 -o boost_threading \
                -lpthread \
                -lboost_thread \
                 -L ~/opt/boost-1.46.1/stage/lib \
                boost_threading.cpp
(time -p LD_LIBRARY_PATH=~/opt/boost-1.46.1/stage/lib ./boost_threading  \
                1>/dev/null) 2>&1 | head -1 | awk '{ print $2 }'
     10000 0.03
    100000 0.35
   1000000 3.43
  10000000 29.57
 100000000 327.37

Теперь Go:

make && make -s test

6g go_threading.go
6l -o go_threading go_threading.6
     10000 0.00
    100000 0.03
   1000000 0.35
  10000000 3.72
 100000000 38.27

Разница очевидна.

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

Посты по теме:

среда, 13 апреля 2011 г.

Конференция ACCU 2011

Хоть на Google I/O в этом году не получилось попасть, так как все было распродано менее чем за час, есть другие интересные конференции.

Например, ACCU 2011. Место проведения от моего офиса всего в часе езды, не пришлось платить за гостиницу.

Тематики сессий весьма разнообразные.

Сегодня я посетил:

  • Introduction to Scala. До этого я про язык Scala только название, поэтому это были весьма полезные полтора часа. Если вы любите Java, но вам не хватает функциональных примочек типа списковых выражений, currying, pattern matching, call by name и более краткого синтаксиса в целом, но при этом вы хотите иметь обьектно- и функционально- ориентированный язык, компилирующий для JVM, то Scala - это самое оно. Хотя лично у меня впечатление неоднозначное из-за дикой перегруженности языка наворотами, из-за которой для "правильного программирования" надо также овладеть "правильными шаблонами". А тут уже какой-то С++ получается. Сама презентация была весьма живая и информативная. Для интересующихся - блог автора.
  • Worst practices for creating domain-specific modelling languages. Не самая захватывающая, но таки полезная презентация о том, почему и как создаются проблемно ориентированные языки.
  • GoLightly: Building VM-based Language Runtimes In Go. Меня презентация реально вставила. Тетка отожгла неимоверно. За полтора часа она умудрилась дать очень понятную вводную по ключевым возможностям Go, успев даже коснуться недокументированных модулей типа "unsafe" и показать как можно обойти стройную систему безопасной типизации в Go, и затем описала свой проект по моделированию разных процессорных архитектур на этом языке. Ниже есть слайды ее презентации, но к сожалению в них нет той части про надругательноство на системой типов в Go. Может она выложит обновленную версию сегодня-завтра.

Завтра хочу сходить на "Distributed Computing 2.0", "ComputErl - Erlang-based Framework for Many Task Computing", "CPU Caches and Why You Care" Скотта Меерса.

Кстати, чтобы уж два раза не вставать, в последнем выпуске ACCU'шного журнала CVu была моя статейка "The First Little Step into Test-Driven Development" (так как электронная версия журнала находится в платной части сайта, то я выложил только страницы с моей статьей).

вторник, 12 апреля 2011 г.

Пример параллельного программирования в Go

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

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

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

Несложная задача. Только есть одно "но". Количество исходников, которые планируется использовать как эталонные - около 15 тысяч файлов, суммарным объемом чуть меньше гига (для удобства они завернуты в один TAR). Подобный "прогон" может быть весьма долгим. И есть естественное желание сделать тест максимально быстрым, используя многопроцессорную машину, ибо задача прекрасно распараллеливается.

Как вариант - можно сделать Makefile и запускать его с ключом "-j" в GNU Make. Но если написать специализированную многопоточную программу, то можно достичь лучшей производительности.

Итак, очевидно: вместо последовательного выполнения нужно запускать компиляцию каждого файла в параллельных потоках. Но так как файлов много (~15 тысяч), неэффективно просто одновременно запустить столько много потоков. Разумнее всего будет иметь пул потоков, где их количество будет определяться, например, количеством процессоров (например, умноженное на 2). Пул будет назначать очередную задачу на свободный поток, и если все потоки заняты, он будет блокироваться до тех пор, пока не появиться свободный.

Таким образом, мы будем поддерживать занятыми N потоков, обеспечивая оптимальную загрузку процессоров, не тратя время на лишние переключения контекста и постоянное создание и уничтожение потоков.

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

Итак: данная программа берет TAR с исходниками, распаковывает его, и каждый файл прогоняет через компилятор.

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

Главная концепция, которая используется в этой программе - это каналы. По каналам можно синхронно передавать данные и функции между потоками (Go-рутинами).

Далее, можно просто смотреть по исходнику. Самое интересное место там, где видно, как функция "compile()" может вызываться из нескольких потоков без каких-либо изменений.

package main

import (
        "archive/tar"
        "container/vector"
        "exec"
        "flag"
        "fmt"
        "io"
        "os"
        "strings"
)

// Два флага: количество потоков и имя компилятора.
var jobs *int = flag.Int("jobs", 0, "number of concurrent jobs")
var compiler *string = flag.String("cc", "bcom", "compiler name")

func main() {
        flag.Parse()
        os.Args = flag.Args()
        args := os.Args

        ar := args[0]
        r, err := os.Open(ar, os.O_RDONLY, 0666);
        if err != nil {
                fmt.Printf("unable to open TAR %s\n", ar)
                os.Exit(1)
        }
        // defer - это аналог "finally {}", гарантированное выполнение
        // кода при выходе из блока.
        defer r.Close()

        // Цикл распаковки TAR.
        fmt.Printf("- extracting %s\n", ar)
        // Создаем контекст для распаковки.
        tr := tar.NewReader(r)
        tests := new(vector.StringVector)
        // Последовательный проход по архиву, сохранение файлов и составление
        // списка для компиляции.
        for {
                // Получаем дескриптор следующего файла в архиве.
                hdr, _ := tr.Next()
                if hdr == nil {
                        break
                }
                name := &hdr.Name
                // Если это не заголовочный файл, сохраним имя.
                if !strings.HasPrefix(*name, "HDR_") {
                        tests.Push(*name)
                }
                // Создаем новый файл.
                w, err := os.Open("data/" + *name, os.O_CREAT | os.O_RDWR, 0666)
                if err != nil {
                        fmt.Printf("unable to create %s\n", *name)
                        os.Exit(1)
                }
                // Копируем содержимое в текущий файл.
                io.Copy(w, tr)
                w.Close()
        }

        fmt.Printf("- compiling...\n")
        *compiler , _ = exec.LookPath(*compiler)
        fmt.Printf("- compiler %s\n", *compiler)

        if *jobs == 0 {
                // Вызываем "compile()" последовательно, в основном потоке.
                fmt.Printf("- running sequentially\n")
                for i := 0; i < tests.Len(); i++ {
                        compile(tests.At(i))
                }
        } else {
                // Запускаем "compile()" в параллельных потоках.
                fmt.Printf("- running %d concurrent job(s)\n", *jobs)

                // Канал задач: в этот канал мы будем класть имена файлов,
                // которые надо скомпилировать. Потоки-runner'ы будут ждать
                // сообщений из этого канала. Канал имеет ограничение по
                // длине. Это аналог семафора, чтобы блокировать главный
                // поток, если все runner'ы заняты.
                tasks := make(chan string, *jobs)

                // Канал подтверждения полного завершение потока-runner'а.
                // Главный поток будет ждать, пока все runner'ы ответят
                // по этому каналу. Тип сообщений тут не важен.
                done := make(chan bool)

                // Запускаем runner'ы.
                for i := 0; i < *jobs; i++ {
                        go runner(tasks, done)
                }

                // Передаем в канал имена файлов для обработки. При
                // достижении максимального размера канала, главный поток
                // будет заблокирован.
                for i := 0; i < tests.Len(); i++ {
                        tasks <- tests.At(i)
                }

                // Посылаем всем потокам команду завершиться и ждем
                // подтверждения о нормальном выходе от каждого потока.
                for i := 0; i < *jobs; i++ {
                        tasks <- ""
                        <- done
                }
        }
}

// Поток-runner.
func runner(tasks chan string, done chan bool) {
        // Бесконечный цикл.
        for {
                // Ждем сообщения из канала. Обычно, поток заблокирован
                // на этом месте.
                name := <- tasks
                // Если имя пустое, нас просят завершиться.
                if len(name) == 0 {
                        break
                }
                // Компилируем файл.
                compile(name)
        }
        // Посылаем сообщение, что поток завершился.
        done <- true
}

func compile(name string) {
        // Вызываем компилятор.
        c, err := exec.Run(*compiler, []string{*compiler, name},
                           os.Environ(), "./data", exec.DevNull,
                           exec.PassThrough, exec.PassThrough)
        if err != nil {
                fmt.Printf("unable to compile %s (%s)\n", name, err.String())
                os.Exit(1)
        }
        c.Wait(0)
}

Makefile:

target = tar_extractor

all:
        6g $(target).go
        6l -o $(target) $(target).6

Я погонял это добро под Линуксом 64-бит на восьми процессорном блейде. Во время тестирования я был на машине один, так что результаты разных прогонов можно сравнивать. Файл "huge.tar" содержит ~15 тысяч исходников и имеет размер один гигабайт.

Так выглядит загрузка процессоров, когда машина ничего не делает (все процессоры почти на 100% в idle):

Cpu0  :  0.0%us,  0.0%sy,  0.0%ni,100.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu1  :  0.0%us,  0.0%sy,  0.0%ni, 99.7%id,  0.3%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu2  :  0.0%us,  0.0%sy,  0.0%ni,100.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu3  :  0.0%us,  0.0%sy,  0.0%ni,100.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu4  :  0.0%us,  0.0%sy,  0.0%ni,100.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu5  :  0.0%us,  0.3%sy,  0.0%ni, 99.3%id,  0.3%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu6  :  0.0%us,  0.0%sy,  0.0%ni,100.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu7  :  0.0%us,  0.0%sy,  0.0%ni,100.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st

Запускаем в последовательном режиме (-jobs 0):

make && time -p ./tar_extractor -jobs 0 huge.tar

Время работы:

real 213.81
user 187.32
sys 61.33

Практически все процессоры на 70-80% ничего не делают (все снимки я делал во время стадии компиляции):

Cpu0  : 11.9%us,  4.3%sy,  0.0%ni, 82.5%id,  1.3%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu1  :  9.6%us,  2.7%sy,  0.0%ni, 87.7%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu2  :  4.3%us,  1.3%sy,  0.0%ni, 92.7%id,  1.7%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu3  : 16.0%us,  6.0%sy,  0.0%ni, 78.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu4  : 12.6%us,  4.3%sy,  0.0%ni, 82.7%id,  0.3%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu5  : 11.6%us,  3.3%sy,  0.0%ni, 85.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu6  :  4.7%us,  1.3%sy,  0.0%ni, 94.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu7  : 16.6%us,  6.3%sy,  0.0%ni, 77.1%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st

Суммарная загрузка процессоров - 2.7%:

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
15054 tester    18   0 41420 4980 1068 S  2.7  0.1   0:02.96 tar_extractor

Теперь запускаем с пулом потоков, но только с одним каналом (-jobs 1).

Время:

real 217.87
user 191.42
sys 62.53

Процессоры:

Cpu0  :  5.7%us,  1.7%sy,  0.0%ni, 92.7%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu1  : 13.3%us,  5.3%sy,  0.0%ni, 81.3%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu2  :  7.0%us,  2.7%sy,  0.0%ni, 89.3%id,  0.7%wa,  0.0%hi,  0.3%si,  0.0%st
Cpu3  : 15.3%us,  5.7%sy,  0.0%ni, 77.7%id,  1.3%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu4  :  6.0%us,  2.0%sy,  0.0%ni, 92.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu5  : 14.3%us,  7.3%sy,  0.0%ni, 78.4%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu6  :  7.0%us,  2.3%sy,  0.0%ni, 90.7%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu7  : 15.3%us,  6.6%sy,  0.0%ni, 78.1%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st

Понятно, что картина такая же, так как реально мы также гоняем один поток.

А теперь включаем пул потоков (-jobs 32):

make && time -p ./tar_extractor -jobs 32 huge.tar

Время работы упало почти в семь раз:

real 38.38
user 195.55
sys 69.92

Общая загрузка процессоров (во время стадии компиляции) возросла до 23%:

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
17488 tester    16   0 45900 9732 1076 S 23.6  0.1   0:06.40 tar_extractor

Видно, что все процессоры реально заняты:

Cpu0  : 56.3%us, 26.3%sy,  0.0%ni, 17.3%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu1  : 55.5%us, 27.9%sy,  0.0%ni, 15.6%id,  1.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu2  : 56.1%us, 25.9%sy,  0.0%ni, 15.0%id,  0.7%wa,  0.3%hi,  2.0%si,  0.0%st
Cpu3  : 58.1%us, 26.2%sy,  0.0%ni, 15.6%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu4  : 57.2%us, 25.8%sy,  0.0%ni, 17.1%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu5  : 56.8%us, 26.2%sy,  0.0%ni, 16.9%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu6  : 59.0%us, 26.3%sy,  0.0%ni, 13.0%id,  1.7%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu7  : 56.5%us, 27.2%sy,  0.0%ni, 16.3%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st

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

Посты по теме Go:

среда, 6 апреля 2011 г.

Код возврата процесса в случае его падения

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

С багом мы разобрались (включая проблему в Makefile), но возник у меня общий вопрос: с каким именно кодом завершается процесс, если он упал, не успев выполнить exit().

В UNIXах есть специальные макросы, которыми можно проинспектировать код возврата wait(). Но, все UNIXы разные, и к тому же есть еще Windows.

В итоге я написал небольшую самопадающую программу:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
  char cmd[80];
  int r;
  sprintf(cmd, "%s ?", argv[0]);
  if (argc > 1) {
    if (argv[1][strlen(argv[1]) - 1] == '1')
      *(char *)0 = 0;
    exit(0x77);
  }
  printf("Normal: %08X\n", system(cmd));
  cmd[strlen(cmd) - 1] = '1';
  printf("Crash : %08X\n", system(cmd));
  return 0;
}

И запустил на некоторых характерных машинах.

Windows 7, Visual Studio 2010, "cl crash.c && crash":

Normal: 00000077
Crash : C0000005

Linux x86_64 ("cс -o crash crash.c && ./crash"):

Normal: 00007700
Crash : 0000000B

Сигнал 0x0B (13) - это, кстати, SIGSEGV, segmentation violation, что, собственно, и произошло.

Solaris SPARC 5.10:

Normal: 00007700
Segmentation Fault - core dumped
Crash : 00008B00

HP-UX Itanium 2:

Normal: 00007700
sh: 25112 Memory fault(coredump)
Crash : 00008B00

AIX 5.2:

Normal: 00007700
Crash : FFFFFFFF

Тут, видимо, до system() код возврата не дошел совсем.

Вывод: все крайне зависит (как всегда) от операционной системы.

суббота, 2 апреля 2011 г.

Unit-тестирование для подсветки грамматики

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

Я сейчас делаю небольшой проект по добавлению в putty возможности налету, прямо на уровне терминала, подсвечивать грамматику некоторого языка программирования. Основная сложность у меня в том, что язык крайне неуклюж - это некоторый диалект бейсика с парой сотней операторов, заточенных для работы с базой данных. Грамматика не контекстно-свободна, нерегулярна и полна неоднозначностей, которые разрешаются на основе огромного количества частных случаев.

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

В итоге после пары недель мытарств, я таки взял cmockery, написал всю необходимую «обвеску» и переделал все примеры в тесты.

Например:

void test_Ticket_dd6a19efa5_DATE(void **state) {
  string_eq("0029  ENTRIES<1, AB.CDE.VALUE.DATE>    = TODAY",
            "..............a........................b......");
  string_eq("0036  ENTRIES<1, AB.CDE.BOOKING.DATE>  = TODAY",
            "..............a........................b......");
  string_eq("0036  ENTRIES<1, AB.CDE.TOOKING DATE>  = TODAY",
            "..............a.................bbbb...c......");
  string_eq("0036 DATE = TODAY",
            ".....aaaa.b......");
  string_eq("0036  DATE = TODAY",
            "......aaaa.b......");
}

void test_Ticket_e8e02762a0_V_TIME(void **state) {
  string_eq("0017     V.TIME = 'x'",
            "................a.bbb");
  string_eq("0034     V.DELTA = TIME() - TIME1",
            ".................a.bbbb...c......");
}

void test_Ticket_0bcfac1fb6_READNEXT_FROM(void **state) {
  string_eq("0167     READNEXT ID FROM 9 ELSE DONE = 1 ",
            ".........aaaaaaaa....bbbb.c.dddd......e.f.");
}

И таких тестов сотни.

Макрос "string_eq" не является стандартным для cmockery, и под ним скрывается приличный кусок моего велосипеда. Вызывается функция подсветки строки, и по ней делается проход для отмечания факта смены цвета путем увеличения индекса (начальный индекс цвета - "а"). Точка значит неподсвеченный символ. Немного топорно, но позволяет не хардкодить в тестах коды конретных цветов. Конечно, сильно облегчает жизнь тот факт, что данный язык строчно-ориентированный. Иначе все было бы сложнее.

После этого жизнь радикально изменилась. Теперь я легко меняю код и одной командой проверяю, не сломал ли я чего из старого. Те два дня, что я потратил на написание дополнительного кода для тестов уже в сотни раз окупились.

Каждую новую фичу (=очередной частный случай) или багфикс я начинаю с теста. И только потом код. Реально не могу представить, как бы я дальше работал над проектом без тестов.

Тут получается вообще чистая класска TDD – сначала тесты, а только потом код.