Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 55, средняя оценка - 4.71
CEBEP
106 / 106 / 9
Регистрация: 21.03.2010
Сообщений: 440
#1

Производительность операций - C++

20.11.2011, 06:34. Просмотров 7650. Ответов 135
Метки нет (Все метки)

Не уверен в своих силах для самостоятельной оценки сабжа. Где можно найти информацию о производительности стандартных операций с++ (гуглением не справился, нашел только сравнение реализации на с++, джаве и на нескольких интерпретируемых языках)?
То есть интересует информация плана << : * как 1:15 или <= : == как 25:24... То есть, чрезвычайно интересно знать, какие операции выбирать если есть альтернатива.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2011, 06:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Производительность операций (C++):

Вставить между цифрами 1, 2,..., 8, 9 в данном порядке, знак одной из 4-х арифметических операций так, чтобы результат восьми послед-х операций =100 - C++
Вычисления проводятся слева-направо, ни одна операция не имеет приоритета. Добавлено через 2 минуты задача вынесла моск, прошу помочь

Производительность - C++
Подскажите, где или что почитать о том, как писать БЫСТРЫЕ программы? (про разработку высоконагруженных программ). Копаюсь в интернете -...

Производительность кода - C++
Интересует сабж как таковой, и конкретно это: std::string STR = &quot;ABC&quot;; if ( strcmp(STR.c_str(), &quot;ABC&quot; ) == 0 ) или std::string STR...

Влияет ли на производительность - C++
Влияет ли на производительность определение(тоесть реализация) функций внутри класса, а также использование вложенных классов?

Производительность многопоточности - C++
Доброго времени суток. Решил заняться многопоточностью, и натолкнулся на непонимание с производиельность Есть код в 2 потока: ...

Производительность DLL - C++
Привет всем, у меня вопрос по производительности подключения DLL-ки по сравнению с чтением из файла. В программе использую небольшую...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 05:48 #91
Цитата Сообщение от CEBEP Посмотреть сообщение
То, как он работает очевидно.
Только для программиста может быть очевидным, что любая замена, уменьшающая суммарное количество делений и умножений, ускоряет исполнение при условии не увеличения общего числа операйций, а не только при условии его сокращения. И только если он знает, что быстрее сложить, чем умножить. Но если в результате растёт число операций, то лучше использовать деление/умножение.
0
CEBEP
106 / 106 / 9
Регистрация: 21.03.2010
Сообщений: 440
22.11.2011, 05:51  [ТС] #92
И вообще, часто это звучит так:
я: Мужики, мне надо оптимизировать код.
мне: Да ты дебил, его бесполезно оптимизировать!
я: Да вот же, посмотри, есть разница
мне: Вы профан! Нету!

Добавлено через 2 минуты
Цитата Сообщение от taras atavin Посмотреть сообщение
Только для программиста может быть очевидным
Ну да. Но ведь это действительно ясно: что бы сложить в бинарной системе счисления нужно сделать что-то типа сложения столбиком а перемножить явно сложнее. Я включил это сравнение в свой тест не для того, чтобы установить факт а чтобы получить соотношение времени затрачиваемого на операции
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 06:02 #93
Цитата Сообщение от LosAngeles Посмотреть сообщение
taras atavin, с какими скобками? Если такими a*(b+c) то нет, не меньше. Кончай уже фантазировать, тему всё-таки дети читают, а то вдруг и правда кто-то поверит в твои спичечные оптимизации. Всё что ты писал до этого, ниодна твоя оптимизация не существует в природе!
Все мои оптимизации существуют. У меня за 44 минуты полностью выполнился код, неоптимизированная версия которого за весь день не дошла до одного процента, а теоритическая оценка времени полного исполнения неоптимизированной версии превышает 6 тысячь лет, хотя на замену опреаций и приходятся скорее всего доли секунды, а остальное на сжатие и алгоритм. А вот ты действительно фантазируешь, ни одна твоя оптимизация не существует в природе, агресивный релиз просто не ставится в настройках из-за дефицита знаний опций компилятора.

Добавлено через 9 минут
Цитата Сообщение от CEBEP Посмотреть сообщение
Ну да. Но ведь это действительно ясно: что бы сложить в бинарной системе счисления нужно сделать что-то типа сложения столбиком а перемножить явно сложнее. Я включил это сравнение в свой тест не для того, чтобы установить факт а чтобы получить соотношение времени затрачиваемого на операции
Столбиком? Эйси. Число операций с цифрами при сложении столбиком 2n, где n - разрядносить, а при умножении столбиком 3n^2. То есть при максимально дебильной реалицзации обеих операйций отношение для 32-х битных операндов равнятеся 48-ми, твой тест доказывает, что умножение как то оптимизировано, иначе такое гигантское отношение хоть как то бы проявилось даже на фоне длительности запоминания самого времени. Для 64-битных кривоумнодение медленнее в 96 раз, для 128-ми битных - в 192 раза. И так далее.
0
CEBEP
106 / 106 / 9
Регистрация: 21.03.2010
Сообщений: 440
22.11.2011, 06:12  [ТС] #94
Цитата Сообщение от taras atavin Посмотреть сообщение
Число операций с цифрами при сложении столбиком 2n, где n - разрядносить, а при умножении столбиком n^2+4n
ненене. Ежу понятно что там не так. Во первых зависимости от числа разрядов не будет - для этого нужна проверка, а она будет дольше, чем выполнить операцию для всех разрядов. А умножение то уж точно там выполняется иначе (на базе побитовых сдвигов, думаю).
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 06:46 #95
Что касается индекса и указателя. Просто [CPP]a[100] ганатированно не медленее, чем
C++
1
2
p=a+100;
*p
, но
C++
1
2
3
4
for (i=n; i>=1; --i)
{
 a[i]
}
медленне, чем
C++
1
2
3
4
for (p=a+n-1; p>=a; --p)
{
 *p
}
.
C++
1
for (p=a; p<=a+n-1; ++p)(
тоже медленее, чем
C++
1
for (p=a+n-1; p>=a; --p)
, а
C++
1
for (p=a+n-1; p>=a; --p)
медленее, чем
C++
1
for (i=n; i>0; --i)
, но различие между
C++
1
for (p=a+n-1; p>=a; --p)
и
C++
1
2
e=a+n-1;
for (p=a; p<=e; ++p
и
C++
1
i=a+n-1;
на значимо, а
C++
1
2
e=n-1;
for (i=a; i<=e; ++i
чуть быстрее, но разницу съест и даст обратный эффект высисление указателя по индексу.

Добавлено через 3 минуты
Цитата Сообщение от CEBEP Посмотреть сообщение
Во первых зависимости от числа разрядов не будет - для этого нужна проверка, а она будет дольше, чем выполнить операцию для всех разрядов.
Какя проврека? Число разрядов известно на этапе разработки. Или ты думаешь, что незначащие нули в старших разрядахц цифрами не являются?

Добавлено через 16 секунд
Цитата Сообщение от CEBEP Посмотреть сообщение
Во первых зависимости от числа разрядов не будет - для этого нужна проверка, а она будет дольше, чем выполнить операцию для всех разрядов.
Какая проврека? Число разрядов известно на этапе разработки. Или ты думаешь, что незначащие нули в старших разрядах цифрами не являются?

Добавлено через 8 минут
Кстати, меньшим числом опреаций можно было бы обойтись при использовании системы с большим основанием, например, сложение тех же 32-х битных операндов, но при спользовании шестнадцатеричных операций использует вместо 64-х оперций с цифрами только 16. Вопрос в том, как реализовать быстрое шестнадцатеричное сложение. Таблицей сложенгия? Она будет содержать 256 байт и требовать отдельного вычисления адреса, правда с помощью логической операции, которая может исполняться быстрее арифметической. Ещё меньше операий с цифрами при основании 256, но такая таблица весит 65536 слов, зато операций с цифрами будет всего 8.

Добавлено через 11 минут
Зависимости от числа разрядов не будет в единственном случае - если процессор реализует операции малой разрядности через аналог разрядности в регистр с занулением старших разрядов. Тогда нет разница 16 разрядов занулять, или 24, в любом случае будет затрачено одно и то же время, но тогда минимальноле время расходуется при сложении операндов разрядности регистр, так как эта опреция не требует зануления старших разрядов, то есть выполняется без вспомогательной предварительной операции. Но и в этом случае операции повышенной разрядности, для которых в процссоре нет готовых аппаратных реализаций, реализуются инлайновой функцией на асме и расходуют больше времени. Кстати, ты обратил внимание, что я не упомянул разрядности вроде 22-х, или 34-х бит?
1
CEBEP
106 / 106 / 9
Регистрация: 21.03.2010
Сообщений: 440
22.11.2011, 06:47  [ТС] #96
Цитата Сообщение от taras atavin Посмотреть сообщение
на значимо
Установить это - цель эксперимента.
Цитата Сообщение от taras atavin Посмотреть сообщение
шестнадцатеричное сложение
что-то я не пойму. В памяти всё так или иначе двоичное. Другие системы счисления - вопрос представления данных...
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 07:20 #97
Цитата Сообщение от CEBEP Посмотреть сообщение
В памяти всё так или иначе двоичное. Другие системы счисления - вопрос представления данных...
Ты хоть в курсе, что интеловские камни умеют работать со смешанными системами? Например, с двоично-десятичной? Приведение же из двоичной в двоично-шестнадцатеричную и назад не требует фактического преобразования, так же как и любые другие приведения между смешанными системами, с большими основаниями равными целым степеням двойки и двоичной системой. А это открывает возможность полностью скрытого использования систем с увеличенным основнием. Возможная цель - обработка четрёх, или даже восьми бит за одну операцию. Возможные препятствия: больше время исполнения шестнадцатеричной операции и повышенаая сложность АЛУ. Я не берусь утверждать целесообразность такого подхода, тем более его применение конкртено интелом. Возможно на этом пути больше проблем, чем преимуществ. Это просто кривопредположение, из которого не следует делать ни каких выводов. Кстати, я не спроста в контексте повышеняи основания толкую только о числе операций, но не о времени.

Добавлено через 5 минут
Цитата Сообщение от taras atavin Посмотреть сообщение
на значимо
не значимо, очепятка.

Добавлено через 33 секунды
Цитата Сообщение от taras atavin Посмотреть сообщение
высисление
вычисление. Очепятка.

Добавлено через 1 минуту
Цитата Сообщение от taras atavin Посмотреть сообщение
i=a+n-1;
это здесь случайно.

Добавлено через 7 минут
Цитата Сообщение от CEBEP Посмотреть сообщение
А умножение то уж точно там выполняется иначе (на базе побитовых сдвигов, думаю).
ну сдвинул ты первый операнд на все похзиции поочерёдно. Дальще что? Возмём 4-х битный пример
 00000010
*00000110
 ----------
 00000010
 00000100
 00001000
 00010000
 --------
 0001110

Добавлено через 6 минут
А должно быть:
 00000010
*00000110
 --------
 00000000
 00000100
 00001000
 00000000
 --------
 00001100
, но AND всех бит первого операнда с одним битом второго + сдвиг результата экивалентен паралельному умножению вего первого операнда на цифру второго. Вот тебе и один из путей оптимизации умножения, а сложение аналогичным образом нельзя оптимизировать. Приходим к n+2n^2, всё равно супрекриво, твоему тесту не соответствует.
0
CEBEP
106 / 106 / 9
Регистрация: 21.03.2010
Сообщений: 440
22.11.2011, 07:23  [ТС] #98
0010 * 0110 = 1100. Даже не представляю, как это происходит, но фором можно записать такое используя &, + и <<
0
Bers
Заблокирован
22.11.2011, 08:28 #99
Цитата Сообщение от CEBEP Посмотреть сообщение
Суммирование (add), по весу ровно столько же, сколько и перемножение (mul), если, конечно, реализация выберет mul а не что-то из перебранного выше.
Я заметил, я ничерта не понимаю, о чем вы говорите. Вы как то так неочевидно мысли излагаете.

Я вам говорю - любой код пишите, хоть на с++, хоть на си, хоть на бейсике.
Замер производительности все равно делается уже ассемблированного кода ПОСЛЕ компиляции.

Дальше тупо суммируется вес ассемблированного кода.

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

Я конечно, не разбираюсь в ассемблере, но по моему это очивидно, не?

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

И эти абсолютные веса уже можно смело сравнивать.

Получается, что алгоритм замеров таков:

1. Пишутся две функции на языке высокого уровня, которые нужно сравнить по производительности.

2. Компилируются.

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

4. Утилитка возвращает абсолютный вес этого кода.

5. Сравниваются веса.

Если получится, что допустим вес одной функции 2, а другой - 1,5, значит первая работает быстрее второй в 2.0/1,5 раза.

6. Профит!
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 08:32 #100
Цитата Сообщение от Bers Посмотреть сообщение
Дальше тупо суммируется вес ассемблированного кода.
Не все операции выполняются за равное время. Откуда ты взял равенство времени для mul и add? По принципу одна команда там и там, а процессор делит работу на такты? Ну так разные операции могут занимать разное число тактов,
Assembler
1
XOR AX,AX;
быстрее, чем
Assembler
1
MOV AX, 0;
, mul тоже тратит больше тактов, чем add. А есть машины, у кторых одна операция может занимать десятки тысячь тактов, например, спектрум может копировать большие куски памяти не циклом и даже не MOVS с репером повторения, а одной блочной операцией, но шина у него 8-ми битная, соответственно чем больше байт копируешь, тем больше требуется тактов.
0
Bers
Заблокирован
22.11.2011, 08:43 #101
Либо я чего то не понимаю. Либо вы чего то не понимаете.


Пофигу, скольков ремени тратит XOR AX,AX;
Главное, что бы это время было константным.

Больше ничего не требуется, для оценки производительности исходного кода.
Скомпилировал, и оценил ассемблированный код. Все!
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 08:52 #102
Цитата Сообщение от Bers Посмотреть сообщение
Я конечно, не разбираюсь в ассемблере, но по моему это очивидно, не?
Абсолютно не очевидно, но часто верно. Для такого вывода надо знать, что есть дальние и ближние переходы, что разные операции перехода выполняются за разное время, что если ты не уложился в дальность ближнего перехода, то будет дальний, что есть кэш, что он работает на повыешонной в сравнении с оперативкой частоте, что большие куски кода в кэш тупо не влезают и много чего ещё. Часто больший по размеру код оказывается быстрее за счёт более быстрых операций. Какой цикл с чёным числом шагов меньше весит? Где все шаги явные, или где вместо одного тела цикла имеется два его экземпляра? Так вот, иногда быстрее второй вариант, а меньше всегда первый. Часто быстрее больший код с тормозными операциями, но работающий с более компактными данными. Вообще нет общих правил оптимизации по времени, кроме:
1. Избегайте сравнения в цикле с чем бы то ни было, кроме ноля. Но только если это не ведёт к усложнению тела цикла.
2. Избегайте постфиксной формы инкремента/декремента.
3. Избегайте мультипликативных операций везде, где это не ведёт к увеличению общего числа операций.
4. Избегайте вычислений с плавающей запятой везде, где их можно без усложнения алгоритма заменить целочисленными.
5. Избегаейте передачи больших объектов по значению.
6. Избегайте рекурсии везде, где она не вытекает из самой задачи, или из структуры данных. Неоправданная рекурися ведёт к тормозам, но там, где она вытекает из задачи, или из структуры данных, любая попытка избавить от неё ведёт к усложеннию алгоритма и может привести к ещё большим тормозам.
Всё остальное делается с кучей тестов и замерами времени. В том числе, пробуют как экономить размер кода, так и несколько его раздувать, менять представление данных, используют априорную информацию о структуре матриц коэффициентов систем уравнений для оптимизации на уровне алгоритма.
1
Bers
Заблокирован
22.11.2011, 08:54 #103
taras atavin, похоже вы в танке.
1
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 09:01 #104
Цитата Сообщение от Bers Посмотреть сообщение
Пофигу, скольков ремени тратит XOR AX,AX;
Главное, что бы это время было константным.
Время исполнения конкретно XOR AX,AX; констана, но не время исполнения абстрактной операции в расчёте на операцию, или на байт кода этой операции. А так как нет ни константы для времени исполнения одной абстравтной операции, ни константного множителя от длины кода, то замеры веса асемблерного кода не имеют значения вообще. Для оптимизации важны тесты.

Добавлено через 2 минуты
Цитата Сообщение от Bers Посмотреть сообщение
taras atavin, похоже вы в танке.
Броня между нами, факт. Но в танке не я. Кстати, ТС наглядно продемострировал, что сложение быстрее умножения. Но точного алгорима умножения не знаем ни он, ни я. У нас получается суперкривое умножение, в десятки раз отстающее от сложения, фирма же сделала лучше.
0
Bers
Заблокирован
22.11.2011, 09:02 #105
Цитата Сообщение от taras atavin Посмотреть сообщение
Время исполнения конкретно XOR AX,AX; констана, но не время исполнения абстрактной операции в расчёте на операцию, или на байт кода этой операции.
Так оценивать то нужно не коня в сферическом вакуме!
А конкретную команду, с её конкретными аргументами!

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

А следовательно - можно получить абсолютные оценки производительностей алгоритмов, вместо грубых приблизительных расчетов завязанных на времени.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.11.2011, 09:02
Привет! Вот еще темы с ответами:

копирование строк, производительность - C++
подскажи, как максимально быстро скопировать сроку memcpy или я написал свою функцию size_t i = 0; while (*(szReceiver + i) =...

Константы, геттеры/сеттеры и производительность - C++
Есть глобальная константа, определяющая размер большого количества массивов. Также есть множество обращений к массивам с использованием...

Производительность CPU, КЕШ, многопоточность - C++
Доброго времени суток! Суть проблемы - есть курсовой по системному программированию но я не знаю с чего и начать ( Тема:...

Вопрос про многопоточность и производительность - C++
Здравствуйте! Подскажите пожалуйста ответы на следующие вопросы: 1) Правда ли,что многопоточность в программе позволяет увеличить...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.11.2011, 09:02
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru