lib: Add strongly typed 64bit int_sqrt
Subsystems (2)
PATCH v10 1/3 lib: Add strongly typed 64bit int_sqrt
There is no option to perform 64bit integer sqrt on 32bit platform. Added stronger typed int_sqrt64 enables the 64bit calculations to be performed on 32bit platforms. Although int_sqrt() is a rough approximation, the same algorithm is used in int_sqrt64() as good enough on 32bit platform.
--- include/linux/kernel.h | 9 +++++++++ lib/int_sqrt.c | 31 +++++++++++++++++++++++++++++++ 2 files changed, 40 insertions(+)
include/linux/kernel.h +9 -0
@@ -460,6 +460,15 @@ extern int func_ptr_is_kernel_text(void *ptr);unsigned long int_sqrt (unsigned long ); +#if BITS_PER_LONG <64 +u32 int_sqrt64 (u64 x); +#else +static inline u32 int_sqrt64 (u64 x) +{ +return (u32 )int_sqrt (x); +} +#endif +extern void bust_spinlocks (int yes);extern int oops_in_progress;/* If set, an oops, panic(), BUG() or die() is in progress */ extern int panic_timeout;
lib/int_sqrt.c +31 -0
@@ -7,6 +7,7 @@#include <linux/kernel.h> #include <linux/export.h> +#include <linux/bitops.h> /** * int_sqrt - rough approximation to sqrt
@@ -36,3 +37,33 @@ unsigned long int_sqrt(unsigned long x)return y; }EXPORT_SYMBOL (int_sqrt); + +#if BITS_PER_LONG <64 +/** +* int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input +* is expected. +* @x: 64bit integer of which to calculate the sqrt +*/ +u32 int_sqrt64 (u64 x) +{ +u64 b, m, y =0 ; + +if (x <=1 ) +return x; + + m =1ULL << (fls64 (x) & ~1ULL ); +while (m !=0 ) { + b = y + m; + y >>=1 ; + +if (x >= b) { + x -= b; + y += m; + } + m >>=2 ; + } + +return y; +} +EXPORT_SYMBOL (int_sqrt64); +#endif
Signature · 1 line
2.15.0
From: Crt Mori
Quoted 7 lines
Sent: 20 December 2017 14:20
There is no option to perform 64bit integer sqrt on 32bit platform. Added stronger typed
int_sqrt64enables the 64bit calculations to be performed on 32bit platforms. Althoughint_sqrt()is a rough approximation, the same algorithm is used inint_sqrt64()as good enough on 32bit platform.
The algorithm used gives an exact (rounded down) square root, not an approximation.
With minor changes it ought to be possible to remove most of the 64bit arithmetic and shifts.
If you care about performance then using 32 bit maths will be much faster.
David
Quoted 12 lines · David Laight
From: Crt Mori
Quoted 7 lines
Sent: 20 December 2017 14:20
There is no option to perform 64bit integer sqrt on 32bit platform. Added stronger typed
int_sqrt64enables the 64bit calculations to be performed on 32bit platforms. Althoughint_sqrt()is a rough approximation, the same algorithm is used inint_sqrt64()as good enough on 32bit platform.The algorithm used gives an exact (rounded down) square root, not an approximation.
OK, noted. This is from new changed function indeed - will change in v11.
Quoted 5 lines
With minor changes it ought to be possible to remove most of the 64bit arithmetic and shifts.
If you care about performance then using 32 bit maths will be much faster.
I need precision not the performance. That is why I would like to leave int_sqrt as one for good performance while my will be used when you require a precision.
Quoted 2 lines
David
Quoted 4 lines · David Laight
With minor changes it ought to be possible to remove most of the 64bit arithmetic and shifts.
If you care about performance then using 32 bit maths will be much faster.
Some, u64 add/sub/shift isn't exactly expensive, but yes, I also indicated that improvement is possible. At the very least y can be made a u32 I suppose.
Quoted 10 lines · Peter Zijlstra
Quoted 4 lines · David Laight
With minor changes it ought to be possible to remove most of the 64bit arithmetic and shifts.
If you care about performance then using 32 bit maths will be much faster.
Some, u64 add/sub/shift isn't exactly expensive, but yes, I also indicated that improvement is possible. At the very least y can be made a u32 I suppose.
OK, is there any more easy optimizations you see?
From: Crt Mori
Quoted 8 lines
Sent: 20 December 2017 16:17
Quoted 5 lines · Peter Zijlstra
Quoted 3 lines · David Laight
With minor changes it ought to be possible to remove most of the 64bit arithmetic and shifts.
Quoted 7 lines
Quoted 5 lines
Quoted 1 line
If you care about performance then using 32 bit maths will be much faster.
Some, u64 add/sub/shift isn't exactly expensive, but yes, I also indicated that improvement is possible. At the very least y can be made a u32 I suppose.
OK, is there any more easy optimizations you see?
I think this version works.
It doesn't have the optimisation for small values.
unsigned int sqrt64(unsigned long long x)
{
unsigned int x_hi = x >> 32;
unsigned int b = 0;
unsigned int y = 0;
unsigned int i;
for (i = 0; i < 32; i++) {
b <<= 2;
b |= x_hi >> 30;
x_hi <<= 2;
if (i == 15)
x_hi = x;
y <<= 1;
if (b > y)
b -= ++y;
}
return y;
}Put it through cc -O3 -m32 -c -o sqrt64.o sqrt64.c and then objdump sqrt64.o and compare to that of your version.
David
Quoted 20 lines · David Laight
From: Crt Mori
Quoted 8 lines
Sent: 20 December 2017 16:17
Quoted 5 lines · Peter Zijlstra
Quoted 3 lines · David Laight
With minor changes it ought to be possible to remove most of the 64bit arithmetic and shifts.
Quoted 7 lines
Quoted 5 lines
Quoted 1 line
If you care about performance then using 32 bit maths will be much faster.
Some, u64 add/sub/shift isn't exactly expensive, but yes, I also indicated that improvement is possible. At the very least y can be made a u32 I suppose.
OK, is there any more easy optimizations you see?
I think this version works.
It doesn't have the optimisation for small values.
Quoted 8 lines
unsigned int sqrt64(unsigned long long x)
{ unsigned int x_hi = x >> 32; unsigned int b = 0; unsigned int y = 0; unsigned int i;
Perhaps add:
if (x <= UINT_MAX) return int_sqrt((unsigned long)x);
Quoted 18 lines
for (i = 0; i < 32; i++) { b <<= 2; b |= x_hi >> 30; x_hi <<= 2; if (i == 15) x_hi = x; y <<= 1; if (b > y) b -= ++y; } return y; }Put it through cc -O3 -m32 -c -o sqrt64.o
sqrt64.cand then objdump sqrt64.o and compare to that of your version.David
From: Joe Perches
Quoted 1 line
Sent: 20 December 2017 17:20
...
Quoted 11 lines
Quoted 11 lines
I think this version works.
It doesn't have the optimisation for small values.unsigned int sqrt64(unsigned long long x)
{ unsigned int x_hi =3D x >> 32; unsigned int b =3D 0; unsigned int y =3D 0; unsigned int i;
Quoted 5 lines
=20
Perhaps add:
=20if (x <=3D UINT_MAX) return int_sqrt((unsigned long)x);
Actually something like:
i =3D 32;
if (!x_hi) {
x_hi =3D x;
i =3D 16;
}
=09
if (!(x_hi & 0xffff0000)) {
x_hi <<=3D 16;
i -=3D 8;
}Repeat for 0xff000000, 0xf0000000 and 0xc0000000 and adjust loop to count d= own.
David
Quoted 15 lines
=20
Quoted 14 lines
for (i =3D 0; i < 32; i++) { b <<=3D 2; b |=3D x_hi >> 30; x_hi <<=3D 2; if (i =3D=3D 15) x_hi =3D x; y <<=3D 1; if (b > y) b -=3D ++y; } return y; }Put it through cc -O3 -m32 -c -o sqrt64.o
sqrt64.cand then objdump sqr=
t64.o
Quoted 4 lines
Quoted 4 lines
and compare to that of your version.
David
Quoted 41 lines · David Laight
From: Crt Mori
Quoted 8 lines
Sent: 20 December 2017 16:17
Quoted 5 lines · Peter Zijlstra
Quoted 3 lines · David Laight
With minor changes it ought to be possible to remove most of the 64bit arithmetic and shifts.
Quoted 7 lines
Quoted 5 lines
Quoted 1 line
If you care about performance then using 32 bit maths will be much faster.
Some, u64 add/sub/shift isn't exactly expensive, but yes, I also indicated that improvement is possible. At the very least y can be made a u32 I suppose.
OK, is there any more easy optimizations you see?
I think this version works.
It doesn't have the optimisation for small values.unsigned int sqrt64(unsigned long long x)
{ unsigned int x_hi = x >> 32; unsigned int b = 0; unsigned int y = 0; unsigned int i; for (i = 0; i < 32; i++) { b <<= 2; b |= x_hi >> 30; x_hi <<= 2; if (i == 15) x_hi = x; y <<= 1; if (b > y) b -= ++y; } return y; }
Quoted 5 lines
Put it through cc -O3 -m32 -c -o sqrt64.o
sqrt64.cand then objdump sqrt64.o and compare to that of your version.David
Wow, thanks. This seems like a major change.
I did a quick run through unit tests for the sensor and the results are way off. On the sensor I had to convert double calculations to integer calculations and target was to get end result within 0.02 degC (with previous approximate sqrt implementation) in sensor working range. This now gets into 3 degC delta at least and some are way off. It might be off because of some scaling on the other hand during the equation (not exactly comparing sqrt implementations here).
I will need a bit more testing of this to see if it is replaceable.
From: Crt Mori
Quoted 2 lines
Sent: 20 December 2017 17:30
To: David Laight
...
Quoted 24 lines
Quoted 15 lines
I think this version works.
It doesn't have the optimisation for small values.unsigned int sqrt64(unsigned long long x)
{ unsigned int x_hi = x >> 32; unsigned int b = 0; unsigned int y = 0; unsigned int i; for (i = 0; i < 32; i++) { b <<= 2; b |= x_hi >> 30; x_hi <<= 2;Quoted 8 lines
if (i == 15) x_hi = x; y <<= 1; if (b > y) b -= ++y; } return y; }
Quoted 1 line
Wow, thanks. This seems like a major change.
Not really, it is just doing it slightly differently.
The algorithm is the 'schoolboy' one that used to be taught at school. (Although I found it in a boot from the 1930s.)
I compared the object code for amd64 (doesn't need to reload 'x_hi' half way through) against the original loop.
They are much the same size, execution speed will depend the lengths of the dependency chains.
Quoted 9 lines
I did a quick run through unit tests for the sensor and the results are way off. On the sensor I had to convert double calculations to integer calculations and target was to get end result within 0.02 degC (with previous approximate sqrt implementation) in sensor working range. This now gets into 3 degC delta at least and some are way off. It might be off because of some scaling on the other hand during the equation (not exactly comparing sqrt implementations here).
I will need a bit more testing of this to see if it is replaceable.
You probably need to put values through both (all 3) functions to see where you are getting errors.
It might be rounding, or there might be a fubar somewhere.
David
From: Crt Mori
Quoted 26 lines
Sent: 20 December 2017 17:30
Quoted 25 lines
Quoted 1 line
OK, is there any more easy optimizations you see?
I think this version works.
It doesn't have the optimisation for small values.unsigned int sqrt64(unsigned long long x)
{ unsigned int x_hi = x >> 32; unsigned int b = 0; unsigned int y = 0; unsigned int i; for (i = 0; i < 32; i++) { b <<= 2; b |= x_hi >> 30; x_hi <<= 2; if (i == 15) x_hi = x; y <<= 1; if (b > y) b -= ++y; } return y; }
..
Quoted 8 lines
I did a quick run through unit tests for the sensor and the results are way off. On the sensor I had to convert double calculations to integer calculations and target was to get end result within 0.02 degC (with previous approximate sqrt implementation) in sensor working range. This now gets into 3 degC delta at least and some are way off. It might be off because of some scaling on the other hand during the equation (not exactly comparing sqrt implementations here).
I didn't get it quite right...
The last few lines need to be:
if (b > y) {
b -= ++y;
y++;
}
}
return y >> 1;
}Although that then fails for inputs larger than 2^62.
David
RnJvbTogQ3J0IE1vcmkNCj4gU2VudDogMjAgRGVjZW1iZXIgMjAxNyAxNzozMA0KPiBJIGRpZCBh IHF1aWNrIHJ1biB0aHJvdWdoIHVuaXQgdGVzdHMgZm9yIHRoZSBzZW5zb3IgYW5kIHRoZSByZXN1 bHRzDQo+IGFyZSB3YXkgb2ZmDQo+IC4uLg0KDQpUcnkgdGhpcyB2ZXJzaW9uIGluc3RlYWQ6DQp1 bnNpZ25lZCBpbnQgc3FydDY0KHVuc2lnbmVkIGxvbmcgbG9uZyB4X2luKQ0Kew0KICAgICAgICB1 bnNpZ25lZCBpbnQgeCA9IHhfaW4gPj4gMzI7DQoNCiAgICAgICAgdW5zaWduZWQgaW50IGIgPSAw Ow0KICAgICAgICB1bnNpZ25lZCBpbnQgeSA9IDA7DQogICAgICAgIHVuc2lnbmVkIGludCBpOw0K DQogICAgICAgIGkgPSAzMTsNCiAgICAgICAgaWYgKCF4KSB7DQogICAgICAgICAgICAgICAgeCA9 IHhfaW47DQogICAgICAgICAgICAgICAgaSA9IDE1Ow0KICAgICAgICB9DQogICAgICAgIGlmICgh KHggJiAweGZmZmYwMDAwKSkgew0KICAgICAgICAgICAgICAgIHggPDw9IDE2Ow0KICAgICAgICAg ICAgICAgIGkgLT0gODsNCiAgICAgICAgfQ0KICAgICAgICBpZiAoISh4ICYgMHhmZjAwMDAwMCkp IHsNCiAgICAgICAgICAgICAgICB4IDw8PSA4Ow0KICAgICAgICAgICAgICAgIGkgLT0gNDsNCiAg ICAgICAgfQ0KICAgICAgICBpZiAoISh4ICYgMHhmMDAwMDAwMCkpIHsNCiAgICAgICAgICAgICAg ICB4IDw8PSA0Ow0KICAgICAgICAgICAgICAgIGkgLT0gMjsNCiAgICAgICAgfQ0KDQogICAgICAg IGRvIHsNCiAgICAgICAgICAgICAgICBiIDw8PSAyOw0KICAgICAgICAgICAgICAgIGIgfD0geCA+ PiAzMDsNCiAgICAgICAgICAgICAgICB4IDw8PSAyOw0KICAgICAgICAgICAgICAgIGlmIChpID09 IDE2KQ0KICAgICAgICAgICAgICAgICAgICAgICAgeCA9IHhfaW47DQogICAgICAgICAgICAgICAg eSA8PD0gMTsNCiAgICAgICAgICAgICAgICBpZiAoYiA+IHkpIHsNCiAgICAgICAgICAgICAgICAg ICAgICAgIGIgLT0gKyt5Ow0KICAgICAgICAgICAgICAgICAgICAgICAgeSsrOw0KICAgICAgICAg ICAgICAgIH0NCiAgICAgICAgfSB3aGlsZSAoLS1pKTsNCg0KICAgICAgICAvKiAnYicgYmVjb21l cyAzMyBiaXRzIGlmIHRoZSBpbnB1dCBpcyBncmVhdGVyIHRoYW4gMl42MiAqLw0KICAgICAgICBi IDw8PSAxOw0KICAgICAgICBiIHw9IHggPj4gMzE7DQogICAgICAgIGlmIChiID4geSB8fCAoYiA9 PSB5ICYmIHggJiAoMXUgPDwgMzApKSkNCiAgICAgICAgICAgICAgICB5IHw9IDE7DQoNCiAgICAg ICAgcmV0dXJuIHk7DQp9DQoNCkkndmUgdGVzdGVkIHRoYXQgb25lIHdpdGggbW9yZSB2YWx1ZXMu DQoNCglEYXZpZA0KDQo=
Quoted 6 lines · David Laight
From: Crt Mori
Quoted 4 lines
Sent: 20 December 2017 17:30
I did a quick run through unit tests for the sensor and the results are way off
...
Quoted 8 lines
Try this version instead:
unsigned intsqrt64(unsigned long long x_in){ unsigned int x = x_in >> 32; unsigned int b = 0; unsigned int y = 0; unsigned int i;
i can be u8. And I will still use explicit typing.
Quoted 10 lines
i = 31;
if (!x) {
x = x_in;
i = 15;
}
if (!(x & 0xffff0000)) {
x <<= 16;
i -= 8;
}Quoted 9 lines
if (!(x & 0xff000000)) {
x <<= 8;
i -= 4;
}
if (!(x & 0xf0000000)) {
x <<= 4;
i -= 2;
}This part above looks like FLS
Quoted 22 lines
do {
b <<= 2;
b |= x >> 30;
x <<= 2;
if (i == 16)
x = x_in;
y <<= 1;
if (b > y) {
b -= ++y;
y++;
}
} while (--i);
/* 'b' becomes 33 bits if the input is greater than 2^62 */
b <<= 1;
b |= x >> 31;
if (b > y || (b == y && x & (1u << 30)))
y |= 1;
return y;
}Quoted 4 lines
I've tested that one with more values.
David
This one indeed works. I did some more testing this morning and I am fine with either.
So question is: Do I make change as per David's suggestion with his sign-off, or leave the version it was before the change?
RnJvbTogQ3J0IE1vcmkNCj4gU2VudDogMjEgRGVjZW1iZXIgMjAxNyAxMzoxOA0KLi4uDQo+ID4g ICAgICAgICB1bnNpZ25lZCBpbnQgaTsNCj4gDQo+IGkgY2FuIGJlIHU4LiBBbmQgSSB3aWxsIHN0 aWxsIHVzZSBleHBsaWNpdCB0eXBpbmcuDQoNCnU4IHdpbGwgYWRkIGV4dHJhIGNvZGUsIHVuc2ln bmVkIGludCBpcyBnb29kLg0KJ3gnIG5lZWRzIHRvIGJlIHUzMiwgJ3knIGFuZCAnYicgY291bGQg YmUgbGFyZ2VyLg0KDQpJIHdhcyB0ZXN0aW5nIGluIHVzZXJzcGFjZS4NCg0KLi4uDQo+IFRoaXMg cGFydCBhYm92ZSBsb29rcyBsaWtlIEZMUw0KSXQgYWxzbyBkb2VzIHRoZSByZXN0IG9mIHRoZSBy ZXF1aXJlZCBzaGlmdHMuDQoNCi4uLg0KPiBUaGlzIG9uZSBpbmRlZWQgd29ya3MuIEkgZGlkIHNv bWUgbW9yZSB0ZXN0aW5nIHRoaXMgbW9ybmluZyBhbmQgSSBhbQ0KPiBmaW5lIHdpdGggZWl0aGVy Lg0KPiANCj4gU28gcXVlc3Rpb24gaXM6IERvIEkgbWFrZSBjaGFuZ2UgYXMgcGVyIERhdmlkJ3Mg c3VnZ2VzdGlvbiB3aXRoIGhpcw0KPiBzaWduLW9mZiwgb3IgbGVhdmUgdGhlIHZlcnNpb24gaXQg d2FzIGJlZm9yZSB0aGUgY2hhbmdlPw0KDQpJZiB5b3UgZ2VuZXJhdGUgdGhlIGFjdHVhbCBwYXRj aCBJIGNhbiBhZGQgYW4gYXBwcm9wcmlhdGUgc2lnbi1vZmYNCihvciB3aGF0ZXZlciBpcyBuZWVk ZWQpLg0KDQoJRGF2aWQNCg0K
Quoted 2 lines · David Laight
Quoted 1 line
This part above looks like FLS
It also does the rest of the required shifts.
Still, fls() + shift is way faster on hardware that has an fls instruction.
Writing out that binary search doesn't make sense.
From: Peter Zijlstra
Quoted 1 line
Sent: 21 December 2017 14:12
...
Quoted 7 lines
Quoted 2 lines
Quoted 1 line
This part above looks like FLS
It also does the rest of the required shifts.
Still,
fls()+ shift is way faster on hardware that has an fls instruction.Writing out that binary search doesn't make sense.
If the hardware doesn't have an appropriate fls instruction the soft fls()will be worse.
If you used fls() you'd still need quite a bit of code to generate the correct shift and loop count adjustment. Given the cost of the loop iterations the 3 tests are noise. The open coded version is obviously correct...
I didn't add the 4th one because the code always does 2 iterations.
If you were really worried about performance there are faster algorithms (even doing 2 or 4 bits a time is faster).
David
Quoted 1 line
From simple strong typing of existing
int_sqrtwe came to something a
bit more complex or better. Can we decide now which we want in, or I submit v12 and we decide then (although it is not a v12, but whole new thing)?
Quoted 26 lines · David Laight
From: Peter Zijlstra
Quoted 1 line
Sent: 21 December 2017 14:12
...
Quoted 7 lines
Quoted 2 lines
Quoted 1 line
This part above looks like FLS
It also does the rest of the required shifts.
Still,
fls()+ shift is way faster on hardware that has an fls instruction.Writing out that binary search doesn't make sense.
If the hardware doesn't have an appropriate fls instruction the soft fls()will be worse.
If you used
fls()you'd still need quite a bit of code to generate the correct shift and loop count adjustment. Given the cost of the loop iterations the 3 tests are noise. The open coded version is obviously correct...I didn't add the 4th one because the code always does 2 iterations.
If you were really worried about performance there are faster algorithms (even doing 2 or 4 bits a time is faster).
David
It has been some time now since this moved. I have decided not to use David's implementation because I want to maintain also range above 2^62
Are there any additional objections for this not to go in as it is?
Quoted 33 lines · Crt Mori
From simple strong typing of existing
int_sqrtwe came to something a bit more complex or better. Can we decide now which we want in, or I submit v12 and we decide then (although it is not a v12, but whole new thing)?Quoted 26 lines · David Laight
From: Peter Zijlstra
Quoted 1 line
Sent: 21 December 2017 14:12
...
Quoted 7 lines
Quoted 2 lines
Quoted 1 line
This part above looks like FLS
It also does the rest of the required shifts.
Still,
fls()+ shift is way faster on hardware that has an fls instruction.Writing out that binary search doesn't make sense.
If the hardware doesn't have an appropriate fls instruction the soft fls()will be worse.
If you used
fls()you'd still need quite a bit of code to generate the correct shift and loop count adjustment. Given the cost of the loop iterations the 3 tests are noise. The open coded version is obviously correct...I didn't add the 4th one because the code always does 2 iterations.
If you were really worried about performance there are faster algorithms (even doing 2 or 4 bits a time is faster).
David
From: Crt Mori [mailto:[email protected]]
Quoted 5 lines
Sent: 09 January 2018 15:18
It has been some time now since this moved. I have decided not to use David's implementation because I want to maintain also range above 2^62
The last version I did supported the full range.
David
Quoted 8 lines · David Laight
From: Crt Mori [mailto:[email protected]]
Quoted 5 lines
Sent: 09 January 2018 15:18
It has been some time now since this moved. I have decided not to use David's implementation because I want to maintain also range above 2^62
The last version I did supported the full range.
Nothing changed below that comment, so I was assuming it is not supported (or did I miss a mail?).
Also fls discussion had opposite opinions or it just seems inconclusive to me?
Quoted 3 lines
David
So you all agree David Laight version is much better and should be used instead of currently proposed version?