www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - ow Integers Should Work

reply bearophile <bearophileHUGS lycos.com> writes:
Found through Reddit, two blog posts about how integers should behave in system
languages (with hardware support):

http://blog.regehr.org/archives/641
http://blog.regehr.org/archives/642

Bye,
bearophile
Dec 05 2011
next sibling parent reply Don <nospam nospam.com> writes:
On 05.12.2011 14:31, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave in
system languages (with hardware support):

 http://blog.regehr.org/archives/641
 http://blog.regehr.org/archives/642

 Bye,
 bearophile


Not very convincing, since he proposes a change to existing 
architectures, and seems completely unaware of the overflow flag.
If you can change existing architectures, why not simply allow an 
exception to be generated if an overflow occurs?

Doesn't seem at all helpful to D.
Dec 05 2011
next sibling parent reply Manu <turkeyman gmail.com> writes:
I can agree that in some circumstances, a ranged and saturated integer mode
would be REALLY handy (colours, sound samples), but I can't buy in with the
whole trapping overflows and stuff... most architectures will require
explicit checking of the overflow bit after every operation to support
this. Also, contrary to his claim, I find that wrapping is usually what I
DO want in this case..
It's super rare that I write any code that pushes the limits of an int
(unless we're talking 8-16 bit, see my range+saturation comment before),
and when I do write code that pushes the range of an int, I can't think of
a time when I've not wanted to wrap as expected. If I'm dealing with
integers that big, chances are I'm dealing with memory ranges, bit masks,
or some compression/crypto type thing where the algorithms depend on it.
Not only am I aware of the wrapping behaviour, it's usually the intent...

On 5 December 2011 18:37, Don <nospam nospam.com> wrote:


 On 05.12.2011 14:31, bearophile wrote:


 Found through Reddit, two blog posts about how integers should behave in
 system languages (with hardware support):

 http://blog.regehr.org/**archives/641<http://blog.regehr.org/archives/641>
 http://blog.regehr.org/**archives/642<http://blog.regehr.org/archives/642>

 Bye,
 bearophile


 Not very convincing, since he proposes a change to existing architectures,
 and seems completely unaware of the overflow flag.
 If you can change existing architectures, why not simply allow an
 exception to be generated if an overflow occurs?

 Doesn't seem at all helpful to D.
Dec 05 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Manu:


 Also, contrary to his claim, I find that wrapping is usually what I
 DO want in this case..
 It's super rare that I write any code that pushes the limits of an int
 (unless we're talking 8-16 bit, see my range+saturation comment before),
 and when I do write code that pushes the range of an int, I can't think of
 a time when I've not wanted to wrap as expected.


The code you usually write seems rather unusual. I have kind of the opposite
situations.

But first of all, "trapping" ints are needed to avoid bugs in normal code. Some
bugs are shown here:
http://embed.cs.utah.edu/ioc/

Bye,
bearophile
Dec 05 2011
next sibling parent reply Manu <turkeyman gmail.com> writes:
 Manu:


 Also, contrary to his claim, I find that wrapping is usually what I
 DO want in this case..
 It's super rare that I write any code that pushes the limits of an int
 (unless we're talking 8-16 bit, see my range+saturation comment before),
 and when I do write code that pushes the range of an int, I can't think


 of

 a time when I've not wanted to wrap as expected.


 The code you usually write seems rather unusual. I have kind of the
 opposite situations.

 But first of all, "trapping" ints are needed to avoid bugs in normal code.
 Some bugs are shown here:
 http://embed.cs.utah.edu/ioc/



I write C/C++ systems/embedded/games code (not a small industry by any
measure), and I'm looking to D as a successor.. I'm NOT interested in D as

supported, and I'm happy with them for their purpose. I realise I seem to
be one of the odd ones out on this forum currently, hence I like to throw
my 2c in from time to time :) .. but I don't believe I'm alone.. the rest
of the gamedev community will find D soon enough if the language gets it
right...

I did see some examples of the common overflow bugs via links in your OP,
but I just have never run into those problems myself.. A couple of them
depended on an actual bug in your code. for instance this one:

*result = result * 10 + cursor - '0';*

Should have been:

*result * 10 + (cursor - '0')*

This isn't a legitimate runtime error, it's compile time/logic bug.
Perhaps a warning should be generated at compile time if the logic can
be deduced... (probably impossible)

If you're suggesting the reason for trapping overflow's is
specifically to CATCH bugs like this, then maybe make is a compiler
flag when building a debug binary? (ie. assert on integer overflow).
Dec 05 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Manu:


 but I don't believe I'm alone.. the rest
 of the gamedev community will find D soon enough if the language gets it
 right...


I think games are one of the most important short-term purposes of D, despite I
think D was not explicitly designed to write games.



 If you're suggesting the reason for trapping overflow's is
 specifically to CATCH bugs like this, then maybe make is a compiler
 flag when building a debug binary? (ie. assert on integer overflow).


Right.


I think D2/D3 has also a bit of hope to replace some of the purposes of Ada
language. Walter maybe didn't think of it when he designed D, but D shares some
design purposes with Ada. Walter past work in aeronautical engineering leads
naturally to a language that shares some of the purposes of Ada. For such
purposes correctness and reliability are of the highest importance, this also
means full type safety (implicit type conversions = bad) and number safety
(integral overflows = bad). Defining something like a "MISRA-D" (a strict and
safe subset of D similar to MISRA-C) is an option, and maybe it will produce a
less butchered language.

Bye,
bearophile
Dec 05 2011
next sibling parent reply Manu <turkeyman gmail.com> writes:
 Manu:


 but I don't believe I'm alone.. the rest
 of the gamedev community will find D soon enough if the language gets it
 right...


 I think games are one of the most important short-term purposes of D,
 despite I think D was not explicitly designed to write games.


I agree, it certainly didn't seem to be a major consideration early on, but
I don't think any decisions yet made prohibit it from being well suited.
If as you say, there is some focus to generate interest from the game
community, it would be really nice to have a few binary GDC cross compiler
distributions available (for windows, linux users never have problems
building the toolchain themselves). ARM/PPC, maybe MIPS toolchains hosted
somewhere on the website might really help encourage some people get
started, and I'd love to spend some time on the standard libraries for
these platforms.



 If you're suggesting the reason for trapping overflow's is

 specifically to CATCH bugs like this, then maybe make is a compiler
 flag when building a debug binary? (ie. assert on integer overflow).


 Right.


 I think D2/D3 has also a bit of hope to replace some of the purposes of
 Ada language. Walter maybe didn't think of it when he designed D, but D
 shares some design purposes with Ada. Walter past work in aeronautical
 engineering leads naturally to a language that shares some of the purposes
 of Ada. For such purposes correctness and reliability are of the highest
 importance, this also means full type safety (implicit type conversions =
 bad) and number safety (integral overflows = bad). Defining something like
 a "MISRA-D" (a strict and safe subset of D similar to MISRA-C) is an
 option, and maybe it will produce a less butchered language.


I appreciate the attention to floating point detail made in D, and this
isn't incompatible with gamedev, but making standard ints compromise basic
hardware implementation just won't fly.
Compile time flag maybe to enable integer exceptions perhaps, or a special
mode like you say...
Dec 06 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Manu:


 but making standard ints compromise basic hardware implementation just won't
fly.<


Ada language does those things, and it's used to fly planes :-) So maybe it
will fly.

Today some online games are managing real money of the players. You don't want
to use raw integers to manage those important numbers :-)

Bye,
bearophile
Dec 07 2011
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/07/2011 11:46 AM, bearophile wrote:

 Manu:


 but making standard ints compromise basic hardware implementation just won't
fly.<


 Ada language does those things, and it's used to fly planes :-) So maybe it
will fly.


Maybe. Ada in action: http://www.youtube.com/watch?v=kYUrqdUyEpI


 Today some online games are managing real money of the players. You don't want
to use raw integers to manage those important numbers :-)


Therefore, don't do that.
Dec 07 2011
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 12/7/2011 2:46 AM, bearophile wrote:

 Today some online games are managing real money of the players. You don't
 want to use raw integers to manage those important numbers :-)


Banks have been using computer programs to handle money forever, so has every 
piece of accounting software. I.e. it's a well understood and solved issue.

It'd be very foolish for online game developers to try to reinvent this.

And frankly, we'd also be foolish to try and reinvent it without consulting
with 
someone who does financial software professionally.
Dec 07 2011
prev sibling next sibling parent Iain Buclaw <ibuclaw ubuntu.com> writes:
On 6 December 2011 10:27, Manu <turkeyman gmail.com> wrote:

 Manu:


 but I don't believe I'm alone.. the rest
 of the gamedev community will find D soon enough if the language gets it
 right...


 I think games are one of the most important short-term purposes of D,
 despite I think D was not explicitly designed to write games.



 I agree, it certainly didn't seem to be a major consideration early on, but
 I don't think any decisions yet made prohibit it from being well suited.
 If as you say, there is some focus to generate interest from the game
 community, it would be really nice to have a few binary GDC cross compiler
 distributions available (for windows, linux users never have problems
 building the toolchain themselves). ARM/PPC, maybe MIPS toolchains hosted
 somewhere on the website might really help encourage some people get
 started, and I'd love to spend some time on the standard libraries for these
 platforms.


If you ping me on IRC to get this moving, could put some time into
setting up a toolchain for such purposes over the weekend. ie: such as
a sript to set-up cross compiling from the current host to target B.


-- 
Iain Buclaw

*(p < e ? p++ : p) = (c & 0x0f) + '0';
Dec 06 2011
prev sibling next sibling parent Manu <turkeyman gmail.com> writes:
Cheers, I'll do that! I've still had nothing but trouble getting cygwin to
build the mips toolchain we were experimenting with. I don't know enough
about GCC and making it work >_<.
Although ideally a binary distribution would probably want to be
mingw/msys based.

On 6 December 2011 14:23, Iain Buclaw <ibuclaw ubuntu.com> wrote:


 On 6 December 2011 10:27, Manu <turkeyman gmail.com> wrote:

 Manu:


 but I don't believe I'm alone.. the rest
 of the gamedev community will find D soon enough if the language gets






 it

 right...


 I think games are one of the most important short-term purposes of D,
 despite I think D was not explicitly designed to write games.



 I agree, it certainly didn't seem to be a major consideration early on,


 but

 I don't think any decisions yet made prohibit it from being well suited.
 If as you say, there is some focus to generate interest from the game
 community, it would be really nice to have a few binary GDC cross


 compiler

 distributions available (for windows, linux users never have problems
 building the toolchain themselves). ARM/PPC, maybe MIPS toolchains hosted
 somewhere on the website might really help encourage some people get
 started, and I'd love to spend some time on the standard libraries for


 these

 platforms.


 If you ping me on IRC to get this moving, could put some time into
 setting up a toolchain for such purposes over the weekend. ie: such as
 a sript to set-up cross compiling from the current host to target B.


 --
 Iain Buclaw

 *(p < e ? p++ : p) = (c & 0x0f) + '0';
Dec 06 2011
prev sibling parent reply "Kagamin" <spam here.lot> writes:
On 2011-Dec-05 18:30:54+00:00, bearophile wrote:

 Manu:

 but I don't believe I'm alone.. the rest
 of the gamedev community will find D soon enough if the language gets it
 right...


 I think games are one of the most important short-term purposes of D, despite
I think D was not explicitly designed to write games.


I played a game, where experience counter was int32, it wasn't meant to
overflow during normal play, but it allowed console commands, which could be a
lot of fun, so I made xp overflow to negative values, it didn't make any
trouble, just in the case it used checked arithmetic, it would crash, not so
much fun.
Dec 06 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Kagamin:


I played a game, where experience counter was int32, it wasn't meant to
overflow during normal play, but it allowed console commands, which could be a
lot of fun, so I made xp overflow to negative values, it didn't make any
trouble, just in the case it used checked arithmetic, it would crash, not so
much fun.<


If that game is written in C/C++ then those languages don't define what happens
when you add 1 to the max signed integer. This means crashing the game in that
case is OK according to the specs of those languages.

And even if that experience counter is an unsigned integer, that in C/C++ has
to wrap to zero, how many signed or unsigned 32 bit integers there are in a
game? A lot. I presume that for most of them a silent wrap to the minimum
integer doesn't lead to a fun game. As it usually happens in complex systems,
there are far more ways for that system to not work than to work. In most cases
implicit modular arithmetic doesn't lead to smooth error behaviours.

Bye,
bearophile
Dec 07 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/07/2011 11:41 AM, bearophile wrote:

 [...] As it usually happens in complex systems, there are far more ways for
that system to not work than to work. [...]


Maybe we should exclusively study the ways for for the system to work, 
as that seems to be less complex.
Dec 07 2011
prev sibling parent reply Paulo Pinto <pjmlp progtools.org> writes:
Am 05.12.2011 19:04, schrieb Manu:

     Manu:

      > Also, contrary to his claim, I find that wrapping is usually what I
      > DO want in this case..
      > It's super rare that I write any code that pushes the limits of
     an int
      > (unless we're talking 8-16 bit, see my range+saturation comment
     before),
      > and when I do write code that pushes the range of an int, I can't
     think of
      > a time when I've not wanted to wrap as expected.

     The code you usually write seems rather unusual. I have kind of the
     opposite situations.

     But first of all, "trapping" ints are needed to avoid bugs in normal
     code. Some bugs are shown here:
     http://embed.cs.utah.edu/ioc/


 I write C/C++ systems/embedded/games code (not a small industry by any
 measure), and I'm looking to D as a successor.. I'm NOT interested in D

 are well supported, and I'm happy with them for their purpose. I realise
 I seem to be one of the odd ones out on this forum currently, hence I
 like to throw my 2c in from time to time :) .. but I don't believe I'm
 alone.. the rest of the gamedev community will find D soon enough if the
 language gets it right...
Dec 05 2011
parent =?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <xtzgzorex gmail.com> writes:
On 05-12-2011 20:34, Paulo Pinto wrote:

 Am 05.12.2011 19:04, schrieb Manu:

 Manu:


 Also, contrary to his claim, I find that wrapping is usually what I
 DO want in this case..
 It's super rare that I write any code that pushes the limits of


 an int

 (unless we're talking 8-16 bit, see my range+saturation comment


 before),

 and when I do write code that pushes the range of an int, I can't


 think of

 a time when I've not wanted to wrap as expected.


 The code you usually write seems rather unusual. I have kind of the
 opposite situations.

 But first of all, "trapping" ints are needed to avoid bugs in normal
 code. Some bugs are shown here:
 http://embed.cs.utah.edu/ioc/


 I write C/C++ systems/embedded/games code (not a small industry by any
 measure), and I'm looking to D as a successor.. I'm NOT interested in D

 are well supported, and I'm happy with them for their purpose. I realise
 I seem to be one of the odd ones out on this forum currently, hence I
 like to throw my 2c in from time to time :) .. but I don't believe I'm
 alone.. the rest of the gamedev community will find D soon enough if the
 language gets it right...








and more practical with efficient GCs and various advancements in JIT/VM 
technology (for instance, Mono has an LLVM back end and VM-supported 
continuations).

- Alex
Dec 05 2011
prev sibling parent reply Don <nospam nospam.com> writes:
On 05.12.2011 18:36, bearophile wrote:

 Manu:


 Also, contrary to his claim, I find that wrapping is usually what I
 DO want in this case..
 It's super rare that I write any code that pushes the limits of an int
 (unless we're talking 8-16 bit, see my range+saturation comment before),
 and when I do write code that pushes the range of an int, I can't think of
 a time when I've not wanted to wrap as expected.


 The code you usually write seems rather unusual. I have kind of the opposite
situations.

 But first of all, "trapping" ints are needed to avoid bugs in normal code.
Some bugs are shown here:
 http://embed.cs.utah.edu/ioc/


Those mostly aren't relevant for D. C has many cases of undefined 
behaviour because it doesn't require twos-complement arithmetic. D 
doesn't have that problem.
We still need to tidy up the semantics of << and >> to remove undefined 
behaviour. But it's hard to do much more than that.

The "overflow12.pdf" paper on that site shows statistics that overflow 
is very often intentional. It's strong evidence that you *cannot* make 
signed overflow an error. Even if you could do it with zero complexity 
and zero performance impact, it would be wrong.
Dec 05 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Don:


 The "overflow12.pdf" paper on that site shows statistics that overflow 
 is very often intentional.


In C/C++ code, but we are developing D, a new language that hopes to fix some
of the mistakes of languages invented lot of time ago.



 It's strong evidence that you *cannot* make signed overflow an error.


In C/C++ code, maybe, yet they suggest to invent better tools to find overflow
in C/C++ programs too.

In better/modern languages signed overflow is correct only in the precise
points where it is required. The overflow (for signed) or wraparound (for
unsigned) has not to be the default behaviour, because it's crappy and often
leads to bugs.



  Even if you could do it with zero complexity 
 and zero performance impact, it would be wrong.


In C/C++, maybe. But not in D/Ada/Delphi/Haskell/etc.

Bye,
bearophile
Dec 05 2011
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Don:


 The "overflow12.pdf" paper on that site shows statistics that overflow 
 is very often intentional.


This is expected, the C/C++ programmers are using the semantics of their
language. But it's just because they are using a language with a bad integer
semantics.
A better designed language gives you a way to tell the compiler where you want
overflow (or the default behaviour of the ALU you are using), where you want
wraparound, and where you want some overflow errors. I have seen enough
overflow-related bugs in supposed higher-quality C code written by experts.

Bye,
bearophile
Dec 05 2011
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 12/5/2011 1:37 PM, Don wrote:

 The "overflow12.pdf" paper on that site shows statistics that overflow is very
 often intentional. It's strong evidence that you *cannot* make signed overflow
 an error. Even if you could do it with zero complexity and zero performance
 impact, it would be wrong.


Here's an email from Andy Koenig from the C++ mailing list that I think is very 
relevant (there are a lot of very experienced people on that list, lots of 
mistakes we can avoid by listening to them):
-----------------------------------------
Subject: [c++std-ext-11967] Re: Two's-Complement Arithmetic
From: "Andrew Koenig" <ark acm.org>
To: <c++std-ext accu.org>
Date: Mon, 5 Dec 2011 22:08:29 -0500


 With respect to overflow, I wonder how many of these issues would
 not be better addressed with a Scheme-like bignum type that is cheap
 for (31- or) 63-bit integers, and involves memory allocation only on
 overflow.





 +1, would love to have had this years ago.


Sounds a little like Python 3 integers.

And while I'm thinking about Python 3 arithmetic, there's something else in
Python 3
That I'd love to have in C++, namely a guarantee that:

1) Converting a string to a floating-point number, whether through
input
at run time or writing a floating-point literal as part of a
program,
always yields the correctly rounded closest floating-point value to
the infinite-precision value of the literal.

2) Converting a floating-point number to a string without a
specified
number of significant digits yields the string with the smallest
number of
significant digits that, when converted back to floating point
according
to (1), yields exactly the same value as the one we are converting.

Techniques for solving these problems were published more than 20 years ago,
so it's hard to argue against them on the basis of novelty.  Moreover, these
rules
would have some nice properties, among them:

Printing a floating-point number without specifying accuracy and
reading
it back again into a variable with the same precision gives you the
same value.

Printing a floating-point literal with default precision gives you
the same value as the literal unless the literal has too many
significant digits to represent accurately.

References here:

http://www.cs.washington.edu/education/courses/cse590p/590k_02au/print-fp.pdf
http://www.cs.washington.edu/education/courses/cse590p/590k_02au/read-fp.pdf
Dec 05 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Walter:


 there's something else in Python 3
 That I'd love to have in C++, namely a guarantee that:


This is not about integers but yeah, I'd like the better str <-> float
conversions of Python in D too.

Bye,
bearophile
Dec 05 2011
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<->  float
conversions of Python in D too.


Do you have any test data that they actually are better in Python (apart from 
just being better specified)?
Dec 05 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/5/11 10:15 PM, Walter Bright wrote:

 On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<-> float
 conversions of Python in D too.


 Do you have any test data that they actually are better in Python (apart
 from just being better specified)?


I can tell Google's double-conversion routines (http://goo.gl/RU5g4) are 
faster than sprintf/sscanf, in addition to being better specified. We 
use them at Facebook.

Andrei
Dec 05 2011
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 12/5/2011 8:48 PM, Andrei Alexandrescu wrote:

 On 12/5/11 10:15 PM, Walter Bright wrote:

 On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<-> float
 conversions of Python in D too.


 Do you have any test data that they actually are better in Python (apart
 from just being better specified)?


 I can tell Google's double-conversion routines (http://goo.gl/RU5g4) are faster
 than sprintf/sscanf, in addition to being better specified. We use them at
 Facebook.


Darn, licensing problems:

"Redistributions in binary form must reproduce the above copyright notice, this 
list of conditions and the following disclaimer in the documentation and/or 
other materials provided with the distribution."

http://www.opensource.org/licenses/bsd-license.php
Dec 05 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/6/11 1:16 AM, Walter Bright wrote:

 On 12/5/2011 8:48 PM, Andrei Alexandrescu wrote:

 On 12/5/11 10:15 PM, Walter Bright wrote:

 On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<-> float
 conversions of Python in D too.


 Do you have any test data that they actually are better in Python (apart
 from just being better specified)?


 I can tell Google's double-conversion routines (http://goo.gl/RU5g4)
 are faster
 than sprintf/sscanf, in addition to being better specified. We use
 them at
 Facebook.


 Darn, licensing problems:

 "Redistributions in binary form must reproduce the above copyright
 notice, this list of conditions and the following disclaimer in the
 documentation and/or other materials provided with the distribution."

 http://www.opensource.org/licenses/bsd-license.php


This is a general issue. Can it be overcome by distributing the text in 
the HTML documentation included with the download?

Andrei
Dec 06 2011
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 12/6/2011 9:11 AM, Andrei Alexandrescu wrote:

 On 12/6/11 1:16 AM, Walter Bright wrote:

 On 12/5/2011 8:48 PM, Andrei Alexandrescu wrote:

 On 12/5/11 10:15 PM, Walter Bright wrote:


 Darn, licensing problems:

 "Redistributions in binary form must reproduce the above copyright
 notice, this list of conditions and the following disclaimer in the
 documentation and/or other materials provided with the distribution."

 http://www.opensource.org/licenses/bsd-license.php


 This is a general issue. Can it be overcome by distributing the text in the
HTML
 documentation included with the download?


Every customer who builds a program with D will have to have that notice 
somewhere in it. It's the old Tango problem.
Dec 06 2011
prev sibling parent Derek <ddparnell bigpond.com> writes:
On Wed, 07 Dec 2011 04:11:40 +1100, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 12/6/11 1:16 AM, Walter Bright wrote:

 On 12/5/2011 8:48 PM, Andrei Alexandrescu wrote:

 On 12/5/11 10:15 PM, Walter Bright wrote:

 On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<-> float
 conversions of Python in D too.


 Do you have any test data that they actually are better in Python  
 (apart
 from just being better specified)?


 I can tell Google's double-conversion routines (http://goo.gl/RU5g4)
 are faster
 than sprintf/sscanf, in addition to being better specified. We use
 them at
 Facebook.


 Darn, licensing problems:

 "Redistributions in binary form must reproduce the above copyright
 notice, this list of conditions and the following disclaimer in the
 documentation and/or other materials provided with the distribution."

 http://www.opensource.org/licenses/bsd-license.php


 This is a general issue. Can it be overcome by distributing the text in  
 the HTML documentation included with the download?


It's the "binary form" phrase that's a problem. Does it mean "executable  
form" rather than "text form", or "digital" rather than "hardcopy" form?

-- 
Derek Parnell
Melbourne, Australia
Dec 06 2011
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 12/5/2011 8:48 PM, Andrei Alexandrescu wrote:

 On 12/5/11 10:15 PM, Walter Bright wrote:

 On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<-> float
 conversions of Python in D too.


 Do you have any test data that they actually are better in Python (apart
 from just being better specified)?


 I can tell Google's double-conversion routines (http://goo.gl/RU5g4) are faster
 than sprintf/sscanf, in addition to being better specified. We use them at
 Facebook.


This one is apparently in wide use:

http://www.netlib.org/fp/dtoa.c
Dec 05 2011
prev sibling parent reply Don <nospam nospam.com> writes:
On 06.12.2011 05:15, Walter Bright wrote:

 On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<-> float
 conversions of Python in D too.


 Do you have any test data that they actually are better in Python (apart
 from just being better specified)?


Bug 5229 is an example.

I have five papers on this topic. Most recent is the excellent:
Florian Loitsch, "Printing FP numbers quickly and accurately with 
integers" (2010)
Dec 05 2011
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 12/5/2011 10:52 PM, Don wrote:

 On 06.12.2011 05:15, Walter Bright wrote:

 On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<-> float
 conversions of Python in D too.


 Do you have any test data that they actually are better in Python (apart
 from just being better specified)?


 Bug 5229 is an example.

 I have five papers on this topic. Most recent is the excellent:
 Florian Loitsch, "Printing FP numbers quickly and accurately with integers"
(2010)


Right now, we rely on C's standard library. Often, it's deficient. We should 
roll our own, like we did with the math routines, and make sure the D standard 
reflects the modern thinking on it.

(Python's implementation currently uses David Gay's dtoa.c)
Dec 05 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/6/11 1:20 AM, Walter Bright wrote:

 On 12/5/2011 10:52 PM, Don wrote:

 On 06.12.2011 05:15, Walter Bright wrote:

 On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<-> float
 conversions of Python in D too.


 Do you have any test data that they actually are better in Python (apart
 from just being better specified)?


 Bug 5229 is an example.

 I have five papers on this topic. Most recent is the excellent:
 Florian Loitsch, "Printing FP numbers quickly and accurately with
 integers" (2010)


 Right now, we rely on C's standard library. Often, it's deficient. We
 should roll our own, like we did with the math routines, and make sure
 the D standard reflects the modern thinking on it.

 (Python's implementation currently uses David Gay's dtoa.c)


Translating dtoa.c to D and making sure it works during compilation 
sounds like a great project. People who want to help D in any way, 
please take notice :o).

Andrei
Dec 06 2011
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 12/6/2011 9:14 AM, Andrei Alexandrescu wrote:

 Translating dtoa.c to D and making sure it works during compilation sounds like
 a great project. People who want to help D in any way, please take notice :o).


Sadly, despite dtoa.c's wide use, there doesn't appear to be a test suite for 
it. I suppose we could email David Gay and ask.
Dec 06 2011
parent bcs <bcs example.com> writes:
On 12/06/2011 09:49 AM, Walter Bright wrote:

 On 12/6/2011 9:14 AM, Andrei Alexandrescu wrote:

 Translating dtoa.c to D and making sure it works during compilation
 sounds like
 a great project. People who want to help D in any way, please take
 notice :o).


 Sadly, despite dtoa.c's wide use, there doesn't appear to be a test
 suite for it. I suppose we could email David Gay and ask.


Fuzz test it?

Feed it and the clone random data (after a archive of selected values) 
until they give different results or you get sick of waiting.
Dec 06 2011
prev sibling parent David Nadlinger <see klickverbot.at> writes:
On 12/6/11 6:14 PM, Andrei Alexandrescu wrote:

 On 12/6/11 1:20 AM, Walter Bright wrote:

 (Python's implementation currently uses David Gay's dtoa.c)


 Translating dtoa.c to D and making sure it works during compilation
 sounds like a great project. People who want to help D in any way,
 please take notice :o).


Isn't there the same licensing problem with David Gay's code as well? 
»provided that this entire notice is included […] in all copies of the 
supporting documentation for such software.«

David
Dec 06 2011
prev sibling parent reply Don <nospam nospam.com> writes:
On 06.12.2011 08:20, Walter Bright wrote:

 On 12/5/2011 10:52 PM, Don wrote:

 On 06.12.2011 05:15, Walter Bright wrote:

 On 12/5/2011 8:10 PM, bearophile wrote:

 This is not about integers but yeah, I'd like the better str<-> float
 conversions of Python in D too.


 Do you have any test data that they actually are better in Python (apart
 from just being better specified)?


 Bug 5229 is an example.

 I have five papers on this topic. Most recent is the excellent:
 Florian Loitsch, "Printing FP numbers quickly and accurately with
 integers" (2010)


 Right now, we rely on C's standard library. Often, it's deficient. We
 should roll our own, like we did with the math routines, and make sure
 the D standard reflects the modern thinking on it.

 (Python's implementation currently uses David Gay's dtoa.c)


The Loitsch paper is very interesting, it presents a simple very fast 
method which works in 99.5% of cases. Then, you fall back to the simple 
slow method for the remaining 0.5%. The slow case is rare enough that 
it's not worth optimizing it.

By contrast, dtoa.c is very complicated, because its fast method only 
works for ~75% of cases, so there are many optimisations for special 
cases of the slow method.
Dec 08 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/8/11 4:47 AM, Don wrote:

 The Loitsch paper is very interesting, it presents a simple very fast
 method which works in 99.5% of cases. Then, you fall back to the simple
 slow method for the remaining 0.5%. The slow case is rare enough that
 it's not worth optimizing it.


I think a D implementation starting from Loitsch's paper would be 
absolutely terrific for Phobos.

I've had these ideas of compile-time function tabulators for a long 
time, which would made for a great article, but I'm blocked by the 
inability to format floating-point numbers as strings during compilation.


Andrei
Dec 08 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/5/11 9:57 PM, Walter Bright wrote:

 http://www.cs.washington.edu/education/courses/cse590p/590k_02au/print-fp.pdf

 http://www.cs.washington.edu/education/courses/cse590p/590k_02au/read-fp.pdf


In fact there's more recent work on that, see http://goo.gl/H6VZD. It's 
been on reddit, too: http://goo.gl/teyDy. That work is implemented in 
Google's double-conversion library: http://goo.gl/RU5g4.

I wanted for a long time to have double->string and string->double 
routines in native D that are CTFE-able. Those would make it possible to 
generate function tables and other awesome applications. If someone 
could find the time to e.g. take dmc's floating point formatting/parsing 
routines and translate them to D, that would be great.


Andrei
Dec 05 2011
prev sibling parent bcs <bcs example.com> writes:
On 12/05/2011 01:37 PM, Don wrote:

 On 05.12.2011 18:36, bearophile wrote:

 Manu:


 Also, contrary to his claim, I find that wrapping is usually what I
 DO want in this case..
 It's super rare that I write any code that pushes the limits of an int
 (unless we're talking 8-16 bit, see my range+saturation comment before),
 and when I do write code that pushes the range of an int, I can't
 think of
 a time when I've not wanted to wrap as expected.


 The code you usually write seems rather unusual. I have kind of the
 opposite situations.

 But first of all, "trapping" ints are needed to avoid bugs in normal
 code. Some bugs are shown here:
 http://embed.cs.utah.edu/ioc/


 Those mostly aren't relevant for D. C has many cases of undefined
 behaviour because it doesn't require twos-complement arithmetic. D
 doesn't have that problem.
 We still need to tidy up the semantics of << and >> to remove undefined
 behaviour. But it's hard to do much more than that.

 The "overflow12.pdf" paper on that site shows statistics that overflow
 is very often intentional. It's strong evidence that you *cannot* make
 signed overflow an error. Even if you could do it with zero complexity
 and zero performance impact, it would be wrong.


What is needed is a type that has *defined* overflow characteristics 
(IIRC unsigned does but there might be value in having a signed one as 
well) and, maybe, another one that traps. Undefined overflow is a bugs 
waiting to happen:

// In C
for (short i = 1; i > 0; i++);

Under GCC, no optimisation finishes in ms. With -O9, it's an endless loop.
Dec 05 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/5/11 10:37 AM, Don wrote:

 On 05.12.2011 14:31, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave
 in system languages (with hardware support):

 http://blog.regehr.org/archives/641
 http://blog.regehr.org/archives/642

 Bye,
 bearophile


 Not very convincing, since he proposes a change to existing
 architectures, and seems completely unaware of the overflow flag.
 If you can change existing architectures, why not simply allow an
 exception to be generated if an overflow occurs?

 Doesn't seem at all helpful to D.


Agreed. One thought that comes to mind is using the small int 
optimization for BigInt, i.e. use no dynamic allocation and built-in 
operations whenever possible if the value is small enough. Does BigInt 
currently do that?

Andrei
Dec 05 2011
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/05/2011 06:25 PM, Andrei Alexandrescu wrote:

 On 12/5/11 10:37 AM, Don wrote:

 On 05.12.2011 14:31, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave
 in system languages (with hardware support):

 http://blog.regehr.org/archives/641
 http://blog.regehr.org/archives/642

 Bye,
 bearophile


 Not very convincing, since he proposes a change to existing
 architectures, and seems completely unaware of the overflow flag.
 If you can change existing architectures, why not simply allow an
 exception to be generated if an overflow occurs?

 Doesn't seem at all helpful to D.


 Agreed. One thought that comes to mind is using the small int
 optimization for BigInt, i.e. use no dynamic allocation and built-in
 operations whenever possible if the value is small enough. Does BigInt
 currently do that?

 Andrei


It does not.
Dec 05 2011
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:


 Agreed. One thought that comes to mind is using the small int 
 optimization for BigInt, i.e. use no dynamic allocation and built-in 
 operations whenever possible if the value is small enough. Does BigInt 
 currently do that?


Both the small int optimization (32 or 64 bit? To be decided still), and the
memory pool for bigints are not yet implemented. This also means the recent
suggested improvements of the GC are able to improve the  performance of code
that use BigInts (I have already verified it).

Bye,
bearophile
Dec 05 2011
prev sibling parent reply bcs <bcs example.com> writes:
On 12/05/2011 08:37 AM, Don wrote:

 On 05.12.2011 14:31, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave
 in system languages (with hardware support):

 http://blog.regehr.org/archives/641
 http://blog.regehr.org/archives/642

 Bye,
 bearophile


 Not very convincing, since he proposes a change to existing
 architectures, and seems completely unaware of the overflow flag.


I think he's looking at it form the language theory standpoint. As such, 
architectures has nothing to do with it (the architectures to be 
targeted has yet to be defined at that point) and getting access to the 
overflow flag would require exposing it natively in the language.


 If you can change existing architectures, why not simply allow an
 exception to be generated if an overflow occurs?

 Doesn't seem at all helpful to D.
Dec 05 2011
parent reply Don <nospam nospam.com> writes:
On 06.12.2011 05:21, bcs wrote:

 On 12/05/2011 08:37 AM, Don wrote:

 On 05.12.2011 14:31, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave
 in system languages (with hardware support):

 http://blog.regehr.org/archives/641
 http://blog.regehr.org/archives/642

 Bye,
 bearophile


 Not very convincing, since he proposes a change to existing
 architectures, and seems completely unaware of the overflow flag.


 I think he's looking at it form the language theory standpoint. As such,
 architectures has nothing to do with it (the architectures to be
 targeted has yet to be defined at that point)and getting access to the
 overflow flag would require exposing it natively in the language.


It's not that he hasn't specified an architecture. It's a proposal which 
does not work on _any_ existing architectures!
It's pure fantasy.

And he talks about NaN, when he means infinity. Floating point overflow 
never results in a NaN. He doesn't seem to know anything about 
saturating integer arithmetic, which exists in hardware (even x86 
machines have supported a couple of operations since 1996).

Useless.
Dec 05 2011
parent reply bcs <bcs example.com> writes:
On 12/05/2011 11:20 PM, Don wrote:

 On 06.12.2011 05:21, bcs wrote:

 On 12/05/2011 08:37 AM, Don wrote:

 On 05.12.2011 14:31, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave
 in system languages (with hardware support):

 http://blog.regehr.org/archives/641
 http://blog.regehr.org/archives/642

 Bye,
 bearophile


 Not very convincing, since he proposes a change to existing
 architectures, and seems completely unaware of the overflow flag.


 I think he's looking at it form the language theory standpoint. As such,
 architectures has nothing to do with it (the architectures to be
 targeted has yet to be defined at that point)and getting access to the
 overflow flag would require exposing it natively in the language.


 It's not that he hasn't specified an architecture. It's a proposal which
 does not work on _any_ existing architectures!
 It's pure fantasy.


Well you can do it on x86. The fact the it doesn't provied hardware 
traps is irrelevant. You might need to add a lot of branches but you can 
get the semantics he is asking for.

That said, there is another interesting (but independent) question of 
can it be done efficiently? You might have a very good question there, 
but that isn't the question regehr is considering.


 And he talks about NaN, when he means infinity. Floating point overflow
 never results in a NaN.


You have a point there.


 He doesn't seem to know anything about
 saturating integer arithmetic, which exists in hardware (even x86
 machines have supported a couple of operations since 1996).

 Useless.


Again, he's not interested in the hardware implementation, he's only 
interested in the defined semantics of the language, the things you can 
count on regardless of that instruction set you are using. The fact the 
x86 has saturating integer operations is moot because C doesn't have a 
type the end up using them.
Dec 06 2011
parent reply Don <nospam nospam.com> writes:
On 07.12.2011 05:11, bcs wrote:

 On 12/05/2011 11:20 PM, Don wrote:

 On 06.12.2011 05:21, bcs wrote:

 On 12/05/2011 08:37 AM, Don wrote:

 On 05.12.2011 14:31, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave
 in system languages (with hardware support):

 http://blog.regehr.org/archives/641
 http://blog.regehr.org/archives/642

 Bye,
 bearophile


 Not very convincing, since he proposes a change to existing
 architectures, and seems completely unaware of the overflow flag.


 I think he's looking at it form the language theory standpoint. As such,
 architectures has nothing to do with it (the architectures to be
 targeted has yet to be defined at that point)and getting access to the
 overflow flag would require exposing it natively in the language.


 It's not that he hasn't specified an architecture. It's a proposal which
 does not work on _any_ existing architectures!
 It's pure fantasy.


 Well you can do it on x86. The fact the it doesn't provied hardware
 traps is irrelevant. You might need to add a lot of branches but you can
 get the semantics he is asking for.

 That said, there is another interesting (but independent) question of
 can it be done efficiently? You might have a very good question there,
 but that isn't the question regehr is considering.


 And he talks about NaN, when he means infinity. Floating point overflow
 never results in a NaN.


 You have a point there.


 He doesn't seem to know anything about
 saturating integer arithmetic, which exists in hardware (even x86
 machines have supported a couple of operations since 1996).

 Useless.


 Again, he's not interested in the hardware implementation, he's only
 interested in the defined semantics of the language, the things you can
 count on regardless of that instruction set you are using. The fact the
 x86 has saturating integer operations is moot because C doesn't have a
 type the end up using them.


He's talking about system languages. A system language has to have a 
close relationship to the architecture.

By contrast, if you don't care about performance, it's easy -- just use 
BigInts for everything. Problem solved.

Looks like I have to put it more bluntly: I don't think he knows what 
he's talking about. (On this particular topic).
Dec 06 2011
next sibling parent Paulo Pinto <pjmlp progtools.org> writes:
Don Wrote:


 On 07.12.2011 05:11, bcs wrote:

 On 12/05/2011 11:20 PM, Don wrote:

 On 06.12.2011 05:21, bcs wrote:

 On 12/05/2011 08:37 AM, Don wrote:

 On 05.12.2011 14:31, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave
 in system languages (with hardware support):

 http://blog.regehr.org/archives/641
 http://blog.regehr.org/archives/642

 Bye,
 bearophile


 Not very convincing, since he proposes a change to existing
 architectures, and seems completely unaware of the overflow flag.


 I think he's looking at it form the language theory standpoint. As such,
 architectures has nothing to do with it (the architectures to be
 targeted has yet to be defined at that point)and getting access to the
 overflow flag would require exposing it natively in the language.


 It's not that he hasn't specified an architecture. It's a proposal which
 does not work on _any_ existing architectures!
 It's pure fantasy.


 Well you can do it on x86. The fact the it doesn't provied hardware
 traps is irrelevant. You might need to add a lot of branches but you can
 get the semantics he is asking for.

 That said, there is another interesting (but independent) question of
 can it be done efficiently? You might have a very good question there,
 but that isn't the question regehr is considering.


 And he talks about NaN, when he means infinity. Floating point overflow
 never results in a NaN.


 You have a point there.


 He doesn't seem to know anything about
 saturating integer arithmetic, which exists in hardware (even x86
 machines have supported a couple of operations since 1996).

 Useless.


 Again, he's not interested in the hardware implementation, he's only
 interested in the defined semantics of the language, the things you can
 count on regardless of that instruction set you are using. The fact the
 x86 has saturating integer operations is moot because C doesn't have a
 type the end up using them.


 
 He's talking about system languages. A system language has to have a 
 close relationship to the architecture.


Ada is a systems language and if I am not mistaken allows for the type of rules
he is describing.


and also has some of the strict rules he advocates.

I am pretty sure that there are quite a few systems languages that have more
precise rules regarding integer overflow.
Dec 07 2011
prev sibling parent reply bcs <bcs example.com> writes:
On 12/06/2011 11:50 PM, Don wrote:

 He's talking about system languages. A system language has to have a
 close relationship to the architecture.

 By contrast, if you don't care about performance, it's easy -- just use
 BigInts for everything. Problem solved.

 Looks like I have to put it more bluntly: I don't think he knows what
 he's talking about. (On this particular topic).


I know exactly what you have been saying I just think you are wrong, not 
because I don't think you knows what you are talking about but because I 
think you are evaluating his conclusion based on a different criteria 
than he is.

More specifically, I think we are dealing with a differing order of 
priories for system languages. Mine would put safety (i.e. NO undefined 
behaviour) over performance. I think he is going the same way. 
Personally, if I could only have one, I think I'd (first) go with 
defining overflow semantics rather than trapping but I'm not sure which 
is more useful in a systems context.

Can we at least agree that if you are only going to have one signed 
integer semantic, that undefined overflow is the worst possible choice?
Dec 07 2011
parent reply Don <nospam nospam.com> writes:
On 08.12.2011 05:46, bcs wrote:

 On 12/06/2011 11:50 PM, Don wrote:

 He's talking about system languages. A system language has to have a
 close relationship to the architecture.

 By contrast, if you don't care about performance, it's easy -- just use
 BigInts for everything. Problem solved.

 Looks like I have to put it more bluntly: I don't think he knows what
 he's talking about. (On this particular topic).


 I know exactly what you have been saying I just think you are wrong, not
 because I don't think you knows what you are talking about but because I
 think you are evaluating his conclusion based on a different criteria
 than he is.


HE PROPOSES CHANGING INSTRUCTION SETS.


 More specifically, I think we are dealing with a differing order of
 priories for system languages. Mine would put safety (i.e. NO undefined
 behaviour) over performance. I think he is going the same way.
 Personally, if I could only have one, I think I'd (first) go with
 defining overflow semantics rather than trapping but I'm not sure which
 is more useful in a systems context.

 Can we at least agree that if you are only going to have one signed
 integer semantic, that undefined overflow is the worst possible choice?


Yes, but D doesn't have undefined overflow. So it's irrelevant.
Dec 08 2011
parent bcs <bcs example.com> writes:
On 12/08/2011 04:15 AM, Don wrote:

 On 08.12.2011 05:46, bcs wrote:

 On 12/06/2011 11:50 PM, Don wrote:

 He's talking about system languages. A system language has to have a
 close relationship to the architecture.

 By contrast, if you don't care about performance, it's easy -- just use
 BigInts for everything. Problem solved.

 Looks like I have to put it more bluntly: I don't think he knows what
 he's talking about. (On this particular topic).


 I know exactly what you have been saying I just think you are wrong, not
 because I don't think you knows what you are talking about but because I
 think you are evaluating his conclusion based on a different criteria
 than he is.


 HE PROPOSES CHANGING INSTRUCTION SETS.


[citation needed]

I just re-scanned both posts. The closest thing I found to suggesting 
that instruction sets be changed is proposing iNaN be used and that (if 
you scan futher up) is listed as one possibility (late trapping) along 
side another (early trapping) that (if you scan even further up) isn't 
even being suggested for every operation but only for non-intermediate 
values.


 More specifically, I think we are dealing with a differing order of
 priories for system languages. Mine would put safety (i.e. NO undefined
 behaviour) over performance. I think he is going the same way.
 Personally, if I could only have one, I think I'd (first) go with
 defining overflow semantics rather than trapping but I'm not sure which
 is more useful in a systems context.

 Can we at least agree that if you are only going to have one signed
 integer semantic, that undefined overflow is the worst possible choice?


 Yes, but D doesn't have undefined overflow. So it's irrelevant.


I'm not talking about D. Well, not directly anyway. So that irrelevant. 
And I think we have concluded that there isn't a single bit of this back 
and forth that we both care about.
Dec 08 2011
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 12/5/2011 5:31 AM, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave in
 system languages (with hardware support):

 http://blog.regehr.org/archives/641 http://blog.regehr.org/archives/642

 Bye, bearophile


Lotsa good comments on HN:

http://news.ycombinator.com/item?id=3312101
Dec 05 2011
prev sibling parent bcs <bcs example.com> writes:
On 12/05/2011 05:31 AM, bearophile wrote:

 Found through Reddit, two blog posts about how integers should behave in
system languages (with hardware support):

 http://blog.regehr.org/archives/641
 http://blog.regehr.org/archives/642


I've been following that guy for a while now. He's doing some REALLY 
nifty work with regards to automating processing regarding bugs.


 Bye,
 bearophile
Dec 05 2011