BOOST vs BICYCLE
От: Dmi_3 Россия  
Дата: 06.12.06 21:33
Оценка: 143 (16) +2 -1 :))) :))) :))
О BOOST, тебя хвалить устали
Твои заслуги возносив.
С "велосипедами" из stall-и
Ты борешься, нас не спросив.

PR пронёсся над умами
В фаворе ты, но вот беда
Теперь, когда ты рядом с нами
Ты сам "велосипедом" stall

Я вру? Бессовестно тревожу
Покой зомбированных тел?
Ну что же объясню попозже,
Что этим я сказать хотел.

Возьму, последуя примеру
Тех, кто хулит велосипед,
Банальный код. Но заная меру
Не буду bind-ить стих и вред.

Да ВРЕД иначе и не скажешь
О том ветвистом копипэйст.
Под компиляторы однажды
Настроенном в ущерб себе.


Както мне понадобился генератор псевдослучайных чисел. И следуя модному течению я решил использовать boost::random::linear_feedback_shift. По своему прежнему опыту я знал каким хорошим алгоритмом является LFSR. Мой велосипед, основанный на нём, служил мне верой и правдой уже не один год.
Справедливости ради хочу сказать, что использовал старую версию boost_1_33_0. Ну не могу я скачивать все версии BOOST подряд. Но вряд ли сейчас ситуация изменилась.
И вот начались мои мучения. Удовлетворив всем (даже закомментированным) STATIC_ASSERT-ам (спасибо, что хоть они есть) я подобрал template параметры и... Моя программа вошла в бесконечный цикл. Вернее это я теперь знаю, что он бесконечный. А сперва я очень радовался быстрой работе и якобы огромному периоду boost::random:: linear_feedback_shift генератора. Но чудес не бывает, и когда этот якобы огромный период превысил число возможных состояний генератора, я забеспокоился. Но как можно обвинить ВЕЛИКИЙ BOOST!? Естественно, я стал искать свою ошибку. Потратив пару дней я находился в свирепом настроении. Заказчик (физик-ядерщик) требовал продукт, а программа работать не хотела. Но вот, наконец, я провёл полное доказательство правильности своего алгоритма (Те кто этим занимался знает, что это адская работа). Оставался лишь хвалёный (читай PR-еный) BOOST-ом linear_feedback_shift. И я отправился в чтение кода BOOST. К счастью оказалось, что boost::random не слишком завязан на остальные дебри BOOST. Раскрыв всего десяток макросов, пройдя всего пару десятков include, мне удалось частично понять немного странную логику разработчиков.
И не надо обвинять меня в лишней работе. Я искал ошибку в незнакомом коде и по любому должен был пройти по этим #define #ifdef и #include. К слову сказать, если бы они меньше внимания уделяли тому чтобы их велосипеды ездили везде, всё могло бы быть гораздо проще и понятнее. Как известно, программы пишут не для компиляторов, а для людей. Но плюньте в глаза тому, кто скажет, что этот принцип распространяется на BOOST.
Но вернёмся к пресловутому linear_feedback_shift. Сперва я обнаружил, что он почти не в состоянии выдать своё заявленное минимальное значение. Мой плохой английский не позволил мне выяснить в документации это точная нижняя граница или просто некое число меньшее\равное этой границе. Пришлось изменить мой алгоритм (от чего он стал труднее для понимания) и использовать метод linear_feedback_shift::max. Вы думаете это спасло отца русской демократии? Как бы не так! Доказать что linear_feedback_shift::operator() никогда не выдаёт значение возвращаемое linear_feedback_shift::max я не смог, но исчерпывающий поиск для нескольких разных инстанциаций linear_feedback_shift показал, что таки не выдаёт. В процессе этого поиска дополнительно выяснилось, что обычный период генератора даже меньше чем у ::rand(). И ни в одном случае не превосходит половины возможного числа состояний генератора. То есть генератор не выдаёт как минимум половину чисел, в которую обычно и входят min и max. Причём Вам будет довольно таки трудно найти именно те template параметры, при которых он всё-таки выдаёт хотя-бы половину. А если Вы хотите чтобы порядок этих чисел ещё и напоминал случайный, (не слишком ли много Вы хотите?) то Вы должны быть специалистом по генераторам случайных чисел, или потратить кучу времени на подбор чудесной комбинации правильных параметров ибо в документации (не говоря уже о assert-ах) такой информации нет.
Впрочем, в утверждении, что генератор не выдаёт min я погрешил против истины. Иногда ВЫДАЁТ!!! И при этом его период равен единице!!! То есть он или не выдаёт min совсем или выдаёт его всегда! Замечательный генератор. Вы не находите? Примерно такая же ситуация имеет место для чисел близких к минимуму или максимуму.
А сейчас ВНИМАНИЕ. На арене фокусник.
МНЕ УДАЛОСЬ менее чем за 100 часов(а у меня старый, медленный комп) получить ВСЕ псевдослучайные числа в том порядке, в котором их выдают ВСЕ 32-битные (и менее) инстанциации этого генератора удовлетворяющие STATIC_ASSERT-ам и инициализированные default значением.
И это говорит не столько о высокой скорости работы генератора, сколько о смехотворности его среднего периода. В общем, могу рекомендовать несколько инстанциаций этого генератора только для локального внутри метода использования, если Вам абсолютно неважно качество получаемых чисел и крайне важна сверхвысокая скорость работы (всё в регистрах, память не задействована).
В документации сказано (насколько позволяет понять мой отвратительный английский) что качество linear_feedback_shift генератора среднее (quality: medium).
cycle length is limited to the maximum value representable in one machine word, fails some statistical tests, can be improved with the xor_combine compound engine.
Формально к этому не придраться. Но мы и без того знаем, что период любого генератора не может быть больше числа его состояний, а "some" в свете вышеизложенного лучше перевести как "большинство". Что касается xor_combine compound engine, то он может сделать хорошими 90% наших отвратительных велосипедных генераторов. Но случайная инстанциация boost::random::linear_feedback_shift обычно не входит даже в эти 90%.
После этого исследовать другие характеристики генератора мне не захотелось и, покатавшись (получая синяки и шишки при падениях) на этом BOOST велосипеде я хотел вернулся к своему старенькому велосипеду (тоже LFSR), который выдаёт любой (хоть 64-битный) интегральный тип во всём его диапазоне, гарантирует период=(1<<47)-1; (Если кому мало можно легко добавить), работает правда почти на 80% медленнее, но позволяет делать прямое позиционирование в любую часть генерируемой последовательности, и давно успешно прошел все известные мне методы проверки генераторов псевдослучайных чисел. Увы, я их не так много знаю. Кроме того (в коммерческой версии) он гарантирует, что это качество останется одинаковым для любых его инстанциаций. Завистники, правда, говорят, что его sizeof в десятки раз больше бустовского, но мне редко приходилось видеть программы использующие сотни \ тысячи генераторов одновременно и\или передающих их параметром по значению (как в BOOST) так, что это не должно быть большой проблемой. В 1989 году на 16 разрядном ДВК-2 с 56 килобайтами памяти это не стало проблемой. Но на свою беду я решил сделать вторую попытку и использовал boost::lagged_fibonacci. Большой sizeof этого генератора вселял надежду, а (даже указанная в документации) скорость работы была на пару процентов выше чем у моего велосипеда. Увы, меня ждало горькое разочарование. В документации я опять же этого не нашел, но оказалось что несколько генераторов с разным состоянием могут выдавать абсолютно одинаковые последовательности и это не удивительно если посмотреть как написаны operator== и seed(it&,it). Кроме того большинство бустовских генераторов нельзя использовать в программах высокой надёжности от которых, например, зависят жизни людей. ВСЁ! Я поставил крест на использовании boost::random::AnyEngine, но пока ещё хотел использовать boost::random::AnyDistribution. Поэтому адаптировал свой велосипед к бустовскиму интерфейсу и стал использовать его как boost::random::Engine. Кстати до адаптации его интерфейс был прост как грабли. Вы знаете что такое STL итератор? Так вот этот велосипед – STL совместимый random_access итератор кольцевой неизменяемой последовательности равномерно распределённых беззнаковых псевдослучайных чисел. Он так и назван. Вопросы остались? Нужно долго изучать Random Number Generator Library Concepts, копаться в документации и коде изучая некие engine, distribution, seed, validate, min, max, reset? Нужно объяснять что означает равенство генераторов? Нужно выяснять имеет ли генератор эффект девятки? Поздравляю, базируясь лишь на своих знаниях C++ (а STL его часть) Вы за несколько секунд (или минут в зависимости от сообразительности) узнали почти всё о новом незнакомом генераторе псевдослучайных чисел даже не заглядывая в документацию. Нет, Вам возможно придётся таки залезть туда когда Вы захотите использовать разность итераторов или специфический конструктор (BOOST такой функциональности, кажется, даже не предоставляет), но начать работу вы сможете сразу. А теперь дайте документацию и исходники BOOST незнакомому с ним человеку и включите секундомер…
Что? Вы хотите распределение вероятностей отличное от равномерного? Желаете генерировать не unsigned int а std::vector<double> или Ваш some_other_type? В чём проблема? STL итератор легко параметризуется типом итерируемых значений. Хотя у меня этого и не сделано.
Для меня до сих пор является загадкой, почему boost::random::Engine_конструктор по умолчанию не проводит первичную рандомизацию и создаёт объект в одном и том же состоянии. Неужели я сам каждый раз должен каким-то чудом создать буфер случайных чисел и передать его в конструктор или функцию seed? Если мне вдруг понадобиться такая функциональность (например для снятия рандомизации при отладке) то можно создать глобальный константный объект и присваивать его текущему генератору. С моей точки зрения это даже проще чем reset, а обычный случай должен подразумевать начальную рандомизацию. Коммерсанты требуют от меня знаний BOOST и отказывают в приёме на работу. Что же пусть платят деньги, чтобы их программисты забивали себе головы новыми ни для чего не нужными концепциями и тратили время на подбор template параметров, генерацию случайных затравок (часть из которых просто нельзя генерировать) и поиски ошибок в BOOST генераторах.
Но продолжим. Как Вы помните я решил не отказываться от написанных в BOOST распределений и вот что я обнаружил. boost::normal_distribution вызывает Engine разное количество раз и выдаёт коррелирущие соседние значения. По видимому, это является следствием неграмотной и неполной оптимизации. Кроме того моему учёному заказчику было мало обычного double, а работать с big_precision_real_number буст не захотел. Приведу исходный бустовский и аналогичный мой код с комментариями. В буст коде расскажу почему он плохо написан. В своём, почему значения будут коррелировать.
// deterministic polar method, uses trigonometric functions
template<class RealType = double>
class normal_distribution
{
public:
  typedef RealType input_type;
  typedef RealType result_type;

#if !defined(BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS) && !(defined(BOOST_MSVC) && BOOST_MSVC <= 1300)
    BOOST_STATIC_ASSERT(!std::numeric_limits<RealType>::is_integer);
#endif

// Почему используются целые константы?
// result_type – вещественный тип
// и может не уметь так создаваться
  explicit normal_distribution(const result_type& mean = result_type(0),
                               const result_type& sigma = result_type(1))
    : _mean(mean), _sigma(sigma), _valid(false)
  {
// Мой коллега писавший class big_precision_real_number
// поленился написать operator>=
// в template всегда лучше использовать operator<
    assert(sigma >= result_type(0));
  }

