leventov 31 дек 2011 в 18:21

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

3 мин

15K

Assembler * Высоконагруженные системы *

Туториал

+78

Комментарии 22

teplenev 31 дек 2011 в 18:44

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

IDY 31 дек 2011 в 18:46

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

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

leventov 31 дек 2011 в 18:51

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

Pleshner 3 янв 2012 в 10:20

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

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

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

leventov 3 янв 2012 в 11:18

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

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

Monnoroch 31 дек 2011 в 19:05

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

leventov 31 дек 2011 в 19:07

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

Monnoroch 31 дек 2011 в 19:11

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

leventov 31 дек 2011 в 19:14

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

leventov 31 дек 2011 в 19:15

* ее даже

Monnoroch 31 дек 2011 в 19:17

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

Monnoroch 31 дек 2011 в 19:20

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

biseptol 1 янв 2012 в 15:56

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

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

Monnoroch 31 дек 2011 в 19:15

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

leventov 31 дек 2011 в 19:51

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

ciiccii 1 янв 2012 в 02:23

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

leventov 1 янв 2012 в 07:51

Отправил

ciiccii 1 янв 2012 в 15:12

Спасибо.

Vurtatoo 1 янв 2012 в 07:31

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

mejedi 1 янв 2012 в 07:39

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

НЛО прилетело и опубликовало эту надпись здесь

leventov 1 янв 2012 в 13:04

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

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

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

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий