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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 55, средняя оценка - 4.71
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
20.11.2011, 06:34     Производительность операций #1
Не уверен в своих силах для самостоятельной оценки сабжа. Где можно найти информацию о производительности стандартных операций с++ (гуглением не справился, нашел только сравнение реализации на с++, джаве и на нескольких интерпретируемых языках)?
То есть интересует информация плана << : * как 1:15 или <= : == как 25:24... То есть, чрезвычайно интересно знать, какие операции выбирать если есть альтернатива.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
prazuber
108 / 108 / 3
Регистрация: 29.04.2010
Сообщений: 240
21.11.2011, 19:57     Производительность операций #81
Предлагаю ТСу забить на такого рода оптимизацию. Все равно в итоге выигрыш будет незначительным.

Если необходимо ускорить код, то надо переходить на чистый С. Надо считать массив из файла, где заранее кол-во элементов неизвестно? realloc в помощь. Если известно приблизительное количество элементов, можно еще ускорить процесс.

Необходимо решать большие СЛАУ? Может вы просто метод не тот выбрали?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Bers
Заблокирован
21.11.2011, 20:09     Производительность операций #82
Извиняюсь за сумбур. Ибо я ассемблер не ведаю. И возможно просто не понимаю о чем сейчас напишу.

Мне вот интересно, а вот так можно сделать:

Если допустим, операция + (причем в ассемблированном варианте, а не на языке с++) весит.. нууу пусть будит 1 условная единица.

Допустим * - 2 условных единицы

А разделить - 3 условных единицы, ну и тд


После компиляции, просматривается кусок кода (функции, которую нужно замерить), и тупо подсчитывается, сколько условных единиц она наберёт.

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

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

Как вам идея?

Все что нужно - на одно-ядерном компьютере при 100% загрузке процессора (а ещё лучше не на многозадачной ОС) погонять ассемблированные команды, и определить их адекватные условные веса.

Можно вообще весь ассемблер "оценить". И потом получать в условных единицах абсолютную оценку производительности функций, алгоритмов и тп
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
22.11.2011, 01:45  [ТС]     Производительность операций #83
Цитата Сообщение от Bers Посмотреть сообщение
замерить его "условную тяжесть"
Суммирование (add), по весу ровно столько же, сколько и перемножение (mul), если, конечно, реализация выберет mul а не что-то из перебранного выше.
fasked
22.11.2011, 02:40
  #84

Не по теме:

Пишите на ассемблере, вот где для оптимизаций непочатый край. А Си и С++ оставьте для продакшн кода

LosAngeles
Заблокирован
22.11.2011, 04:56     Производительность операций #85
Цитата Сообщение от Bers Посмотреть сообщение
Конечно, нужно как то учесть поправку на то, что разные коды могут выполняться одновременно на разных ядрышках. Но! В целом, даже не зная, сколько времени будит исполняться код, можно же замерить его "условную тяжесть". И сравнивать разные куски кода друг с другом. Ведь все равно, тот кусок, который наберёт больше условных единиц будит работать медленнее более легковесных аналогов.
Как вам идея?
мерять то в любом случае пока нечего. Все вышеприведённые "оптимизации" тарасика ассемблируются совершенно одинаково, код до оптимизации эквивалентен коду после. Все они высосаны из пальца и существуют только в его голове)
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 05:23     Производительность операций #86
C++
1
x=a*b+a*c;
- плохрой пример, так как со скобками будет на одну операцию меньше. Но идея, надеюсь, понятна?
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
22.11.2011, 05:33  [ТС]     Производительность операций #87
Цитата Сообщение от LosAngeles Посмотреть сообщение
Все они высосаны из пальца и существуют только в его голове)
да блин! почему тогда результаты сравнения далеки от 1? Вы выбрали какое-то одно сравнение, которое я добавил по причинам, далёким от насущной необходимости и решили что всё не имеет смысла. Приведите мне достоверное рассуждение, показывающее, что, скажем, обращение к элементу вектора - тот же самый асэмблеровский код, что и обращение к элементу массива! Это, в конце концов, глупо - утверждать то, что не соответствует эксперименту. Я в самом начале просил, чтобы если вы хотите сказать "нет разницы", то скажите мне как настроить мой тест, чтобы он подтвердил ваши слова! А иначе - вон из моего топа, я не интересуюсь вашим мнением.

Добавлено через 5 минут
Цитата Сообщение от taras atavin Посмотреть сообщение
Но идея, надеюсь, понятна?
зачем вообще мусолить этот пример? То, как он работает очевидно. лучше бы разобрали то, как работает разыменование итераторов. 10 минут чтения книги Герба Статтера (смотри выше) дали мне больше чем весь этот флуд на 9 страниц
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 05:35     Производительность операций #88
Цитата Сообщение от LosAngeles Посмотреть сообщение
мерять то в любом случае пока нечего. Все вышеприведённые "оптимизации" тарасика ассемблируются совершенно одинаково, код до оптимизации эквивалентен коду после. Все они высосаны из пальца и существуют только в его голове)
Я не придумал сам ни одной из этих оптимизаций, все взяты из книг. Хороший компилятор оптимизирует x++ до ++x? Эйси. Но всегда ли гарантируется такая оптимизация? ТС продемонстрировал, что это не так. И даже при такой оптимизации ++x грантированно не медленее, чем x++, это же оносится и к случаю, когда автоматическая оптимизация не выполняется вовсе и ко всем возможным промежуточным вариантам. А x++ может быть медленее ++x. И причина как раз в создании и уничтожении временного объекта. На чистых сях этой разницы нет, так как там это синтаксичесик различные формы одного оператора. А теперь теория: все сравнения в заголовке с нолём выполняются не по cmp, а по jnz/jz, а эти команды не требуют загрузки лишнего чилсового операнда, в отличие от cmp. Адрес же грузится в любом случае одинаково, так как любые сравнения в заголовке цикла выполняются с целью перехода. То есть
Assembler
1
2
DEC AX;
JNZ loop1;
быстрее, чем
Assembler
1
2
3
INC AX;
CMP lim;
JLE loop1;
, так как в первом случае грузится только два кода операции и адрес перехода, а во втором три кода операции, предел сравнения и адрес перехода. Сам я придумал только алгоритмические оптимизации и сжатие данных, но ни одной замены операции с целью оптимизации.
LosAngeles
Заблокирован
22.11.2011, 05:37     Производительность операций #89
taras atavin, с какими скобками? Если такими a*(b+c) то нет, не меньше. Кончай уже фантазировать, тему всё-таки дети читают, а то вдруг и правда кто-то поверит в твои спичечные оптимизации. Всё что ты писал до этого, ниодна твоя оптимизация не существует в природе!
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
22.11.2011, 05:45  [ТС]     Производительность операций #90
LosAngeles, вы голословны. покажите всё-таки, как убедится в ваших словах
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
22.11.2011, 05:48     Производительность операций #91
Цитата Сообщение от CEBEP Посмотреть сообщение
То, как он работает очевидно.
Только для программиста может быть очевидным, что любая замена, уменьшающая суммарное количество делений и умножений, ускоряет исполнение при условии не увеличения общего числа операйций, а не только при условии его сокращения. И только если он знает, что быстрее сложить, чем умножить. Но если в результате растёт число операций, то лучше использовать деление/умножение.
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
22.11.2011, 05:51  [ТС]     Производительность операций #92
И вообще, часто это звучит так:
я: Мужики, мне надо оптимизировать код.
мне: Да ты дебил, его бесполезно оптимизировать!
я: Да вот же, посмотри, есть разница
мне: Вы профан! Нету!

Добавлено через 2 минуты
Цитата Сообщение от taras atavin Посмотреть сообщение
Только для программиста может быть очевидным
Ну да. Но ведь это действительно ясно: что бы сложить в бинарной системе счисления нужно сделать что-то типа сложения столбиком а перемножить явно сложнее. Я включил это сравнение в свой тест не для того, чтобы установить факт а чтобы получить соотношение времени затрачиваемого на операции
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 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 раза. И так далее.
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
22.11.2011, 06:12  [ТС]     Производительность операций #94
Цитата Сообщение от taras atavin Посмотреть сообщение
Число операций с цифрами при сложении столбиком 2n, где n - разрядносить, а при умножении столбиком n^2+4n
ненене. Ежу понятно что там не так. Во первых зависимости от числа разрядов не будет - для этого нужна проверка, а она будет дольше, чем выполнить операцию для всех разрядов. А умножение то уж точно там выполняется иначе (на базе побитовых сдвигов, думаю).
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 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-х бит?
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
22.11.2011, 06:47  [ТС]     Производительность операций #96
Цитата Сообщение от taras atavin Посмотреть сообщение
на значимо
Установить это - цель эксперимента.
Цитата Сообщение от taras atavin Посмотреть сообщение
шестнадцатеричное сложение
что-то я не пойму. В памяти всё так или иначе двоичное. Другие системы счисления - вопрос представления данных...
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 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, всё равно супрекриво, твоему тесту не соответствует.
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
22.11.2011, 07:23  [ТС]     Производительность операций #98
0010 * 0110 = 1100. Даже не представляю, как это происходит, но фором можно записать такое используя &, + и <<
Bers
Заблокирован
22.11.2011, 08:28     Производительность операций #99
Цитата Сообщение от CEBEP Посмотреть сообщение
Суммирование (add), по весу ровно столько же, сколько и перемножение (mul), если, конечно, реализация выберет mul а не что-то из перебранного выше.
Я заметил, я ничерта не понимаю, о чем вы говорите. Вы как то так неочевидно мысли излагаете.

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Профит!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.11.2011, 08:32     Производительность операций
Еще ссылки по теме:

Влияет ли на производительность C++
C++ Константы, геттеры/сеттеры и производительность
C++ Производительность CPU, КЕШ, многопоточность

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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 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-ми битная, соответственно чем больше байт копируешь, тем больше требуется тактов.
Yandex
Объявления
22.11.2011, 08:32     Производительность операций
Ответ Создать тему
Опции темы

Текущее время: 16:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru