LINUX.ORG.RU

Ranged for vs Indexed for

 


1

5

Что в должно быть быстрее на arm для контейнера std::vector<T>?

Ranged for:

std::vector<SomeStruct> vec;
for (const auto& v : vec)
{
  // do something with v
}


Indexed for:
std::vector<SomeStruct> vec;
for (size_t i = 0, size = vec.size(); i < size; i++)
{
  const auto& v = vec[i];
  // do something with v
}


Мои синтетические замеры дают приблизительно одинаковые результаты. Профилирование под xcode показывает странные результаты - indexed for получается иногда сильно быстрее, чем range for.
Самостоятельно выводы сделать не получается, надеюсь на коллективный разум ЛОРа.

★★★★★
Ответ на: комментарий от aureliano15

Ну, в данном случае речь не об Intel, а об arm, как я понял.

Все верно. На x86, даже код транслированный из C++ в JavaScript, прожевывает все это легко.

Разумеется, я не готов утверждать, что arm-аналог не врёт.

Не думаю, что я способен посчитать накладные расходы цикла лучше, чем это сделает профайлер, написанный специалистами в этой области.

А если бы убедился в обратном, то продолжил бы чесать репу. :-)

Я, пожалуй, отвлекусь на другую задачу, коих в этом проекте все еще выше крыши :)

andreyu ★★★★★
() автор топика
Ответ на: комментарий от andreyu

Не думаю, что я способен посчитать накладные расходы цикла лучше, чем это сделает профайлер, написанный специалистами в этой области.

У профайлера более глобальные задачи: он показывает общую статистику, используя точки останова или что-то вроде того. А простая вставка в код 2 ассемблерных команд: перед и после нужного блока и вывод разницы — очевидно проще, точнее и надёжнее, хотя глобальную статистику по всему приложению не предоставляет.

aureliano15 ★★
()
Ответ на: комментарий от andreyu

Because I removed

const auto& v = x[i];
q += v;
and replaced it with
q += x[i];

auto is evil!!! its makes code write only, really hard to comeback after several month to code that uses auto and read it.

Also, it makes hard for compiler to optimize code

CyberK
()
Ответ на: комментарий от CyberK

Because I removed [skip] and replaced it with

Вот и ответ. Всегда не доверял этим вашим auto, но не из-за производительности, а из-за нечитабельности: язык превращается в какой-то нетипизированный бейсик. А он оказывается ещё и тормозит... вон оно как.

aureliano15 ★★
()
Ответ на: комментарий от andreyu

Чем std::vector<T> хуже T[]?

Ничем. Это просто обёртка над сишным массивом.

А является ли простое итерирование узким горлышком? :)

a1batross ★★★★★
()
Ответ на: комментарий от a1batross

Чем std::vector<T> хуже T[]?

Ничем. Это просто обёртка над сишным массивом.

Уточню: над динамически распределённым массивом в общем случае.

А является ли простое итерирование узким горлышком? :)

Обычно циклы, если они достаточно длинные, являются узким горлышком.

aureliano15 ★★
()
Ответ на: комментарий от aureliano15

Профайлер может вставлять перед каждым вызовом функции/метода вызов своего обработчика, время работы которого ему известно. Тем самым он имеет возможность достаточно точно посчитать время работы функции. Но как это работает в реальности мне неизвестно.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от CyberK

Because I removed ... and replaced it with ...

Непонятно, почему компилятор генерировал разный код в этих случаях?

auto is evil!!! its makes code write only, really hard to comeback after several month to code that uses auto and read it.

Тем не менее, это вполне удобно в таких случаях:

const auto size = vec.size();

auto idx = decltype(size);

auto& v = vec[idx];

auto it = vec.begin();

auto a = any_cast<T*>(some_ptr);


Also, it makes hard for compiler to optimize code

Но почему? Компилятор же сам выводит тип, а значит вольности у него больше.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от andreyu

Тем не менее, это вполне удобно в таких случаях:

А чем удобнее писать auto вместо int/float/anytype? Чтоб потом листать код и смотреть, а что за тип у массива, элемент которого присваивается ссылке типа auto, вместо того, чтобы сразу это увидеть?

aureliano15 ★★
()
Ответ на: комментарий от CyberK

Because I removed

Попробовал сделать auto& v = x[i]; вместо const auto& v = x[i];. Получил противоположный результат. Можно ли сделать вывод, что виновато const auto, а не auto само по себе?

andreyu ★★★★★
() автор топика
Ответ на: комментарий от a1batross

Ничем. Это просто обёртка над сишным массивом.

О чем и речь, stl сам по себе не является проблемой.

А является ли простое итерирование узким горлышком? :)

Нет, узким горлом является алгоритм. Но мне не хватает ума избавиться некоторой математики. Я и так оптимизировал расчеты достаточно сильно. Захотел экономии на спичках.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от aureliano15

Обычно циклы, если они достаточно длинные, являются узким горлышком.

За счёт кода выполняемого на одной итерации. Сам переход к следующему элементу играет слишком незначительную роль.

a1batross ★★★★★
()
Ответ на: комментарий от andreyu

Захотел экономии на спичках.

А если компилятор или стандартная библиотека обновятся? И будет наоборот?

a1batross ★★★★★
()
Ответ на: комментарий от aureliano15

А чем удобнее писать auto вместо int/float/anytype?

Запись получается лаконичнее и проще для чтения. Как пример auto it = vec.begin(); вместо std::vector<T>::iterator it = vec.begin(); (или объявление где-либо альяса на этот тип итератора).

Чтоб потом листать код и смотреть, а что за тип у массива, элемент которого присваивается ссылке типа auto, вместо того, чтобы сразу это увидеть?

А зачем объявлять переменную где-то далеко от ее использования? И в каком из приведенных мною выше примеров вы не можете определить тип?

andreyu ★★★★★
() автор топика
Ответ на: комментарий от a1batross

Обычно циклы, если они достаточно длинные, являются узким горлышком.

За счёт кода выполняемого на одной итерации. Сам переход к следующему элементу играет слишком незначительную роль.

Согласен. Но всё-таки, имхо, это такое место, которое стоит оптимизировать наиболее тщательно. Тем более, что разных циклов над разными типами и с непохожей обработкой может быть очень много, а способ итерации как правило везде схожий.

aureliano15 ★★
()
Ответ на: комментарий от a1batross

Сам переход к следующему элементу играет слишком незначительную роль.

Профайлер говорит, что operator!=() слишком дорого мне обходится.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от a1batross

А если компилятор или стандартная библиотека обновятся? И будет наоборот?

А если электричество пропадет? Это же не повод не пользоваться им сейчас.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от andreyu

пример auto it = vec.begin(); вместо std::vector<T>::iterator it = vec.begin();

Согласен. Хотя как по мне, проще typedef (там в самом названии алиаса можно заложить сакраментальный смысл), но это уже дело вкуса.

А зачем объявлять переменную где-то далеко от ее использования?

В принципе, да. Но по мне это как в языках, где нет типизации, заменять её комментарием типа // это int. Часть недостатков языка снимает, но костыль.

И в каком из приведенных мною выше примеров вы не можете определить тип?

Ну, например, в этих:

auto& v = vec[idx];

auto it = vec.begin();

Понятно, что это примеры. В полном коде скорее всего где-то недалеко описывался бы и сам vec. Но без auto даже выдернутый из кода кусок, как эти 2, был бы понятнее.

aureliano15 ★★
()
Ответ на: комментарий от aureliano15

Согласен. Хотя как по мне, проще typedef (там в самом названии алиаса можно заложить сакраментальный смысл), но это уже дело вкуса.

До появления auto так и приходилось делать. Но это менее удобно. Кроме того самому нужно помнить об этом альясе, а читающему нужно о нем как-то узнать.

Ну, например, в этих:

А зачем в этих примерах вам нужно знать тип? В первом примере вероятно ссылка на какую-то структуру. Во втором примере итератор.

