Помогите ускорить функцию на С

[fan_of_algoritms]

Как ускорить функцию?

Используется синтаксис 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;
}
 

[manul91]

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

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

[FomaNeverov]

Запустить в цикле, выполнить 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 глобальной или статичной, что-бы каждый раз не создавалась при вызове функции, или сравнивать сразу с числом.

[Sender]

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 --

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

[Pphantom]

Sender в сообщении #1341250 писал(а):

Или сразу

return (abs(d1 - d2) <= DBL_EPSILON);

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

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

[Munin]

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

[Sender]

Pphantom в сообщении #1341263 писал(а):

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

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

[Munin]

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

[Sender]

Munin в сообщении #1341273 писал(а):

каждая за своё количество

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

[GAA]

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. Различие невелико, но может и сыграть.


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

[Pphantom]

Sender в сообщении #1341271 писал(а):

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

Если я правильно помню, она выставляет флаги, которые потом сами надо как-то обрабатывать. В случае проверки на нестрогое равенство надо обрабатывать два флага вместо одного, и это занимает больше времени. Хотя наверняка утверждать не буду, возможно, что разница действительно пропала (раньше обычно была).

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

[fan_of_algoritms]

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

Используется синтаксис 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 раза.

[Pphantom]

fan_of_algoritms в сообщении #1341348 писал(а):

Идея, чтобы при сравнении чисел сопоставить абстрактный ноль машинному, хотя, я могу и неверно что-то понимать легко.

Дело в том,что порядок в double может оказаться меньше, чем $10^{-16}$. В итоге Вы получите, что, например, числа $10^{-50}$ и $10^{-100}$ равны, хотя они отличаются на 50 порядков. В некоторых случаях это, конечно, окажется разумным, а в некоторых - нет.

[fan_of_algoritms]

Pphantom в сообщении #1341350 писал(а):

fan_of_algoritms в сообщении #1341348 писал(а):

Идея, чтобы при сравнении чисел сопоставить абстрактный ноль машинному, хотя, я могу и неверно что-то понимать легко.

Дело в том,что порядок в double может оказаться меньше, чем $10^{-16}$. В итоге Вы получите, что, например, числа $10^{-50}$ и $10^{-100}$ равны, хотя они отличаются на 50 порядков. В некоторых случаях это, конечно, окажется разумным, а в некоторых - нет.

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

Используется синтаксис C++

long double

, как буд-то трудно было сделать.

[upgrade]

Иногда можно сразу возвращать дельту, если она возвращается в переменную boolean, то в переменной будет ЛОЖЬ если 0 и ИСТИНА, если не ноль.
как то так видимо в c++

bool dx(x1,x2)
{
return x1-x2;
}