Join Yalantis and get a $1000 sign-in bonus! React.js, React Native, Python, Java, DevOps, BА. Apply now!
×Закрыть

Странное выполнение С++ кода

Может кто сталкивался или может обьяснить в чем может быть дело.
Есть две версии одного и тогоже кода.
Для замеров оба куска кода 10М итераций.

bool HArrayFixRAM::insert(uint* key, uint value)
{
	if (pLastContentCell + RowLen > pLastContentCellOnLastPage)
	{
		ContentPage* pLastContentPage = new ContentPage();

		pContentPages[ContentPagesCount++] = pLastContentPage;

		if (ContentPagesCount == ContentPagesSize)
		{
			reallocateContentPages();
		}

		pLastContentCell = pLastContentPage->pContent;
		pLastContentCellOnLastPage = pLastContentCell + MAX_SHORT;
	}

	//insert value ============
	uint keyOffset = 0;

	uint headerOffset = key[0] >> HeaderBits;
	ContentCell* pContentCell = pHeader[headerOffset];

        if (!pContentCell)
	{
		pHeader[headerOffset] = pLastContentCell;

		pLastContentCell->Type = (ONLY_CONTENT_TYPE + KeyLen);

		//fill key
		for (; keyOffset < KeyLen; keyOffset++, pLastContentCell++)
		{
			pLastContentCell->Value = key[keyOffset];
		}

		pLastContentCell->Value = value;
		pLastContentCell++;

		return true;
	}
	
	return true;

Эта версия выполняется около 850 мсек.

Ровно такая же версия, но на один блок выполнения длинее
(if закомментирован в середине).

bool HArrayFixRAM::insert(uint* key, uint value)
{
	if (pLastContentCell + RowLen > pLastContentCellOnLastPage)
	{
		ContentPage* pLastContentPage = new ContentPage();

		pContentPages[ContentPagesCount++] = pLastContentPage;

		if (ContentPagesCount == ContentPagesSize)
		{
			reallocateContentPages();
		}

		pLastContentCell = pLastContentPage->pContent;
		pLastContentCellOnLastPage = pLastContentCell + MAX_SHORT;
	}

	//insert value ============
	uint keyOffset = 0;

	uint headerOffset = key[0] >> HeaderBits;
	ContentCell* pContentCell = pHeader[headerOffset];

//COMMENTED HERE, BLOCK WILL BE EXECUTED ALWAYS
//if (!pContentCell)
	{
		pHeader[headerOffset] = pLastContentCell;

		pLastContentCell->Type = (ONLY_CONTENT_TYPE + KeyLen);

		//fill key
		for (; keyOffset < KeyLen; keyOffset++, pLastContentCell++)
		{
			pLastContentCell->Value = key[keyOffset];
		}

		pLastContentCell->Value = value;
		pLastContentCell++;

		return true;
	}
	
	return true;

Вдруг работает в два раза быстрее, всего 405 мсек о_О.
По логике ведь все должно быть наоборот. Второй кусок кода на целый блок комманд выполнения длинее.
Чую както все это связано с ковеером проца, кешами L1/L2, но пока не представляю как это все можно связать. Может у кого есть простое обьяснение, почему так произошло.

👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn

Похожие топики

Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Глупый вопрос: а ты что, ищешь положение ключа простым перебором? И после этого ещё жалуешься на производительность?

Там все сложно, подробнее можно глянуть здесь github.com/Bazist/HArray
Это малая малая часть оптимизированной реализации Trie. Переборы только там где в бранчах до 4 элементов, тоесть там где это оправдано

Если там четыре элемента — зачем тебе цикл? И почему до 4, а не до 16 к примеру?
И смысл тогда вообще строить таблицу ключ -> значение, если можно тупо реализовать поиск по ключу перебором массива, а ключ сделать полем самого объекта, если его там ещё нет? Вплоть до того, что массив делать гарантированного размера, просто заполнив нулями и храня размер.

Но есть вариант что я просто не совсем понимаю алгоритм пока не сталкивался с Trie. Однако всё равно, по описанию он мне показался оптимизированным на куда большие объёмы.

Но есть вариант что я просто не совсем понимаю алгоритм пока не сталкивался с Trie. Однако всё равно, по описанию он мне показался оптимизированным на куда большие объёмы.

Здесь есть описание
github.com/...​ter/Trie_for_beginners.md

compiler optimized out

ContentCell* pContentCell = pHeader[headerOffset];

Ещё одна неочевидная проблема — два оператора return. Отсюда компилятор считает ветки независимыми. Сделай один, оцени разницу.

А вот сейчас разработчикам компиляторов было действительно обидно ;D

Вот ничего не могу сказать о компиляторах. Но два return — это чаще всего таки два return.Ничего особенно плохого в этом нет для прикладного программирования. Но когда речь идёт об оптимизации линейных алгоритмов — таки надо понимать, как это будет исполняться процом. Я уверен, что для проца это предсказание альтернативного перехода, притом достаточно далеко чтобы сорвать конвейризацию.

В любом случае ПРОВЕРИТЬ не сложно. Я бы на компилятор точно не надеялся. Мне проще написать в коде чего я хочу, чем заниматься предсказаниями на кофейной гуще.

подобное встречал в go, где после добавления доп. if’а для избежания лишних присваиваний и т.п., оно резко медленнее раза в 2-3 стало (2 точно). операций 5-6 до ифа и внутри ифа было операции 3-4, в основном присваивания. ифом хотел уменьшить количество выполняемых инструкций...

подобное встречал в go

дальше не читал

Во втором случае нет доступа на чтение в pHeader, только на запись. Может быть(?) какая-то мутка с кешами, когда чтение после записи дампит кеш, а несколько записей подряд возможны без дампа.

Мсье, которые знают толк, компилируют оба куска кода с флажками для максимальной производительности и сравнивают получившийся асемблерный код. Для достижения дзена можно обратиться на stackoverflow.

Все тоже самое.
Было

unsigned int headerOffset = key[0] >> 8;
0135100D mov ecx,dword ptr [eax]
0135100F shr ecx,8

if (!pHeader[headerOffset])
01351012 cmp dword ptr [eax+ecx*4],0
01351016 jne main+1Fh (0135101Fh)
{
pHeader[headerOffset] = 1;
01351018 mov dword ptr [eax+ecx*4],1

Стало

unsigned int headerOffset = key[0] >> 8;
00C9100D mov ecx,dword ptr [eax]
00C9100F shr ecx,8

//if (!pHeader[headerOffset])
{
pHeader[headerOffset] = 1;
00C91012 mov dword ptr [eax+ecx*4],1
}

Как оно еще может скомпилироваться ? Разница естественно только в cmp и условном переходе jne. Все основные фокусы начинаются на конвеере с опережающим выполнением.

Там много кода под ифом. Не думаю, что конвейер одного ифа может всю функцию тормознуть в 2 раза. Надо смотреть в работу с кешами.

Попробуйте во втором варианте вставить __sync_synchronize (или какой там у Вас компилер) и сравнить скорость первого без барьера и второго с барьером.

Как оно еще может скомпилироваться.

Никогда не берусь угадывать, на какие трюки способен компилятор. Почему LLVM может вызвать никогда не вызываемую функцию? (смотреть раздел Примеры некоторых интересных оптимизаций в LLVM). Я удивился и расширил свой кругозор после ознакомления со статьей. Если в асемблерном коде причина тормоза не очевидна, вряд ли рядовой разработчик сможет ее объяснить. Для этого нужно иметь обширные знания по устройству процессорров. «Причиной всему cache-miss», «это очевидно фокус на конвеере», «стопудово branch misprediction» являются хорошими догадками, но предсказать (и доказать!) что происходит на самом деле крайне трудно. Да и мне кажется излишним.

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

Да и мне кажется излишним.

Если не заниматься практическим граблеведением, то не научишься грабли обходить.

Так вроде как уже разобрался. Мне достаточно что с мат точки зрения это уже две разные задачи. Одна требует последовательного выполнения, вторая может паралеллится. Что там и как проектировали в процессоре, это уже вопрос второй. Если бы я проектировал блок предсказания процессора, то наверняка бы воспользовался этой особенностью и начал опережающее выполнение неконфликтующих между собой итераций.

Не надо демонизировать процессор. Сделай маленький пример и я тебе укажу точное место почему это происходит (если это возможно воспроизвести на gcc, а не только на msvc). У меня есть возможность инструментировать код с наносекундным разрешением, обычно этого более достаточно, чтобы сказать какое место нужно оптимизировать.

Ужал до минимума. Разница в выполнении около 30% blog.booben.com/...​yFix_WhatHappens_Test.zip

Схоже, що оця ваша перевірка — це cache miss якби не у половині випадків. Бо pHeader у вас здоровезний і у навіть у L3 кеш не влазить. Якщо ініціалізувати
keys[i][0] = (uint)rand();// * (uint)rand();
щоб використовувалась така його частина, що влізе у L1/L2 кеш — все починає літати.
Disclaimer: я не перевіряв тулами, що власне можуть вказувати cache miss, як VTune.

Звернення до pHeader по всій довжині є в обох варіантах.

У другому варіанті — лише запис, можна не чекати діставання значення pHeader з оперативки і взагалі його звідти не діставати, суто писати туди.

Так, але як я розумію воно повино бути туди записано фізично, без зволікань. В іншому випадку, що трапиться якщо код з іншого потоку спробує прочитати це значення.

Ні, ніяких гарантій тут нема і я сподіваюсь, що ви про це в курсі. Можете загуглити std::memory_order Взагалі коли читаєш про проблеми одночасності та причинності у concurrency — згадується релятивізм %) Але у межах одного потоку послідовність (причинність), звичайно, гарантується і якщо для цього треба вбити кеш — що поробиш.

але в цілому цікава думка.
Якщо код замінити з
pHeader[headerOffset] = pLastContentCell;
на
pHeader[headerOffset] = pHeader[headerOffset] + 1;
То знову все стає на свої місця.
Можливо це якось звязано з інвалідацією данних.

Смотри, картина такая:

gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609
1) gcc -O3 with all code compiled in: Insert: 328990 msec
2) gcc -O3 with commented out line: Insert: 328680 msec

профилировать нечего, сорри. Разницы никакой.

1) gcc -O0 with all code compiled in: Insert: 893966 msec
2) gcc -O0 with commented out line: Insert: 468734 msec

Без оптимизации похоже на твой случай. У компилятора крайняя степень амнезии при компиляции с -O0, ничего не хранится локально, никакие переменные, всё заново загружается и пересчитывается, даже headerOffset, операция доступа к pHeader[headerOffset] становится нетривиальной, каждый раз вычисляется смещение к данным класса.

Вторая проблема — рандомный доступ к памяти. Памяти огромный кусок, ни в какие кеши он не помещается. Но если ты читаешь из памяти, причём по рандомным индексам (key[0] >> 8), то каждый раз вычитывается 64 байта из памяти, из которых ты используешь только 4 или 8 в завимимости от x86/x86_64. Но так как соседствуют множество операций «не в тему», то возможно этот кешлайн будет забыт и сброшен обратно в память. Если строку закомментировать, то будет использоваться WB кеш в режиме WA (write-allocate), что быстрее, никакого чтения из рандомной памяти.

При включённом оптимизаторе чтение и запись в тот же участок — это соседние операции без промежуточных обращений к данным класса, всё происходит в рамках одного кешлайна. При следующем вызове функции будет аллоцирован новый кешлайн и так до тех пор пока они не закончатся, потому будет проседание производительности. Т.к. рандом хреноватый по умолчанию, то у меня из 10,000,000 итераций 2,500,000 пришлись по тому же кешлайну, что использовался в предыдущих операциях, а это 1/4 попаданий в кеш, что довольно таки много при таком варварском чтении и записи в память.

Никакой магии, сплошное везение (или невезение).

Кажется я начал понимать что происходит.
На самом деле этот иф в корне меняет суть алгоритма

if (!pContentCell)

Для этого всеголишь нужно взглянуть на то, как этот кусок кода вызывается в цикле

for (uint i = 0; i(знак меньше)COUNT_KEYS; i++)
{
ha.insert(keys[i], 1)
}

Так вот, пока этот иф имеется, все итерации выполняются практичекски всегда последовательно их почти невозможно параллелить. Потому что этот иф примерно по семантике «Кто первый встал, того и тапки». Если вставать все будут в разнобой (параллельно), то исход тапок будет непредсказуем.

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

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

Это возможно проверить? В смысле, как-то вывести данные в момент исполнения, чтобы этим выводом не утопить производительность ниже планки эксперимента, но увидеть есть параллелизм?

Если нет — то уже говорил, проверь этот if на незначимом коде. Очень вероятно что преобразование типа указатель -> boolean является весьма нетривиальной операцией. Это ж не C, это C++, он объектно-ориентированный да ещё и со множественным наследованием. А потому за разыменованием указателя стоит огромная махина приведения типов к нужному.

Think in Java =)
Но на самом деле тут Си и тут все иначе.

Если нет — то уже говорил, проверь этот if на незначимом коде

Любой незначимый код в релиз версии Си компилятором успешно будет выкошен.

Очень вероятно что преобразование типа указатель -> boolean является весьма нетривиальной операцией

Здесь никаких преобразований нет, поскольку для машинных комманд boolean это число. Если 0 то false, все остальное True.

А вот я бы не стал так сильно утверждать, что тайпкасты не занимают времени. Это для тебя что 0 что false — одно и то же. А у компилятора не факт, что там прямая JMZ команда генерится, может быть тайпкаст.

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

Тебе что, так сложно проверить сравнением с NULL вместо неявного тайпкаста? Вот просто взять и проверить, в одной строчке кода. Чи пан має час та натхнення?

А у компилятора не факт, что там прямая JMZ команда генерится, может быть тайпкаст.

Тайпкасты и прочья боксинги унбоксинги это для вирт машин уготованы.
В Си обычно все попроще будет. Напр. такой код скомпилится в одно и тоже

int xx = 1;
int* bbb = (int*)(bool*)(short*)(int*)(void*)&xx;

int* bbb = &xx;

М? Что не так-то?
godbolt.org/g/D9sTGY

«Что-то не так» наступает при ссылках на объекты.
«Что-то не так» наступает при тайпкасте указателя

Я не спорю, возможно компилятор это понимает и сам оптимизирует. Но возражать вместо того чтобы проверить — этого я не понимаю.

Смотря при каких ссылках, и при касте каких указателей.
Конкретно в примере автора всё будет как он написал: приведённый код скомпилится в одно и то же. Это ж просто указатели на примитивные типы, там даже при желании мудрить некуда.

Вот с кастом указателей на производные/базовые классы при множественном наследовании действительно может понадобиться выполнять некоторое смещение. «Огромной махиной», впрочем, там тоже не пахнет: это всего лишь плюс/минус какая-то константа от адреса, на который ссылается указатель.
Махина включается уже когда наследование виртуальное.

Этого может быть достаточно, чтобы компилятор вызвал упреждающий malloc рассчитывая на обработку прототипа класса. Я же говорю, неявные тайпкасты — такая вещь, которой надо избегать. Использовать их повсеместно — всё равно что бегать голым на пьяной гей-тусовке и верить что это ни о чём ещё не говорит.

Даже для самой удобочитаемости кода — да сравни автор этот указатель с NULL, и никакого тайпкаста в рантайме не будет в принципе, всё будет сделано на этапе компиляции.

ЕСТЬ РАЗНИЦА для языков с ООП и без него. В обычных С указатель вообще не объект, это целочисленное поле. Его типизация не более чем защита от дурака. Вплоть до того, что можно забыть его инициализировать и получить непредсказуемые данные (что потом оказывается уязвимостью).

Можно пример каста в C++, где компилятору будет иметь смысл вызвать упреждающий malloc (и хотя бы в двух словах объяснить, зачем ему это понадобится)?
Я вроде уже не первый год работаю на C++, но вот конкретно об этом моменте сейчас в первый раз слышу.

А также, чем отличается указатель C от указателя (НЕ указателя на член) C++?
Я всегда думал, что в C++ только указатели на члены являются сложными объектами, а просто указатели на данные (на примитивные типы или объекты классов, неважно) — это те же целочисленные поля.

На счет параллелить..
С++ компиллер ничего втихаря не парралелит и никаки потоки не создает.
Так что , если сам прогерр не постарается, то параллелизму тут неоткуда взяться.

Параллелится на уровне конвеера процессора, постоянно идёт опережающее выполнение

А что мешает задать явный параллелизм? То есть написать код таким образом, чтобы он выполнялся не кусками по одному циклу, а по восемь и более?

Да и в принципе, мне кажется тебе нужно научиться предсказывать размеры карты, и не добавлять туда элементы по одному. А к примеру, по 64К за раз, блоками. И не ключ -> указатель, а ключ -> значение. Почему так: ты экономишь одно разыменование указателя на каждом запросе, и данные тянутся не откуда-то из кучи (читай прокачиваются через оперативу с синхронизацией ядер проца), а лежат вот тут рядышком в кеше. А если ты ключ поместишь в сам объект, то тебе и карту строить не придётся, достаточно один раз отсортировать массив.

Для highload такие мелочи имеют значение. Общение проца с кешем 10-20 раз шустрее общения с оперативой. Особенно при записи. Потому операции с массивами предпочтительнее одинарных, операции с ulong предпочтительнее операций с битами, и даже тот факт что число беззнаковое имеет значение для конвейра.

PS. Кстати, а зачем тебе вообще понадобилось выносить эту хрень в отдельный метод? Как по мне, прекрасный маленький кусок кода для инлайновой функции, а то и честной вставки прямо в код. Разве что многопоточности боишься.

Почему так: вход в стек, возврат из стека — всё это геморойно для процессора. А линейный предсказуемый кусок кода — то что доктор прописал! Прежде всего за счёт попадания целиком в L1 кеш команд, даже без упреждающего исполнения это круто.

Странно, начал урезать код, до демонстрационных нескольких строк и баг вдруг пропал.
Все стало на свои места. Разбираюсь в чем фокус.

10 млн итераций всей функции или цикла в ней?

Да, совет для удобочитаемости кода: чем дальше зона видимости переменной, тем длиннее и понятнее должно быть её имя. А переменным с короткой зоной видимости надо давать короткие имена и не заморачиваться с префиксными типами — пусть эту работу делает за тебя IDE, оно лучше тебя знает где объявлены твои идентификаторы.

А вот идентификаторы вроде Type — настоящее табу для программиста, за его нарушение полагается звонок в полночь 1 января с убедительной просьбой разрулить баги. Что такое «тип» — вообще непонятно никому, даже телепатам.

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

Попробуй вывести этот же оператор if отдельной строчкой в конце, можешь добавит внутрь какого-то несущественного кода (например, засекание времени) и посмотреть что будет. Попробуй скопипастить эту строчку 20 раз и посмотреть как изменится.

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

Рискну предположить, что твой pContentCell ни разу не boolean, а указатель. И там весьма сложное преобразование типов, вероятно процессор даже предсказывает переход по этому указателю. Если так — ещё до входа в цикл вычисли это boolean значение и сделай if уже по нему. Попробуй скормить ему ключевое слово const, компилятор это учитывет при оптимизациях.

Я вообще не сильно понимаю ЗАЧЕМ ты вводишь переменную pContentCell, её значение сильно не очевидно. Что мешает сравнить значение с null? Попробуй его не вычислять, а сразу вписать
if(null==pHeader[headerOffset]){ // бла-бла-бла

pHeader[headerOffset]

его значение часто нулевое?
Эта функция выполняется параллельно 10М раз или строго последовательно?

Изначально там всегда нули. Потом случайным образом начинают по нему заполнятся значения. Примерно как хешфункция разбрасывает по хештаблице. Далее по теорвер чем дальше тем меньше вероятность попасть в пустую ячейку

В смысле, нули? Целочисленное значение, либо же там данные типа «указатель»?
Просто есть вероятность, что когда if закомменчен, то и переменная pContentCell не вычисляется, компилятор видит что нигде не использована, и просто «оптимизирует» как Кличко затраты на дороги.

Там простой кейс, классика для конвеера )

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

Вверху там простой цикл логики нет вообще. Это первое что в голове было, но я сразу отмел. Сама логика тут простая. Если ячейка в массиве пустая то записать значение, иначе пропустить и выйти.
По ассемблерному коду смотрел, вроде ничего необычного (на мои конечно весьма посредственные знания асма) но через часик я запощу что есть. Плюс если нужно могу сам проект запостить, урезанный до демонстрации этой странности

Плюс если нужно могу сам проект запостить, урезанный до демонстрации этой странности

Да, это будет лучше всего. Поздно вечером я смогу запрофайлить этот код.

Подписаться на комментарии