Чем на ваш взгляд запись SomeType& v = vec.[idx]; удобнее записи с auto?
Единственное, что приходит в голову - переход на описание типа делается на один хоткей дольше (даже если вы используете vim). А пользователи ide увидят тип наведя мышкой (тем более, что они все равно руку держат на мышке).

andreyu ★★★★★
() автор топика
Ответ на: комментарий от aureliano15

В принципе, да. Но по мне это как в языках, где нет типизации, заменять её комментарием типа // это int. Часть недостатков языка снимает, но костыль.

Я, к примеру, использую auto там, где читабельность не теряется: итератор, явный каст, получение ссылки на элемент контейнера, создание/получение указателя на некий объект. Наверное где-то еще использую, но сходу не вспомню, поскольку делается это все на автомате.

Пока писал этот пост, вспомнил занятную вещь - «венгерская нотация». Я когда-то по глупости использовал «системную венгерскую»:

char szVar[]; // ясен только тип переменной, но не ее назначение
unsigned long ulVar; // аналогично


вместо «венгерскую для приложений» (иначе говоря, «венгерская для людей»):
float spriteWidth; // ширина спрайта
int currentPage; // индекс текущей страницы


В итоге в коде было ясно какого типа переменная, но читать такое говно было крайне сложно. Хотя в Майкрософт считали, что код должен выглядеть как говно и использовали именно «системную венгерскую».

andreyu ★★★★★
() автор топика
Ответ на: комментарий от andreyu

В примере ниже, std::vector<T>.size() вызывается только один раз, а область видимости ограничена циклом:

Блин, точно. Я с утра читал через одно место и не увидел, что первая вычисление size() в инициализационной части. Сорян.

Dudraug ★★★★★
()
Ответ на: комментарий от Dudraug

Я с утра читал через одно место и не увидел, что первая вычисление size() в инициализационной части. Сорян.

Бывает. В моем случае косяк был эпичнее - я в своем примере написал vec[idx] = vec[--size]; вместо vec[idx] = vec.back();. А потом свой ошибочный пример сравнил с vec.clear();.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от andreyu

Чем на ваш взгляд запись SomeType& v = vec.[idx]; удобнее записи с auto?

SomeType ничем не удобнее. А запись Coord& v = vec[idx] сразу намекает, что в векторе лежат какие-то координаты.

переход на описание типа делается на один хоткей дольше (даже если вы используете vim).

Я ни vim'ом для написания программ не пользуюсь, ни ide (за исключением случаев, когда нужна форма ui), предпочитая относительно простые, но всё-таки графические текстовые редакторы. Тут в параллельном треде vim обсуждают. В своё время я много хорошего для программистов про emacs слышал, но так и не дошли руки его нормально освоить. Они в плане юзабельности примерно одинаковы, или один однозначно лучше другого, или есть свои плюсы и минусы и у того, и у другого?

Пока писал этот пост, вспомнил занятную вещь - «венгерская нотация». Я когда-то по глупости использовал «системную венгерскую»: char szVar[];

Я по возможности (без фанатизма, конечно) стараюсь начинать имена числовых переменных с n, а строк с s. Индексы i, j, k. Но, конечно, цепочки типа lptrStrZ* не использую. :-) И да, назначение переменной важнее типа, особенно когда по назначению можно догадаться и о типе.

aureliano15 ★★
()
Ответ на: комментарий от aureliano15

А запись Coord& v = vec[idx] сразу намекает, что в векторе лежат какие-то координаты.

А вот вариант, более близкий к реальности: auto& c = m_coords[idx];. Мне он явно дает понять, что будет в c ;)

или один однозначно лучше другого, или есть свои плюсы и минусы и у того, и у другого?

Для меня vim лучше emacs. Для кого-то другого это будет иначе. Мои попытки перебраться на emacs успехом не увенчались. Хотя я честно пытался это сделать (в основном из-за хвалебных од приверженцев емакса). Но вим меня держит своей навигацией и удобством работы с текстом.

Я по возможности (без фанатизма, конечно) стараюсь начинать имена числовых переменных с n, а строк с s. Индексы i, j, k. Но, конечно, цепочки типа lptrStrZ* не использую. :-)

