пятница, 29 мая 2009 г.

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

Казалось бы проблемы из-за сравнения знаковых и беззнаковых значений давно известны и обходятся опытными разработчиками. Однако, разработчики компилятора 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 может принимать отрицательные значения и результат сравнения проверяет командой, которая знак не учитывает.

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

пятница, 22 мая 2009 г.

ordered_unique vs hashed_unique

Контейнер 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 элементов из-за парадокса дней рождения.

воскресенье, 17 мая 2009 г.

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

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

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

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

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

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

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

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

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

среда, 6 мая 2009 г.

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

Библиотека 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 и далее можно развивать эту идею как вам больше нравится.