Code @ C++

Ubuntu 9.10 fast review

2009-11-05T21:10:00.006+03:00

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

Окно микшера сделали симпатичнее, чем было, но посмотрел я туда не из любопытства, а потому что не заработал звук через S/PDIF->HDMI. Пока не ясно как это чинить.

Зачем-то установился Network Manager, который написал, что не может управлять моими сетями. Оно и к лучшему — сеть работала отлично, как и раньше.

Попробовал новый официальный клиент обмена сообщениями Empathy. Аккаунт импортировался из Pidgin без проблем, но сообщения приходили в неправильной кодировке. Разбираться стало лень, поэтому пока остается Pidgin.

Ожидаемо порадовало наличие gcc версии 4.4.1. На этом пока все и закончилось, т.к. остальное работает без замечаний и без заметных нововведений.

Deleting incomplete type

2009-10-23T14:26:00.002+04:00

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

Дело в том, что стандарт в части 5.3.5/5 разрешает удаление объектов неполностью определенных типов:

If the object being deleted has incomplete class type at the point of deletion and the complete class has a non-trivial destructor or a deallocation function, the behavior is undefined.

Продемонстрировать проблему можно на следующем простом примере:

struct X; // неполностью определенный тип (определяется позднее)

int main()
{
 X* x = 0;
 delete x; // стандарт разрешает это

 return 0;
}

struct X
{
private:
 ~X() {}; // private destructor
};

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

Useful templates

2009-10-23T12:00:00.000+04:00

В дополнение к предыдущему сообщению ещё пара полезных шаблонов:

//Безопасное удаление
template<typename T>
inline void SafeDelete( T*& p )
{
  // Проверка, что тип полностью определен
  typedef char type_must_be_complete[ sizeof(T)? 1: -1 ];
  (void) sizeof(type_must_be_complete);
  // проверять p на равенство нулю не нужно, т.к. стандарт 
  // гарантирует корректную работу delete
  delete p;
  p = NULL;
}

Если нет запрета на использование boost, то лучше использовать boost::checked_delete.

// Безопасное удаление через Release
template<typename T, typename D>
inline void SafeRelease( T*& p, D d ) 
{ 
  if ( p != NULL ) {
    (p->*d)();
    p = NULL;
  }
}
template<typename T>
inline void SafeRelease( T*& p) 
{ 
  return SafeRelease( p, &T::Release );
}

UPD:22окт добавлена проверка на то, что тип является полностью определенным.

Portable way to shut up compiler warning

2009-10-19T14:14:00.008+04:00

Совсем недавно Герб Саттер (Herb Sutter) привел пример портируемого способа запретить вывод предупреждений компилятора о неиспользуемых переменных. Широко используемый способ — определить макрос следующего вида:

#define UNUSED(x) x

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

template<class T> void ignore( T& ) { }

Можно это определение поместить в неймспейс для избежания конфликтов, чего нельзя сделать с макросом. Следует отметить, что параметр функции ignore<T> следует оставить без имени, чтобы не получить предупреждение теперь уже в другом месте.

Использовать шаблонную функцию довольно просто:

static void Constraints(D* p)
{
  B* pb = p;
  ignore(pb); // portably suppresses the warning
}

От себя хотел бы дополнить, что лучше писать так:

template<class T> void ignore( const T& ) { }

Это необходимо по причинам, которые обсуждались на stackoverflow.com.
UPD:Саттер услышал замечание насчет const и обновил свое сообщение.

Do not use & for arrays

2009-10-18T20:21:00.003+04:00

Представьте, что вам попался код следующего вида:

typedef unsigned char Str255[257];
Str255 Blah;

void f( Str255 s )
{
  memcpy(&Blah, &s, sizeof(Str255)); // error here
}

int main()
{
  Str255 x("Blah");
  f( x );
}

Вопрос в том, почему данный код будет работать неверно, т.е. в Blah будет скопировано не содержимое x, а непонятный мусор? Ошибка тут в том, что в memcpy не нужно использовать &, а писать memcpy(Blah, s, sizeof(Str255));. Потому что s и &s — это разные указатели, и они даже имеют разный тип: unsigned char * and unsigned char (*)[257] соответсвенно. Обычно указатель на первый элемент массива и указатель на массив — это одно и тоже, но в нашем случае это не так. Посмотри как выглядит функция f, если не использовать typedef:

void f( unsigned char* s )
{
  memcpy(&Blah, &s, sizeof(Str255)); // error here
}

При вызове этой функции, в соответсвии с пунктом 4.2 стандарта C++, массив будет неявно преобразован в указатель и мы получим, что s указывает на массив с текстом, но &s будет указывать на указатель, который хранится на стеке, т.е. при копировании мы получим содержимое стека в Blah. Чтобы избежать такого недоразумения лучше использовать std::string в C++, ну а в C просто не использовать typedef для строк и понимать что происходит.

Best font for programming

2009-10-09T22:30:00.003+04:00

Наверное, многие уже слышали о шрифте Consolas. Его особенность в том, что он был разработан с нуля для использования всех преимуществ ClearType. Другие моноширинные шрифты сглаживаются операционной системой и, как правило, смотрятся размыленно со включенным ClearType. Шрифт совершенно бесплатный и может быть скачан тут.

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

Consolas, 10pt:

Lucida Console, 9pt:

Шкриншоты позаимствованы с www.codinghorror.com.

Determining 32 vs 64 bit in C++

2009-10-02T11:59:00.004+04:00

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

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

template<int> void DoMyOperation();

template<> void DoMyOperation<4>() 
{
  // do 32-bits operations
}

template<> void DoMyOperation<8>() 
{
  // do 64-bits operations
}

int main()
{
  // appropriate function will be selected at compile time 
  DoMyOperation<sizeof(size_t)>(); 

  return 0;
}

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

Microsoft Innovation Day осень 2009

2009-09-30T21:10:00.007+04:00

Вчера прошел традиционный форум компаний разработчиков Microsoft Innovation Day. На этот раз веб-разработчиков выделили в отдельную секцию, поэтому секций было три. Я посетил техническую.

На технической секции немного рассказали о том, что Windows 7 выходит, но так как об этом и так все знают, то особенно на это не задерживались. Упомянули только, что есть Platform Update для Windows XP и Windows Vista, который добавляет некоторые возможности новой ОС (подробнее...).

Очень поверхностно рассказали о новых продуктах семейства Office 2010, а также SQL Server 2008 R2. В Office ожидается веб варианты компонентов офиса как аналог Google Docs, но доступны они будут через корпоративный Share Point сервер, что и понятно — все-таки они не бесплатные. Это видится как очередной шаг к сервисам в облаке.

В SQL Server 2008 R2 интерес представляет новая технология StreamInsight. Но о ней рассказали не очень подробно и понятно (я так и не понял, можно ли будет хранить видео в БД), однако есть первоисточник где можно почитать об этом подробнее.

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

В конце показали ролик с представлением Microsoft о будущем Office 2019:

Судя по видео у нас в 2019 году будут не whiteboards, а transparentboards, что не очень удобно на мой взгляд :)

integer types

2009-09-18T15:54:00.005+04:00

Стандарт C'99 ISO подразумевает наличие файла stdint.h с определением типов, которые полезны для портируемых программ или описания форматов сетевых пакетов (типы вроде uint8_t и int64_t и так далее...). Поскольку Visual C++ 2008 не поддерживает полностью стандарт С99, то там этого файла нет. Если же пользоваться этими типами хочется, то можно использовать портируемую версию этого хедера — pstdint.h, которая распространяется под BSD лицензией, т.е. даром.

Официальный блог - Google Россия: Объявляем о начале регистрации заявок на участие в Google Developer Day 2009 в Москве

2009-09-17T11:26:00.000+04:00

Официальный блог - Google Россия: Объявляем о начале регистрации заявок на участие в Google Developer Day 2009 в Москве

boost 1.40

2009-08-28T22:45:00.002+04:00

Тихо и незаметно вчера вышла очередная версия библиотеки boost. Список изменений небольшой, в основном затронута библиотека Asio.

Changing wallpaper on Linux programmatically

2009-08-28T21:55:00.007+04:00

Для тех, кто хочет начать работать с GNOME, но не знает с чего начать, вот задачка — поменять обои рабочего стола. Это я так пытаюсь подойти к проблеме поддержки разных обоев для двух мониторов (точнее, монитора и HD телевизора в моем случае). В KDE с этим проблем нет, но в GNOME такой настройки нет. Оказалось, что сделать это несложно. Проблемой я собирался заняться давно, но преодолеть лень и написать код меня сподвигнул этот вопрос.