Значит вы используете какой-то вариант «системной венгерской». Никакой полезной нагрузки эти префиксы не несут, а сложность чтения увеличивают.

И да, назначение переменной важнее типа, особенно когда по назначению можно догадаться и о типе.

Да, и такая нотация называется «венгерская для приложений» :)

andreyu ★★★★★
() автор топика
Ответ на: комментарий от andreyu

А запись Coord& v = vec[idx] сразу намекает

А вот вариант, более близкий к реальности: auto& c = m_coords[idx];

Тоже верно.

Для меня vim лучше emacs. Для кого-то другого это будет иначе. Мои попытки перебраться на emacs успехом не увенчались. Хотя я честно пытался это сделать (в основном из-за хвалебных од приверженцев емакса). Но вим меня держит своей навигацией и удобством работы с текстом.

Понял, спасибо за информацию. Значит, если дойдут руки, начну с vim'а. Тем более, что мне он привычней (правда, используется исключительно за неимением лучшего на серверах через ssh, команды i, a, esc, d, /, ?, n, N :w и :q, клавиши, заменяющие стрелки, уже забыл, т. к. в большинстве реализаций можно использовать стрелки, вот сегодня из соседнего треда про f узнал).

Значит вы используете какой-то вариант «системной венгерской». Никакой полезной нагрузки эти префиксы не несут, а сложность чтения увеличивают.

Не готов пока с этим ни соглашаться, ни оспаривать. Надо будет подумать.

aureliano15 ★★
()
Ответ на: комментарий от aureliano15

Значит, если дойдут руки, начну с vim'а.

Будьте готовы к отладке в gdb/lldb. На данный момент для вима нет адекватной интеграции с отладчиком.

клавиши, заменяющие стрелки, уже забыл

h j k l, а стрелки у меня отключены, что бы не было соблазна :)

Не готов пока с этим ни соглашаться, ни оспаривать. Надо будет подумать.

Я когда-то тоже считал такую нотацию удобной.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от andreyu

Значит, если дойдут руки, начну с vim'а.

Будьте готовы к отладке в gdb/lldb. На данный момент для вима нет адекватной интеграции с отладчиком.

Она мне и не нужна. Использую gdb из консоли.

h j k l, а стрелки у меня отключены, что бы не было соблазна :)

А зачем отключены, если не секрет? Т. е. чтобы запомнить эти клавиши, отключить имеет смысл. Но когда уже запомнил?..

aureliano15 ★★
()
Ответ на: комментарий от aureliano15

Она мне и не нужна. Использую gdb из консоли.

Тогда все хорошо. А если вы используете tmux, то вообще прекрасно :)

А зачем отключены, если не секрет? Т. е. чтобы запомнить эти клавиши, отключить имеет смысл. Но когда уже запомнил?..

На самом деле отключать их нет смысла. Тем более, что тянуться до arrow keys неудобно.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от andreyu

А если вы используете tmux, то вообще прекрасно :)

Вот за это спасибо. Слово такое слышал, но как-то не придавал значения. А сейчас глянул — действительно удобно. В konsole можно сделать кучу вкладок и переключаться между ними, но так, чтоб несколько терминалов сразу на одном экране — этого в konsole нет.

aureliano15 ★★
()
Ответ на: комментарий от andreyu

«иногда»

А в каком окружении происходит замер?

Имеется мысль, что как минимум ядро цпу должно быть целиком отдано такого вида бенчамарку, дабы контекст не переключался. По хорошему надо считать ещё распределение сколько стоит виток цикла в 90;70;50% случаев например.

По поводу замеров с минимальной стоимостью см. rdtsc, правда под arm похоже всё чуть сложнее(за неимением сей инструкции), но должен быть интристик подходящий.

Как ни странно, если не пустой цикл гонять (правда на x86_64 замерялось) быстрее всего оказывается вариант когда итерируешься по выделенной под вектор памяти с помощью обычных указателей. Варианты с индексом и итератором пусть и не сильно, но сливают(врать не буду, цифры уже не помню).

pon4ik ★★★★★
()
Ответ на: комментарий от aureliano15

