Оптимизируются ли тривиальные операции?

durka82

Например логические выражения не вычисляются дальше, если результат уже очевиден.
А есть ли такое для обычной арифметики?
Например умножение на 0, сложение с 0 и умножение на 1 (да и на другие степени 2-ки).
В принципе такие вещи могли бы оптимизироваться на уровне проца.
Или это все из области фантастики?
Вот например в архитектуре АРМ есть похожие вещи (условное выполнение).
Правда в этом случае они не подходят (правда я не спец по этой архитектуре - мб там есть и такие возможности).
Если таких оптимизаций нет в проце, то мб их делают на уровне компиляторов?

kruzer25

умножение на 1 (да и на другие степени 2-ки).
Если a*b - то как ты себе это представляешь? Для того, чтобы понять, надо ли что-то оптимизировать - надо понять, не является ли b степенью двойки, а на это у современных процессоров навряд ли уйдёт меньше тактов, чем на собственно умножение без всякой оптимизации.
Если a*C (C - константа) - то запросто. Например, компилятор, если видит, что C - степень двойки, тупо заменяет это выражение на a<<D.

procenkotanya

В компиляторе при возможности арифметику упрощают. В процах не силён, но знаю, что xor eax, eax точно является "особым случаем" :).

durka82

Хрен с ними - со степенями двойки.
В первую очередь интересует умножение на 0.
Даже так - известен наиболее вероятный кандидат на 0 (из двух операндов) - то есть даже если второй операнд = 0 - это переживаемо.
Или даже в такой трактовке оптимизация отсутствует?
Если a*b - то как ты себе это представляешь?
На самом деле встроить проверку равенства 0 одного из операндов умножения на уровне проца проблемы никакой (да и ресурсов тоже мало надо).
Вопрос скорее в том, есть ли процы, где это реализовано? Или этого нет?
Тогда почему нет: никому не надо, не приходило в голову, не окупается и тп?
Если a*C (C - константа) - то запросто. Например, компилятор,
Это слишком тривиальный случай.

durka82

В компиляторе при возможности арифметику упрощают
Если уж зашла речь про оптимизаторы компиляторов, спрошу: если заданы 2 выражения, у которых есть общие операции, компиляторы это оптимизируют?
Грубо:
x=a+b*c
y=b*c+d
чтобы умножение выполнилось только 1 раз.
что xor eax, eax точно является "особым случаем"
Ну тут и проверять, и выполнять нечего - результат всегда один и тот же ;)

kokoc88

Вопрос скорее в том, есть ли процы, где это реализовано? Или этого нет?
А зачем? С точки зрения языка всегда есть последовательность вычисления выражений, так что умножение f*0 или 0*f всегда будет вычислять результат f.

kruzer25

Он имеет в виду ситуацию, когда оба множителя - переменные, а не результаты вызова функций ;)

kokoc88

Он имеет в виду ситуацию, когда оба множителя - переменные, а не результаты вызова функций
Думаю, что на большинстве процессоров умножение занимает 1 такт. Так что смысла в проверках нет.

kruzer25