Нам понадобятся: Ubuntu, любимый текстовый редактор, пакет build-essentials, libglib-2.0-dev, libgconf2-dev и консоль. Думаю, что ставить пакеты все умеют (кто не умеет — читать тут).

В текстовом редакторе создаем файл следующего содержания:

// bkgmanage.c
#include <glib.h>
#include <gconf/gconf-client.h>
#include <stdio.h>

typedef enum {
    WALLPAPER_ALIGN_TILED     = 0,
    WALLPAPER_ALIGN_CENTERED  = 1,
    WALLPAPER_ALIGN_STRETCHED = 2,
    WALLPAPER_ALIGN_SCALED    = 3,
    WALLPAPER_NONE            = 4
} WallpaperAlign;

gboolean set_as_wallpaper( const gchar *image_path, WallpaperAlign align )
{
    GConfClient *client;
    char        *options = "none";

    client = gconf_client_get_default();

    // TODO: проверить, что image_path является файлом и вообще существует
    if ( image_path == NULL ) options = "none";
    else {
        gconf_client_set_string( client, 
            "/desktop/gnome/background/picture_filename",
            image_path,
            NULL );
        switch ( align ) {
            case WALLPAPER_ALIGN_TILED: options = "wallpaper"; break;
            case WALLPAPER_ALIGN_CENTERED: options = "centered"; break;
            case WALLPAPER_ALIGN_STRETCHED: options = "stretched"; break;
            case WALLPAPER_ALIGN_SCALED: options = "scaled"; break;
            case WALLPAPER_NONE: options = "none"; break;
        }
    }
    gboolean result = gconf_client_set_string( client, 
        "/desktop/gnome/background/picture_options", 
        options,
        NULL);
    g_object_unref( G_OBJECT(client) );

    return result;
}

int main(int argc, const char* argv[])
{
  if ( argc > 1 ) {
    printf( "Setting %s as wallpaper... ", argv[1] );
    if ( set_as_wallpaper( argv[1], WALLPAPER_ALIGN_STRETCHED ) ) printf( "Ok\n" );
    else printf( "Failed\n" );
  } else printf( "Usage: ./bkgmanage <filename>\n" );

  return 0;
}

gconf — это библиотека для управлением аналогом реестра в GNOME. С помощью неё и исправляется параметр /desktop/gnome/background/picture_filename для замены картинки, а также /desktop/gnome/background/picture_options для определения параметров отображения этой картинки. Изменения вступают в силу мгновенно.

Сборка указанного выше файла тоже не составляет труда. Достаточно в консоли ввести:

gcc -Wall -g `pkg-config --libs --cflags glib-2.0 gconf-2.0` bkgmanage.c -o bkgmanage

Тут pkg-config возвращает все необходимые пути к include-файлам и библиотеки, необходимые для линковки, что очень удобно. В результате получается исполняемый файл bkgmanage.

Далее, остается сделать GUI для удобного выбора картинок для каждого монитора с последующей склейкой в один файл. Пока не решил какой фреймворк для этого выбрать — основная идея, что хочется писать на С++, но Qt имеет слишком много зависимостей, которые в GNOME по умолчанию отсутствуют...

Trigraph sequences in C++

2009-08-06T10:06:00.004+04:00

C++ стандарт в части 2.3/1 утверждает, что перед началом любой обработки кода все вхождения трех символов, указанных в таблице, будут заменены на один соответствующий символ.

----------------------------------------------------------------------------
| trigraph | replacement | trigraph | replacement | trigraph | replacement |
----------------------------------------------------------------------------
| ??=      | #           | ??(      | [           | ??<      | {           |
| ??/      | \           | ??)      | ]           | ??>      | }           |
| ??’      | ˆ           | ??!      | |           | ??-      | ˜            |
----------------------------------------------------------------------------

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

printf( "What??!\n" )

Выдаст пользователю такой текст:

What|

Помимо этого есть такая же таблица для пар символов, которая делает следующий код вполне корректной программой на С++:

%:include <stdio.h>

%:ifndef BUFSIZE
 %:define BUFSIZE  512
%:endif