Кроме того, tmux можно интегрировать с vim (ну или наоборот, зависит от точки зрения).

andreyu ★★★★★
() автор топика
Ответ на: комментарий от pon4ik

А в каком окружении происходит замер?

Тот замер делался на iphone 7.

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

Еще большей синтетикой попахивает :)

По поводу замеров с минимальной стоимостью см. rdtsc, правда под arm похоже всё чуть сложнее(за неимением сей инструкции), но должен быть интристик подходящий.

В этой ветке уже обсуждали этот вопрос. Мое кунг-фу недостаточно прокачано для проведения таких тестов.

Как ни странно, если не пустой цикл гонять (правда на x86_64 замерялось) быстрее всего оказывается вариант когда итерируешься по выделенной под вектор памяти с помощью обычных указателей. Варианты с индексом и итератором пусть и не сильно, но сливают(врать не буду, цифры уже не помню).

Чисто теоретически это вполне логично. Итерация по указателю быстрее инерции по индексу, которая, в свою очередь, быстрее итерации по итератору.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от aureliano15

Потому что этот анонимус — баненый-перебаненый Сережа Марков: мальчик, у которого смайликов в тексте куда больше извилин в мозгах. Его «мнение» интересно только профессиональным психиатрам, наблюдающим наследственную дегенерацию лобных долей мозга, ответственных за то, чтобы пациент смог молчать, когда его мнение некомпетентно.

unanimous ★★★★★
()
Ответ на: комментарий от andreyu

Еще большей синтетикой попахивает :)

Ну это да, но если делать синтетику то только через матумбуtaskset(или что там под айось есть).

По поводу профилирования в условиях реального выполнения - есть два подхода:

сэмплерный - раз в n времени посмотреть где прога живёт, потом, отсортировать по частоте попаданий. Крайне не точный, хорошо подходит для анализа производительности i/o и других активностей где порядок времени выполнения начинает измерятся с микросекунд. Это всякие perf, oprofile, профилировщик в студии

инструментальный - тем или иным способом участки кода оборачиваются в эффективные замеры времени и эффективное сохранение этих замеров, либо подсчёт статистики на месте (без накопления всех замеров). Единственный адекватный вариант если начал считать десятки микросекунд и ниже. Это gprof, callgrind(использует виртуализацию насколько я знаю не использовал его кроме как потыкать), easy_profiler и куча самопальных лясов(моё любимое :)).

Как там профилирует xcode я не вкурсе, но если там сэмплерный профайлер, то сиё есть пальцем в небо он у тебя на другой машине/телефоне при другом запущенном ПО покажет другие результаты скорее всего при оценке таких тонких материй как скорость итерации цикла.

Я вот думаю прикрутить к текущей поделке easy_profiler. Ибо наконец то есть возможность юзать свежие стандарты. Надеюсь это не будет таким же разочарованием как spdlog.

pon4ik ★★★★★
()
Ответ на: комментарий от andreyu

And now imagine that I am developer that need to maintain this line of code after you. So I open the code and see

auto& c = m_coords[idx];
In next line I'll probably want to do something with this c. But is it Vector2, Vector3, PointIdx, what kind of data type is it? What can I do with it? It's hard to tell unless I am familiar with the code, or jump to vector declaration to read and understand. And in case of explicitly type instead of auto my life would be much easier. I have much more info about the task in same line. This is what I call «write only»

CyberK
()
Ответ на: комментарий от andreyu

Если компилятор докажет, что размер контейнера не будет меняться внутри цикла.

Переменная запросто может оказаться в регистре. Но ведь это поле как раз будет меняться вместе с размером контейнера, ведь оно же должно отражать текущий размер.

Переменная запросто может оказаться в регистре.

Окей, тогда может оказаться и медленнее.

f1u77y ★★★★
()
Ответ на: комментарий от aureliano15

так, чтоб несколько терминалов сразу на одном экране — этого в konsole нет

Есть View → Split View, но оно по мне менее удобное, чем аналогичная функциональность tmux.

f1u77y ★★★★
()
Ответ на: комментарий от andreyu

Вот и ответ. Всегда не доверял этим вашим auto