  // compiler-generated copy constructor is NOT fine, need to purge cache
// Я так и не смог понять, почему необходимо сбрасывать кеш.
// и почему его ненужно сбрасывать при присваивании.
// Мне кажется, это лучше делать явно через reset
  normal_distribution(const normal_distribution& other)
    : _mean(other._mean), _sigma(other._sigma), _valid(false)
  {
  }

// Комментарий вводит в заблуждение.
  // compiler-generated copy ctor and assignment operator are fine

// Обращение к членам класса в template опасно проводить без this->
// даже если Вы используете префиксное подчёркивание.
  RealType mean() const { return _mean; }
  RealType sigma() const { return _sigma; }

// Информация о валидности вполне может содержаться в самом кеше.
  void reset() { _valid = false; }

// Кажется, operator() должен быть константным?
  template<class Engine>
  result_type operator()(Engine& eng)
  {
#ifndef BOOST_NO_STDC_NAMESPACE
    // allow for Koenig lookup
    using std::sqrt; using std::log; using std::sin; using std::cos;
#endif
    if(!_valid) {
// 1) Почему _r1 _r2 входят в состояние объекта?
// Достаточно стековых переменных.
// 2) В общем случае опасно читать\менять состояние объекта не атомарно,
// а прямая работа с членами-данных оптимизируется
// компиляторами заметно хуже, чем с auto переменными.
// 3) Пользователь может "заложиться" на фиксированное число
// вызовов eng() при генерации. Нужно хотя бы предупредить!
      _r1 = eng();
      _r2 = eng();
// Зачем постоянно использовать лишние операции?
// Будет яснее и быстрее, если однократно вычислить константы,
// а не делать это на каждом втором вызове.
      _cached_rho = sqrt(-result_type(2) * log(result_type(1)-_r2));
      _valid = true;
    } else {
      _valid = false;
    }
    // Can we have a boost::mathconst please?
// Раз всё равно требуется конструироваться от double
// зачем выше использовали целые константы?
    const result_type pi = result_type(3.14159265358979323846);
    
// Часто sin_cos это одна инструкция процессора или один
// кеширующий result_type::метод и лучше вычислять их парой
// а не в разных вызовах.
    return _cached_rho * (_valid ?
                          cos(result_type(2)*pi*_r1) :
                          sin(result_type(2)*pi*_r1))
      * _sigma + _mean;
// Правильность самой формулы вычисления вызывает сомнения.
  }

#if !defined(BOOST_NO_OPERATORS_IN_NAMESPACE) && !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
// Почему количество пробелов при вводе и выводе не совпадает?
  template<class CharT, class Traits>
  friend std::basic_ostream<CharT,Traits>&
  operator<<(std::basic_ostream<CharT,Traits>& os, const normal_distribution& nd)
  {
    os << nd._mean << " " << nd._sigma << " "
       << nd._valid << " " << nd._cached_rho << " " << nd._r1;
    return os;
  }

// Странно, что ctor сбрасывает кеш, а ввод из потока нет.
// И чем так отличается _r2 что не участвует во вводе\выводе?
  template<class CharT, class Traits>
  friend std::basic_istream<CharT,Traits>&
  operator>>(std::basic_istream<CharT,Traits>& is, normal_distribution& nd)
  {
    is >> std::ws >> nd._mean >> std::ws >> nd._sigma
       >> std::ws >> nd._valid >> std::ws >> nd._cached_rho
       >> std::ws >> nd._r1;
    return is;
  }
#endif
private:
// Слишком избыточное состояние генератора провоцирует к ошибкам
// Хватило бы result_type _cached, _mean, _sigma;
  result_type _mean, _sigma;
  result_type _r1, _r2, _cached_rho;
  bool _valid;
};

А теперь о boost::uniform_on_sphere… Там тоже ошибка (к счастью крайне маловероятная) деления на ноль. А о скорости его работы даже говорить не хочется. Как ни учён был мой заказчик, но сфера у него была обычная 3D и задержки связанные с генерацией произвольного N-мерного вектора свели бы на нет все мои прошлые усилия. Для 1D и 2D случаев это ещё заметнее. ASSERT или исключение на случаи меньше единицы отсутствуют.
Вот сижу теперь и думаю зачем я корячился переводя документацию(мне это сложно я программист а не переводчик) если в итоге пришлось всё самому делать?
Не знаю как Вы, а я больше в BOOST ни ногой. Я ЕМУ НЕ ВЕРЮ. И его разработчики сделали всё, чтобы было труднее ему поверить. Разбираться в правильности (в данном случае ошибочности) его кода почти невозможно. А я копался в одной из самых понятных (имхо) частей BOOST.
Есть ещё желающие говорить что BOOST это не пропиареный велосипед? Вы скажете в любом коде могут быть ошибки. Наверно да. Но еслибы на мой код в течении хотябы месяца пялились бы тысячи программистов в нём не осталось бы ни одной ошибки. А сколько лет бусту? Действительно, наши велосипеды часто имеют ошибки. Но имеет ли право такая библиотека содержать такие ошибки? И чем тогда она отличается от наших велосипедов? Кстати, хоть это ничего и не меняет, поправьте меня если в новой версии этих ошибок нет. Может быть тогда мне удасться поверить в буст. Он хоть и велосипед но не хуже 90% наших велосипедов.