void copy(char d<::>, const char s<::>, int len)
<%
    while (len-- >= 0)
    <%
        d<:len:> = s<:len:>;
    %>
%>

Стандарт поддерживает эти символы для совместимости, т.к. на очень старом железе в Европе не было части символов. Интересно, что в будущем стандарте С+x0 было предложено отказаться от поддержки триграфов, однако, этого видимо не произойдет. Подробнее тут.

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

работаем с Windows Registry

2009-07-13T00:45:00.002+04:00

Для восстановления веток реестра в Windows существует функция RegRestoreKey. До Windows Vista ей можно было свободно пользоваться для восстановления, например, настроек по умолчанию программы. В Windows Vista это стало требовать поднятия уровня процесса(elevation) с появлением назойливого диалога UAC. Конечно, понятно, что большинство читающих эту статью живут с отключенным UAC, но подавляющее большинство обычных пользователей(по данным Microsoft) UAC не выключают. У RegRestoreKey есть ещё один недостаток — она работает с файлами в бинарном формате, который отличается для каждой новой версии ОС.

Однако, существует в Windows и программа reg.exe, которая имеет встроенный парсер REG-фалов. Да, именно тех, которые описывают ключи в обычном тектовом формате. Команды import и export этой утилиты не требуют каких либо повышенных прав. Конечно, здесь речь идет о разделах HKCU. Почему эти функции не выделили в отдельный API остается загадкой.

Ниже приведен пример использования этой утилиты в программе:

// Получаем указатель на REG файл прилинковынный в ресурсы
HRSRC hRsrc = ::FindResource( NULL, MAKEINTRESOURCE(IDR_DEFSETTINGS), L"REG" ); // IDR_DEFSETTINGS - идентификатор ресурса с файлом. Может быть другим.
HGLOBAL hGlobal = ::LoadResource( NULL, hRsrc );
LPVOID lpReg = ::LockResource( hGlobal );

// Сохраняем во временный файл
wchar_t path_buf[MAX_PATH];
SHGetFolderPath( NULL, CSIDL_APPDATA, NULL, SHGFP_TYPE_CURRENT, &path_buf[0] );
const wstring temp_filename = path_buf+L"\\temp_reg.reg";
ofstream os( temp_filename.c_str(), ios_base::binary );
os.write( static_cast<char*>(lpReg), ::SizeofResource( NULL, hRsrc ) );
os.close();

// Готовим параметры reg.exe.
wstring params( L"import \"");
params += temp_filename;
params += L"\""; // Путь к файлу должен быть в кавычках на случай пробелов

// Запускаем reg.exe
SHELLEXECUTEINFO se = {0};
se.cbSize = sizeof SHELLEXECUTEINFO;
se.fMask = SEE_MASK_NOCLOSEPROCESS|SEE_MASK_UNICODE;
se.hwnd = GetSafeHwnd();
se.lpFile = L"reg.exe"; // находится в system32, поэтому путь указывать необязательно
se.lpParameters = params.c_str();
se.nShow = SW_HIDE; // Смотреть на консольку пользователю ни к чему
if ( ShellExecuteEx( &se ) ) {
  WaitForSingleObject( se.hProcess, INFINITE ); // хотя тут и написано INFINITE, но в реальной жизни лучше указать таймаут
  CloseHandle( se.hProcess );
} else {
 // Ошибка запуска. Как-то обрабатываем эту ситуацию.
}

// Удаляем временный файл
_wremove( temp_filename.c_str() );

Windows Intenals 5-th

2009-07-07T10:25:00.002+04:00

Наконец-то вышло пятое издание Windows Internals и уже почтальон везет его ко мне :) Книга потолстела на 250 страниц, как пишет Марк Руссинович(Mark Russinovich) у себя в блоге. Были добавлены главы посвященные Hyper-V, Kernel Transaction Manager, Code Integrity, Thread Pools, Mandatory Integrity Controls, Windows Driver Framework и ещё немного об утилитах SysInternals. До конца года обещается 6-е издание, которое пополнеет ещё на 100 страниц и будет содержать информацию специфичную для Windows 7 и Windows Server 2008 R2.

hex to long

2009-07-02T10:27:00.002+04:00

