пятница, 2 марта 2012 г.

Любоыптное поведение константной ссылки в C++

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

class SomeClass {
public:
    SomeClass(const std::string & name)  
      : obj_name(name)  
    { 
       std::cout << "object \"" << obj_name.c_str() << "\" created" << std::endl; 
    }
    ~SomeClass()  
    { 
       std::cout << "object \"" << obj_name.c_str() << "\" destroyed" << std::endl;  
    }
private:
    std::string obj_name;
};
SomeClass get_some_class_heap() {
    return *(new SomeClass("HeapObjectFromFunc"));
}
SomeClass get_some_class_val() {
    return SomeClass("ValueObjFromFunc");
}
void test_const_ref_func() {     
    const SomeClass & value_obj_from_func_ref(get_some_class_val()); // 1    
    const SomeClass & heap_obj_from_func_ref(get_some_class_heap()); // 2    
    const SomeClass & heap_obj_ref(*(new SomeClass("HeapObj"))); // 3   
    // 
    std::cout << "end of const_ref_func()" << std::endl;
}
int main(int argc, char *argv[])
{  
 
    test_const_ref_func();
 
}

Получаем вот такой вот вывод:

object "HeapObjectFromFunc" created
object "ValueObjFromFunc" created
object "HeapObj" created
end of const_ref_func()
object "ValueObjFromFunc" destroyed
object "HeapObjectFromFunc" destroyed

 
Первый случай - все понятно: константная ссылка получает временный value-объект и "держит" его, не давая ему умереть, пока сама не выйдет за пределы области видимости функции test_const_ref_func().
Второй случай - то же самое, но возвращается ссылка не на value-объект, а на объект, созданный в куче. Казалось бы - вот они, умные указатели! Но... см.третий случай.
Третий случай - умный указатель получает ссылку на тут же динамически созданный объект. Разумеется, он не удаляет объект после того, как выходит за пределы видимости. Если бы было иначе - отладка программ на C++ была бы еще более непредсказуемой и сложной задачей, чем даже сейчас. И, кстати, поведение компилятора в этом плане во втором случае тоже вызывает много вопросов.
 
 

среда, 29 февраля 2012 г.

Бьярн страуструп про необходимость сборщика мусора в C++

Прочитал статью на хабре про недавнюю конференцию по C++11 - новому стандарту языка C++. Бьярн Страуструп очень тонко прошелся по всем языкам с автоматическим управлением памятью:
“But I think that Garbage Collection is not as critical for C++ as it is for many of the other languages. We just don’t generate that much garbage”

Что в вольном изложении можно перевести  так: "Мы не так много срем, чтобы нам понадобился сборщик мусора".

воскресенье, 15 января 2012 г.

Компилирование библиотек 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

четверг, 5 января 2012 г.

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

Подсчёт количества ненулевых бит в числе 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. Большая и полезная для понимания внутреннего устройства буста статья.

пятница, 30 сентября 2011 г.

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

Не люблю различные бенчмарки типа 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 гигабайта.

понедельник, 6 июня 2011 г.

Работа с регулярными выражениями в 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