leventov Dec 31 2011 at 22:21

Оптимизация длинной арифметики на C++

3 min

15K

Assembler*High performance*

Tutorial

+78

Comments 22

teplenev Dec 31 2011 at 22:44

Самый новогодний программерский пост! :)

IDY Dec 31 2011 at 22:46

А вот эти «такты» — это окргугление попугаев по среднему? Просто слабо представляется работа clock_gettime на таких промежутках времени в многозадачной ОС (ведь многозадачной?)

А так спасибо за пост.

leventov Dec 31 2011 at 22:51

Такты = наносекунды *3.2
У меня много ядер. Вообще, есть предпосылки считать, что это именно такты. Большинство значений получились круглыми + 0,04 (остаток от временной доли обвязки после деления). Я эти 0,04 отовсюду вычел.

Pleshner Jan 3 2012 at 14:20

Во-первых спасибо за хороший пост, во-вторых — оптимизация за счет инлайнов — это уже какой-то прошлый век, ИМХО.

Вот про оптимизацию циклов чуть по методу Loop-invariant Code Motion + про инлайны в комментариях:

blogerator.ru/page/zametki-ob-optimizacii-programm-1-loop-invariant-code-motion-licm-singleton-i-optimizacija-funkcij

leventov Jan 3 2012 at 15:18

Не очень понял, к чему тут про LICM, в сишном цикле из поста как раз все что можно оптимизировано.

По секрету, в посте действительно неправильно почти все что можно, зря спешил. Напишу «опровержение».

Monnoroch Dec 31 2011 at 23:05

Ухх, было дело, помню-помню, такой же велосипед писал.

leventov Dec 31 2011 at 23:07

Интересно, что написано внутри GMP. К сожалению, не хватило времени туда залезть.

Monnoroch Dec 31 2011 at 23:11

Да, мне тоже всегда было интересно. Версии GMP всегда меня по производительности уделывали, но оно и понятно — в документации сказано, что библиотека при компиляции умеет определять множество разных процессоров и соответствующим образом выбирать исходник.
Кстати, система Mathematica использует какую-то свою версию GMP, потому, что она, в свою очередь, уделывает собранный мной GMP. Что, кстати, удивительно, ведь я-то собираю на целевой машине, а WR вынуждены собирать универсально.

leventov Dec 31 2011 at 23:14

Я его ее не померил. Будет чем первого заняться :)

leventov Dec 31 2011 at 23:15

* ее даже

Monnoroch Dec 31 2011 at 23:17

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

Monnoroch Dec 31 2011 at 23:20

По поводу умножения — у меня помнится на x86 катастрофически нехватало регистра. Там же, если делать столбиком, необходимо хранить 2 счетчика цикла. Ух, как я мучался, помню… Хотя это наверное потому, что ассемблер я довольно ознакомительно знаю.

biseptol Jan 1 2012 at 19:56

Умножение делается очень быстро свертками Фурье. Перемножаешь свертки множителей, получаешь свертку произведения; обратная БПФ — и вот тебе результат.

Я этот велосипед на ассемблере писал году эдак в 2002, вот мне делать было нехер тогда. :-)

Monnoroch Dec 31 2011 at 23:15

Кстати, по поводу gcc версии. Вы, наверное, зря циклы переделывали из индексной формы в хитрые операции с указателями — компилятору сложнее оптимизировать код в этом случае. Возможно, если бы вы переписали код более высокоуровнево, получилось бы даже быстрее.

leventov Dec 31 2011 at 23:51

А там проще и не напишешь, оба лимита используются и в теле, и в условии цикла. Так писалось само, индексно — может быть уже целью.

ciiccii Jan 1 2012 at 06:23

а можно на код полностью взглянуть, пожалуйста?

leventov Jan 1 2012 at 11:51

Отправил

ciiccii Jan 1 2012 at 19:12

Спасибо.

Vurtatoo Jan 1 2012 at 11:31

Кстати, это походу последний пост в 2011 году по местному времени.
С наступившим всех.

mejedi Jan 1 2012 at 11:39

Респект за умелое использование constraints в inline assembly.

UFO just landed and posted this here

leventov Jan 1 2012 at 17:04

bx и dx для логичности написал, в реальности от компиляции к компиляции GCC выбирает из dx, di и r8.

Меня тоже тянуло, попробовал один раз навести порядок:

: [th] "D" (th), [oz] "S" (oz),

Итерация замедлилась на 0,15 такта!