#prog #cpp #meme

#cpp #quotes

#cpp #meme

#cpp #article #performancetrap

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

Пожалуй, наиболее показательный пример применительно к C++ — это std::unordered_map. В отличие от std::map, к этому контейнеру нет требования, что элементы должны храниться в отсортированном порядке. По идее, это должно развязывать руки тем, кто пишет контейнеры. Однако стандарт C++ также накладывает серьёзные ограничения на стабильность итераторов для unordered_map. Именно, стандарт предписывает, что операции мапы инвалидируют ссылки на ключи и элементы только в том случае, если элементы удаляют — все остальные операции, включая всё то, что вызывает пересчёт хешей, ссылки сохраняют. На практике это означает, что любая конформная реализация обязана класть хранимые элементы в отдельный узел — с указателями на следующий и предыдущий элемент — память под который выделяется в куче. Мало того, что это требует +2 * sizeof(ptr) на каждый элемент — из-за использования аллокатора память под элементы выделяется в относительно произвольном порядке, что не позволяет нормально задействовать кеш процессора. Альтернативные реализации, такие, как abseil::flat_hash_map, могут иметь на порядок более высокую производительность за счёт использования структур данных, лучше использующих кеш процессора — ценой гарантий стабильности ссылок, разумеется.

Но есть и более тонкие ловушки. У std::multiset — упорядоченного контейнера, поддерживающего более чем однократное вхождение элементов — есть методы lower_bound, upper_bound и equal_range. Первые два метода возвращают первое и последнее вхождение указанного элемента в упорядоченной последовательности, а третий возвращает два итератора, между которыми находятся все элементы, равные предоставленному. В C++11 был добавлен неупорядоченный аналог этого контейнера — std::unordered_multiset. lower_bound и upper_bound по понятным причинам не имеют смысла для этого контейнера, а вот equal_range есть — видимо, для облегчения миграции с std::multiset. Но есть небольшая проблема: этот метод возвращает пару обычных итераторов. А это подразумевает, что все равные элементы хранятся в контейнере подряд. Соответственно, insert должен делать дополнительную работу по поиску места для вставки, и становится всё медленнее по мере увеличения числа элементов. В статье unordered_multiset’s API affects its big-O автор модифицировал реализацию unordered_multiset из libc++, убрав метод equal_range. Замеры показали, что это позволяет изменить код, чтобы существенно ускорить метод insert.

#prog очередные подставы в #cpp. На этот раз — с дефолтными операторами перемещения

#prog #cpp #video

Санитайзеры и стандарт не спасут

Или как опыт работы со студентами позволил найти баги в компиляторах, в динамических анализаторах, статических анализаторах и даже, по всей видимости, в стандарте.

Докладчик ссылается на ссылки в своей презентации, так что вот она (PDF).

#prog #cpp #python

Что общего у C++ и Python?

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

#cpp #meme

#prog #cpp

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

В C++ операции хеширования можно переопределять для конкретных контейнеров (это один из шаблонных параметров), но по умолчанию используется std::hash. Для того, чтобы определить операцию хеширования для своего типа, нужно написать специализацию std::hash для своего типа (обязательно в пространстве имён std) и написать свою реализацию operator(), которая будет принимать хэшируемый объект и возвращать std::size_t в качестве результата.

Пусть у нас вот такой простой тип:

struct Point {
    int x;
    int y;
};

Попробуем сделать его хешируемым:

#include <cstddef>
#include <functional>

template <> struct std::hash<Point> {
    std::size_t operator()(const Point& p) {
        // а как...
    }
};

И вот тут мы сталкиваемся с проблемой: при условии, что у нас все поля хэшируемые, как нам получить хэш от всех них? Увы, std тут вообще никак не помогает. Максимум, что могут предложить на просторах интернета — это использовать boost::hash_combine (это даже рекомендуют на cppreference.com). Мало того, что тащить буст ради этого не хочется, так ещё и комбинирование происходит на уровне готовых хэшей. Это фактически приводит к двойному хэшированию, что обычно на качестве хэш-функции сказывается не в лучшую сторону.

В теории можно было бы организовать разделение на саму хэш-функцию и на описание того, какие и в каком порядке поля типа хэшируются... То есть сделать так, как в Rust. И это даже предлагали сделать для C++ в предложении N3980 aka Types Don't Know #. И подано это предложение было... 24 мая 2014 года. То есть десять лет назад, да. А воз и ныне там.

#prog #cpp

doctest is a new C++ testing framework but is by far the fastest both in compile times (by orders of magnitude) and runtime compared to other feature-rich alternatives. It brings the ability of compiled languages such as D / Rust / Nim to have tests written directly in the production code thanks to a fast, transparent and flexible test runner with a clean interface.

Советую также посмотреть, чем отличается от прочих фреймворков для тестирования в C++.