Size based vector

https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306

Мы тут в Гугле экспериментировали с тем как репрезентовать вектор. Существует два способа:

1. Указатель на начало, конец и указатель на конец вместимости

2. Или указатель на начало, размер и вместимость

Оба варианта имеют свои особенности и слабые места. Первый вариант плох тем, что когда вы хотите посчитать size(), то вы вычитаете два указателя: end - begin. Вычитание указателей в численном представлении эквивалентно формуле (end_as_num - begin_as_num) / sizeof(T), где T -- тип вектора. Вот это деление на константу порой выбешивает, например, когда sizeof(T) не является степенью двойки. Компилятору приходится это деление переводить в умножение и теперь когда вы вызываете size(), то у вас откуда-то страшные конструкции вида https://godbolt.org/z/zKGz7nEE6

Но первый вариант неплох, когда вы итерируетесь и надо просто сравнивать с концом. Почему? Во втором варианте вам надо при вызове .end() загружать два регистра -- начало и размер, чтобы сложить. В итоге у вас баланс между двумя опциями

.size() выливается в умножение при sizeof(T) не степень двойки

.end() загружает два регистра

Остальные операции чуть чуть поменяются, но в основном размен происходит у этих двух.

Оказалось, что .end() чаще вызывается один раз, а .size() намного чаще в том числе и внутри циклов, потому что... Ну потому что программистам удобнее работать с числами, а не указателями. Или по каким-то ещё причинам.

В итоге мы увидели улучшение перфа всего прода на 0.12% с особенно важными серверами с исправлениями на 0.5-0.6%, о чем и поделились в discourse.llvm. Понятное дело, что кто-то слишком сильно пользовался репрезентацией вектора, но мы всех их починили и выкатили. Теперь хотим выкатить и в unstable ABI в libcxx.

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