#prog #cpp #rust #article

How to rewrite a C++ codebase successfully (in Rust)

Ценно в том числе примерами реальных багов на границе FFI

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

TIL что для #cpp есть предложение закрепить в стандарте тот факт, что в байте ровно 8 бит. Сейчас это не так: стандарт (и сишный тоже) требует, чтобы в char было минимум 8 бит, но точное их количество может быть больше, и это количество записано макросом CHAR_BIT из limits.h/climits.

#prog #cpp #meme

#prog #rust #cpp #article

Type Inference in Rust and C++

<...>My feeling is that literally everything above is indicative of a trade-off pattern.

If you want to have a fancy, bespoke modern type checker with Hindley-Milner type inference semantics, you need to accept one of the following:

1. Bad performance for your type checker with a risk of exponential blow-up.
2. No features that look anything like “the compiler picks the best option out of several ones”. No function overloading, implicit conversions, etc.

Надо отдельно отметить, что deref coercion под "pick the best option out of several ones" не подпадает — Target является у трейта ассоциированным типом, а не параметром, поэтому реализаций Deref у каждого конкретно взятого типа не более одной

#prog #cpp #article

How C++ Resolves a Function Call

Взгляд на порядок разрешения имён при вызове функции в C++ с высоты птичьего полёта, с примером, который проходит по всем шагам.

#prog #cpp #article

Carbon is not a programming language (sort of)

TL;DR: Carbon не столько про сам язык, сколько про процесс эволюции языка.

#prog #cpp #article

Why safety profiles failed

TL;DR:

10 лет назад Страуструп и Ко представили идею safety profiles: набор стандартизированных статических анализаторов, которые бы увеличивали безопасность кода на C++, причём практически без изменений исходного кода, и которые можно было бы активировать одной командой компилятора. Идея оказалась настолько привлекательной, что комитет по C++ (WG21) принял несколько предложений касательно профилей.

Однако за 10 лет весь выхлоп от профилей весьма мал: криво работающий -Wlifetime и... Вроде бы всё. Даже спецификации какой-то за столько времени так и не сделали.

В своём тексте Sean Baxter, автор компилятора Circle, пишет о том, почему идея safety profiles не работает и, более того, в принципе не может работать.

#cpp #meme

#prog #cpp #article

C++26: no more UB in lexing

(на практике, правда, главные реализации и так нормально такой код обрабатывали)

#prog #cpp