Компилирование библиотек boost

У меня есть QtCtreator под Windows и необходимо скомпилировать библиотеки буста. Сначала скачиваем последнюю версию исходников буста. На текущий момент это версия 1.48.
1) Распаковываем архив (я распаковал его на диск C:\ ).
2) Создаем и устанавливаем следующие переменные окружения:
      BOOST_ROOT="C:\boost_1_48_0"
      BOOST_BUILD_PATH="%BOOST_ROOT%\tools\build\v2\engine"
3) Компилируем утилиту bjam.exe, которая потом поможет нам скомпилировать сам буст. Для этого в командной строке меняем текущий каталог на "C:\boost_1_48_0\tools\build\v2\engine", после чего компилируем bjam, вызывая из командной строки скрипт "build.bat" с параметром "mingw":
      >  build.bat  mingw
Варианты параметров запуска командного фала для других компиляторов можно найти в самом командном файле в комментариях: "Toolsets supported by this script are: borland, como, gcc, gcc-nocygwin,  intel-win32, metrowerks, mingw, msvc, vc7, vc8, vc9, vc10".
Итак, теперь в результате у нас есть папка "C:\boost_1_48_0\tools\build\v2\engine\bin.ntx86", а в ней два файла:  "b2.exe" и "bjam.exe". Скопируем их в "C:\Windows\System32". Теперь их можно вызывать из командной строки.
4) Собственно компиляция библиотек boost. Для этого в командной строке переходим в в папку "C:\boost_1_48_0", после чего выполняем команду компиляции библиотек буста:
    >  bjam --toolset=gcc link=static stage

Вот и все.

Ссылки по теме:
Mismatched versions of Boost.Build engine and core
Building Boost for static linking (MinGW)
Сборка библиотеки Boost

Подсчет количества ненулевых бит с помощью "магических чисел"

Подсчёт количества ненулевых бит в числе v за log2(v) проходов (на примере 8-битного числа):
    v = (v & 0x55) + ((v >> 1) & 0x55);
    v = (v & 0x33) + ((v >> 2) & 0x33);
    return (v & 0x0f) + ((v >> 4) & 0x0f);

Число разбивается на группы бит одной длины (сперва по одному биту). Затем значения соседних пар одновременно складываются и сохраняются в новых группах в два раза большей длины до тех пор, пока не будут сложены половинки числа.
Поскольку длина суммы двух чисел равна длине большего числа с битом для переноса, поэтому для каждой группы в маске групп достаточно иметь единиц не больше номера шага (то есть 1+log2 от длины группы). Hапример, для подсчёта единичных бит в 32-битном числе (с оптимизацией):


#define g21 0x55555555ul // = 0101_0101_0101_0101_0101_0101_0101_0101
#define g22 0x33333333ul // = 0011_0011_0011_0011_0011_0011_0011_0011
#define g23 0x0f0f0f0ful // = 0000_1111_0000_1111_0000_1111_0000_1111


v = (v & g21) + ((v >> 1) & g21);
v = (v & g22) + ((v >> 2) & g22);
v = (v + (v >> 4)) & g23;
return (v + (v >> 8) + (v >> 16) + (v >> 24)) & 0x3f;


Для сокращения количества шагов можно суммировать тройки и т.д.:

#define g31 0x49249249ul // = 0100_1001_0010_0100_1001_0010_0100_1001
#define g32 0x381c0e07ul // = 0011_1000_0001_1100_0000_1110_0000_0111


v = (v & g31) + ((v >> 1) & g31) + ((v >> 2) & g31);
v = ((v + (v >> 3)) & g32) + ((v >> 6) & g32);
return (v + (v >> 9) + (v >> 18) + (v >> 27)) & 0x3f;

Оригинальный пост (датирован 2003-м годом)  находится здесь. А у себя я его продублировал на тот случай, если вдруг что-то случится с этой веткой форума.

Крайне полезные статьи

Приведу список отличных статей, которые очень сильно помогли мне:

Перевод статьи про d-указатели (aka pimpl, чеширский кот и т.п.). Рассказано, что такое д-указатели, зачем они нужны, как их использование помогает соблюдению бинарной совместимости, как увеличивается производительность при перемещении pimpl-объектов и многое другое. Попутно рассказывается, что такое бинарная совместимость вообще, зачем она нужна и для чего в программах на C++ крайне важно в целях бинарной совместимости все детали реализации писать в cpp-файлах, оставляя в h-файлах только самый необходимый минимум объявлений.

Использование dll в Visual C++. Рассказывается, как подключать dll-библиотеки к программе. Рассматривается три способа использования библиотек: явное подключение, неявное подключение (с использованием lib-файлов) и отложенное подключение библиотек. Описывается, что такое lib-файл и для чего он нужен. Описываются особенности использования библиотечных классов, переменных и функций.

Threading without headache. Описывается, как в Qt писать многопоточные приложения без использования таких базовых примитивов, как, например, мьютексы. Если кто не читал - обязательно прочитать. Я был так впечатлен, что тут же за пару дней переделал свой проект, полностью убрав из него мьютексы. Все вызовы методов интерфейсов заменил механизмом сигналов и слотов. Можно сказать, что я вообще абстрагировался от того факта, что приложение многопоточное- за меня все делает великолепный фреймворк Qt. Описывается, зачем нужна функция moveToThread(). Также советую почитать дополнительно про отправку/прием событий QEvent - иногда вместо механизма сигналов и слотов может быть удобнее использовать сообщения. Еще советую почитать это

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

Подсчет количества битов в числе. Тут описан наиболее шаманский способ "магических чисел". Остальные способы (последовательный сдвиг и предварительный подсчет) слишком тривиальны, чтобы давать по ним ссылки.

Статья про boost::bind. Большая и полезная для понимания внутреннего устройства буста статья.

Бенчмарк оперативной памяти

Не люблю различные бенчмарки типа SiSoft Sandra и подобные за то, что у них у разных версий на одном и том же компьютере разные показатели. Как правило, у новых версий показатели выше. На одном и том же компьютере. Это ставит под сомнение фактическую ценность таких бенчмарков как источников каких-то абсолютных показателей. Да и и их ценность при сравнительном тестировании тоже весьма сомнительна - ну кто знает, что они там имеют ввиду под своими попугаями? Вот функция memcpy(), например, проста для понимания и широко используется и поэтому именно она может быть использована для измерения скорости обмена между процессором и ОЗУ. Набросал простой бенчмарк:

#include <QtCore/QCoreApplication>
#include <vector>
#include <iostream>
#include <QTime>
#include <QDebug>
#include <QThread>
 
class MemReadTestThread : public QThread {
const unsigned char * test_memory_block;
const size_t test_memory_size;
const size_t repeat_count;
const size_t buf_size;
public:
    MemReadTestThread(const unsigned char * block, const size_t size, const size_t bufsize, const size_t repeat_cnt)
        : QThread(), test_memory_block(block), test_memory_size(size), repeat_count(repeat_cnt), buf_size(bufsize)
    {
    }
    void run() {
        setPriority(HighPriority);
        std::vector<unsigned char> buf(buf_size);
 
        for(size_t n = 0; n < repeat_count; n++) {
            size_t i = 0;
            while(i + buf_size < test_memory_size) {
                memcpy(&buf[0], &test_memory_block[i], buf_size);
                i += buf_size;
            }
        }
    }
};
 
