Pull to refresh

Comments 36

Многое непонятно, но выглядит круто!
В данной конкретно задаче вместо огромного количества перестановок, которые превращаются в изнасилование регистров полезнее было бы использовать asm инструкцию bswap, сократить количество циклов и вместо обращения buf+i обращаться к buf, и потом делать buf++. Все это для начала, конечно )
Спасибо за замечание. Можно, наверное, посвятить еще один обзор-исследование, почему этого не сделал компилятор :). Но суть поста была не совсем в том, как эффективно решить эту задачу «вручную», а как понять, что нагенерил компилятор и в чем проблемы исполнения этого кода.
UFO landed and left these words here
Ух ты, а откуда такая терминология?
UFO landed and left these words here
Когда подбирают проверочное слово, то говорят про корень слова, а не суффиксы, а корень в обоих случаях один — лин. </gramanaci>
UFO landed and left these words here
Самое близкое русское слово к «inline» в данном контексте, мне кажется, что «внутритекстовый».
Но имхо лучше вообще не переводить.
Самое близкое — встраиваемый
inline function = встраиваемая функция
Да, тоже соглашусь, что «встраиваемая» — наиболее подходящий термин, я просто о нем совсем забыл. Хотя оборот «функция была встроена компилятором» звучит как-то не очень. Может быть «вставлена» или «подставлена»…
А чем вам не нравится «встроена компилятором»?

встроена = перенесена внутрь чего-либо (в данном случае внутрь другой функции)

по сравнению с:

вставлена — она и так вставлена — не передает суть того, что именно тело функции встроилось в другую функцию

подставлена — это скорее к ситуации, когда вместо цикла
for( int i = 0; i < N;++i ) *p++ = 0;
вставляется memset, т.е. подстановка намекает на «применение частного случая», достаточно вспомнить математику: подставим х =…
«Подставлена», «раскрыта», «развернута»…
Почему компилятор настолько тупой, что при суммировании пытается заново загрузить значение из памяти, а не использует возвращённое значение функции? И почему для этапа перестановки не загружает всё в один регистр, чтобы потом одним махов выгрузить dword, а насилует память 4мя сохранениями char?
Компиляторы ещё не настолько умны? Как выглядел бы C код с учётом исправления перечисленных выше проблем?
Говоря в VisualC есть ещё дико оптимизированная инструкция bswap, заодно и с ней сравнение неплохо бы увидеть.
Компилятор пытается загрузить значение из памяти просто чтобы его получить — то, что 4 char образуют один unsigned int он почему-то не сообразил. Почему он не смог хотя бы достать big[0] и big[1] за одно обращение (и использовать потом bh и bl) — тем более непонятно.

Код на регистрах мог бы выглядеть так:
unsigned int chend2(unsigned int p){
	unsigned int res=p&0xff;
	p>>=8;	res=(res<<8)|(p&0xff);
	p>>=8;	res=(res<<8)|(p&0xff);
	p>>=8;	res=(res<<8)|p;
	return res;
}
Почему компилятор настолько тупой, что при суммировании пытается заново загрузить значение из памяти, а не использует возвращённое значение функции? И почему для этапа перестановки не загружает всё в один регистр, чтобы потом одним махов выгрузить dword, а насилует память 4мя сохранениями char?
Компиляторы ещё не настолько умны?

Я не берусь судить о том, на сколько туп компилятор, но (забыв о типах данных) насилия над памятью тут нет. Да, значение, которое получено в (встроенной) функции выгружено в память, а для суммирования выполняется загрузка по тому же адресу. Но, процессор использует store buffer чтобы вернуть выгруженные данные для вычисления, совершенно не ожидая их загрузки.
Распознавать последовательности записи и чтения невыровненных данных по одному адресу, по-видимому, компилятор пока не умеет.
Компиляторы ещё не настолько умны?

В какой-то момент я попробовал скомпилировать порядка сотни самых простых кусков кода строк по 5 одним и тем же коммерческим компилятором.

Результаты совершенно произвольные. Где-то компилятор все понимает и оптимизирует до упора — вплоть до полного удаления бессмысленного кода. Где-то он генерирует настолько тупой и прямолинейный код, что создается впечатление, что там оптимизатора нет вообще.

Объяснение разработчиков компилятора — компилятор «не обучен» выявлять такие куски. Там нет умного искусственного интеллекта со здравым смыслом на все случаи жизни, там просто набор шаблонных правил — образцов ситуаций и действий по оптимизации на эти ситуации. Ну и плюс в оптимизаторе тоже есть ошибки — не все задуманные оптимизации не всегда срабатывают.
Серьезное исследование. Правда, первое, что мне пришло в голову — unsigned int chend(unsigned int p){
return CHH[p&0xffff]|CHL[p>>16];
}

где массивы CHH и CHL заполняются заранее — работает примерно в 1.5 раза быстрее, чем перестановка и последующее суммирование.
Если честно проблема и решение целиком высосаны из пальца.

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

unsigned int change_endianess(unsigned int *big)
{
unsigned int t = *big;
unsigned int r = ((t&0xFF)<<24)|((t&0xFF00)<<8)|((t&0xFF0000)>>8)|((t&0xFF000000)>>24);
*big = r;
return r;
}
Если честно, то Вы, кажется, не поняли сути проблемы. Речь шла не о том, как написать максимально быструю имплементацию простого алгоритми, а о том, как, используя профилировщик, определить существование провала производительности и понять причину его возникновения. А как исправить, это уже совсем другая история. Мой вариант был приведен только для того, чтобы отделить проблемное чтение данных от функции перестановки в которой производилась запись.
Естественно, в Вашем варианте перестановка будет сделана в регистрах, и суммирование тоже будет в регистре. Однако, это решение подходит для моего рафинированного примера, который был редуцирован из несколько более сложного для наглядности. В реальном примере все было не так очевидно, но его приводить — значит загромождать пост длинными листингами.
Мне понятна идея. Но пример рафинирован настолько, что стал тривиальным и скучным. Не интересно смотреть использование профилировщика там где и так всё ясно. Любой кто читал документацию по оптимизации знает по ограничения store-to-load (еще со времен Pentium 4, а то и раньше).

Было бы интересно посмотреть пример, где без профилировщика реально не разобраться.

PS Я не настаиваю что мой вариант самый быстрый, но в данном случае он должен быть первым «наивным» вариантом. Т.к. преобразовывать int* в char* чтобы байты переставить это через чур.

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

Можно взять какую-нибудь популярную (или не очень) open-source программу в качестве подопытной. Будет живой пример как искать хот-споты и оптимизировать программу в целом.
Для этого программа должна быть действительно интересной, и все-равно, все занимательные случаи в ней вряд-ли будут. А те случаи, которые я рассматриваю, мы редуцируем из реальных приложений, которые вряд ли можно публично рассматривать.
У меня получилось, что оно всего на 15% быстрее, чем вариант с разделением (2.0 нс на элемент против 2.3 нс) — а никак не в три раза. Если результат не возвращать в массив, можно выиграть еще 7% (1.86 нс).
В три раза по сравнению с исходным «плохим». Вариант с разделением тоже в три раза быстрее. В итоге они примерно равны (мой и с разделением).
Но, все равно спасибо за Вашу имплементацию.
Кстати, у меня она работает только в 2 раза быстрее.
Оптимальный код:

[code]
for (i = 0; i < 1024; i++){
sum += _byteswap_ulong(*(unsigned long*)(buf+i));
[/code]
Юзайте интринсики господа.
При чтении комментариев постоянно вспоминаю Буратино. Там, где его Мальвина учила математике:
"-У вас в кармане два яблока… — Врете, ни одного…-Я говорю, предположим, у вас в кармане два яблока. Некто взял у вас одно яблоко. Сколько у вас осталось яблок?
-Два… -Почему? — БУРАТИНО: Я же не отдам Некту яблоко, хоть он дерись! "

Так и здесь — люди обсуждают учебный пример.
Ничего страшного, может стоит обратить внимание, и предложить хаброжителям интересные примеры алгоритмов для оптимизации?
Вот что значит настоящий customer orientation :) У Мальвины его не было.
А интересные примеры алгоритмов — да, будем думать.
Эх, а когда-то только такты надо было посчитать по таблице :)
По одной таблице — такты, по другой — байты. И выбрать, что важнее.
Only those users with full accounts are able to leave comments. Log in, please.

Information

Founded
Location
США
Website
www.intel.ru
Employees
5,001–10,000 employees
Registered
Representative
Виктор Гурылев

Habr blog