вторник, 1 января 2030 г.

О блоге

Более двадцати лет я занимался разработкой ПО, в основном как программист и тим-лид, а в 2012-2014гг как руководитель департамента разработки и внедрения ПО в компании Интервэйл (подробнее на LinkedIn). В настоящее время занимаюсь развитием компании по разработке ПО stiffstream, в которой являюсь одним из соучредителей. Поэтому в моем блоге много заметок о работе, в частности о программировании и компьютерах, а так же об управлении.

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

понедельник, 31 декабря 2029 г.

[life.photo] Характерный портрет: вы и ваш мир моими глазами. Безвозмездно :)

Вы художник? Бармен или музыкант? Или, может быть, коллекционер? Плотник или столяр? Кузнец или слесарь? Владеете маленьким магазинчиком или управляете большим производством? Реставрируете старинные часы или просто починяете примус? Всю жизнь занимаетесь своим любимым делом и хотели бы иметь фото на память?

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

вторник, 15 октября 2024 г.

[prog.c++] Никогда не задумывался о таком поведении С++ в случае адресов вложенных объектов, а ведь оно логично

Давайте посмотрим на структуру данных B:

struct A {};

struct B : public A {
    A _first;
};

Какой у нее размер? С учетом того, что даже у пустой структуры размер будет, как минимум, 1 байт. И что в C++ есть empty base class optimization.

То, что B наследуется от пустого A благодаря empty base class optimization не увеличивает размер B. Т.е. размер B будет определяться размером поля B::_first, а это один байт. Следовательно, sizeof(B) должен быть равен единице.

На самом деле нет.

Дело в адресах для объекта B и для его поля B::_first:

B b;
A * p1 = &b; // Это легально т.к. B есть A благодаря наследованию.
A * p2 = &b._first;

assert(p1 != p2);

Объект типа B является объектом типа A из-за наследования. Соответственно, адрес объекта типа B будет и адресом объекта типа A.

Внутри типа B есть еще один объект типа A. И у него так же есть свой адрес.

При этом объект B и его поле B::_first -- это два разных объекта типа A.

А в C++ у двух разных объектов одного типа не может быть одинаковых адресов.

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

Убедиться в этом можно на wandbox - цынк

Информация об этой особенности C++ найдена здесь.

PS. Какой практический смысл у этой информации? Вероятно, никакого. Но это лишняя иллюстрация того, сколько же разных нюансов приходится учитывать при развитии C++.

пятница, 11 октября 2024 г.

[life.work] 30 лет профессионального программизма

Как же все-таки летит время. Вроде бы недавно публиковал аналогичный пост, но про 25 лет, а тут хоба! И уже 30.

Ну а так-то да, где-то в октябре 1994-го мне сделали трудовую книжку и я стал считаться профессиональным программистом. Писать программки начал пораньше, года с 1990-го, но именно за зарплату только с 1994-го.

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

среда, 9 октября 2024 г.

[prog.data.structures] В склерозник: ссылки на тему prefix/radix tree

Довелось недавно столкнуться с темой prefix/radix деревьев. По ходу изучения нашел несколько ссылок, которые для меня оказались полезными, поэтому зафиксирую их в склерозник, чтобы было проще найти в будущем.

Даю только ссылки, без пространных пояснений, уж извините меня за халтуру, но так проще.

Adaptive Radix Tree. Собственно, основная PDF-ка, с которой и следует начинать.

HAT-trie, a cache-conscious trie. Обзор сразу нескольких подходов к реализации префиксных деревьев и хеш-таблицы с переходом к рассказу об их комбинации HAT-trie. Плюс реализация этой идеи на C++.

Crit-bit trees и qp tries and crit-bit tries. Еще несколько вариаций на тему префиксных деревьев.

Akamai Radix Tree. Реализация на C++ radix tree от Akamai. Очень интересно если хочется посмотреть, как это дело можно реализовать. Хотя оформлена библиотека (в плане описания, документации, примеров и комментариев в коде), как по мне, бестолково. Поэтому разбираться не просто + реализация на многоэтажных шаблонах, так что требуется хорошее знание C++.

Compressing dictionaries with a DAWG и Directed Acyclic Word Graphs. Пара статей вокруг идей о том, как можно сократить объем данных в префиксном дереве.

Ну и вот эта ссылка регулярно всплывала, хотя напрямую к теме, вроде бы, не относится: Implementation of sparse_hash_map, dense_hash_map, and sparsetable.

От себя добавлю, что для сценария, в котором мне потребовалось что-то вроде prefix/radix дерево, "классический" вариант префиксного дерева вел к слишком большому расходу памяти. И, как я понял, это характерно для подобного рода деревьев, поэтому как раз и есть статьи о том, как уменьшить объем данных.

пятница, 4 октября 2024 г.

[prog.c++] Использование одного аргумента шаблона (aka Traits) вместо нескольких

В догонку ко вчерашнему посту про недостающую функциональность в std::vector.

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

Кстати говоря, есть у меня ощущение, что в любом C++ном проекте, который писали обычные люди, вроде меня, а не монстры, вроде Девида Вандервуда или Барри Ревзина, куча кода поломается, если в std::vector начнут использовать собственные аллокаторы. Поломается потому, что код написан в стиле:

void do_something(const std::vector<int> & data) {...}

И даже шаблонный код написан вот так:

template<typename T>
void do_something(const std::vector<T> & data) {...}

а не вот так (хотя бы вот так):

template<typename T, template Allocator>
void do_something(const std::vector<T, Allocator> & data) {...}

Впрочем, это уже совсем другая история...

Но если пофантазировать?

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

Это подход на базе Traits. Уже не помню, откуда про него узнал, не удивлюсь, если из книг Александреску. Но подход уже старый и мы, например, применяем его в RESTinio.

Суть в том, что шаблон параметризуется отдельным типом Traits, внутри которого уже сосредоточена все остальная нужная шаблону информация.

Например, для std::vector это могло бы выглядеть так:

template<typename T>
struct default_vector_traits {
  using allocator = std::allocator<T>;
};

template<typename T, typename Traits = default_vector_traits<T> >
class vector {...};

И если бы со временем нам бы потребовалось добавить в шаблон std::vector еще один параметр (тот же нужный мне growth_policy), то это можно было бы сделать не меняя списка параметров для std::vector:

struct default_vector_growth_policy {
  std::size_t operator()(std::size_t current_capacity) const {
    // Код примерный, прошу помидорами не бросаться ;)
    return (current_capacity > 1 ? static_cast<std::size_t>(capacity * 1.5) : 2);
  }
};

template<typename T>
struct default_vector_traits {
  using allocator = std::allocator<T>;
  growth_policy = default_vector_growth_policy;
};

template<typename T, typename Traits = default_vector_traits<T> >
class vector {...};

И если бы мне захотелось использовать с векторами собственную политику роста емкости, то мне бы потребовалось всего лишь:

struct my_growth_policy {
  std::size_t operator()(std::size_t current_capacity) const {...}
};

template<typename T>
struct my_vector_traits : public std::default_vector_traits<T> {
  using growth_policy = my_growth_policy;
};

using my_int_vector = std::vector<int, my_vector_traits<T>>;

Понятное дело, что шаблоны классов контейнеров из стандартной библиотеки на Traits уже не перевести. Но если вы пишите свои библиотеки шаблонных классов (особенно собственных типов контейнеров, неприведихоспади!), то имеет смысл подумать о применении подхода с Traits.

четверг, 3 октября 2024 г.

[prog.c++] В std::vector не хватает вот какой штуки...

Интересно, много ли C++ программистов задумывается о том, а как растет std::vector, когда мы в него добавляем элементы через push_back и не имеем возможности сделать предварительно reserve?

А ведь рост размера std::vector может существенным образом повлиять на расход памяти.

Предположим, что реализация std::vector в вашей стандартной библиотеке использует коэффициент 1.5 для увеличения размера вектора. Т.е. вы делаете push_back в полный вектор и опа! Ваш вектор увеличился в полтора раза. Была емкость на 1000 элементов, а стала на 1500. А использоваться оттуда будет 1001.

А если реализация стандартной библиотеки использует коэффициент 2, то дела еще хуже.

Сильно негативно это начинает проявляться на векторах размером в миллион-два-три и т.д. Если у вас в программе таких векторов не один и не два, то вы с удивлением для себя сможете обнаружить, что в этих векторах где-то 1/5 или 1/4, а то и 1/3 объема не занято. Что в сумме может дать десятки мегабайт впустую потраченной памяти.

Чтобы этого не происходило приходится вручную контролировать размер и емкость вектора и, опять же, вручную дергать reserve перед push_back-ами.

А то, что делается вручную, легко забыть или же сделать неправильно 😣

Поэтому мне лично не хватает возможности задать для std::vector какую-то собственную политику роста. Что-то типа:

struct my_growth_policy {
  [[nodiscard]] std::size_t operator()(std::size_t current_capacity) {
    return ... // здесь какие-то вычисления.
  }
};

using my_vector = std::vector<my_data, std::allocator<my_data>, my_growth_policy>;

Тогда не пришлось бы вручную контролировать емкость перед каждым push_back-ом.

Но, боюсь, в стандартном std::vector такого не будет никогда.