class MemWriteTestThread : public QThread {
unsigned char * test_memory_block;
const size_t test_memory_size;
const size_t repeat_count;
const size_t buf_size;
public:
    MemWriteTestThread(unsigned char * block, const size_t size, const size_t bufsize, const size_t repeat_cnt)
        : QThread(), test_memory_block(block), test_memory_size(size), buf_size(bufsize), repeat_count(repeat_cnt)
    {
    }
    void run() {
        setPriority(HighPriority);
        std::vector<unsigned char> buf(buf_size);
 
        for(size_t n = 0; n < repeat_count; n++) {
            size_t i = 0;
            while(i + buf_size < test_memory_size) {
                memcpy(&test_memory_block[i], &buf[0], buf_size);
                i += buf_size;
            }
        }
    }
};
 
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    using namespace std;
    const size_t size = 768*1024*1024;
    const size_t bufsize = 32*1024;
    vector<unsigned char> bytes1(size), bytes2(size);
    
    //засекаем время
    QTime time;
    time.restart();
    const size_t count = 10; 
    //создаем и запускаем 2 потока чтения из памяти
    MemReadTestThread rt1(&bytes1[0], bytes1.size(), bufsize, count);
    MemReadTestThread rt2(&bytes2[0], bytes2.size(), bufsize, count);
    rt1.start();
    rt2.start();
    //ждем, пока оба не завершатся
    rt1.wait();
    rt2.wait();
    //узнаем время выполнения и считаем результат
    float secs = (float) time.elapsed()/1000;
    size_t total_megabytes_copied = ((bytes1.size()+bytes2.size())/(1024*1024))*count;
    qDebug() << "********** memory read ************";
    qDebug() << "time = " << secs << " sec, copied size = " << total_megabytes_copied << " megabytes";
    float megbytes_per_sec = (float)total_megabytes_copied/secs;
    qDebug() << megbytes_per_sec << " megabytes per sec";
 
    //засекаем время
    time.restart();
    //создаем и запускаем два потока записи в память
    MemWriteTestThread wt1(&bytes1[0], bytes1.size(), bufsize, count);
    MemWriteTestThread wt2(&bytes2[0], bytes2.size(), bufsize, count);
    wt1.start();
    wt2.start();
    //ждем, пока не завершатся
    wt1.wait();
    wt2.wait();
    //узнаем время и вычисляем результат 
    secs = (float) time.elapsed()/1000;
    total_megabytes_copied = ((bytes1.size()+bytes2.size())/(1024*1024))*count;
    qDebug() << "********** memory write ************";
    qDebug() << "time = " << secs << " sec, copied size = " << total_megabytes_copied << " megabytes";
    megbytes_per_sec = (float)total_megabytes_copied/secs;
    qDebug() << megbytes_per_sec << " megabytes per sec";
 
    return a.exec();
}

Комментировать особо нечего, кроме того, почему нам нужно тестировать в двух потоках. Тут все очень интересно. Как всем известно, в современных контроллерах памяти, если есть две одинаковые (по объему и скорости) планки памяти, то есть возможность использовать двухканальный режим памяти. То есть две 64-битные планки памяти (а они имеют именно такую разрядность) как бы превращаются в одну большую 128-битную планку памяти. Соответственно,  скорость работы увеличивается в 2 раза. Этот режим называется dual ganged mode. А есть еще dual unganged mode - это тоже режим с удвоенной пропускной способностью, но контроллер памяти обращается к памяти не как к одной 128-битной планке, а как к двум планкам, каждая из которых имеет свою собственную независимую 64-битную шину. То есть можно в одну планку писать и одновременно что-то читать с другой планки памяти. При этом удвоенная скорость будет только в том случае, если тестировать две планки памяти независимо друг от друга, то есть в разных потоках. Чтобы убедиться в этом, можно эту програмку сделать однопоточной и увидеть воочию двукратное падение скорости. Разумеется, это относится только к unganged mode, т.к. ganged mode совершенно все равно, сколько потоков будет запущено - на результат это не повлияет. Трудность заключается в том, что нет уверенности, что один тестируемый массив полностью расположен в одной планке, а второй - полностью в другой планке и это может негативно повлиять на итоговый результат. С другой стороны, в реальных приложениях вряд ли кто-то будет пытаться расположить массивы данных так, чтобы они оптимальным образом были рассредоточены по двум планкам памяти, поэтому результаты работы данного простого бенчмарка, в принципе, ближе к реальности, чем в идеальном случае. А результаты у меня такие:

Это материнская плата MSI 760GM-P33 на чипсете 760G и процессор AMD X4 640 и две планки памяти DDR3-1333 по 2 гигабайта.

Работа с регулярными выражениями в std::tr1

TR1 - крайне полезное расширение STL, и, что самое важное, есть во многих компиляторах.

Допустим, нам нужно распарсить строку с диапазонами страниц для печати, разделенными запятыми. Строка типа "1, 2, 4-7, 10". Первое, что пришло в голову:

using namespace std;
string str = "  1 , 2, 4 , 3 - 7 , 9 - 11";
//отдельная цифра может быть окружена пробелами со всех сторон
const string numb = "[\\s]*[0-9]+[\\s]*";
//диапазон -это либо одна цифра, либо две цифрыЮ разделенные тире
const string diapason = numb + "(\\-" + numb + "){0,1}";
const std::tr1::regex regex_diap(diapason);
//выводим все подстроки, соответствующие паттерну
const tr1::sregex_token_iterator end;
tr1::sregex_token_iterator iter = tr1::sregex_token_iterator(str.begin(), str.end(), regex_diap);
for (; iter != end; ++iter)
    std::cout << *iter << std::endl;

В результате программа выведет:
1
2
4
7 - 3
8 - 11

Все хорошо до тех пор, пока мы не попробуем вместо правильной строки ввести, например, такую неправильную строку: " 1 , 2, 4 , 3aaa - 7 , 9 - 11". В этом случае программа выведет следующее:
1
2
4
3
7
9 - 11

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

using namespace std;
//входная строка
string str = "  1 , 2, 4 , 5 - 7, 9 - 11";
//целое число, которое может быть обрамлено пробельными символами
const string numb = "[\\s]*[0-9]+[\\s]*";
//вот тут мы используем т.н. просмотр вперёд и назад
const string one_page = "(?<=(,|^))" + numb + "(?=(,|$))";
const string many_page = "(?<=(,|^))" + numb + "\\-" + numb + "(?=(,|$))";
//число или диапазон
const string one_many_page = "(" + one_page + "|" + many_page + ")";
const tr1::regex rx(one_many_page);
const tr1::sregex_token_iterator end;
tr1::sregex_token_iterator it;
for (it = tr1::sregex_token_iterator(str.begin(), str.end(), rx); it != end; ++it)
    std::cout << *it << std::endl;

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

const string numb = "[\\s]*[0-9]+[\\s]*";
const string one_page = "(?<=(,|^))" + numb + "(?=(,|$))";
 

Аналогично с диапазоном чисел:

const string numb = "[\\s]*[0-9]+[\\s]*";
сonst string many_page = "(?<=(,|^))" + numb + "\\-" + numb + "(?=(,|$))";
 

Ну и регулярное выражение, которое выбирает ИЛИ число ИЛИ диапазон:

const string one_many_page = "(" + one_page + "|" + many_page + ")";
 

Теперь, если указать неверный диапазон чисел типа " 1 , 2, 4 , 7aaa - 3, 8 - 11", то на выходе получим:
1
2
4
8 - 11

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

Для подсветки синтаксиса использовал highlight.hohli.com

"Черная магия" гугловских программистов

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

int XX[] = { 1, 2, 3, 4 };
size_t N = sizeof(XX) / sizeof(XX[0]);

Обычно это оформляют в макрос следующего вида:

#define count_of(arg) (sizeof(arg) / sizeof(arg[0]))

Однако он может послужить причиной ошибки, так как ему случайно можно подсунуть простой указатель, и он не будет возражать по этому поводу:

void Test(int C[3])
{
  int A[3];
  int *B = Foo();
  size_t x = count_of( A ); // Ok
  x = count_of( B ); // Error
  x = count_of( C ); // Error
}

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

template <typename T, size_t N>
char (&ArraySizeHelper(T (&array)[N]))[N];
#define arraysize(array) (sizeof(ArraySizeHelper(array))) 

Объяснено на хабре было плохо (ну для меня по крайней мере), потом нашел другое объяснение, где уже было немного понятнее.
К моему позору, я начисто забыл, как в С++ выглядит прототип функции, возвращающей ссылку на массив. А выглядит он, например, так:

int (&get_array())[10];

Это прототип функции, возвращающей ссылку на массив из 10 интов. Такой способ определения ссылки на массив из N элементов - это наследие C. Выглядит точно так же, как и определение указателя на массив, достаточно "&" заменить на "*".
Далее все очень просто:

template <typename T, size_t N> char (&ArraySizeHelper(T (&array)[N]))[N];

- это шаблонизированный прототип функции, принимающей ссылку на массив произвольного типа T из N элементов и возвращающий ссылку на массив типа char из N элементов. Очевидно, что char потому, что число элементов в массиве в этом случае равно количеству байт, занимаемым массовом. Смысл шаблона функции именно в том, что размер массива "магически" передается сразу на выход функции, фактически определяя тип возвращаемого значения (а конкретно размер) во время компиляции. То есть, фактически, саму функцию определять не надо - достаточно только ее прототипа. А он будет сгененерирован во время компиляции. То, что функция реально не вызывается, вызвало у меня некое недопонимание. Однако именно так дело и обстоит. Такова особенность работы функции sizeof() - ей достаточно знать только тип вычисляемого выражения. А он известен на этапе компиляции. То есть нет необходимости вызывать саму функцию. А значит, нет необходимости и ее реализовывать - достаточно только объявления. Почитав немного Александреску, такие фокусы воспринимать уже гораздо легче и привычнее.Чтобы было понятнее, лучше всего привести пару примеров. У нас определен такой массив:

const int arr_size = 10;

const int int_arr[arr_size]; 

Теперь, если раскрыть шаблон ArraySizeHelper для него, то мы получим такое определение функции:

char (&ArraySizeHelper(int (&array)[10]))[10]; 

То есть прототип функции, получающей параметром ссылку на массив из 10 целых чисел и возвращающую ссылку на массив из 10 char. Естественно, что sizeof() для массива из 10 элементов типа char вернет 10.

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

template <typename T, size_t N>
char (&ArraySizeHelper(T (&array)[N]))[N];
#define arraysize(array) (sizeof(ArraySizeHelper(array)))
 
void Test(int C[3])
{
  int A[3];
  int *B = Foo();
  size_t x = arraysize( A ); // Ok
  x = arraysize( B ); // Ошибка компиляции
  x = arraysize( C ); // Ошибка компиляции
}

P.S.
Для подсветки синтаксиса использовал highlight.hohli.com

Boost spirit

Использование boost::spirit - Очень интересный способ парсинга строк. Приведу краткий пример:

#include <string>
#include <map>
#include <iostream>

#include <boost/spirit/core.hpp>
#include <boost/spirit/actor/assign_actor.hpp>
#include <boost/spirit/actor/insert_at_actor.hpp>
#include <algorithm>

using namespace boost::spirit;

bool parseConfig( const char * str, std::map<std::string,std::string> & mp ) {
    mp.clear();
    std::string key;

    return parse(str,
        ((lexeme_d[+alnum_p][assign_a(key)] >> '=' >> lexeme_d[+alnum_p][insert_at_a(mp,key)]) % ','),
        space_p
    ).full;
}

void show_elem(const std::pair<std::string,std::string> & pair) {
    std::cout << pair.first << " = " << pair.second << std::endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::map<std::string,std::string> map;

    std::cout << parseConfig(" key1=val1, key2=val2, param=param_val ", map) << std::endl;
    std::for_each(map.begin(), map.end(), show_elem);

    return 0;
}


Colored with dumpz.org

Пример будет дополняться объяснениями.

Очень хорошо объяснено тут:
http://blog.alno.name/ru/2008/09/parsers-in-cpp-with-boost-spirit