Comments 65
UFO just landed and posted this here
Похоже Travis Downs хотел что-то написать для микроконтроллера, потому что там такие вещи уже давно исследованы. И никто в здравом уме не будет делать проверку на границу цикла через вызов функции, всегда так и делали, задаешь константу и потом с ней уже сравниваешь.
Справедливости ради, стоит заметить, что вектор для микроконтроллеров редко используют, вместо этого array, у которого size() это constexpr выражение, поэтому там таких проблем и нет.
И да лучше использовать вообще цикл с обходом диапазона.
Справедливости ради, стоит заметить, что вектор для микроконтроллеров редко используют, вместо этого array, у которого size() это constexpr выражение, поэтому там таких проблем и нет.
И да лучше использовать вообще цикл с обходом диапазона.
UFO just landed and posted this here
никто в здравом уме не будет делать проверку на границу цикла через вызов функции, всегда так и делали, задаешь константу и потом с ней уже сравниваешь
Это проистекает не из здравости ума, а из святой до наивности убеждённости этих разработчиков в том, что если написан вызов функции, то он будет на каждой итерации. Хотя здесь проблема вовсе не в том, что компилятор не умеет оптимизировать, а в том, что не имеет права. Про алиасинг большинство людей, вводящих константу, не только не подумает, а даже и не знает. Как следствие, это выстрелит в другом месте их кода.
UFO just landed and posted this here
В старом с++ на некоторых контейнерах size() имел линейную сложность. Это была жизненная необходимость выносить его из тела цикла.
UFO just landed and posted this here
В «старом» C++ только у std::list метод size мог быть линейным, а мог быть и константным — реализациям предоставлялся выбор. Это сейчас комитет (очевидно, под давлением M$) принял генитальное решение сделать std::list::size константным — в результате в стандартной библиотеке у нас больше нет такого абстрактного типа данных как «двусвязный список».
UFO just landed and posted this here
Ой, правда что ли? :)
Скажите, а почему тогда
для случая this != &other даёт линейную сложность от std::distance(first, last)?
Скажите, а почему тогда
splice(const_iterator pos, list& other, const_iterator first, const_iterator last)для случая this != &other даёт линейную сложность от std::distance(first, last)?
UFO just landed and posted this here
Если речь заходит о чуть более специфических операциях, то всё становится куда интереснее, так как константный size() позволяет реализовать ряд других методов (которые, ИМХО, используются как минимум не реже) более эффективно. Howard Hinnant об этом хорошо писал в своё время.
Если есть подобная необходимость, то можно подсчитывать размер внешними средствами. Т.е. из двусвязного списка сделать особую химеру имени std довольно легко, а вот наоборот — нет.
Похоже Ваше мнение о сложности std::list не популярно, как и моё :).
По сути «химера» это лишь дополнительное поле размера, которое создаёт линейную сложность лишь при вставке части от другого списка.
Однако при вставке другого списка целиком — сложность константна (т.к. размер вставляемого списка известен).
Исходя из структуры данных «двусвязный список», линейная сложность вставки куска из другого списка действительно «сюрприз». Но для универсальной библиотеки контейнеров это лучше, так как многие другие операции будут эффективнее. Это можно понять и простить :).
По сути «химера» это лишь дополнительное поле размера, которое создаёт линейную сложность лишь при вставке части от другого списка.
Однако при вставке другого списка целиком — сложность константна (т.к. размер вставляемого списка известен).
Исходя из структуры данных «двусвязный список», линейная сложность вставки куска из другого списка действительно «сюрприз». Но для универсальной библиотеки контейнеров это лучше, так как многие другие операции будут эффективнее. Это можно понять и простить :).
По сути «химера» это лишь дополнительное поле размера, которое создаёт линейную сложность лишь при вставке части от другого списка
Реализация понятна. Речь о внешнем поведении.
Однако при вставке другого списка целиком — сложность константна (т.к. размер вставляемого списка известен)
Какая половая разница известен нам размер или нет? У двусвязного списка вставка куска другого списка всегда константна, вне зависимости от того, представляет ли этот кусок весь список или его часть. Так что здесь никакой «прибавки» нет.
Но для универсальной библиотеки контейнеров это лучше
Для универсальной библиотеки контейнеров лучше, что в ней нет реализации двусвязного списка? Оригинальный подход — с таким надо идти в комитет по стандартизации :)
так как многие другие операции будут эффективнее
Во-первых, как я и говорил, сделать химеру легко и поверх. Во-вторых, вполне возможно, что при таких требованиях нужна другая структура данных.
Во-во-во, советы двадцатилетней давности как догмат современной разработки. Я об этом и говорю.
Мда, все больше разочаровываюсь в C++. Почему же, чтобы написать простой цикл надо так извращаться?
А если бы вы читали статью внимательнее, то заметили бы:
А как же for-цикл с обходом диапазона, появившийся в C++11?
Спешу вас обрадовать: он работает! Это, по сути, синтаксический сахар, за которым скрывается почти в том же виде наша версия с итератором, где мы фиксировали указатель end в локальной переменной до начала цикла. Так что быстродействие у него то же.
При чём тут C++? Заметьте, код корректно работает во всех версиях, дело только в производительности. Ну а то, что для написания производительного кода приходится закапываться в асм и архитектуру процессора, никогда никого не удивляло.
Возможно потому что здесь (на первый взгляд) нарушается основополагающий принцип C++ Don’t pay for what you don’t use
Мы теряем производительность из-за возможности изменять размер вектора, которая не используется. То есть платим за то, что не используем.
При этом вектор в С++ позиционируется как безопасная замена массива из С, работающая без потери производительности.
Мы теряем производительность из-за возможности изменять размер вектора, которая не используется. То есть платим за то, что не используем.
При этом вектор в С++ позиционируется как безопасная замена массива из С, работающая без потери производительности.
Так вектор и не теряет. Немного маскирует. На чистом uint8_t* вы получите ту же самую беду с алиасингом, если не как автор в примере с указателем передадите по значению, а создадите свой struct с указателем и длинной и передадите указтель на этот самый struct. Это очень часто используется в C для всевозможных массивов и буферов и точно так же стреляет.
UFO just landed and posted this here
В коде написаны явные вызовы size() и оператора индексирования [] для каждого элемента массива. Для такой простой операции как увеличить на 1 — это может быть довольно накладно.
Код работает даже лучше, чем написан. В чём извращение? :)
Код работает даже лучше, чем написан. В чём извращение? :)
Не надо. Это как-раз хорошая иллюстрация на тему преждевременной оптимизации. Не нужно всегда и везде добиваться предельно возможной скорости. Только если профайлер показал в таком цикле hot spot, только в этом случае нужно «извращаться», как вы выразились. Но тогда это уже придется делать на любом языке, иной раз с гораздо большими затратами по сложности и времени.
Спасибо за перевод. У меня появился ещё один аргумент в войне за возвращение strict aliasing в проект. К сожалению сейчас по причинам зависимостей и глубокой истории включен -fno-strict-aliasing. Он вообще абсурдно популярен. С одной стороны люди не хотят разбираться с правилами и багами оптимизированного билда, но с другой иногда существенно теряют в производительности, что и показано в статье.
Он вообще абсурдно популярен.Реальность, к сожалению, такова, что очень много кода ломается при строгом алиасинге разными неочевидными способами (когда-то обсуждали в этом топике).
Интересно. Проверил исходную версию кода на gcc 9.2 и i7-8700, результаты совсем другие:
- O1
8-bit test: 0.051112 ms
32-bit test: 0.059481 ms - O2
8-bit test: 0.008815 ms
32-bit test: 0.006372 ms - O3
8-bit test: 0.000545 ms
32-bit test: 0.00189 ms - O3 + march=native
8-bit test: 0.000387 ms
32-bit test: 0.001062 ms
Да и на gcc 8 восьмибитная версия быстрее получается...
Нет возможности запустить бенчмарк, но дизасм на gcc 9.2, да и на любом другом, такой же, как у автора статьи: godbolt.org/z/VtCGU4
PVS-Studio умудрились набросать интересную статью так ни разу и не вставив картинку с единорогом :) Удивительно.
Хочу заметить что с range-based for компилятор генерирует код такой же как ваш лучший вариант https://gcc.godbolt.org/z/f84s8e .
UFO just landed and posted this here
Очевидно — нельзя будет менять вектор и код не скомпилируется.
Не поможет даже теоретически. Наличие const-квалификаторов не влияет на оптимизацию кода, насколько я знаю.
UFO just landed and posted this here
UFO just landed and posted this here
В С++ приняты два понятия неизменяемости — "логическая" и "физическая".
Даже ключевое слово сделали для таких фокусов.
Не очень понятно, что даст возможность вектора только расти в плане безопасности, ведь наступит реаллокация и всё.
UFO just landed and posted this here
- Каким образом?
- Вектора растут не монотонно.
- При итерации по индексу, как в статье, действительно поможет. Для итераторов — нет.
- Рост — это монотонное изменение размера по определению.
в многопоточной среде?
Конкретно в примере из статьи да, добавление элементов в конец вектора из другого потока ничего не сломает. В чуть более сложном случае может и сломать, так что в целом предложение PeterK я тоже не совсем понимаю.
лучше на std::array, но это уже другая история
UFO just landed and posted this here
Ох, тут SIMD'у есть где разгуляться
А почему в вынесении v.size() за пределы цикла мы на компилятор не полагаемся, но при этом верим что i++ это правильно?
Потому что про i++ компилятор имеет и прав, и возможность убрать лишние операции, превратив в ++i, а v.size() выносить за пределы цикла нет. Если я, конечно, правильно понял вашу претензию к i++
Конкретно для POD типов компилятор так умеет. На остальных классах это не всегда возможно из-за природы постинкремента.
Некоторые программисты считают что лучше выработать у себя дефолтный стиль кода, который правильный в большем числе случаев (например по умолчанию всё конст, по умолчанию прединкремент, по умолчанию всегда RAII etc). И пост инкремент использовать только в том контексте, где он имеет смысл.
Некоторые программисты считают что лучше выработать у себя дефолтный стиль кода, который правильный в большем числе случаев (например по умолчанию всё конст, по умолчанию прединкремент, по умолчанию всегда RAII etc). И пост инкремент использовать только в том контексте, где он имеет смысл.
Надо бы ещё в хабы «Ассемблер» и «Высокая производительность» — чуть не пропустил статью из-за этого.
давно для себя усвоил, если память позволяет, то нужно работать в родной размерности вычислительной системы, уменьшать смысла нет. Это я про МК
Sign up to leave a comment.
Инкремент элементов вектора