You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by sebb <se...@gmail.com> on 2013/03/25 11:50:43 UTC
Re: svn commit: r1460604 - in /commons/proper/math/trunk/src:
changes/changes.xml main/java/org/apache/commons/math3/util/FastMath.java
On 25 March 2013 10:46, <lu...@apache.org> wrote:
> Author: luc
> Date: Mon Mar 25 10:46:42 2013
> New Revision: 1460604
>
> URL: http://svn.apache.org/r1460604
> Log:
> Improved speed of FastMath.abs methods, by removing branching.
>
> JIRA: MATH-954
>
> Modified:
> commons/proper/math/trunk/src/changes/changes.xml
> commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java
>
> Modified: commons/proper/math/trunk/src/changes/changes.xml
> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1460604&r1=1460603&r2=1460604&view=diff
> ==============================================================================
> --- commons/proper/math/trunk/src/changes/changes.xml (original)
> +++ commons/proper/math/trunk/src/changes/changes.xml Mon Mar 25 10:46:42 2013
> @@ -55,10 +55,13 @@ This is a minor release: It combines bug
> Changes to existing features were made in a backwards-compatible
> way such as to allow drop-in replacement of the v3.1[.1] JAR file.
> ">
> + <action dev="luc" type="update" issue="MATH-954" due-to="Charles Cooper">
> + Improved speed of FastMath.abs methods for all signatures, by removing branching.
> + </action>
> <action dev="luc" type="update" issue="MATH-953" due-to="Charles Cooper">
> Improved speed of several FastMath methods.
> </action>
> - <action dev="luc" type="fix" issue="MATH-934">
> + <action dev="luc" type="fix" issue="MATH-934">
> Fixed Complex.reciprocal() for zero argument.
> </action>
> <action dev="luc" type="update" issue="MATH-951" due-to="Charles Cooper">
>
> Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java
> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java?rev=1460604&r1=1460603&r2=1460604&view=diff
> ==============================================================================
> --- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java (original)
> +++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java Mon Mar 25 10:46:42 2013
> @@ -2987,7 +2987,8 @@ public class FastMath {
> * @return abs(x)
> */
> public static int abs(final int x) {
> - return (x < 0) ? -x : x;
> + final int i = x >>> 31;
> + return (x ^ (~i + 1)) + i;
Are we sure that's faster?
Surely branches aren't significantly slower than arithmetic operations.
> }
>
> /**
> @@ -2996,7 +2997,12 @@ public class FastMath {
> * @return abs(x)
> */
> public static long abs(final long x) {
> - return (x < 0l) ? -x : x;
> + final long l = x >>> 63;
> + // l is one if x negative zero else
> + // ~l+1 is zero if x is positive, -1 if x is negative
> + // x^(~l+1) is x is x is positive, ~x if x is negative
> + // add around
> + return (x ^ (~l + 1)) + l;
> }
>
> /**
> @@ -3005,7 +3011,10 @@ public class FastMath {
> * @return abs(x)
> */
> public static float abs(final float x) {
> - return (x < 0.0f) ? -x : (x == 0.0f) ? 0.0f : x; // -0.0 => +0.0
> + if ((Float.floatToRawIntBits(x) & Integer.MIN_VALUE) == 0) {
> + return x;
> + }
> + return -x;
> }
>
> /**
> @@ -3014,7 +3023,10 @@ public class FastMath {
> * @return abs(x)
> */
> public static double abs(double x) {
> - return (x < 0.0) ? -x : (x == 0.0) ? 0.0 : x; // -0.0 => +0.0
> + if ((Double.doubleToRawLongBits(x) & Long.MIN_VALUE) == 0) {
> + return x;
> + }
> + return -x;
> }
>
> /**
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: svn commit: r1460604 - in /commons/proper/math/trunk/src: changes/changes.xml
main/java/org/apache/commons/math3/util/FastMath.java
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 25/03/2013 12:56, sebb a écrit :
> On 25 March 2013 11:44, Luc Maisonobe <Lu...@free.fr> wrote:
>> Le 25/03/2013 11:50, sebb a écrit :
>>> On 25 March 2013 10:46, <lu...@apache.org> wrote:
>>>> Author: luc
>>>> Date: Mon Mar 25 10:46:42 2013
>>>> New Revision: 1460604
>>>>
>>>> URL: http://svn.apache.org/r1460604
>>>> Log:
>>>> Improved speed of FastMath.abs methods, by removing branching.
>>>>
>>>> JIRA: MATH-954
>>>>
>>>> Modified:
>>>> commons/proper/math/trunk/src/changes/changes.xml
>>>> commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java
>>>>
>>>> Modified: commons/proper/math/trunk/src/changes/changes.xml
>>>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1460604&r1=1460603&r2=1460604&view=diff
>>>> ==============================================================================
>>>> --- commons/proper/math/trunk/src/changes/changes.xml (original)
>>>> +++ commons/proper/math/trunk/src/changes/changes.xml Mon Mar 25 10:46:42 2013
>>>> @@ -55,10 +55,13 @@ This is a minor release: It combines bug
>>>> Changes to existing features were made in a backwards-compatible
>>>> way such as to allow drop-in replacement of the v3.1[.1] JAR file.
>>>> ">
>>>> + <action dev="luc" type="update" issue="MATH-954" due-to="Charles Cooper">
>>>> + Improved speed of FastMath.abs methods for all signatures, by removing branching.
>>>> + </action>
>>>> <action dev="luc" type="update" issue="MATH-953" due-to="Charles Cooper">
>>>> Improved speed of several FastMath methods.
>>>> </action>
>>>> - <action dev="luc" type="fix" issue="MATH-934">
>>>> + <action dev="luc" type="fix" issue="MATH-934">
>>>> Fixed Complex.reciprocal() for zero argument.
>>>> </action>
>>>> <action dev="luc" type="update" issue="MATH-951" due-to="Charles Cooper">
>>>>
>>>> Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java
>>>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java?rev=1460604&r1=1460603&r2=1460604&view=diff
>>>> ==============================================================================
>>>> --- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java (original)
>>>> +++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java Mon Mar 25 10:46:42 2013
>>>> @@ -2987,7 +2987,8 @@ public class FastMath {
>>>> * @return abs(x)
>>>> */
>>>> public static int abs(final int x) {
>>>> - return (x < 0) ? -x : x;
>>>> + final int i = x >>> 31;
>>>> + return (x ^ (~i + 1)) + i;
>>>
>>> Are we sure that's faster?
>>>
>>> Surely branches aren't significantly slower than arithmetic operations.
>>
>> The tests I did using Gilles PerfTestUtils show an improvement. Not a
>> very big one (about 5%), but an improvement.
>>
>> The reason for that is most probably branch prediction errors at
>> processor level. Once code has been inlined and compiled to native code,
>> the prediction of the branch to follow (if or else) drives the speed. As
>> for an abs() method, I think branch prediction is 50% true, 50% false
>> (it is not the same for a loop for example, as for example if you
>> iterate 10 times, it means the condition will be to stay in the loop 9
>> times and to exit only 1 time).
>
> What about
>
> if (x >= 0) return x;
> return -x;
>
> Would that be any faster?
No, it is still branching.
> It's simpler to read.
Sure.
Luc
>
>> Luc
>>
>>>
>>>> }
>>>>
>>>> /**
>>>> @@ -2996,7 +2997,12 @@ public class FastMath {
>>>> * @return abs(x)
>>>> */
>>>> public static long abs(final long x) {
>>>> - return (x < 0l) ? -x : x;
>>>> + final long l = x >>> 63;
>>>> + // l is one if x negative zero else
>>>> + // ~l+1 is zero if x is positive, -1 if x is negative
>>>> + // x^(~l+1) is x is x is positive, ~x if x is negative
>>>> + // add around
>>>> + return (x ^ (~l + 1)) + l;
>>>> }
>>>>
>>>> /**
>>>> @@ -3005,7 +3011,10 @@ public class FastMath {
>>>> * @return abs(x)
>>>> */
>>>> public static float abs(final float x) {
>>>> - return (x < 0.0f) ? -x : (x == 0.0f) ? 0.0f : x; // -0.0 => +0.0
>>>> + if ((Float.floatToRawIntBits(x) & Integer.MIN_VALUE) == 0) {
>>>> + return x;
>>>> + }
>>>> + return -x;
>>>> }
>>>>
>>>> /**
>>>> @@ -3014,7 +3023,10 @@ public class FastMath {
>>>> * @return abs(x)
>>>> */
>>>> public static double abs(double x) {
>>>> - return (x < 0.0) ? -x : (x == 0.0) ? 0.0 : x; // -0.0 => +0.0
>>>> + if ((Double.doubleToRawLongBits(x) & Long.MIN_VALUE) == 0) {
>>>> + return x;
>>>> + }
>>>> + return -x;
>>>> }
>>>>
>>>> /**
>>>>
>>>>
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>
>>>
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: svn commit: r1460604 - in /commons/proper/math/trunk/src:
changes/changes.xml main/java/org/apache/commons/math3/util/FastMath.java
Posted by sebb <se...@gmail.com>.
On 25 March 2013 11:44, Luc Maisonobe <Lu...@free.fr> wrote:
> Le 25/03/2013 11:50, sebb a écrit :
>> On 25 March 2013 10:46, <lu...@apache.org> wrote:
>>> Author: luc
>>> Date: Mon Mar 25 10:46:42 2013
>>> New Revision: 1460604
>>>
>>> URL: http://svn.apache.org/r1460604
>>> Log:
>>> Improved speed of FastMath.abs methods, by removing branching.
>>>
>>> JIRA: MATH-954
>>>
>>> Modified:
>>> commons/proper/math/trunk/src/changes/changes.xml
>>> commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java
>>>
>>> Modified: commons/proper/math/trunk/src/changes/changes.xml
>>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1460604&r1=1460603&r2=1460604&view=diff
>>> ==============================================================================
>>> --- commons/proper/math/trunk/src/changes/changes.xml (original)
>>> +++ commons/proper/math/trunk/src/changes/changes.xml Mon Mar 25 10:46:42 2013
>>> @@ -55,10 +55,13 @@ This is a minor release: It combines bug
>>> Changes to existing features were made in a backwards-compatible
>>> way such as to allow drop-in replacement of the v3.1[.1] JAR file.
>>> ">
>>> + <action dev="luc" type="update" issue="MATH-954" due-to="Charles Cooper">
>>> + Improved speed of FastMath.abs methods for all signatures, by removing branching.
>>> + </action>
>>> <action dev="luc" type="update" issue="MATH-953" due-to="Charles Cooper">
>>> Improved speed of several FastMath methods.
>>> </action>
>>> - <action dev="luc" type="fix" issue="MATH-934">
>>> + <action dev="luc" type="fix" issue="MATH-934">
>>> Fixed Complex.reciprocal() for zero argument.
>>> </action>
>>> <action dev="luc" type="update" issue="MATH-951" due-to="Charles Cooper">
>>>
>>> Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java
>>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java?rev=1460604&r1=1460603&r2=1460604&view=diff
>>> ==============================================================================
>>> --- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java (original)
>>> +++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java Mon Mar 25 10:46:42 2013
>>> @@ -2987,7 +2987,8 @@ public class FastMath {
>>> * @return abs(x)
>>> */
>>> public static int abs(final int x) {
>>> - return (x < 0) ? -x : x;
>>> + final int i = x >>> 31;
>>> + return (x ^ (~i + 1)) + i;
>>
>> Are we sure that's faster?
>>
>> Surely branches aren't significantly slower than arithmetic operations.
>
> The tests I did using Gilles PerfTestUtils show an improvement. Not a
> very big one (about 5%), but an improvement.
>
> The reason for that is most probably branch prediction errors at
> processor level. Once code has been inlined and compiled to native code,
> the prediction of the branch to follow (if or else) drives the speed. As
> for an abs() method, I think branch prediction is 50% true, 50% false
> (it is not the same for a loop for example, as for example if you
> iterate 10 times, it means the condition will be to stay in the loop 9
> times and to exit only 1 time).
What about
if (x >= 0) return x;
return -x;
Would that be any faster?
It's simpler to read.
> Luc
>
>>
>>> }
>>>
>>> /**
>>> @@ -2996,7 +2997,12 @@ public class FastMath {
>>> * @return abs(x)
>>> */
>>> public static long abs(final long x) {
>>> - return (x < 0l) ? -x : x;
>>> + final long l = x >>> 63;
>>> + // l is one if x negative zero else
>>> + // ~l+1 is zero if x is positive, -1 if x is negative
>>> + // x^(~l+1) is x is x is positive, ~x if x is negative
>>> + // add around
>>> + return (x ^ (~l + 1)) + l;
>>> }
>>>
>>> /**
>>> @@ -3005,7 +3011,10 @@ public class FastMath {
>>> * @return abs(x)
>>> */
>>> public static float abs(final float x) {
>>> - return (x < 0.0f) ? -x : (x == 0.0f) ? 0.0f : x; // -0.0 => +0.0
>>> + if ((Float.floatToRawIntBits(x) & Integer.MIN_VALUE) == 0) {
>>> + return x;
>>> + }
>>> + return -x;
>>> }
>>>
>>> /**
>>> @@ -3014,7 +3023,10 @@ public class FastMath {
>>> * @return abs(x)
>>> */
>>> public static double abs(double x) {
>>> - return (x < 0.0) ? -x : (x == 0.0) ? 0.0 : x; // -0.0 => +0.0
>>> + if ((Double.doubleToRawLongBits(x) & Long.MIN_VALUE) == 0) {
>>> + return x;
>>> + }
>>> + return -x;
>>> }
>>>
>>> /**
>>>
>>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: svn commit: r1460604 - in /commons/proper/math/trunk/src: changes/changes.xml
main/java/org/apache/commons/math3/util/FastMath.java
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 25/03/2013 11:50, sebb a écrit :
> On 25 March 2013 10:46, <lu...@apache.org> wrote:
>> Author: luc
>> Date: Mon Mar 25 10:46:42 2013
>> New Revision: 1460604
>>
>> URL: http://svn.apache.org/r1460604
>> Log:
>> Improved speed of FastMath.abs methods, by removing branching.
>>
>> JIRA: MATH-954
>>
>> Modified:
>> commons/proper/math/trunk/src/changes/changes.xml
>> commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java
>>
>> Modified: commons/proper/math/trunk/src/changes/changes.xml
>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1460604&r1=1460603&r2=1460604&view=diff
>> ==============================================================================
>> --- commons/proper/math/trunk/src/changes/changes.xml (original)
>> +++ commons/proper/math/trunk/src/changes/changes.xml Mon Mar 25 10:46:42 2013
>> @@ -55,10 +55,13 @@ This is a minor release: It combines bug
>> Changes to existing features were made in a backwards-compatible
>> way such as to allow drop-in replacement of the v3.1[.1] JAR file.
>> ">
>> + <action dev="luc" type="update" issue="MATH-954" due-to="Charles Cooper">
>> + Improved speed of FastMath.abs methods for all signatures, by removing branching.
>> + </action>
>> <action dev="luc" type="update" issue="MATH-953" due-to="Charles Cooper">
>> Improved speed of several FastMath methods.
>> </action>
>> - <action dev="luc" type="fix" issue="MATH-934">
>> + <action dev="luc" type="fix" issue="MATH-934">
>> Fixed Complex.reciprocal() for zero argument.
>> </action>
>> <action dev="luc" type="update" issue="MATH-951" due-to="Charles Cooper">
>>
>> Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java
>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java?rev=1460604&r1=1460603&r2=1460604&view=diff
>> ==============================================================================
>> --- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java (original)
>> +++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/FastMath.java Mon Mar 25 10:46:42 2013
>> @@ -2987,7 +2987,8 @@ public class FastMath {
>> * @return abs(x)
>> */
>> public static int abs(final int x) {
>> - return (x < 0) ? -x : x;
>> + final int i = x >>> 31;
>> + return (x ^ (~i + 1)) + i;
>
> Are we sure that's faster?
>
> Surely branches aren't significantly slower than arithmetic operations.
The tests I did using Gilles PerfTestUtils show an improvement. Not a
very big one (about 5%), but an improvement.
The reason for that is most probably branch prediction errors at
processor level. Once code has been inlined and compiled to native code,
the prediction of the branch to follow (if or else) drives the speed. As
for an abs() method, I think branch prediction is 50% true, 50% false
(it is not the same for a loop for example, as for example if you
iterate 10 times, it means the condition will be to stay in the loop 9
times and to exit only 1 time).
Luc
>
>> }
>>
>> /**
>> @@ -2996,7 +2997,12 @@ public class FastMath {
>> * @return abs(x)
>> */
>> public static long abs(final long x) {
>> - return (x < 0l) ? -x : x;
>> + final long l = x >>> 63;
>> + // l is one if x negative zero else
>> + // ~l+1 is zero if x is positive, -1 if x is negative
>> + // x^(~l+1) is x is x is positive, ~x if x is negative
>> + // add around
>> + return (x ^ (~l + 1)) + l;
>> }
>>
>> /**
>> @@ -3005,7 +3011,10 @@ public class FastMath {
>> * @return abs(x)
>> */
>> public static float abs(final float x) {
>> - return (x < 0.0f) ? -x : (x == 0.0f) ? 0.0f : x; // -0.0 => +0.0
>> + if ((Float.floatToRawIntBits(x) & Integer.MIN_VALUE) == 0) {
>> + return x;
>> + }
>> + return -x;
>> }
>>
>> /**
>> @@ -3014,7 +3023,10 @@ public class FastMath {
>> * @return abs(x)
>> */
>> public static double abs(double x) {
>> - return (x < 0.0) ? -x : (x == 0.0) ? 0.0 : x; // -0.0 => +0.0
>> + if ((Double.doubleToRawLongBits(x) & Long.MIN_VALUE) == 0) {
>> + return x;
>> + }
>> + return -x;
>> }
>>
>> /**
>>
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org