Ну не все так однозначно:
Ranged for vs Indexed for (комментарий)

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

Вот несколько бенчмарков, код которых отличается только отступом слева строки const auto& v = x[i];:

http://quick-bench.com/8tXM_DBFh3F4wSnl-zy8sjHnKDE

http://quick-bench.com/mBRcAF79cbG76pI5QGUo2BHtMtw

http://quick-bench.com/hb3xATTRdzF3hjRwY9ywGPzjC5A

http://quick-bench.com/8DkPXk_iyy6QsSBCjTGoEmc4jGw

http://quick-bench.com/Ss-YGFhfuQvnj2gVgrCqBS8pYQY

Т. е. ни auto&, ни const auto& тут ни при чём. Просто при самом первом тесте const auto& случайно выполнился значительно медленнее, чем обычно, и результат навсегда был сохранён на сервере. При дальнейших нажатиях на эту ссылку или даже повторном вводе того же самого кода, бенчмарк не выполняется, а достаётся однажды сохранённое значение. Но стоит изменить исходный текст (например, добавить лишний пробел), и мы получим совершенно другой результат. :-)

Также хочу поделиться этой радостной вестью с lberserq и CyberK. Интересно, как послать автору баг-репорт?

aureliano15 ★★
()
Ответ на: комментарий от f1u77y

так, чтоб несколько терминалов сразу на одном экране — этого в konsole нет

Есть View → Split View, но оно по мне менее удобное, чем аналогичная функциональность tmux.

Вот ведь как оно бывает: пользовался konsole со времён kde3 и не знал об этом. :-) А действительно есть. И действительно менее удобно, чем tmux (там можно создавать любые комбинации, используя вертикальные и горизонтальные разделители, а в konsole у меня получилось использовать только либо вертикальные, либо горизонтальные). Спасибо за инфу.

aureliano15 ★★
()
Ответ на: комментарий от andreyu

На самом деле отключать их нет смысла. Тем более, что тянуться до arrow keys неудобно.

Вы как и тот аноним, не умеющий читать тему топика? Я в своем сообщении четко написал, что меня интересует и в чем я просил разум ЛОРа помочь разобраться.

i-rinat ★★★★★
()
Ответ на: комментарий от andreyu

Ну так предложите свой правильный вариант.

Пожалуйста :-)

  size_t left = 0, right = vec.size();
  while (left < right) {
    const size_t diff = right - left;
    vec[diff - 1] = vec[right - 1];
    ++left, --right;
  }
  vec.resize(right);

Лол :-)

anonymous
()
Ответ на: комментарий от CyberK

Допустим, есть такая структура:

struct ChooseAdequateNameForThisStruct
{
  uint32_t someId;
  time_t timestamp;
  size_t dataSize;
  uint8_t* data;
};
std::vector<ChooseAdequateNameForThisStruct> someAdequateContainerName;


Как ухудшается читабельность кода с
auto& v = someAdequateContainerName[idx];
и как улучшается читабельнсть с
ChooseAdequateNameForThisStruct& v = someAdequateContainerName[idx];
?

andreyu ★★★★★
() автор топика
Ответ на: комментарий от aureliano15

При дальнейших нажатиях на эту ссылку или даже повторном вводе того же самого кода, бенчмарк не выполняется

Там есть опция для сброса кеша.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Вы как и тот аноним, не умеющий читать тему топика? Я в своем сообщении четко написал, что меня интересует и в чем я просил разум ЛОРа помочь разобраться.

Мой топик, мои правила.

andreyu ★★★★★
() автор топика
Ответ на: комментарий от andreyu

Там есть опция для сброса кеша.

Да. Вот прямо только что заметил. За несколько минут до того, как прочитал это сообщение. Но всё равно это не отменяет того факта, что работают оба варианта примерно одинаково. Хотя мне удалось второй раз воспроизвести разные результаты, и снова не в пользу константного индекса.

aureliano15 ★★
()
Ответ на: комментарий от aureliano15

Ну да, результаты получаются разные. Похоже зависит от ветра на луне.

andreyu ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.