Часть вторая (очень очень спорная. наверно зря пишу)

Кроме того у меня возникли большие сомнения в переносимости. Нет, не самого BOOST.
Об этом разработчики позаботились (это PR), а программ написанных с его использованием. Неужели мы все должны писать так как в BOOST? Обрамляя в угоду недоделанным компиляторам большие куски кода #ifdef-ами и фактически дублируя его с небольшими изменениями для нескольких разных случаев? А как потом его синхронно изменить во всех этих местах?
Проводя аналогию с велосипедами можно сказать, что их велосипеды могут ездить везде но увы по-разному. А мне нужно чтобы пусть не везде, но одинаково.
Приведу (далеко не лучший) пример. Вот наследуюсь я от пресловутого linear_feedback_shift
class my_bicycle : linear_feedback_shift< .... >
{
public:
    // Я могу написать и потом обнаружить что это не переносимо
    bool operator == ( my_bicycle const & x ) const throw ()
    { return this->linear_feedback_shift::operator==(x); }

    // Вероятно, я должен писать так
    // Но лично я не хочу тратить свои мозги на запоминание этого факта.
    // И лично для меня это выглядит менее понятно.
    // Не говоря уже о том, что в бОльшем количестве кода легче совершить ошибку.
    bool operator == ( my_bicycle const & x ) const throw ()
    {
        return
            static_cast<linear_feedback_shift const&>(this)
            ==
            static_cast<linear_feedback_shift const&>(x);
    }

    // Но и это исчо не всё.
    // Мне вообще предлагают лечь под компилятор и получать удовольствие.
#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE
    friend bool operator == ( my_bicycle const& x, my_bicycle const& y ) throw ()
    {
        return
            static_cast<linear_feedback_shift const&>(x)
            ==
            static_cast<linear_feedback_shift const&>(y);
    }
#else
    bool operator == ( my_bicycle const & x ) const throw ()
    {
        return
            static_cast<linear_feedback_shift const&>(*this)
            ==
            static_cast<linear_feedback_shift const&>(x);
    }
#endif
};

Хотите продолжать? Тогда вспомните что некоторые компиляторы ругаются на throw (). Этого мало? Замените #ifndef X на #if !defined(X) для некоторых компиляторов. Верьте! Это можно продолжать! И Ваша жена будет образцом непритязательности и смирения по сравнению с капризным своенравным и взбалмошным компилятором.
Итак пара понятных строк кода выросла до размеров нескольких экранов только потому, что кто-то себя пиарит(?). Скажите, Вы не знаете какие секретные технологии используют разработчики BOOST чтобы сопровождать это безобразие? Я бы за такую задачу не взялся.
Лично я не вижу проблемы в том чтобы отказываться от поддержки плохих компиляторов. Но... Это опять чёртов PR которому последнее время уделяется всё внимание. Вы можете быть откровенно слабым программистом, но если Вы в костюме и галстуке то Ваш код будет называться ПРОДУКТОМ. А мой код назовут "велосипедом" только за то, что я не пользуюсь мобильным телефоном, берегу окружающую среду отказавшись от использования дымящего автомобиля и предпочитаю ходить в джинсах и свитере.

P.S.
PR акция:
1) Поборники и защитники BOOST могут затребовать free-версию вышеозначенного велосипеда в виде MSVC71.hpp и MSVC71.obj файлов и яро её покритиковать.
2) Имеющие хороший пакет для проверки рандомов и желающие его протестировать приветствуются. (Бустовский даже глядеть не хочу)
3) Испытывающие нужду в хорошем генераторе псевдослучайных чисел тоже могут связываться.

P.P.S.
А вообще вся эта PR возня очень напоминает следующее объявление:
Продаю старые файлы windows95.
Файл win386.swp стоит 1386 у.е. (раритет)
Владельцам новых компов предлагаю апгрейд
файлы:
win486.swp за 486 у.е.
Для FAT32 и NTFS
win_pentium1.swp за 1000 у.е.
win_pentium2.swp за 2000 у.е.
win_pentium3.swp за 3000 у.е.

И эксклюзивное предложение!
Только у нас!
Только для Вас!
Последняя модификация!
Легальная авторская копия!
Полная програмная и аппаратная совместимость с 4х-ядерными процессорами!
Поддерживает 256-битные приложения!
Поддерживает длинные имёна!
Русифицирован!
Дружественен к пользователю!
Абсолютно вирусобезопасен!
Содержит электронную подпись!
Обладает возможностью к расширению!
Протестирован InteLL!
Сертифицирован 1BM!
Поддержка Macrohard Mouse, Macrohard Dog и Macrohard Cat!
Файл:
/----------------------------\
| ВИН_ДОУЗ_ПЕНЬ_ТИ_УМ_4.СВАП |
\----------------------------/

ЭЭЭЭ !!! КУДА ВЫ? СТОЙТЕ !!!
ДВА ПО ЦЕНЕ ОДНОГО !!! ТРЕТИЙ БЕСПЛАТНО !!!
Свежие! Создаются в присутствии покупателя!
Ламерам по предъявлению этого объявления скидки!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.