sergey miryanov

How I setup Jenkins to build haskell/network

noreply@blogger.com (Sergey Miryanov) — Mon, 29 Aug 2011 10:15:00 +0000

Haskell/network is https://github.com/haskell/network

What I setup:
* msysgit [1]. Installed to C:\Program Files (x86)\Git
* MinGW [2]. Installed to C:\MinGW
* ghc [3, 4, 5]. Installed to c:\ghc\*
* cabal-install [6]. Installed to c:\ghc

After this I updated SYSTEM PATH environment variable (not user!) in following way:
* C:\MinGW\msys\1.0\bin
* C:\MinGW\bin
* C:\ghc
* C:\ghc\ghc-6.10.4\bin
* C:\ghc\ghc-6.12.3\bin
* C:\ghc\ghc-7.0.3\bin
* C:\Program Files (x86)\Git\cmd
* C:\Program Files (x86)\Git\bin

MinGW required to execute autoreconf.

Jenkins service started with my windows user credentials. This allowed service to access cabal package database, because with default service APPDATA path it fails on cabal update.

Also, maybe I did something wrong but 'cabal install ~~w ghc~~*.exe --only-dependencies --enable-tests' did not work, so I installed all deps manually.

[1] Git-1.7.6-preview20110708.exe from http://code.google.com/p/msysgit/downloads/list
[2] http://sourceforge.net/projects/mingw/files/Automated%20MinGW%20Installer/mingw-get-inst
[3] http://www.haskell.org/ghc/download_ghc_6_10_4
[4] http://www.haskell.org/ghc/download_ghc_6_12_3
[5] http://www.haskell.org/ghc/download_ghc_7_0_3
[6] cabal.exe from http://www.haskell.org/cabal/download.html

valgrind, dlopen and debug info

noreply@blogger.com (Sergey Miryanov) — Fri, 10 Jul 2009 05:34:00 +0000

Столкнулся сегодня с проблемой, что KCachegrind не отображает отладочную информацию для некоторых модулей.

Покопавшись в интернетах наткнулся на этот баг (valgrind doesn't output debug info with dlopen'ed libraries ) и вспомнил, что модули у нас загружаются динамически.

Как сказано в последнем сообщение это все таки баг:

The bug is still there.
I did some debugging with Julian and we came to the conclusion that the problem is with chroot() after dlopen'ing the library.

Я проверил код, но явно chroot нигде не вызывается.

