#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).