Ну вот.
А с "или" и "и" такая оптимизация, во-первых - для простоты разработки (чтобы можно было напистаь что-нибудь вроде fopen(...) or die('shit happens' а во-вторых - чтобы оптимизировать не какие-то там логические операции, а возможные вызовы тяжёлых функций.

kokoc88

А с "или" и "и" такая оптимизация, во-первых - для простоты разработки (чтобы можно было напистаь что-нибудь вроде fopen(...) or die('shit happens' а во-вторых - чтобы оптимизировать не какие-то там логические операции, а возможные вызовы тяжёлых функций.
В принципе ты повторил мои слова выше. В языках программирования boolean выражения часто вычисляются до результата: второй or не вычисляется, если первый true; тоже касается and. Здесь же речь идёт об умножении.

procenkotanya

Если уж зашла речь про оптимизаторы компиляторов, спрошу: если заданы 2 выражения, у которых есть общие операции, компиляторы это оптимизируют?
Да, стараются, по крайней мере :)

procenkotanya

Думаю, что на большинстве процессоров умножение занимает 1 такт.
С каких это пор? GPU-хи не в счёт.

kruzer25

Говорят, что компиляторы оптимизируют даже всякую хрень типа
function test {

int i = 0;

int res = 1;

for(i=0;i++;i<10000) {

res = (res * i)%4958383;

}

int x = 0;

for(i=0;i++;i<1000000) {

x += res ^= x;

}

print 'OK';

}

, превращая её в
function test {

print 'OK';

}

kruzer25


The instruction sets generally include a full set of vector instructions, including multiply, invert and trace

Multiplication
Only unpacked representation is supported. Only two single digit numbers can be multiplied.
First the digits are multiplied as usual using mul.
Then the result is adjusted using aam (ASCII adjust for multiplication).
The processor divides the result by ten, storing the quotient (just the integral part) in the most significant byte of the result and the remainder in the least significant byte of the result.

One advantage of 3DNow! is that it is possible to add or multiply the two numbers that are stored in the same register. With SSE, each number can only be combined with a number in the same position in another register. This capability, known as horizontal in Intel terminology, was the major addition to the SSE3 instruction set.

PMULHRSW Packed Multiply High with Round and Scale treat the sixteen-bit words in registers A and B as signed 15-bit fixed-point numbers between -1 and 1 (eg 0x4000 is treated as 0.5 and 0xa000 as -0.75 and multiply them together with correct rounding.
PMADDUBSW Multiply and Add Packed Signed and Unsigned Bytes Take the bytes in registers A and B, multiply them together, add pairs, signed-saturate and store. IE [a0 a1 a2 ...] pmaddubsw [b0 b1 b2 ...] = [satsw(a0b0+a1b1) satsw(a2b2+a3b3) ...]

PMULLD, PMULDQ Packed signed/unsigned 16->32-bit and 32->64-bit integer multiply
ЗЫ: А вообще, всё это хуйня. Потому что:

MUL Unsigned multiply
:smirk:

vall

Оптимизируются ли тривиальные операции?
Да.

durka82

То есть получается что умножение на 0 будет работать быстрее, чем то же сравнение перед умножением?
Например: 
real x = y==0 ? 0. : y*z

procenkotanya

Где тут хоть слово про "умножение занимает один такт"?

vall

зависит от процессора, компилятора и программы.
на обычных современных процессорах ускорение такой оптимизацией можно получить только если у тебя там в 99.9% случаев 0.
но в этом случае стоит переделать программу более основательно.

durka82

Не, 0 там будет в среднем меньше чем в 10% случаев.
На самом деле задача такая:
есть индексированное множество чисел и итерационное выражение, которое на границе этого множества будет зависеть от чисел, которых нет (то есть они за пределами индексов множества и считаются равными 0).
Соответственно можно подходить противоположно:
1. Везде при вычислении таких выражений втыкать проверки на выход индексов за пределы
2. Добавить к множеству границу, которая всегда хранит 0 и просто в ситуации выхода индексов за пределы будет вычисляться выражение от нулевых значений (правда если значение может зависеть не только от соседних элементов, но и от +-10-го, например, то объем доп памяти сильно возрастет :()
Можно конечно разбить все это множество индексов на области и для каждой проводить вычисления, но это приведет к многократному дублированию кода (или компилятор как раз так и оптимизирует код, развернув такие условия?).
Или это как-то можно сделать красиво?

Oper

Не, 0 там будет в среднем меньше чем в 10% случаев.
На самом деле задача такая:
есть индексированное множество чисел и итерационное выражение, которое на границе этого множества будет зависеть от чисел, которых нет (то есть они за пределами индексов множества и считаются равными 0).
Соответственно можно подходить противоположно:
1. Везде при вычислении таких выражений втыкать проверки на выход индексов за пределы
2. Добавить к множеству границу, которая всегда хранит 0 и просто в ситуации выхода индексов за пределы будет вычисляться выражение от нулевых значений (правда если значение может зависеть не только от соседних элементов, но и от +-10-го, например, то объем доп памяти сильно возрастет :()
Можно конечно разбить все это множество индексов на области и для каждой проводить вычисления, но это приведет к многократному дублированию кода (или компилятор как раз так и оптимизирует код, развернув такие условия?).
Или это как-то можно сделать красиво?
минус 100 за тред

spitfire

А ещё, например, в Haskell, есть такая штука, как ленивые вычисления.

danilov

Преждевременная оптимизация - зло.
Напиши геттер, который возвращает 0 за пределами и всё...
А уже, когда всё заработает, оптимизируй. А так у тебя с большой вероятностью получится быстрый говнокод,
который нигде боле не заюзаешь.
Может, оптимизиция и не нужна буит.

durka82

минус 100 за тред

Можешь ставить хоть минус лимон, но пока ты не аргументируешь свою позицию - грош цена твоей оценке :(

kruzer25

Ага, мой косяк.
Но, по крайней мере, процессор знает о том, что такое "умножение" (т.е. компилятор не переделывает это в сложение а, значит, вполне может и сам провести необходимую оптимизацию.

pitrik2

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

kruzer25

Спроси у интела :D

Oper

Твоя задача никак не связана с твоим вопросом. Оба решения плохи.
Прежде, чем интересоваться оптимизацией на нижних уровнях (компилятора, процессора) сначала
1) подумай, так ли нужна на самом деле оптимизация (для этого надо как минимум иметь рабочую версию программы, скорость работы которой не устраивает) — принцип KISS еще никто не отменял.
2) оптимизируй в первую очередь вычислительный алгоритм.
Судя по твоим постам ты не сделал ни первого, ни второго.

durka82

Твоя задача никак не связана с твоим вопросом. Оба решения плохи.
Спорно.
Прежде, чем интересоваться оптимизацией на нижних уровнях (компилятора, процессора) сначала
1) подумай, так ли нужна на самом деле оптимизация (для этого надо как минимум иметь рабочую версию программы, скорость работы которой не устраивает) — принцип KISS еще никто не отменял.
2) оптимизируй в первую очередь вычислительный алгоритм.

Это все понятно.
Судя по твоим постам ты не сделал ни первого, ни второго.

Вот чтобы сделать это лучше, я и решил просветить для себя этот вопрос ;)

bleyman

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

lubanj

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

lubanj

В твоей задаче правильней добавить ещё строчку и столбец с нулями.
а вот совсем не факт. смотри, он же писал:
 
1. Везде при вычислении таких выражений втыкать проверки на выход индексов за пределы
2. Добавить к множеству границу, которая всегда хранит 0 и просто в ситуации выхода индексов за пределы будет вычисляться выражение от нулевых значений (правда если значение может зависеть не только от соседних элементов, но и от +-10-го, например, то объем доп памяти сильно возрастет )
  

оценим объем вычислений
1. несколько сравнений (если у нас прямоугольная матрица, то это 4 сравнения)
2. умножение (для получения адреса элемента. для прямоугольной опять же тут и сложение добавляется) и вычисление выражения от нулевых значений

durka82

Умножение всегда работает быстрее, чем условный переход. В современных процах условный переход может работать вообще невозможно, чудовищно медленней, потому что выносит моск параллелизатору.
Спасибо, это хороший аргумент, я как-то упустил его из виду.
В твоей задаче правильней добавить ещё строчку и столбец с нулями.
Это вариант №2 из тех, что я предлагал ;)
Но вообще тебе бы лучше убить себя или по крайней мере не заниматься оптимизацией, раз уж не умеешь.
Ты чувствуется еще у утробе матери был супермегаоптимизатором :grin:

durka82

оценим объем вычислений
1. несколько сравнений (если у нас прямоугольная матрица, то это 4 сравнения)
2. умножение (для получения адреса элемента. для прямоугольной опять же тут и сложение добавляется) и вычисление выражения от нулевых значений
Примерно так, но не совсем - все эти операции носят массовый характер (обход и перевычисление всего множества).
Поэтому оценка для 1 такая (для 2д а вот оценка для 2 не совсем такая, так как элементы можно перебирать последовательно, завести кучу (ну или сколько там надо) итераторов и умножения для получения адреса заменить инкрементом (+1, +длина строки, +размер плоскости).

lubanj

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

apl13

В принципе такие вещи могли бы оптимизироваться на уровне проца.
Интересно, как ты себе это представляешь? Инструкция ушла, канал был занят, тот же такт на запуск конвейера...
Может, суперскаляры и проводят такие сравнения, хотя это, ИМХО, лишняя AL, которую полезно было бы употребить на что-нибудь иное.
В списке стандартных оптимизаций есть нестинг, когда основной цикл идет без учета редких случаев, а в случае редкого случая ( :blah: ) происходит прыжок на компенсирующий код. Однако проверка равенста нулю множителя - это, ИМХО, маразм; в нынешних процах она вполне может занять времени и устройств больше, чем само по себе умножение.

durka82

основной баг оратора посоветовшего добавить в итоге рамочку из нулей я заметил в том, что он не учел время на вычисление значения функции в нуле.
в чем у тебя функция заключается?
Функция как раз в этом смысле простая: сумма произведений пар элементов множества.
То есть если одно из чисел = 0, то "пропадает" только 1 умножение.

durka82

Интересно, как ты себе это представляешь?
В блоке умножения добавляется две схемы, каждая реализующая логическое сложение всех битов соответствующего операнда с инверсией выхода (чтобы 1 означала что операнд = 0).
Они также соединяются логическим сложением.
То есть сразу после помещения операндов в регистры мы знаем, имеет ли смысл умножать или нет (если хотя бы один из операндов 0).
Сильно сомневаюсь, что такая схема будет работать столько же, сколько и само умножение (но если для современных процов это так - именно это я и хотел прояснить).
В транзисторах это должно быть немного - несколько сотен на блок умножения (правда в нюансах современной схемотехники не силен, но все равно в масштабах блока умножения это должны быть копейки).
Никаких лишних переходов из-за этого не получается.

Dasar

все это имеет смысл только на логическом уровне - когда мы видим, что целый большой кусок умножается на 0: 0 * f(...).
на уровне проца все это не имеет смысла, т.к. что умножение на нормальное число, что хитрое умножение на 0 - и то, и другое занимает один такт.

kruzer25

все это имеет смысл только на логическом уровне - когда мы видим, что целый большой кусок умножается на 0: 0 * f(...).
Ну и тогда надо, чтобы это была не прозрачная оптимизация, а очень даже явная, чтобы о ней кричали на каждом углу.
Иначе кто-нибудь может не понять, почему же в выражении x*f(...) его функция f иногда не вызывается.

Dasar

да, я как раз хотел добавить, что такую оптимизации на логическом уровне компилятору делать тяжело, потому что он умеет делать только примитивные преобразования кода.
Иначе кто-нибудь может не понять, почему же в выражении x*f(...) его функция f иногда не вызывается
это важно только для функций, которые имеют побочные эффекты, в тех же ФЯ - компилятор знает, какие функции имеют такую побочку, а какие нет.

procenkotanya

на уровне проца ... умножение на нормальное число ... занимает один такт.
Уже второй раз в этой теме. Хоть один пример такого турбореактивного процессора?

Dasar

FMUL Floating point multiply
FMULP Floating point multiply and pop
variations/
operand 8087 287 387 486 Pentium
fmul reg s 90-105 90-105 29-52 16 3/1 FX
fmul reg 130-145 130-145 46-57 16 3/1 FX
fmul mem32 (110-125)+EA 110-125 27-35 11 3/1 FX
fmul mem64 (154-168)+EA 154-168 32-57 14 3/1 FX
fmulp reg s 94-108 94-108 29-52 16 3/1 FX
fmulp reg 134-148 134-148 29-57 16 3/1 FX
s = register with 40 trailing zeros in fraction
или
mulsd xmm, xmm
latency - 5, throughput - 1-2

durka82

А компиляторы про такие операции вообще знают?
А то учитывая, что в языках обычно 4 максимум 8-байтные типы данных (и те только на 64-х битных процах нормально(по скорости) работают) как-то в это не верится :(
Или надо использовать специальные библиотеки/компиляторы?

procenkotanya

latency - 5
Не 1 же!
А первый квот что доказывает?

Dasar

да же на первом pentium - fmul занимает 1-3 такта

procenkotanya

Я не знаю, откуда взяты числа, приведённые в первом квоте, но тестирование на celeron m 1.3GHz показывает 5 тактов для вещественного умножения:


$ cat mul-latency.c 

int main(int k)

{

    int i;

    double l = k, j = 1;



    for (i=1300000000; i; i--)

	j *= l;



    return (int)j;

}



$ gcc -O2 mul-latency.c -funroll-loops -march=pentium-m



$ time ./a.out 



real	0m5.127s

user	0m5.054s

sys	0m0.007s



$ gcc -O2 mul-latency.c -funroll-loops -march=pentium-m -mfpmath=sse



$ time ./a.out 



real	0m5.307s

user	0m5.079s

sys	0m0.016s

затестил на AMD Athlon(tm) 64 Processor 3000+ (1.8GHz у него получилось не меньше 4 тактов на умножение с плавающей точкой.

Spin

Я не знаю, откуда взяты числа, приведённые в первом квоте, но тестирование на celeron m 1.3GHz показывает 5 тактов для вещественного умножения:
code:
$ cat mul-latency.c
int main(int k)
{
int i;
double l = k, j = 1;
for (i=1300000000; i; i--)
j *= l;
return (int)j;
}
$ gcc -O2 mul-latency.c -funroll-loops -march=pentium-m
$ time ./a.out
real 0m5.127s
user 0m5.054s
sys 0m0.007s
$ gcc -O2 mul-latency.c -funroll-loops -march=pentium-m -mfpmath=sse
$ time ./a.out
real 0m5.307s
user 0m5.079s
sys 0m0.016s
затестил на AMD Athlon(tm) 64 Processor 3000+ (1.8GHz у него получилось не меньше 4 тактов на умножение с плавающей точкой.
Мож чего не понимаю... но где в твоем посте такты? Или ты из времени путем деления получил?

Dasar

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

kruzer25

Да вы жжоте, господа.
Что, у тебя там в этом цикле больше ничего не происходит? Я вот вижу там навскидку проверку i!=0 и i-- - они, знаешь ли, не нулевое время делаются.
Или там всё как-то мегаоптимизировано?

apl13

Или надо использовать специальные библиотеки/компиляторы?
Надеюсь, ты не думаешь, что gcc тебе выдаст оптимальнейший код для PIV?

bleyman

Он, видимо, считает, что директива -funroll-loops развернула ему цикл в 1.3*10^9 операций умножения. Что, если мне не изменяет память, должно занимать порядка двух гигов.
Моноид, у тебя экзешник занимает порядка двух гигов, да?
Пиздец ваще, форум заполоняет абортивный материал, мне страшно!

vall

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

kruzer25

Было бы интересно поглядеть на то, что оно действительно сделало ;)

banderon

gcc -W -Wall -O2 -march=k8 -funroll-loops -S test.c

test.c:
int main(int k)

{

    int i;

    double l = k, j = 1;



    for (i=1800000000; i; i--)

        j *= l;



    return (int)j;

}

test.s:
        .file   "test.c"

        .text

        .p2align 415

.globl main

        .type   main, @function

main:

.LFB2:

        cvtsi2sd        %edi, %xmm1

        movl    $1799999999, %eax

        subl    $7, %eax

        movsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        .p2align 47

.L2:

        mulsd   %xmm1, %xmm0

        subl    $8, %eax

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        mulsd   %xmm1, %xmm0

        jne     .L2

        cvttsd2si       %xmm0, %eax

        ret

.LFE2:

        .size   main, .-main

        .section        .eh_frame,"a",@progbits

.Lframe1:

        .long   .LECIE1-.LSCIE1

.LSCIE1:

        .long   0x0

        .byte   0x1

        .string "zR"

        .uleb128 0x1

        .sleb128 -8

        .byte   0x10

        .uleb128 0x1

        .byte   0x3

        .byte   0xc

        .uleb128 0x7

        .uleb128 0x8

        .byte   0x90

        .uleb128 0x1

        .align 8

.LECIE1:

.LSFDE1:

        .long   .LEFDE1-.LASFDE1

.LASFDE1:

        .long   .LASFDE1-.Lframe1

        .long   .LFB2

        .long   .LFE2-.LFB2

        .uleb128 0x0

        .align 8

.LEFDE1:

        .ident  "GCC: (GNU) 4.2.2 (Gentoo 4.2.2 p1.0)"

        .section        .note.GNU-stack,"",@progbits



dsme /tmp $ time ./test.exe; time ./test.exe; time ./test.exe; time ./test.exe;



real    0m4.157s

user    0m4.160s

sys     0m0.000s



real    0m4.158s

user    0m4.110s

sys     0m0.010s



real    0m4.135s

user    0m4.130s

sys     0m0.000s



real    0m4.140s

user    0m4.130s

sys     0m0.000s

/proc/cpuinfo
model name      : AMD Athlon(tm) 64 Processor 3000+

cpu MHz         : 1800.000

procenkotanya

стоило разбавить умножения другими операциями, потому что сейчас ты тестируешь самой плохой вариант - когда помаксимуму загружен FPU, а остальные блоки простаивают
Интересно, почему на это никто не отвечает? Что, когда остальные блоки чем-то заняты, FPU магически начинает быстрее умножать?
И что за индивид интеллектуального уровня пенартура воспользовался аккаунтом ФиДжея?
Если что, в моём случае в цикле было 10 инструкций: 8 умножений, декремент регистра (с установкой флагов условный переход.
Может кто-то может предложить другую методику измерения латентности умножения? Может она даже покажет результат в 1 такт? (собственно, я начал писать в этой теме только потому, что уверенно утверждался такой вот факт, который я считаю неверным)

bleyman

Извини, был не прав.
Насчёт умножения за один такт: прелюбопытнейший факт, мне не удалось заставить cl развернуть цикл, я развернул его ручками (тоже в 8 инструкций) и понял, почему cl его не разворачивал. Время не изменилось вообще. То есть за время выполнения fmul процессор умудряется сожрать декремент eax и условный джамп параллельно. Я был удивлён.
И такой вот код
 int main(int k)

{

    int i, zzz = 13;

    double l = k, j = 1;

    

	#define op do {j *= l; zzz *= k; } while(0)

    for (i=200000000/8; i; i--)

    {

    	op;

    	op;

    	op;

    	op;

    	op;

    	op;

    	op;

    	op;

	}

    return (int)j + zzz;

}

превращается в 
 $main:

; Line 16

	imul	esi, eax

	fmul	ST(0 ST(1)

	fmul	ST(0 ST(1)

	fmul	ST(0 ST(1)

	imul	esi, eax

	fmul	ST(0 ST(1)

	fmul	ST(0 ST(1)

	fmul	ST(0 ST(1)

	imul	esi, eax

	fmul	ST(0 ST(1)

	fmul	ST(0 ST(1)

	imul	esi, eax

	imul	esi, eax

	imul	esi, eax

	imul	esi, eax

	imul	esi, eax

	sub	ecx, 1

	jne	SHORT $main

и тоже жрёт те же ~4.3 такта на итерацию (неразвёрнутую).

bleyman

И ещё поэкспериментировал.
imul жрёт три такта. И тоже полностью параллелится с остальной частью цикла.
Более того, то ли с кэшем инструкций какая-то фигня, то ли вижуальник не понимает особенностей моего процессора, но неразвёрнутый цикл с imul+fmul получается немножко быстрее развёрнутого.
Включение SSE2 чуть-чуть ускоряет, вместо fmul юзается mulsd, который, видимо, ещё лучше параллелится. И, кстати, невзирая на то, что код выглядит так:
 
 $main:

; Line 24

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	imul	ecx, eax

	mulsd	xmm1, xmm0

	imul	ecx, eax

	mulsd	xmm1, xmm0

	imul	ecx, eax

	mulsd	xmm1, xmm0

	imul	ecx, eax

	sub	edx, 1

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	mulsd	xmm1, xmm0

	jne	SHORT $main

... всё равно четыре такта на итерацию. Чота либо я не понимаю чего-то, либо унутре athlon64 3000+ стоит какая-то дико умная неонка.
Так вот, по поводу одного такта на умножение: да, не один =). Но на практике можно считать, что один, потому что вся окружающая хрень в требующиеся четыре такта запихнётся. Может даже вообще бесплатно получится как бы! Ну, как у меня получается — казалось бы, умножение даблов жрёт четыре такта, но можно к нему добавить ещё целочисленное умножение (3 такта декремент(типа 1 такт) и джамп (хз, 1-2 и всё равно получится четыре такта, а не 9-10, как можно было бы ожидать.

Dasar

Интересно, почему на это никто не отвечает? Что, когда остальные блоки чем-то заняты, FPU магически начинает быстрее умножать?
вот FJ тебе развернуто правильно ответил
сегодняшний процессор - это многопараллельный модуль, поэтому чистые оценки выполнения мало интересуют при написании реальных программ, больше интересует некая приблеженная оценка - насколько программа станет медленнее, если в нее добавить ту, или иную инструкцию.
соответственно для умножения - можно считать, что эта приблеженная оценка - 1 такт.

tamusyav

Точнее, если код хорошо параллелится (в частности, нет зависимости от предыдущего результата то 1 такт, если плохо - то зависит от процессора (и не только от него).
А насчет умножения на 0 - если оно не целочисленное, то результат может и не нулем быть.

danilov

А разве целые нонче не в даблах хранятся?

durka82

А насчет умножения на 0 - если оно не целочисленное, то результат может и не нулем быть.
Это как это?
Если так происходит - это ошибка :(
Или процы уже дошли до того, что нулем как таковым не оперируют, а оперируют минимальным числом?

procenkotanya

Многие процессоры при реализации вещественной арифметики следуют стандарту IEEE 754 (иногда с отклонениями в котором есть представления "бесконечностей" различных знаков и "не-числа":


$ cat nan.c

#include <stdio.h>

int main(void)

{

    double inf_p = 1.0/0.0, inf_n = (-1.0)/0.0, nan = 0.0/0.0;



    printf ("+INF: %g, +INF*0: %g, -INF: %g, -INF*0: %g, NaN: %g, NaN*0: %g\n",

	    inf_p,     inf_p*0.0,  inf_n,    inf_n*0.0,  nan,     nan*0.0);



    return 0;

}



$ gcc nan.c

$ ./a.out 

+INF: inf, +INF*0: nan, -INF: -inf, -INF*0: nan, NaN: nan, NaN*0: nan

Кстати, любопытный факт: нули в IEEE 754 тоже разных знаков, и нейтральным элементом относительно сложения является именно отрицательный ноль:
(+0) + (+0) = (+0)
(-0) + (-0) = (-0)
(-0) + (+0) = (+0)
, , : я знаю про такое явление как параллелизм на уровне команд, спасибо. Вы что, ребята, вообще? Я не хотел превращать тред в разгорячённый спор со взаимными оскорблениями. Извините. Но молча пропустить неправильное утверждение тоже не смог. Ещё раз. Есть конкретное понятие "латентности операции". Для большинства арифметических операций она постоянна. Для загрузки числа из памяти, например, латентность переменна, так как оно может лежать в кеше или в оперативке. Утверждение про "умножение занимает один такт" в контексте параллелизма на уровне команд некорректно, хотя бы потому, что никак не ссылается на то, лежит ли это умножение на критическом пути вычислений, или нет. Вот если я скажу, что поскольку декодеры команд популярных процессоров пропускают не более трёх инструкций за такт, поэтому при достаточном параллелизме на уровне команд можно считать, что умножение занимает треть такта, как вы к этому отнесётесь?

apl13

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

Dasar

поэтому при достаточном параллелизме на уровне команд можно считать, что умножение занимает треть такта, как вы к этому отнесётесь?
отлично.
если это справедливо для реальной программы, то чем плоха оценка - что умножение выполняется за треть такта?

barbos

Лингвистически такая конструкция выглядит странно. Что физически могло выполниться за треть такта? oO

apl13

Ты не поверишь - операция с вещественными аргументами! :ooo:

barbos

Ага ) В это точно не поверю :-D
Но я всегда думал, что такт задает наименьший промежуток между стационарными состояниями на процессоре. И только в этих состояниях ясно, что операция начала выполняться или выполнилась. Это не так?

bleyman

Но я всегда думал, что такт задает наименьший промежуток между стационарными состояниями на процессоре. И только в этих состояниях ясно, что операция начала выполняться или выполнилась. Это не так?
---
А хз. Тактовая частота == Clock frequency, то есть это частота центрального кварца на процессоре, не больше и не меньше. Разумеется, внутри процессора есть тыща умножителей и делителей частоты, которые синхронизируют разнообразные процессы, так что хотя некая корреляция между тактовой частотой и реальной латентностью операций есть, статуса закона у неё нет.
Моноид, конечно, прав, говоря, что понятие латентности (то есть минимального времени выполнения данной операции in respect to clock frequency на данном конкретном процессоре) вполне определено, наиболее соответствует неформальному определению "длительность операции" и у операции умножения на исследованных нами современных процах латентность вовсе не 1 такт. И, кстати, видимо меньше, чем у условного перехода. Окей, я был терминологически неправ!
Что касается усреднённого времени, я теперь даже и не знаю. Я проверил — в том же коде дописывание if (k != 0) (я смотрел в листинг, ничего не отоптимизировалось) тоже параллелится с самим умножением (укладываясь в те же три такта, независимо от того, чему равно k). Пытаться построить сложный случай, чтобы выяснить, как джамп влияет на кэш инструкций и предсказатель переходов, мне влом.

vall

усреднённое время исполнения инструкции бессмысленно — как оно будет в реальности сильно зависит от процессора, окружающего кода и состояния кэша.
для разумной оценки нужна более сложная модель чем время_выполнения(кода_кусок) = сумма(среднее_время(инструкция
видел статейку где авторы ужасались от хаотичного поведения современных процессоров -— из-за сложной работы с памятью и кэшами время исполнения кода крайне нестабильно.
Оставить комментарий
Имя или ник:
Комментарий: