www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - C++ bounded::integer library

reply "bearophile" <bearophileHUGS lycos.com> writes:
I am reading all the slides in this page (some are still missing 
and will be added later):
https://github.com/boostcon/cppnow_presentations_2014

Here are the slides of a nice talk, "Removing undefined behavior 
from integer operations: the bounded::integer library":

https://github.com/boostcon/cppnow_presentations_2014/blob/master/files/bounded_integer.pdf?raw=true

Some design decisions are not good (like not throwing at run-time 
on default, the long name, and more). Near the end of the slides 
pack it shows that a bit of language support can help improve 
both the syntax and the usage.

Bye,
bearophile
May 17 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 Here are the slides of a nice talk, "Removing undefined 
 behavior from integer operations: the bounded::integer library":
This may be a good start: https://github.com/nordlow/justd/blob/master/bound.d
May 18 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:

 This may be a good start:

 https://github.com/nordlow/justd/blob/master/bound.d
I presume some ways to improve it are to add to core.bitop some D standard intrinsics to detect overflows and carry, to increase run-time performance to sufficient levels. If they are not fast, people will be less willing to used them. Another way to improve it is to add to D something like the "enum preconditions" I've discussed in past. So this bug can be detected at compile-time: Bound!byte b = 200; A third possible improvement is to add a __traits(value_range, exp) trait that returns the value range of an expression. This could be useful to implement the bound integers well. Other possible more complex problems are shown in that talk about bounded::integer. Bye, bearophile
May 18 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 Another way to improve it is to add to D something like the 
 "enum preconditions" I've discussed in past. So this bug can be 
 detected at compile-time:

 Bound!byte b = 200;
This is already handled For example const b127 = saturated!byte(127); compiles but const b128 = saturated!byte(128); errors as bound.d(421,32): Error: saturated (inout(byte) x) is not callable using argument types (int)
May 19 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:

 Bound!byte b = 200;
This is already handled For example const b127 = saturated!byte(127); compiles but const b128 = saturated!byte(128); errors as bound.d(421,32): Error: saturated (inout(byte) x) is not callable using argument types (int)
Is this giving a compile-time error? saturated!byte b = 127; Bye, bearophile
May 19 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 Is this giving a compile-time error?

 saturated!byte b = 127;
Sorry, I meant something different. I am not sure you can give compile-time errors in most of the significant cases with the current D language. Please correct me if I am wrong. Bye, bearophile
May 19 2014
prev sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Monday, 19 May 2014 at 19:54:07 UTC, bearophile wrote:
 Nordlöw:

 Bound!byte b = 200;
This is already handled For example const b127 = saturated!byte(127); compiles but const b128 = saturated!byte(128); errors as bound.d(421,32): Error: saturated (inout(byte) x) is not callable using argument types (int)
Is this giving a compile-time error? saturated!byte b = 127; Bye, bearophile
Yes saturated!byte bb = 127; fails as bound.d(425,20): Error: saturated!(byte, true) is used as a type because saturated is an instantiator function. Shouldn't it?
May 19 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:

 because saturated is an instantiator function. Shouldn't it?
I still don't understand how you can design a good enough ranged integer without something like "enum preconditions". Functions run at run-time, so currently in D you can't enforce the correctness of literals for not-enum values at compile time. So in general the mutable ranged integer can only give the error at run-time, and this is not acceptable. I am missing something? Bye, bearophile
May 19 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 the error at run-time, and this is not acceptable. I am missing 
 something?
My current solution only supports ranges (min max as template arguments) known at compile-time. It would be nice if we could add a feature to D that specializes return value of bound instantiator based upon if its normal value arguments are constants (enums) and if so infers range checking at compile-time otherwise at run-time. I have already asked for this at the forums, previously. Does this answer your questions? /Per
May 19 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 this at the forums, previously. Does this answer your questions?
To clarify: I personally think we need a completely new language feature in D with which to compile-time-introspect function call arguments to check whether they adhere to certain requirements or matches for example the range of other given types.
May 19 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:

 I personally think we need a completely new language feature in 
 D with which to compile-time-introspect function call arguments 
 to check whether they adhere to certain requirements or matches 
 for example the range of other given types.
I think "enum preconditions" are exactly that :-) But I don't know if they are good enough, if they are a good idea, of if there are better ways to do similar things. But I think something like that is an useful improvement for D, able to remove another limitation of user defined types compared to built-ins. Bye, bearophile
May 19 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 I think "enum preconditions" are exactly that :-) But I don't
Great! :) This can also be used to specialize construction of linear algebra types such as vectors, matrices etc to use stack-allocated value (simd) types when dimensions are fixed and small.
May 19 2014
prev sibling parent reply "Meta" <jared771 gmail.com> writes:
On Monday, 19 May 2014 at 23:02:01 UTC, bearophile wrote:
 I think "enum preconditions" are exactly that :-) But I don't 
 know if they are good enough, if they are a good idea, of if 
 there are better ways to do similar things. But I think 
 something like that is an useful improvement for D, able to 
 remove another limitation of user defined types compared to 
 built-ins.

 Bye,
 bearophile
What's the difference between your proposed "enum precondition" and: void fun(int n) in { static assert(...); } out { static assert(...); } body { //... }
May 20 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
Meta:

 What's the difference between your proposed "enum precondition" 
 and:

 void fun(int n)
 in
 {
     static assert(...);
 }
 out
 {
     static assert(...);
 }
 body
 {
     //...
 }
Those static asserts are useless, because the argument n is not a "static" one. Bye, bearophile
May 20 2014
prev sibling parent reply "Dominikus Dittes Scherkl" writes:
On Sunday, 18 May 2014 at 21:58:54 UTC, bearophile wrote:
 I presume some ways to improve it are to add to core.bitop some 
 D standard intrinsics to detect overflows and carry, to 
 increase run-time performance to sufficient levels. If they are 
 not fast, people will be less willing to used them.
I'm implementing a "safeSigned" type (which uses the bad asymmetric min value of signed types as "NaN"), but one side-product is a somewhat useful function to check for overflow (it doesn't throw, instead the result will be T.max for unsigned arguments or T.min for signed arguments). It doesn't create much overhead and is very easy to do: T saveOp(string op, T)(T x, T y) pure save nogc if(isIntegral!T && (op=="+" || op=="-" || op=="<<" || op=="*")) { mixin("x "~op~"= y"); static if(isSigned!T) { static if(op == "*") { asm naked { jnc opok; } } else { asm naked { jno opok; } } x = T.min; } else // unsigned { asm naked { jnc opok; } x = T.max; } opok: return x; }
May 20 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Tuesday, 20 May 2014 at 09:45:12 UTC, Dominikus Dittes Scherkl 
wrote:
 On Sunday, 18 May 2014 at 21:58:54 UTC, bearophile wrote:
 I presume some ways to improve it are to add to core.bitop 
 some D standard intrinsics to detect overflows and carry, to 
 increase run-time performance to sufficient levels. If they 
 are not fast, people will be less willing to used them.
I'm implementing a "safeSigned" type (which uses the bad asymmetric min value of signed types as "NaN"), but one side-product is a somewhat useful function to check for overflow (it doesn't throw, instead the result will be T.max for unsigned arguments or T.min for signed arguments). It doesn't create much overhead and is very easy to do: T saveOp(string op, T)(T x, T y) pure save nogc if(isIntegral!T && (op=="+" || op=="-" || op=="<<" || op=="*")) { mixin("x "~op~"= y"); static if(isSigned!T) { static if(op == "*") { asm naked { jnc opok; } } else { asm naked { jno opok; } } x = T.min; } else // unsigned { asm naked { jnc opok; } x = T.max; } opok: return x; }
Interesting. You have a typo: save instead of safe You should also guard the use of asm to x86 architectures only with version.
May 20 2014
parent "Dominikus Dittes Scherkl" writes:
On Tuesday, 20 May 2014 at 13:03:59 UTC, Nordlöw wrote:
 You have a typo:  save instead of  safe
Oops. This happens all the time :-/
 You should also guard the use of asm to x86 architectures only 
 with version.
Uh? I thought the D assembler should be generic? So if the target platform provides some similar mnemonic, I could use the same? But ok. It's just the do-it-yourself overflow protection is so awfully slow (especially for multiplication). I have also a protection for exponentiation, and that works without asm. On the other side it requires some helper functions: /// returns the absolute value of x in the fitting unsigned type /// (doesn't fail for T.min) Unsigned!T abs(T)(T x) pure safe nogc if(isIntegral!T) { return (x < 0) ? -x : x; } /// returns the number of the highest set bit +1 in the given value /// or 0 if no bit is set ubyte bitlen(ubyte c) pure safe nogc { return (c>15) ? (c>63) ? (c>127) ? 8 : 7 : (c>31) ? 6 : 5 : (c>3) ? (c>7) ? 4 : 3 : (c>1) ? 2 : c; // of course lookup table would be better but I'm to lazy to create one } /// calculate the maximal power of x that would fit in an ucent /// for smaller types simply shift down the result /// (e.g. divide by 4 to calc the maxpower that would fit in an uint) ubyte maxpow(ulong x) pure safe nogc { assert(x>1); // no useful maxpower exists for 0 and 1 static immutable ubyte[10] mp = [ 127, 80, 63, 55, 49, 45, 43, 40, 38, 37 ]; return (x<139) ? ((x<31) ? ((x<20) ? ((x<16) ? ((x<12) ? mp[x-2] : 47-x) : ((x<18) ? 31 : 30)) : ((x<24) ? ((x<22) ? 29 : 28) : ((x<27) ? 27 : 26))) : ((x<57) ? ((x<41) ? ((x<35) ? 25 : 24) : ((x<48) ? 23 : 22)) : ((x<85) ? ((x<69) ? 21 : 20) : ((x<107) ? 19 : 18)))) : ((x<7132) ? ((x<566) ? ((x<256) ? ((x<185) ? 17 : 16) : ((x<371) ? 15 : 14)) : ((x<1626) ? ((x<921) ? 13 : 12) : ((x<3184) ? 11 : 10))) : ((x<2642246) ? ((x<65536) ? ((x<19113) ? 9 : 8) : ((x<319558) ? 7 : 6)) : ((x<4294967296) ? ((x<50859009) ? 5 : 4) : ((x<6981463658332) ? 3 : 2)))); } /// full exponentiation without overflow /// return T.max(for unsigned) or T.min (for signed) if overflow would occur. T savePow(T)(T base, ubyte exp) pure safe nogc if(isIntegral!T) { static if(isUnsigned!T) { if(!exp) return 1; // x^^0 is always 1 if(exp == 1 || base < 2) return base; // x^^1 = x, so do nothing static if(T.sizeof > ulong.sizeof) { if(base > ulong.max) return T.max; } if(exp > (maxpow(base)>>(5-bitlen(T.sizeof)))) return T.max; return base ^^ exp; } else { auto r = savePow(abs!T(base), exp); if(r > T.max) return T.min; return ((base < 0) && (exp&1)) ? -cast(T)r : cast(T)r; } }
May 20 2014
prev sibling parent reply "david stone" <david doublewise.net> writes:
On Saturday, 17 May 2014 at 17:31:18 UTC, bearophile wrote:
 I am reading all the slides in this page (some are still 
 missing and will be added later):
 https://github.com/boostcon/cppnow_presentations_2014

 Here are the slides of a nice talk, "Removing undefined 
 behavior from integer operations: the bounded::integer library":

 https://github.com/boostcon/cppnow_presentations_2014/blob/master/files/bounded_integer.pdf?raw=true

 Some design decisions are not good (like not throwing at 
 run-time on default, the long name, and more). Near the end of 
 the slides pack it shows that a bit of language support can 
 help improve both the syntax and the usage.

 Bye,
 bearophile
Hello bearophile. I am the presenter / author of said library, so I feel I should comment on this. First, the default overflow policy. This is an issue I have struggled with a bit. The current default is to mirror built-in integers in terms of performance. If a user types bounded::integer<0, 10>, they get a type with no run-time checks. I did consider making bounded::throw_policy the default (right now, the typedef for that is bounded::checked_integer<0, 10>). My reasoning for this that I suspect this is the behavior that most people want. I could be convinced otherwise primarily by way of proving that compilers can optimize away the run-time bounds check for common cases: situations like the integer increment for a loop index variable. I've also considered a debug assert statement for the default. Second, the name. If you have suggestions for something better, I am listening. I definitely understand the importance of common types being short. The previous version of this library had the namespace as bounded_integer and the class type as bounded_integer, so instead of bounded::integer<0, 10>, you had to refer to it as bounded_integer::bounded_integer<0, 10>, which was even worse. My ideal would probably be something like int<0, 10>, but I'm not getting that for fairly obvious reasons. I do find myself not typing out the name of the type very often, though, preferring to let auto deduce the types for me. You say you have more criticisms of the library design, so I hope they are nothing too fundamentally flawed. I would like to hear them so that I can fix them (or perhaps I addressed the issue in my talk? The video is not yet posted). Thank you for the link :)
Jul 15 2014
parent "david stone" <david doublewise.net> writes:
The video of this talk has been uploaded to 
https://www.youtube.com/watch?v=hgeErnYxAUw
Aug 15 2014