Как думаете, чем конвертировать шестнадцатиричную строку в 32-х битное знаковое целое? Порывшись в стандарной библиотеке можно найти функцию strtol. И все работает обычно... до тех пор пока входные данные беззнаковые. Попробуйте конвертировать -1 (0xFFFFFFFF) и ничего не выйдет. strtol решит, что было переполнение и вернет MAX_LONG. Чтобы обойти эту особенность, следует использовать функцию strtoul. Она конвертит строку в беззнаковое целое, а уж потом можно его приравнять к long и старший бит укажет знак.

Пример:

#include <cstdlib>
#include <iostream>
using namespace std;

int main() { 
 string s = "FFFFFFFF";
 char * p;
 long n = strtoul( s.c_str(), &p, 16 ); 
 // overflow when using long n = strtol( s.c_str(), &p, 16 ); 
 if ( * p != 0 ) {  
  cout << "not a number" << endl;  
 }    else {  
  cout << n << endl; // prints -1
 }
}

7 (Seven)

2009-06-25T23:11:00.005+04:00

Был сегодня в Microsoft'е. Из интересного — сертификация под Windows 7 теперь бесплатна. Как получить лого за один день(при должном упорстве) можно посмотреть тут.

Еще выдали интересные книжки «Обеспечение совместимости приложений с Windows 7 — пособие для разработчиков» (PDF версия) и «Обеспечение совместимости приложений в Microsoft Windows Vista и Windows 7 — Руководство для IT-специалистов» (PDF версия).

По мелочам: VS2010 Beta 2 выйдет до конца года, а Windows 7 уже проходит сертификацию в силовых ведомствах.

Немного ссылок

2009-06-24T20:47:00.003+04:00

Не все программисты умеют рисовать. Для них существует www.iconfinder.net. Большинство иконок там используют лицензии GPL, LGPL, CC или Free. Можно задать поиск по ключевым словам и размерам.

Ещё можно искать картинки похожие на те, что где-то увидели. На сайте tineye.com можно загрузить свою картинку и найти похожие с лучшим качеством. Похоже, что поиск работает.

Семинар Microsoft

2009-06-20T18:41:00.002+04:00

Microsoft проводит последний(до выхода Windows 7) однодневный семинар посвященный обсуждению вопросов обеспечения совместимости приложений. Семинар пройдет в Москве 25-го июня. По ссылке можно ещё успеть зарегистрироваться.

x or X and stackoverflow.com

2009-06-20T18:33:00.003+04:00

Некоторое время назад я писал о том как можно проверить наличие той или иной переменной в структуре или классе. Оказалось, что оба описанных метода некорректны с точки зрения стандарта. Решение было получено на страницах сайта stackoverflow.com, который был организован Джоелом Спольски(Joel Spolsky) и Джефом Атвудом(Jeff Atwood). Само решение можно посмотреть тут.

Рекомендую обращаться к страницам указанного сайта тем, кто этого ещё не делает. Там бывают интересные вопросы и ответы.

Хозяйке на заметку

2009-06-09T21:27:00.002+04:00

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

Для целей отладки интересен флаг PAGE_NOACCESS. Он позволяет ловить запись или, что более важно, чтение за пределами некоторой валидной области памяти. Для удобного применения VirtualProtect был создан следующий класс:

struct protect_mem_t {
    protect_mem_t( void* addr, size_t size ) : addr(addr), size(size), is_protected(FALSE) { 
        protect(); 
    }
    ~protect_mem_t() { release(); }
    BOOL protect() { 
        if ( !is_protected ) {
            is_protected = VirtualProtect( addr, size, PAGE_NOACCESS, &old_protect );
        }
 return is_protected;
    }
    BOOL release() { 
        if ( is_protected ) 
            is_protected = !VirtualProtect( addr, size, old_protect, &old_protect );
 return !is_protected;
    }
    
protected:
    void*   addr;
    size_t  size;
    BOOL    is_protected;
    DWORD   old_protect;
};

Применять его можно следующим образом:

const size_t PAGE_SIZE = 4096;

int main()
{
 const size_t var_size = 1024*96; // 1024*96 - некоторый размер. Конкретное значение здесь только в качестве примера.
 const size_t guard_size = PAGE_SIZE*2-var_size%PAGE_SIZE;
 __declspec(align(4096)) char some_var[var_size+guard_size];
 protect_mem_t guard( &some_var[var_size], PAGE_SIZE );

 some_var[5] = 20;   // that's ok
 char x = some_var[5];   // that's ok
 
 char y = some_var[1024*96+1024]; // access violation

 return 0;
}

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

Бывет и такое...

2009-05-29T21:24:00.003+04:00

Казалось бы проблемы из-за сравнения знаковых и беззнаковых значений давно известны и обходятся опытными разработчиками. Однако, разработчики компилятора Microsoft C++, который входит в состав Visual Studio 2008 SP1 сделали такую ошибку, которая и была (не без удивления) обнаружена у нас в компании. Код, который позволяет воспроизвести эту ошибку приведен ниже:

#include <iostream>
using namespace std;

int main()
{
 for ( int k = -4; k < -1; k++ ) {
  unsigned long kkk = (k+4)*8+1;
  bool jjj = kkk < 256;
  if ( jjj == false ) cout << "Impossible!!!" << endl;
 }
}

Если скомпилировать такой код с ключом /O2(cl /EHsc /O2 main.cpp), то будет выведен текст, который не должен быть выведен. Если без ключа оптимизации(cl /EHsc main.cpp), то текст не будет выведен.

Проблема тут в том, что компилятор оптимизурет выражение (k+4)*8+1 < 256 до k < 28, забывая что k может принимать отрицательные значения и результат сравнения проверяет командой, которая знак не учитывает.

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

ordered_unique vs hashed_unique

2009-05-22T23:22:00.009+04:00

Контейнер multi_index библиотеки boost поддерживает несколько типов индексов. Среди них есть два очень похожих — ordered index и hashed index. Разница ясна из названия, hashed index не гарантирует какого-либо порядка сортировки, что, по идее, делает его несколько быстрее. Именно это и утверждается в документации: «they provide much faster lookup of elements, at the expense of losing sorting information». Что означает «much faster» далее не раскрывается.

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

struct container_t {
    complex_elem_t      hashed_index;
    complex_elem_t      ordered_index;

    explicit container_t() : hashed_index(), ordered_index() {};
};

Тип complex_elem_t введен для простой генерации уникальных элементов. Этот класс состоит из 5-ти полей типа short int, что позволило сгенерировать 10 млн. элементов без коллизий. В нем присутствуют операторы == и <. Также пришлось создать функцию hash_value, т.к. boost не умеет считать хэш для таких сложных структур.

Тип контейнера имеет следующий вид:

typedef multi_index_container<
  container_t,
    indexed_by<
      hashed_unique< member<container_t, complex_elem_t, &container_t::hashed_index> >,
      ordered_unique< member<container_t, complex_elem_t, &container_t::ordered_index> > >
  > containers_t;

В своих тестах я заполнял контейнеры элементами количеством от 1 до 10млн. штук. Для каждого производилось несколько поисков и результат усреднялся. Для замеров времени использовалась инструкция процессора rdtsc. Полностью тестовую программу можно скачать тут. Для построения графиков использовался OpenOffice.

На графиках видно, что поиск в ordered index происходит за логарифм, а в hashed index за константу. По X показан размер контейнера, по Y — нормированное количество тактов процессора (измерения проводились на Core2Duo E6420).

Так что, если какой-либо порядок элементов не требуется, то имеет смысл использовать hashed индекс, вместо ordered.

UPD: В первый раз не учитывались коллизии при вставке элементов и, поэтому, старый график был верен только до отметки в ~180 элементов из-за парадокса дней рождения.

Мир IT кардинально меняется?

2009-05-17T15:54:00.004+04:00

В ответ на вопрос Олега о том, что "Мир IT кардинально меняется."

Мы разрабатываем системы безопасности. На первый взгляд - это, как правило, изолированное решение на промышленных серверах и никаких "облаков". Однако, мы уже рассматривали возможность работы в Windows Azure, поэтому далее речь об облаках от Microsoft.

Уже сейчас можно отметить несколько моментов:
1. Дата центров в России с такой ОС пока нет. Постройка самого дата центра стоит половину миллиарда долларов. Всего дата центров у Микрософт около 20 и новых они вроде пока не планируют строить. А при повсеместном переходе "в облака" дата центров нужно будет очень много. Все это займет явно больше 5 лет.
2. Цена интернета должна быть сопоставима с ценой электричества. Ну все к этому идет, правда не только со стороны уменьшения цены интернета.
3. Цена аренды сервиса должна быть очень низкой. Объявленная Микрософтом оказалось предварительно вполне приемлемой.

Первый пункт самый нереалистичный. Несмотря не него, мы уже движемся в сторону "облачных" вычислений и, когда они будут реальны, мы будем готовы. Имеется ввиду, что вся предварительная обработка первичных данных будет идти на специализированном железе, которое работает без ОС или с Embedded версиями. А пост обработка может производится "в облаке", что позволит сократить траты на обслуживание и расширение вычислительных центров. И поддержка готового продукта будет проще без сомнений. Аналогичная схема подойдет для большинства IT-проектов. Распространение "облаков" для IT-компаний видится вовсе не плохим трендом, кроме тех, которые продают вторичные услуги.

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

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

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

А с C++ ничего плохого не случится. Уже сейчас Microsoft продолжила развитие MFC и планирует развивать его в Windows 7. И в Azure он тоже никуда не денется. Т.е. от идеи повсеместного перехода на C# отказались. Ну и сам С++ не стоит на месте. А разработчика остается развиваться вместе с технологиями и все будет в порядке.

Другие стороны boost::format

2009-05-06T00:15:00.004+04:00

Библиотека boost::format предоставляет удобный и безопасный(по сравнению с printf) способ форматирования строк. Возможен как классический printf-стиль:

cout << format("writing %s,  x=%s : %d-th step \n") % "toto" % 40.23 % 50;

Так и другие, более гибкие способы форматирования, как, например, такой:

cout << format("%1% %2% %3% %2% %1% \n") % "11" % "22" % "333"; // 'simple' style.

Самая очевидная проблема с printf — это то, что мы должны точно указать размер каждого аргумента. Например, для time_t в одних случаях писать %I64d, а в других %d. У time_t разный размер может быть и на 32-х битной платформе в зависимости от компилятора. И это только один пример. С boost::format такие проблемы исключаются.

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

string msg = str( boost::format("Debug message %s") % some_msg_string );
log( msg );

вот такую строку:

log("Debug message %s") % some_msg_string;

Добиться этого не сложно. Нужно, всего лишь, перегрузить оператор %. Для этого создадим класс formatted_log_t. А ещё функцию log, которая возвращает экземпляр этого класса. Класс будет содержать в себе экземпляр boost::format.

#include <sstream>
#include <boost/format.hpp>
#include <iostream>
using namespace std;

class formatted_log_t {
public:
    formatted_log_t(const wchar_t* msg ) : fmt(msg) {}
    ~formatted_log_t() { wcout << fmt << endl; }
    
    template <typename T>
    formatted_log_t& operator %(T value) {
        fmt % value;
        return *this;
    }

protected:
    boost::wformat                fmt;
};

Оператор % должен быть шаблонным так как мы не знаем типы форматируемых аргументов. Функция log будет иметь следующий вид:

formatted_log_t log(const wchar_t* msg)
{
    return formatted_log_t( msg );
}

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

#include <sstream>
#include <boost/format.hpp>
#include <iostream>
using namespace std;

enum log_level_t {
    LOG_NOTHING,
    LOG_CRITICAL,
    LOG_ERROR,
    LOG_WARNING,
    LOG_INFO,
    LOG_DEBUG
};

template<int level>
class formatted_log_t {
public:
    formatted_log_t(const wchar_t* msg ) : fmt(msg) {}
    ~formatted_log_t() {
        // GLOBAL_LEVEL is a global variable and could be changed at runtime
        if ( level <= GLOBAL_LEVEL ) wcout << fmt << endl;
    }
    
    template <typename T>
    formatted_log_t& operator %(T value) {
        fmt % value;
        return *this;
    }

protected:
    boost::wformat                fmt;
};

template <int level>
formatted_log_t<level> log(const wchar_t* msg)
{
    return formatted_log_t<level>( msg );
}

Применять этот код можно так:

int main ()
{
    log<LOG_DEBUG>(L"TEST %3% %2% %1%") % 5 % 10 % L"privet";
    return 0;
}

Работа с логом, наверное, самое очевидно, но только одно из возможных применений синтаксиса boost::format и далее можно развивать эту идею как вам больше нравится.