Полез искать дальше и наткнулся на следующий баг (Debug info is lost for .so files when they are dlclose'd ). Что навело меня на мысль не выгружать модули.

И на самом деле помогло.

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

Domain-Specific Program Generation

noreply@blogger.com (Sergey Miryanov) — Sat, 28 Mar 2009 07:12:00 +0000

А ни у кого случайно нет вот этой книги в электронном виде?

upd:
Уже не надо, помогли товарищи из стенфорда. Сейчас у меня есть статьи из нее:
- Program Optimization in the Domain of High-Performance Parallelism
- A Personal Outlook on Generator Research
- PiLib: A Hosted Language for Pi-Calculus Style Concurrency
- A Language and Tool for Generating Efficient Virtual Machine Interpreters
- Optimizing Sequences of Skeleton Calls
- Domain-Specific Optimizations of Composed Parallel Components
- Runtime Code Generation in C++ as a Foundation for Domain-Specific Optimisation
- Guaranteed Optimization for Domain-Specific Programming

ODR violation

noreply@blogger.com (Sergey Miryanov) — Tue, 24 Mar 2009 06:12:00 +0000

Наткнулся сегодня на нарушение ODR (если я правильно понимаю).

Суть в том, что если класс имеет __declspec specifier и, кроме того, имеется forward declaration и у этого forward declaration __declspec specifier не указан, то можно поиметь кучу проблем, например, с экспортом символов в dll - их может в dll просто не оказаться.

Про систему событий

noreply@blogger.com (Sergey Miryanov) — Sun, 22 Mar 2009 07:16:00 +0000

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

Для начала скажу, что если мы регистриуем события begin, end то такая система позволит писать нам this->on_begin () или this->on_end (), а не this->fire_event (begin_signal). К тому же, мы можем иметь любое количество параметров различных типов и проверка типов будет выполняться на этапе компиляции, т.е. например, this->on_begin (clock ()).

Как это использовать:

      DECLARE_EVENT_LIST (reservoir_simulator,
                          signal_params_t,
                          17,
                          ((begin, (clock_t), 1)
                           , (before_initial_conditions, (), 0)
                           , (after_initial_conditions, (), 0)
                           , (begin_large_step, (), 0)
                           , (before_wells_process, (), 0)
                           , (before_grp_process, (), 0)
                           , (after_grp_process, (), 0)
                           , (before_low_skin_factor, (), 0)
                           , (after_low_skin_factor, (), 0)
                           , (after_large_step, (), 0)
                           , (begin_small_steps, (), 0)
                           , (after_small_steps, (), 0)
                           , (before_save_data, (), 0)
                           , (after_save_data, (), 0)
                           , (before_history_matching, (), 0)
                           , (after_history_macthing, (), 0)
                           , (end, (clock_t), 1)
                          ));

_Winnie C++ Colorizer

Самое интересное здесь это:

                          ((begin, (clock_t), 1)
                           , (before_initial_conditions, (), 0)
                           , (after_initial_conditions, (), 0)
                           , (begin_large_step, (), 0)
                           , (before_wells_process, (), 0)
                           , (before_grp_process, (), 0)
                           , (after_grp_process, (), 0)
                           , (before_low_skin_factor, (), 0)
                           , (after_low_skin_factor, (), 0)
                           , (after_large_step, (), 0)
                           , (begin_small_steps, (), 0)
                           , (after_small_steps, (), 0)
                           , (before_save_data, (), 0)
                           , (after_save_data, (), 0)
                           , (before_history_matching, (), 0)
                           , (after_history_macthing, (), 0)
                           , (end, (clock_t), 1)
                          )

_Winnie C++ Colorizer

Это наш список событий - каждое событие описывается кортежом, состоящим из имени события, списка параметров (тоже кортеж) и количества параметров с списке.

Итак:

#define DECLARE_EVENT_LIST(name_, params_, ts_, t_)\
    public:\
    DECLARE_SIGNALS_ENUM(ts_, t_)\
    BOOST_PP_SEQ_FOR_EACH_I(UDECL_I, params_, BOOST_PP_TUPLE_TO_SEQ(ts_, t_))\
    EXPORT_SIGNALS_ENUM(name_, ts_, t_)

_Winnie C++ Colorizer

name_ - prefix, params_ - тип параметров, ts_ - количество событий в кортеже, t_ - кортеж событий. Про params_ я объясню позже.

DECLARE_SIGNALS_ENUM(ts_, t_) - из кортежа событий делаем enum.
BOOST_PP_SEQ_FOR_EACH_I(UDECL_I, params_, BOOST_PP_TUPLE_TO_SEQ(ts_, t_)) - создаем набор функций типа on_[event_name].
EXPORT_SIGNALS_ENUM(name_, ts_, t_) - выгрузка этого дела в питон.

Далее:

#define DECLARE_SIGNALS_ENUM(ts_, t_)\
    enum signal_codes {\
    BOOST_PP_SEQ_FOR_EACH_I(DECLARE_SIGNAL_ENUM_I, _, BOOST_PP_TUPLE_TO_SEQ(ts_, t_))\
  };

_Winnie C++ Colorizer

BOOST_PP_TUPLE_TO_SEQ(ts_, t_) - делаем из кортежа событий последовательность.
BOOST_PP_SEQ_FOR_EACH_I(DECLARE_SIGNAL_ENUM_I, _, BOOST_PP_TUPLE_TO_SEQ(ts_, t_)) - для каждого элемента последовательности применяем макрос DECLARE_SIGNAL_ENUM_I.

#define DECLARE_SIGNAL_ENUM_I(r, data, i, elem)\
    BOOST_PP_CAT(BOOST_PP_TUPLE_ELEM(3,0,elem), _signal),

_Winnie C++ Colorizer

BOOST_PP_CAT(BOOST_PP_TUPLE_ELEM(3,0,elem), _signal) - т.к. событие у нас описывается кортежом и в данном макросе мы получили его в elem, то надо вытащить из него первые элемент, ну и добавить к нему префикс. На выходе получим нечто типа:
enum {
begin_signal,
end_signal,
};

Теперь нам надо создать функции on_[event_name].
BOOST_PP_SEQ_FOR_EACH_I(UDECL_I, params_, BOOST_PP_TUPLE_TO_SEQ(ts_, t_)) - тоже самое, делаем последовательность и для каждого элемента применяем макрос UDECL_I.

#define DECL(type_, name_, t_, ts_)\
    void BOOST_PP_CAT(on_, name_) (PARAM_LIST(BOOST_PP_TUPLE_TO_SEQ(ts_, t_), ts_))\
    {\
        type_ params;\
        PUSH_LIST (BOOST_PP_TUPLE_TO_SEQ(ts_, t_), ts_)\
        this->fire_signal (BOOST_PP_CAT(name_, _signal), params);\
    }

#define UDECL_I(r, data, i, elem)\
    DECL(data, BOOST_PP_TUPLE_ELEM(3,0,elem), BOOST_PP_TUPLE_ELEM(3,1,elem), BOOST_PP_TUPLE_ELEM(3,2,elem))

_Winnie C++ Colorizer

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

PUSH_LIST и PARAM_LIST у меня самописные (т.к. project-specif), но если разобраться как устроены некоторые BOOST_PP то можно подобрать аналог или написать свои, это на самом деле не сложно.

Выгрузка в питон тоже не представляет интереса, т.к. делается по аналогии.

Ну вроде все.

template class overriding

noreply@blogger.com (Sergey Miryanov) — Sun, 22 Mar 2009 07:06:00 +0000

Тут на днях выяснилось, что не все знают про один плюснутый трюк. Как известно, C++ не позволяют иметь шаблонные классы с одинаковым именем, но разным количеством шаблонных параметров. Т.е. код

template <typename X>
struct S
{
};
template <typename X, typename Y>
struct S
{
};

_Winnie C++ Colorizer

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

template <typename X>
struct S_X
{
};
template <typename X, typename Y>
struct S_XY
{
};
template <typename X>
S_X <X>
S (/*params*/)
{
  return S_X <X> (/*params*/);
}
template <typename X, typename Y>
S_XY <X, Y>
S (/*params*/)
{
  return S_XY <X, Y> (/*params*/);
}

_Winnie C++ Colorizer

В первый раз я этот трюк использовал, когда делал свой парсер а-ля boost::spirit. Также он используется при реализации техники Expression Templates.

GCC can't parse a non-parenthesized comma in a template-id within a default argument

noreply@blogger.com (Sergey Miryanov) — Tue, 06 Jan 2009 06:09:00 +0000

Ковырялся вчера с нашим Ядром (тм) и наткнулся на баг в gcc (в Comeau Online компилится), гыгыгы :)
Вот кусок кода, на котором можно протестить:


template <typename T, bool F>
struct sp
{
  sp ()
  {
  }
};

struct X
{
  typedef sp <X, true> sp_x;
  //X (sp_x x = sp_x ())                      // OK
  //X (sp <X, true> x = (sp <X, true> ()))    // OK
  X (sp <X, true> x = sp <X, true> ())        // ERROR
  {
  }
};

Баг в багзилле тоже нашел (#57) =)

noreply@blogger.com (Sergey Miryanov) — Fri, 29 Aug 2008 17:54:00 +0000

Юра Бронников, известный своим переводом SICP на русский, взялся за перевод отличной книги Types and Programming Languages. И он призывает учавствовать в вычитке. Книга планируется к изданию в бумажном виде.

via Alex Ott

boost::python hint

noreply@blogger.com (Sergey Miryanov) — Thu, 24 Jul 2008 17:01:00 +0000

При выгрузке в питон классов с виртуальными функциями wrapper, который будет перенапралять вызовы должен хранить ссылку на питоновский объект. Но в бустовой документации нигде не говорится, что у нее надо увеличивать счетчик. А делать, это желательно. Для этого нужно использовать Py_INCREF/Py_DECREF.

Эксперименты с expression templates и sse

noreply@blogger.com (Sergey Miryanov) — Sat, 05 Jul 2008 16:11:00 +0000

Недавно узнал о новой для себя технике – expression templates, это то знание, которого мне в свое время не хватило, когда я писал парсер а-ля boost::spirit (нашел, кстати, статью, в которой довольно подробно описано как устроен не весть, но часть boost::spirita).

Недавно встала задача выполнения простейших арифметических операций над большими массивами данных. Конечно, это дело можно запрограммировать по старинке, но хочется, чтобы все было красиво и прозрачно – и тут я решил поискать, как, же все таки работает boost::spirit, оказалось, что в его основе лежит очень красивая и элегантная идея (и все менее слоупоки чем я с ней давно знакомы, я думаю). Идея в том, что операции над операндами выполняются не в момент, когда эти операции встречаются в выражении, а только в тот момент, когда результат данного выражения нужен.

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

Я уже говорил, что я решил использовать эту технику для операций над массивами, и тут есть два варианта:
- использовать готовую библиотеку (например, tvmet).
- или написать свою примитивную.

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

Набор классов для базовых операций (+, -, *, /) пишется за пол часа, ничего сложного нет.

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

Второе, что я хотел сделать – это реализовать эти операции с использованием sse – во-первых хотелось наконец руками потрогать sse, во-вторых хотелось хоть не много сгладить потери в реализации, которые возможно (?) будут привнесены техникой.
Для эффективной реализации алгоритмов с sse необходимо, чтобы данные были выровнены на границу 16-байтного слова. По умолчанию стандартный аллокатор не выравнивает память и необходимо либо написать свой, либо найти аллокатор, совместимый со стандартным, который бы выравнивал выделяемую память. Как оказалось, простой аллокатор с такой функциональностью сделать совсем не сложно. Что я, конечно, и сделал.

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

Вот вроде и все. Source code.

asio 1.1.1

noreply@blogger.com (Sergey Miryanov) — Sat, 05 Jul 2008 07:22:00 +0000

Между тем два дня назад вышла новая версия asio, в которой официально добавлен windows::basic_random_access_handle.

На мой вопрос связанный с тем, почему не работает async_read Chris ответил что следует пользоваться async_read_at и соответственно windows::basic_random_access_handle (пример, если кому-нибудь интересно).

Еще раз про asio и про мои тесты

noreply@blogger.com (Sergey Miryanov) — Sun, 29 Jun 2008 18:35:00 +0000

У меня наконец то нашлось достаточно времени чтобы закончить начатые тесты с asio. Буду краток - asio это круто и очень удобно. Как всегда:

seq - seq - файл открыт для последовательного чтения и чтение производится последовательно
seq - rnd - тоже самое, только чтение производится со случаным смещением
rnd - seq - файл открыт для чтения с произвольным доступом, чтение производится последовательно
rnd - rnd - это понятно
seq_nb - rnd - файл открыт для последовательного чтения, без буфферизации, чтение производится со случайным смещением
rnd_nb - rnd - файл открыт для чтения с произвольным доступом, без буфферизации, чтение производится со случайным смещением

Как видно я все таки облажался в прошлом посте на тему, и чтение с произвольным смещением медленее, чем последовательное. Но при этом можно получить скорость доступа большую 10MB/s.

Реализация asio круче чем моя собственная:

Тут сравнивались только seq_nb/rnd_nb - rnd.

По нижней оси как всегда размер буфера чтения.

asio::io_service::reset hint

noreply@blogger.com (Sergey Miryanov) — Wed, 25 Jun 2008 19:07:00 +0000

Могу посоветовать перед каждым вызовом asio::io_service::run вызывать asio::io_service::reset:

This function must be called prior to any second or later set of invocations of the run(), run_one(), poll() or poll_one() functions when a previous invocation of these functions returned due to the io_service being stopped or running out of work. This function allows the io_service to reset any internal state, such as a "stopped" flag.

Это во многом облегчит жизнь начинающего asio-иста.

asio::windows::basic_stream_handle - 2

noreply@blogger.com (Sergey Miryanov) — Tue, 24 Jun 2008 17:10:00 +0000

Если поковыряться, то можно придумать как запилить asio::windows::basic_stream_handle, чтобы он правильно (опять же на мой взгляд) читал из файлов. Запил на самом деле очень простой и я не вижу причин, почему разработчики не пошли по тому же пути.

Запил - в файл win_iocp_handle_service.hpp после строки 691 добавить следующее:

ptr.get()->Offset = boost::uint64_t (handler.total_transferred_) & 0xFFFFFFFF;
ptr.get()->OffsetHigh = (boost::uint64_t (handler.total_transferred_) >> 32) & 0xFFFFFFFF;

_Winnie C++ Colorizer

diff'ы делать я еще не научился, сорри.

asio::async_read and asio::windows::basic_stream_handle

noreply@blogger.com (Sergey Miryanov) — Tue, 24 Jun 2008 16:33:00 +0000

Ковыряюсь тут с asio на предмет ассинхронного чтения файлов. Как выяснилось последняя версия - 1.1.0 - не умеет правильно читать из файлов. Простой код (см. ниже) не работает.

asio::windows::basic_stream_handle<> handle_;
asio::streambuf buf_;

asio::async_read (stream_, buf_, complete_condition_, handler_);

_Winnie C++ Colorizer

Ожидаемое (на мой взгляд) поведение - файл будет полностью считан в буфер buf_. Вместо этого буфер забивается блоком данных (по умолчанию 512b), считанных от начала файла и до тех пор пока размер буфера меньше размера файла.

По совету Alex'a взял версию c cvs.sourceforge - там та же фигня с basic_stream_handle. Но зато появился basic_random_access_handle, на основе которого можно сделать свой поток и читать последовательно (или со случаным доступом) из файла. Поток можно сделать например таким:

struct random_handle_wrapper
{
  random_handle_wrapper (asio::io_service &io_service, HANDLE file)
  : handle_ (io_service, file)
  , file_ (file)
  , transfered_ (0)
  {

  }

  template <typename MutableBufferSequence, typename ReadHandler>
  void async_read_some(const MutableBufferSequence& buffers, ReadHandler handler)
  {
    handle_.async_read_some_at (transfered_, buffers, handler);
  }

  void move_fwd (size_t transfered)
  {
    transfered_ += transfered;
  }

  asio::windows::basic_random_access_handle<> handle_;
  HANDLE            file_;
  boost::uint64_t   transfered_;
};

_Winnie C++ Colorizer

Тогда read_handler примет примерно такой вид:

void read_handler (asio::error_code ec, size_t transferred)
{
  std::cout << std::string (data_.c_array(), data_.c_array() + transferred);
  stream_.move_fwd (transferred);
  asio::async_read (stream_, buf_, complete_condition_, handler_);
}

_Winnie C++ Colorizer

И так уже можно жить.

noreply@blogger.com (Sergey Miryanov) — Sat, 21 Jun 2008 16:52:00 +0000

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

Вести из зазеркалья

noreply@blogger.com (Sergey Miryanov) — Mon, 16 Jun 2008 18:13:00 +0000

Данные результаты тестов официально признаются зафейлеными.

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

async (no buf, seq scan) - последовательное чтение - FILE_ATTRIBUTE_NORMAL | FILE_FLAG_OVERLAPPED | FILE_FLAG_SEQUENTIAL_SCAN | FILE_FLAG_NO_BUFFERING.

async (no buf, rand) - случайное чтение - FILE_ATTRIBUTE_NORMAL | FILE_FLAG_OVERLAPPED | FILE_FLAG_NO_BUFFERING.

async (no buf, seq scan, rand) - случайное чтение - FILE_ATTRIBUTE_NORMAL | FILE_FLAG_OVERLAPPED | FILE_FLAG_SEQUENTIAL_SCAN | FILE_FLAG_NO_BUFFERING.

noreply@blogger.com (Sergey Miryanov) — Thu, 05 Jun 2008 15:05:00 +0000

Кстати, если еще кто не читал, то рекомендую: Assertions, Enhancing Assertions.

Александреску рассказывает как делать Ассерты(тм).

О том как с толком потратить время

noreply@blogger.com (Sergey Miryanov) — Tue, 03 Jun 2008 15:22:00 +0000

В общем, по случаю тут тестировал загрузку больших файлов. Файлы – массив чисел с плавающей точкой, в текстовом виде.

Тестировал на файле из 50М чисел, это примерно 700МB данных.

Я начал с обычного sscanf, долго плясал вокруг него с бубном, подбирал размеры буфера. Пока не уперся в примерно 8MB/s. Думал, что это ограничение жесткого диска, как выяснилось - нет. Затем заменил sscanf на atof, скорости тоже не прибавило. Сделал memory mapped и async IO – это прибавило порядка 20% - для размера буфера, который я считал оптимальным. Но это тоже все не то. Попробовал выкинуть atof из внутреннего цикла – получил порядка 30+ MB/s. Круто. Нашел в интернете парочку быстрых функций – strtod (у меня в тестах "fast" strtod) и fast_atof от IrrLicht.

По просьбе трудящихся, так же включил boost::lexical_cast (он, кстати, показал самый стабильный результат).

Тест с async IO no buffering включил по наводке с сайта. Опять же на первоначальном размере буфера результаты были не лучшие, так что я его включил так, на всякий случай. Конечные результаты показали, что все таки не зря.

Случай первый - стандартные С файлы - FILE.

Случай второй - memory mapped файлы (win32)

Асинхронные файлы (win32)

Чтение производится в два буфера - пока данные загружаются во второй буфер, данные из первого буфера обрабатываются. Проседание производительности для буфера с размером большим 32k, я могу объяснить тем, что прочитанный буфер обрабатывается дольше, чем загружается второй буфер чтения.

Асинхронные файлы без буферизации (win32)

Сравнение "fast" strtod для различных типов чтения файлов

Сравнение IrrLicht fast_atof для различных типов чтения файлов

Во всех случаях по оси Х - размер буфера чтения в байтах, по оси Y - data transfer rate, в MB/s. Для memory mapped файлов во всех случаях размер буфера - 64k. Почему "fast" strtod показал такие странные результаты - надо смотреть, а с этим по определенным причинам плохо.

Да, «быстрые» версии не работают с локалями и прочим, но об этом можно подумать отдельно, если скорость загрузки критична.
Да, тесты банальны – все и так знают, что стандартные функции чересчур медленные.

Ну вот вроде и все.

Loop Stream Detector

noreply@blogger.com (Sergey Miryanov) — Sat, 17 May 2008 19:40:00 +0000

There is another big advantage of small loops, at least on certain processors. The Intel Core 2 front end has a special feature called Loop Stream Detector (LSD). If a loop has no more than 18 instructions (none of which is a call to a subroutine), requires only up to 4 decoder fetches of 16 bytes, has at most 4 branch instructions, and is executed more than 64 times, than the loop is sometimes locked in the instruction queue and therefore more quickly available when the loop is used again. This applies, for instance, to small inner loops which are entered
many times through an outer loop.

Back to the future

noreply@blogger.com (Sergey Miryanov) — Sat, 17 May 2008 19:37:00 +0000

Несколько слов о том, что нас ждет в будущем – в будущем нас ждет полный коммунизмЪ и всеобщее счастье.

В статье приводится не большой пример конструирования lock-free стека. Затем ведется разговор о transactional memory. Про TM в основном на железячном уровне и по большей части на основе довольно старой статьи о HTM. Для HTM будет свой собственный кеш и следовательно данные, которые будут использоваться транзакциями следует отделять от остальных данных.

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

Список приложений
Приложение А.1 – умножение матриц, с разворачиванием и векторизацией.
Приложение А.2 – отладка статического предсказания переходов.
Приложение А.3 – измерения шаринга кеш-линий.
Приложение Б – подсказки по oprofile
Приложение С – типы памяти
Приложение D - libNUMA

How we can do it

noreply@blogger.com (Sergey Miryanov) — Sat, 17 May 2008 19:34:00 +0000

Несколько групп инструментов:
• Инструменты для профилирования работы с памятью
• • oprofile
• • • Можно получить только вероятностные и иногда неточные результаты
• • pfmon
• Инструменты для моделирования работы кешей
• • valgrind --tool=cachegrind
• Инструменты для подсчета используемой памяти
• • valgrind --tool=massif
• • • в случае если используется собственный аллокатор не возможно отследить использование памяти
• • • если используется только обертка над обычными функциями, то можно указать название функции --alloc-fn=function
• • memusage
• Инструменты для профилирования нарушений доступа (page fault)
• • Автор разработал собственную программу для valgrind’a – pagein
• Profile guided optimization
• • gcc –fprofile-generate and -fprofile-use

Те же советы – статическое предсказание переходов, увеличение размера страницы, правильный выбор аллокатора.

What we can do

noreply@blogger.com (Sergey Miryanov) — Sat, 17 May 2008 19:30:00 +0000

Это самое интересное.

1. non-temporal write operations
В случаях, когда обрабатывается большой набор данных, например, загружается с диска и выстраивается в памяти в какую-либо структуру для дальнейшей обработки, то можно отменить кеширование таких данных. Для этого используются streaming SIMD extensions.

2. seq vs rand
Способ обращения к памяти тоже важен. Последовательный доступ более эффективен, чем случайный или по колонкам (например, в матрицах). Если правильно подготовить данные, чтобы обработка выполнялась последовательно, то можно получить очень хороший прирост производительности.

3. loop unrolling
Можно вручную разворачивать циклы, в которых производится обработка больших наборов данных. Делать это стоит для того, чтобы максимально использовать кеш-линию. Под размер кеш-линии можно подстраиваться динамически (sysconf (_SC_LEVEL1_DCACHE_LINESIZE)), либо статически.

4. vectorization
Чтобы выжать максимальную производительность в дополнение к перечисленному, стоит воспользоваться векторизованными операциями (SIMD, SSE).

5. padding
Данные стоит выравнивать и избегать padding’а. Можно сказать gcc --reorganize чтобы он перетасовал данные, чтобы уменьшить padding.

6. critical words
Наиболее часто используемые данные стоит размещать в начале структуры. Если способ доступа (access pattern) заранее не известен, то лучше обращаться к элементам структуры в том порядке, в котором они объявлены.

7. structure cache line alignment
В случае если структура большая (больше кеш-линии), то элементы следует выравнивать по кеш-линии, с учетом правила critical word.

8. alignment
Код и данные должны быть выровнены. В случае если выравнивание отсутствует, то можно получить большие пенальти при работе с памятью.
Отсюда же вытекает, что стек должен быть выровнен. В большинстве случаев компилятор знает размер стека для каждой функции, соответственно он может выравнивать функции. Функции с переменным числом параметров и alloca лишают компилятор такой возможности.

9. code linearization
Переходы плохо предсказываются статически и могут привести к большему количеству промахов в кеш.

10. L1i
Для того чтобы лучше использовать L1i нужно обратить внимание на:
• Уменьшение объема кода.
• Выравнивание кода.
• И линейное выполнение кода (linear code execution without bubbles). Это сложно и автор отсылает к чтению документов по processor design.

11. code inlining
При подстановке функций результирующий код может оказаться больше одной кеш-линии и вполне может оказаться, что этот кусок без инлайна, но умещающийся в кеш-линии будет эффективнее. За этим тоже стоит следить. Компилятору можно об этом сказать, используя always_inline и noinline.

12. Статическое предсказание переходов
В случаях, когда какое-либо условие в большинстве случаев имеет одно значение, компилятору можно сказать об этом. В этом случае, он сможет сгенерировать более эффективный код, за счет размещения реже выполняемой ветки кода за чаще используемой веткой кода. gcc об этом можно сказать с помощью __builtin_expect и флагом –freorder-blocks.

13. small loops
Процессоры умеют определять циклы в коде, если цикл удовлетворяет определенным условиям, то он может быть locked in the instruction queue и поэтому доступ к нему будет происходить быстрее.

14. reduce working set size
Желательно уменьшать размер рабочей области, чтобы она помещалась в L2 кеш и за счет этого уменьшилось общее количество промахов в кеш.

15. TLB usage optimization
Первое – увеличить размер страниц, второе – уменьшить распределение диапазонов адресов. Про первое уже говорилось, про второе тоже, стоит добавить, что существует такая штука как ASLR. ASLR случайным образом распределяет в памяти DSO, стек, кучу и прочее, чтобы предотвратить некоторые атаки. Если производительность выше безопасности то следует ASLR отключать.

16. hardware prefetching
Hardware prefetching работает в границах одной страницы. Насколько я понял, в некоторых ситуациях это может создавать проблемы. Чтобы управлять префетчингом или вообще его отключить существуют MSR регистры.

17. software prefetching
Самое главное правило – сначала профилирование, затем оптимизация, затем снова профилирование. Стоит смотреть на количество промахов в кеш, выделять проблемные места и пробовать их префетчить и затем снова смотреть на количество промахов. Если количество промахов не уменьшилось, то инструкции префетчинга лучше убрать.
gcc умеет префетчить доступ к массивам, обрабатываемым в цикле.

18. speculative load
Процессоры умеют выполнять несколько инструкций одновременно. В некоторых ситуациях код не может быть разделен на конвейеры из-за определенного порядка инструкций и из-за то, что не может быть предсказано содержимое памяти или регистров. Код можно перегруппировать, вынеся команды загрузки данных за команду, которая реально их использует. Для этого используется speculative load – данные загружаются в регистр, далее в том месте где эти данные используются выполняется проверка (либо она делается раньше и автоматически) что данные не изменились в памяти. Если не изменились – загружаются из регистра, если изменились – из памяти.
Корявенько, но надеюсь смысл понятен. В статье более понятный пример.

19. prefetcher thread
Для префетчинга данных можно использовать второй поток, который будет заниматься только префетчингом. У автора на тестах такой вариант оказался производительнее, чем вариант с простым префетчингом.
Недостатком способа является необходимость синхронизировать основной и вспомогательные потоки.

Multi-threading optimizations
Три основных вопроса, которые стоит рассматривать в связи с:
• Конкурентность
• Атомарный доступ
• Пропускная способность

Конкурентный доступ к данным
20. divide modified data
Наилучший случай – потоки работаю с совершенно различными участками памяти (это не относится к hyperthread’ам).
В случае если потоки пишут(!) в перекрывающиеся регионы памяти, может произойти «false sharing» - когда одна и та же кеш-линии из-за RFO постоянно перемещается из кеша одного процессора в кеш другого процессора. Это можно привести к серьезному уменьшению производительности. Этого можно избежать либо полностью разделив данные, либо добавляя padding между элементами структуры, чтобы каждый элемент или группа элементов, обрабатываемых потоком находилась в различных кеш-линиях.

21. group const vars
В противоположность модифицируемым данным константы вполне можно и нужно разделять, поэтому лучше все константы сгруппировать в единый блок.

Можно выделить 4 группы, на которые можно разбивать данные:
• read-only
• read-write
• read-mostly
• per-thread (можно пометить __thread, тогда будет использоваться TLS, но следует иметь в виду, если данные используются только одним потоком, то в других потоках эти данные будут просто занимать данные, кроме того, указатели на данные в TLS не валидные в других потоках, со всеми вытекающими отсюда).

Атомарность доступа
Существует несколько распространенных типов атомарного доступа к данным:
• Bit test
• Load Lock / Store Conditional (LL/SC)
• CAS
• Atomic arithmetic
Операции атомарной арифметики выполняются эффективнее, чем CAS. Хотя последний является более простым.

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

Еще раз NUMA
Несколько советов:
• Реплицировать данные
• Группировать данные по процессорам узла
• Обрабатывать данные блоками на разных процессорах, результат сливать
• Писать данные в локальную память

Let Mortal Kombat begin

noreply@blogger.com (Sergey Miryanov) — Sat, 17 May 2008 19:22:00 +0000

What every programmer should know about memory - это очень большая и интересная статья о работе с памятью. Уверен, что тем, кому приходилось заниматься обработкой больших наборов данных или писать критический к производительности код сталкивались или знают о вещах, о которых говориться в статье.

Память
Итак, в современных компьютерах используется два типа памяти – статическая и динамическая. Статическая память очень быстрая, но очень сложная, поэтому ее очень мало. Динамическая память проще в устройстве, поэтому ее можно сделать больше, поэтому в современных компьютерах ее много. Ну, «много». Простота устройства имеет свои отрицательные стороны. Если при обращении к статической памяти мы моментально получаем ответ (запись или чтение слова), то при обращении к динамической памяти имеет различные задержки и синхронизации. Подробнее про циклы синхронизации написано в статье.

Кеш
Это объясняют, почему доступ к памяти имеет задержки на программном уровне. Чтобы скрыть эти задержки были введены аппаратные кеши – L1, L2 и где то L3. По нарастающей - эти кеши имеют большую емкость и большее время доступа. L1 может быть реализован статической или динамической полно-ассоциативной памятью. L2-кеши как правило реализуются в виде 4- или 8- ассоциативной памяти. В статье довольно подробно рассказано про то, какая бывает память и как она устроена. Нарисованы интересные таблички и графики по времени доступа, в зависимости от размера кеша и ассоциативности L2-кеша. Зависимость между размером кеша и ассоциативностью имеет нелинейный характер (в некоторых источниках указывают, что при увеличении ассоциативности вдвое также вдвое увеличивается «размер» кеша, это неверно в общем случае).

Введение hyperthreading’а означает уменьшение размера кеша вдвое, чтобы компенсировать это можно ввести 16-ассоциативный кеш. Но на самом деле он довольно сложен в организации, поэтому, как правило, добавляют еще один уровень кеша (L3 получается также 4- или 8- ассоциативный), а L2 шарят между ядрами.

На все это стоит обращать внимание при выборе процессора.

L1 кешей сущестует два – для инструкций и для памяти – L1i и L1d. В кеше инструкций хранятся уже декодированные команды, а не просто куски чистой памяти, как в L1d.

L1 кеш обычно per core. Поэтому его будут разделять все процессы. Это следует иметь в виду при создании многопоточных приложений. Ну и hyperthreading тоже разделяет этот кеш и его емкость по сути уменьшается вдвое.

L2 обычно разделяется между ядрами.

Кеши выстроены в иерархию L1(I,d)->L2->L3->main memory. При обращении к памяти слово, а точнее кеш-линия попадает в кеш. Если в кеше нет места для новой кеш-линии может произойти следующее:
• Если у процессора exclusive cache, например в AMD, то кеш-линия присутствует только в одном кеше. Соответственно, когда заканчивается место в кеше она выталкивается в кеш на уровень выше.
• У Intel’a inclusive cache. И кеш-линия присутствует во всех (L1, L2) кешах, соответственно при выталкивании нет необходимости помещать кеш-линию в кеш на уровень выше, так как она уже там находиться. Соответственно inclusive caches оперативнее выталкивают линии из кеша.

Эти вещи также стоит учитывать при выборе процессора.

На SMP машинах процессоры имеют доступ ко всей памяти и поэтому кеши ядер не могут работать независимо друг от друга, т.к. у разных процессоров в кеше может оказаться одна и та же кеш-линия. Поддержание процессорами состояния своих кешей в не противоречивом состоянии называется cache coherency. Для этого кеш-линии, в которые производилась запись, помечаются dirty-флагом. Если другой процессор обращается кеш-линии другого процессора, которая помечена этим флагом, то происходит запись кеш-линии в память и загрузка ее в кеш другого процессора. При этом кеш-линии непомеченные данным флагом могут присутствовать в кешах нескольких процессоров.

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

Для поддержания памяти в целостном состоянии были разработаны различные протоколы и один из них это MESI (и самый распространенный). M – Modified, E – Exclusive, S – Shared, I – Invalid. Опять же с этим практически не приходиться сталкиваться в обычной жизни, но знать об этом стоит.

Изначально все кеш-линии помечены как Invalid. При записи в кеш-линию она помечается M, при чтении – либо S, либо E, смотря сколько процессоров читают из кеш-линии одновременно. При попытке чтения кеш-линии в состоянии M другим процессором, она будет записана в память и затем передана в кеш другого процессора. Этот процесс называется RFO – Request For Ownership. Также перемещение потока на другой процессор может вызвать RFO. Не смотря на то, что MESI предназначен для эффективной реализации кешей, одного его не достаточно. В SMP на производительность оказывает влияние и пропускная способность шины (FSB) и необходимость синхронизации.

В статье приведена таблица, сколько примерно тактов занимает доступ к кешу и памяти:
• Registers <= 1
• L1d ~ 3
• L2 ~ 14
• Main memory ~240.

Но это все в идеальном случае. На практике чаще всего получается все сильно хуже.

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

Существенным является размер рабочей области – working set size – в том случае, когда этот размер превышает размер какого-либо кеша, то начинаются пенальти, и заметно снижается скорость доступа.

Имеет значение характер работы с памятью. При этом можно использовать различные префетчи. При большом размере рабочей области на производительность будут оказывать влияние промахи в TLB кеш.

При больших размерах рабочей области и при последовательном доступе существенным будет и размер кеша, как L1 так и L2. Чем больше размер, тем выше производительность. При случайном доступе преимущество большого кеша будет не так явно заметно.

Для записи обычно существует несколько стратегий (write-through, write-back), но с ними обычно приходиться иметь дело на уровне ядра.

В случае параллельной обработки можно добиться 2 и 4 кратного увеличения производительности для 2 и 4 потоков, но только если размер рабочей области не превышает размеры кеша (в данном случае кеша L2) и только в случаях, когда потоки не выполняются независимо. Это в случае «чистых» потоков, в случае hyperthreading’а все не много по-другому, так как они разделяют все кеши и память. Приводится формула и график, рассчитанный на ее основе. По графику можно заключить, что если программа имеет небольшое число удачных попаданий в кеш (hit-rates), то использование нескольких потоков выгодно. В случае если программа имеет высокий уровень попаданий, то получить прирост производительности для нескольких потоков довольно сложно.

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

Процессор загружает в кеш память блоками, называемыми кеш-линиями. Для загрузки одной кеш-линии процессору необходимо выполнить несколько операций чтения данных. Это привносит свои задержки. Чтобы их скрыть процессор умеет загружать и предоставлять доступ к запрошенному слову, а остальную часть кеш-линии загружать в фоне. Данное слово называется критическим (critical word). Желательно, чтобы это критическое слово находилось в начале кеш-линии.

Виртуальная память
Процессор имеет подсистему виртуальной памяти. Для обеспечения доступа к ней операционная система хранит таблицы страниц. При доступе к какой-либо памяти ОС транслирует виртуальный адрес в физический с помощью этих таблиц. Эти таблицы располагаются в основной памяти поэтому доступ к ним желательно также оптимизировать. Для этого процессор имеет TLB кеш (Translation Look-Aside Buffer). L1TLB кеш очень маленький и поэтому очень быстрый. TLB кеш имеет несколько уровней и L1TLB разделен на кеш инструкций и данных.

TLB кеш также можно префетчить, но не явно, а за счет префетчинга код и данных.

Таблица страниц для каждого процесса своя, от распределения используемых диапазонов адресов зависит количество уровней таблиц, и соответственно время доступа. Если имеется такая возможность, то желательно распределение адресов уменьшить. Также количество и размер таблиц страниц зависит от размера страницы. В случаях с большим размером страницы можно получить прирост производительности. Говорят, что в мире больших БД это нормальная практика увеличивать размер страницы.

Чтобы использовать страницы большего размера в линуксе необходимо использовать hugetlbfs.

NUMA
Non Uniform Memory Access. Имеется куча процессоров, к каждому их которых подсоединена своя память. Но все процессоры имеют доступ ко всей, общей, памяти. Это создает отдельные трудности, т.к. обращение к чужой памяти требует, чтобы процессор-владелец передал запрошенную память (кеш-линию) другому процессору. Это вносит задержки, которые есть и с которыми надо как то бороться, или как то скрывать. Что можно сделать – уменьшить количество запросов к чужой памяти, это можно делать через affinity mask. Кроме того, DSO объекты могут быть общими для всех процессов, выполняющихся на разных процессорах. Обращение к DSO приведет к доступу в чужую память и к потере производительности. С этим тоже можно бороться (на уровне приложений или ОС?) с помощью зеркалирования DSO. В линуксе информацию о доступной NUMA-памяти и кешах можно получить через sysfs (/sys/devices/system/cpu/cpu*/cache).

noreply@blogger.com (Sergey Miryanov) — Fri, 02 May 2008 18:12:00 +0000

Вы можете лучше управлять потоками DX.

Ну и чтобы два раза не вставать: не большой пример с интересными цифрами.