2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Помогите ускорить функцию на С
Сообщение25.09.2018, 04:59 


31/01/12
88
Как ускорить функцию?

Используется синтаксис C++
bool EqualDoubles(
                        const double & d1,
                        const double & d2
                )
{
        const double epsilon = DBL_EPSILON;
        if((d1 - d2) > epsilon) return false;
        if((d1 - d2) < -epsilon) return false;
        return true;
}
 

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 05:22 


24/08/12
505
1) Сравнение действительных чисел на равенство - не конструктивная операция. Если вам кажется, что это нужно - то у вас что-то не так (в программировании, все итак конструктивно по-факту)

2) Но если уж ОЧЕНь нужно - можно положить DBL_EPSILON=0 и пользоваться просто if (d1 == d2) с тем же успехом.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 07:03 


28/07/17
230
Запустить в цикле, выполнить 1 000 000 раз и измерить время - т.е. проверить всё самому. Попробовать такие варианты:
Код:
        double x = d1 - d2;
        const double epsilon = DBL_EPSILON;

        if(x > epsilon) return false;
        if(x < -epsilon) return false;
        return true;

Код:
        const double epsilon = DBL_EPSILON;
        if(abs(d1 - d2) > epsilon) return false;
        return true;

Можно попробовать в функцию передать уже разность d1 - d2. Попробовать сделать epsilon глобальной или статичной, что-бы каждый раз не создавалась при вызове функции, или сравнивать сразу с числом.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 09:20 
Заслуженный участник


14/01/11
2021
FomaNeverov в сообщении #1341235 писал(а):
Код:
        const double epsilon = DBL_EPSILON;
        if((d1 - d2) > abs(epsilon)) return false;
        return true;


Или сразу
Код:
return (abs(d1 - d2) <= DBL_EPSILON);


-- Вт сен 25, 2018 09:25:32 --

Или вообще отказаться от вызова и запихать это выражение в вызывающий код. :-)

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 10:01 
Супермодератор
Аватара пользователя


09/05/12
16543
Кронштадт
Sender в сообщении #1341250 писал(а):
Или сразу
Код:
return (abs(d1 - d2) <= DBL_EPSILON);

Проверять нестрогое равенство для вещественных чисел с практической точки зрения бессмысленно, а проверка строгого, насколько я помню, выполняется в среднем быстрее.

Правда, и исходный код в целом с практической точки зрения лишен смысла. DBL_EPSILON - это же предопределенная константа, характерная относительная погрешность типа double. Т.е. для чисел порядка единицы или более это de facto проверка на точное равенство, а для меньших чисел - как повезет, у них же порядок может быть и меньше.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 10:10 
Заслуженный участник
Аватара пользователя


30/01/06
67802
В практической жизни намного полезнее проверка на равенство с настраиваемой или указанной погрешностью. Можно и с относительной.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 10:22 
Заслуженный участник


14/01/11
2021
Pphantom в сообщении #1341263 писал(а):
Проверять нестрогое равенство для вещественных чисел с практической точки зрения бессмысленно, а проверка строгого, насколько я помню, выполняется в среднем быстрее.

Вроде бы и в том, и в другом случае сравнение выполняется одной ассемблерной инструкцией наподобие FCOMI. Это применительно к архитектуре x86, конечно.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 10:42 
Заслуженный участник
Аватара пользователя


30/01/06
67802
Вот только "ассемблерные инструкции" (машинные команды) раздела F* (с плавающей запятой) могут выполняться за много-много тактов, каждая за своё количество. Тут надо детальней копаться.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 12:54 
Заслуженный участник


14/01/11
2021
Munin в сообщении #1341273 писал(а):
каждая за своё количество

В том-то и дело, что в обоих случаях используется одна и та же. Просто флаги разные устанавливаются.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 13:33 
Экс-модератор


12/07/07
3585
Донецк, Украина
Sender, x86 — это очень широкое понятие. На 286 процессорах — fcom/fcomp/fcompp c переброской битов SW через ax (при помощи fstsw ax) в регистр флагов (при помощи sahf) [Регистр флагов].

На современных процессорах в случае fpu-ориентированных вычислений сравнивать можно fcomi + переход по значениям флагов в eflags. Если fcomi регистровое, то где-то latency — 4 / throughput — 1 (На Sandy Bridge — 4/1; Ivy Bridge — 5/1; SkylakeX — 4/1; см. Agner Fog "4. Instruction tables (Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs)"). Легко нагуглить. Там есть данные и для других процессоров.

Можно было бы на равенство попробовать проверять при помощи хоr (throughput около 0.5). Однако перед сравнением вычитание. Следовательно, для использования хоr нужна пересылка из регистра fpu в регистр общего назначения. Поэтому, если выигрыш и будет, то ничтожный.

Но на сегодняшний день вычисления с числами с плавающей точкой в основном SSE/AVX-ориентированные.

Инструкции сравнения (на равенство, нестрогое и строгое неравенство) cmppd/cmpps быстры (где-то latency — 3, throughput — 0.5), но не изменяют флаги, а заносят в приемник (регистр SSE/AVX) нули или единицы. {UPD. У Sandy Bridge, Ivy Bridge и Haswell latency/ throughput — 3/1 [см., например, “Inel 64 and IA-32 Architectures Optimization manual”] /UPD}. Результат типа Boolean в большинстве компиляторов возвращается функцией через регистр общего назначения: ax/eax/rax. Нужно скопировать из xmm в ax/eax/rax и, если истина кодируется одним битом, то при помощи and обнулить старшие биты {Upd или результат сравнения в регистре xmm скопировать в rax при помощи movmskpd: latency/troughput — 2/1. в случае истины в rax будет как раз 1 в младшем бите. /Upd}.

Очевидная альтернатива: скопировать разность из xmm в регистр общего назначения, выполнить битовую операцию и по результату в регистре флагов занести в ax/eax/rax значение. (Это на глаз не быстрее, а медленнее cmppd). Если же в качестве истины годится любой ненулевой результат, то при сравнении на равенство/неравенство можно результат xor использовать как возвращаемое значение. У xor меньше latency/throughput (где-то 1 / 0.5 или 0.25, если второй операнд в регистре) по сравнению с cmppd. Различие невелико, но может и сыграть.


Да, мне тоже непонятно, для чего нужен текст в стартовом сообщении.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 13:47 
Супермодератор
Аватара пользователя


09/05/12
16543
Кронштадт
Sender в сообщении #1341271 писал(а):
Вроде бы и в том, и в другом случае сравнение выполняется одной ассемблерной инструкцией наподобие FCOMI. Это применительно к архитектуре x86, конечно.
Если я правильно помню, она выставляет флаги, которые потом сами надо как-то обрабатывать. В случае проверки на нестрогое равенство надо обрабатывать два флага вместо одного, и это занимает больше времени. Хотя наверняка утверждать не буду, возможно, что разница действительно пропала (раньше обычно была).

P.S. О, выше GAA дал намного более детальный ответ.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 14:09 


31/01/12
88
Идея, чтобы при сравнении чисел сопоставить абстрактный ноль машинному, хотя, я могу и неверно что-то понимать легко. Пока по замерам, из предлженных вариантов, быстрее всего получается:

Используется синтаксис C++
bool EqualDoubles(
                        const double & d1,
                        const double & d2
                )
{
        register const double difference = d1 - d2;
        if (difference > 2.2204460492503131e-016) return false;
        if (difference < -2.2204460492503131e-016) return false;
        return true;
}


В 1,0657 раза.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 14:18 
Супермодератор
Аватара пользователя


09/05/12
16543
Кронштадт
fan_of_algoritms в сообщении #1341348 писал(а):
Идея, чтобы при сравнении чисел сопоставить абстрактный ноль машинному, хотя, я могу и неверно что-то понимать легко.
Дело в том,что порядок в double может оказаться меньше, чем $10^{-16}$. В итоге Вы получите, что, например, числа $10^{-50}$ и $10^{-100}$ равны, хотя они отличаются на 50 порядков. В некоторых случаях это, конечно, окажется разумным, а в некоторых - нет.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 14:29 


31/01/12
88
Pphantom в сообщении #1341350 писал(а):
fan_of_algoritms в сообщении #1341348 писал(а):
Идея, чтобы при сравнении чисел сопоставить абстрактный ноль машинному, хотя, я могу и неверно что-то понимать легко.
Дело в том,что порядок в double может оказаться меньше, чем $10^{-16}$. В итоге Вы получите, что, например, числа $10^{-50}$ и $10^{-100}$ равны, хотя они отличаются на 50 порядков. В некоторых случаях это, конечно, окажется разумным, а в некоторых - нет.

Спасибо, это понятно. Мне 16 порядка хватит по значениям, важнее не потерять в точности внутри него. Хотя, жаль, конечно, что в MVS нет
Используется синтаксис C++
long double
, как буд-то трудно было сделать.

 Профиль  
                  
 
 Re: Помогите ускорить функцию на С
Сообщение25.09.2018, 14:31 


07/08/14
19/02/19
2879
Иногда можно сразу возвращать дельту, если она возвращается в переменную boolean, то в переменной будет ЛОЖЬ если 0 и ИСТИНА, если не ноль.
как то так видимо в c++
Код:
bool dx(x1,x2)
{
return x1-x2;
}

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group