• bearophile (66/66) Jun 24 2012 Just a recent little coding story.
• Jerome BENOIT (3/4) Jun 24 2012 Is there any GMP port for D ?
• bearophile (5/7) Jun 24 2012 I don't know.
• Jerome BENOIT (2/10) Jun 24 2012
• bearophile (11/12) Jun 24 2012 Multiprecision numbers allocate on the heap when they become
• Jerome BENOIT (3/8) Jun 24 2012 Thanks a lot for the explanation.
• Tobias Pankrath (8/10) Jun 24 2012 Maybe you should post this to the main newsgroup.
• bearophile (6/8) Jun 25 2012 I think both a compiler switch for the compilation unit, and a
• Dmitry Olshansky (7/13) Jun 25 2012 While I think that if you seek anything other then plain fixnum you'd
• Tobias Pankrath (10/27) Jun 25 2012 If you have already written code, it may be cumbersome to port it
• Dmitry Olshansky (4/30) Jun 25 2012 --
• bearophile (10/11) Jun 25 2012 I am not seeing one of the posts of this thread. So I'll answer
• Don Clugston (9/18) Jun 26 2012 Bearophile, haven't you ever read that paper on integer overflow, which
• bearophile (20/32) Jun 26 2012 I have read it time ago, but it seems not having run-time
• Gour (12/16) Jun 25 2012 Have you tried to use Cython which gives some 'static type safety' and
• David (3/14) Jun 25 2012 I would like to see the result with PyPy, Cython is mostly not faster

"bearophile" <bearophileHUGS lycos.com> writes:

Just a recent little coding story.

Python is a good language for "exploratory programming", because 
the programs are succinct, it's flexible, its data structures are 
easy to use and good, there are already written modules to do 
most things, there are very easy to use libraries to plot results 
or import data and so on.

Doing this kind of programing I have written a small 
single-module command line Python program, just few hundred lines 
long. Once debugged it seemed to work, but only up to N=18, 
beyond that it uses too much memory and CPU time for me.

To solve the performance problem I've ported it to D. This 
translation didn't took a lot of time, and the resulting 
single-module D program was just 10-15% longer than the Python 
module. But it didn't work, the results were different from the 
Python veersion. I have spent several hours to find the bug, that 
was a nasty D associative array bug already present in Bugzilla.

This was not nice, but once fixed that, it gave the same results 
as the Python version from N=1 to N=18. Now the program is tens 
of times faster and I'm able to solve for N=19 and even N=20, 
good. Being this exploratory programming I don't know the correct 
results for those N=19 and N=20. I am only able to estimate the 
correct results and the estimate is compatible with the results 
given by the D program. This is good, but spending some hours to 
look for a bug has made me suspicious of the D program, maybe it 
was buggy still.

So I translate the Python program to FreePascal (a modern free 
Object Pascal, similar to Delphi). This translation wasn't hard 
to do, I have used one library of mine that implements 
associative arrays in FreePascal, but it was a little slow and 
boring, and the resulting program was long.

When I run the FreePascal program it gives the same results from 
N=1 to N=18 as the Python version, this is good. But with N=19 it 
gave a run-time integer overflow error. Up to N=18 a certain 32 
bit int variable was enough, but right with N=19 the program 
tried to store inside it a value past 2 billions. A compilation 
switch of FreePascal allows to turn run-time overflows of all 
integral values used by the program into run-time errors.

I have replaced that 32 bit int with a 64 bit int in the 
FreePascal code. Running again the FreePascal program again I 
have found another integral overflow error. If I replace that 
variable too with a 64 bit int, the program runs and it gives a 
number slightly different from the number given by the D code. If 
I compile and run the original FreePascal code without the 
run-time overflow tests it gives the same results as the D 
version for N=19 and N=20.

I can study the D code, looking for variables that cause 
overflow, but this study requires time, because the program is 
small, but its algorithms are intricate.

So for this program born from explorative programming that does 
some integral number crunching:
- Python language is not fit because it's too much slow and 
because in certain cases I prefer a little stronger static type 
safety, that's useful to not waste time debugging the usage of 
intricate data structures.
- FreePascal is not fit because it's not flexible enough and 
because it's too much low-level for a exploration that must be 
quick.
- And D is too much unsafe for such kind of programs, because 
integral numbers can silently overflow.


purposes (it's probably fast enough despite not running on the 
dotnet and it has structs to save memory, it detects run-time 
integral overflows, it has data structures and maybe it's 
flexible enough).

Bye,
bearophile

Jerome BENOIT <g6299304p rezozer.net> writes:

On 24/06/12 23:52, bearophile wrote:
 And D is too much unsafe for such kind of programs, because integral numbers
can silently overflow.

Is there any GMP port for D ?

Jerome

"bearophile" <bearophileHUGS lycos.com> writes:

Jerome BENOIT:

 Is there any GMP port for D ?

 Jerome

I don't know.

(But GMP is NOT a solution to the problems shown in that story).

Bye,
bearophile

Jerome BENOIT <g6299304p rezozer.net> writes:

On 25/06/12 01:51, bearophile wrote:
 Jerome BENOIT:

 Is there any GMP port for D ?

 Jerome

 I don't know.

 (But GMP is NOT a solution to the problems shown in that story).

How come as ``integral numbers (will not be) overflow'' ?

 Bye,
 bearophile

"bearophile" <bearophileHUGS lycos.com> writes:

Jerome BENOIT:

 How come as ``integral numbers (will not be) overflow'' ?

Multiprecision numbers allocate on the heap when they become 
large (or they always allocate on the heap). This has a 
significant performance impact. There are many situations where 
Multiprecision numbers are handy, but there are many other cases 
where you want to keep most of the performance (or memory use, or 
struct layouts, and type signatures, and more) of the normal 
machine fixnums. In this case compilation switches to 
enable/disable run-time overflow errors are useful.

Bye,
bearophile

Jerome BENOIT <g6299304p rezozer.net> writes:

Thanks a lot for the explanation.
Jerome

On 25/06/12 02:54, bearophile wrote:
 Jerome BENOIT:

 How come as ``integral numbers (will not be) overflow'' ?

 Multiprecision numbers allocate on the heap when they become large (or they
always allocate on the heap). This has a significant performance impact. There
are many situations where Multiprecision numbers are handy, but there are many
other cases where you want to keep most of the performance (or memory use, or
struct layouts, and type signatures, and more) of the normal machine fixnums.
In this case compilation switches to enable/disable run-time overflow errors
are useful.

 Bye,
 bearophile

"Tobias Pankrath" <tobias pankrath.net> writes:

On Sunday, 24 June 2012 at 21:52:36 UTC, bearophile wrote:
 Just a recent little coding story.

 

Maybe you should post this to the main newsgroup.

I would prefer a switch that does this per scope, i.e:

void foo()
{
     pragma(check, int_overflow);
     // check only in this function
}

"bearophile" <bearophileHUGS lycos.com> writes:

Tobias Pankrath:

 Maybe you should post this to the main newsgroup.

I don't know if the main newsgroup is the right place.


 I would prefer a switch that does this per scope, i.e:

I think both a compiler switch for the compilation unit, and a 
scope pragma to enable/disable locally, are useful.

Bye,
bearophile

Dmitry Olshansky <dmitry.olsh gmail.com> writes:

On 25-Jun-12 14:01, bearophile wrote:
 Tobias Pankrath:

 Maybe you should post this to the main newsgroup.

 I don't know if the main newsgroup is the right place.


 I would prefer a switch that does this per scope, i.e:

 I think both a compiler switch for the compilation unit, and a scope
 pragma to enable/disable locally, are useful.

While I think that if you seek anything other then plain fixnum you'd 
better make wrapper type adding nessary overflow checks. It should be 
almost as fast as plain fixnum if it's not then it's a bug/feature 
request for optimizer/inliner.


-- 
Dmitry Olshansky

"Tobias Pankrath" <tobias pankrath.net> writes:

On Monday, 25 June 2012 at 10:08:03 UTC, Dmitry Olshansky wrote:
 On 25-Jun-12 14:01, bearophile wrote:
 Tobias Pankrath:

 Maybe you should post this to the main newsgroup.

 I don't know if the main newsgroup is the right place.


 I would prefer a switch that does this per scope, i.e:

 I think both a compiler switch for the compilation unit, and a 
 scope
 pragma to enable/disable locally, are useful.

 While I think that if you seek anything other then plain fixnum 
 you'd better make wrapper type adding nessary overflow checks. 
 It should be almost as fast as plain fixnum if it's not then 
 it's a bug/feature request for optimizer/inliner.

If you have already written code, it may be cumbersome to port it 
to a wrapper type, if the only thing you want to test is, that it 
does not have overflows.

You can't just do alias MyWrapper!int int; can you?

They are a common source of bugs, detecting those should be made 
easy. I do see this as automatic DbC for build-ins and can not 
see any counter argument that would not equally apply to the 
current DbC state.

Except for the fact, that someone has to implement it.

Dmitry Olshansky <dmitry.olsh gmail.com> writes:

On 25-Jun-12 15:21, Tobias Pankrath wrote:
 On Monday, 25 June 2012 at 10:08:03 UTC, Dmitry Olshansky wrote:
 On 25-Jun-12 14:01, bearophile wrote:
 Tobias Pankrath:

 Maybe you should post this to the main newsgroup.

 I don't know if the main newsgroup is the right place.


 I would prefer a switch that does this per scope, i.e:

 I think both a compiler switch for the compilation unit, and a scope
 pragma to enable/disable locally, are useful.

 While I think that if you seek anything other then plain fixnum you'd
 better make wrapper type adding nessary overflow checks. It should be
 almost as fast as plain fixnum if it's not then it's a bug/feature
 request for optimizer/inliner.

 If you have already written code, it may be cumbersome to port it to a
 wrapper type, if the only thing you want to test is, that it does not
 have overflows.

 You can't just do alias MyWrapper!int int; can you?

I surely can do s/int/Integer/.
 They are a common source of bugs, detecting those should be made easy. I
 do see this as automatic DbC for build-ins and can not see any counter
 argument that would not equally apply to the current DbC state.

 Except for the fact, that someone has to implement it.


-- 
Dmitry Olshansky

"bearophile" <bearophileHUGS lycos.com> writes:

Dmitry Olshansky:

 Except for the fact, that someone has to implement it.


I am not seeing one of the posts of this thread. So I'll answer 
here.

The good thing regarding the run-time overflow integral tests is 
that they are already implemented and available as efficient 
compiler intrinsics in both GCC and LLVM back-ends. It's just a 
matter of using them (and introducing the compiler switch and 
some kind of pragma syntax).

Bye,
bearophile

Don Clugston <dac nospam.com> writes:

On 25/06/12 14:24, bearophile wrote:
 Dmitry Olshansky:

 Except for the fact, that someone has to implement it.


 I am not seeing one of the posts of this thread. So I'll answer here.

 The good thing regarding the run-time overflow integral tests is that
 they are already implemented and available as efficient compiler
 intrinsics in both GCC and LLVM back-ends. It's just a matter of using
 them (and introducing the compiler switch and some kind of pragma syntax).

 Bye,
 bearophile

Bearophile, haven't you ever read that paper on integer overflow, which 
you keep posting to the newsgroup???

It clearly demonstrates that it is NOT POSSIBLE to implement integer 
overflow checking in a C-family language. Valid, correct, code which 
depends on integer overflow is very, very common (when overflow occurs, 
it's more likely to be correct, than incorrect).

I don't think you could do it without introducing a no-overflow integer 
type. The compiler just doesn't have enough information.

"bearophile" <bearophileHUGS lycos.com> writes:

Don Clugston:

 Bearophile, haven't you ever read that paper on integer 
 overflow, which you keep posting to the newsgroup???

I have read it time ago, but it seems not having run-time 
overflow tests is not an option for certain programming endeavors 
of mine. This is why I have partially switched back to FreePascal 
for those.


 It clearly demonstrates that it is NOT POSSIBLE to implement 
 integer overflow checking in a C-family language.

Clarke says something nice:
When a distinguished but elderly scientist states that something 
is possible, he is almost certainly right. When he states that 
something is impossible, he is very probably wrong.<

http://embed.cs.utah.edu/ioc/


 Valid, correct, code which depends on integer overflow is very, 
 very common (when overflow occurs, it's more likely to be 
 correct, than incorrect).

I was discussing about an annotation to disable it locally where 
the programmer wants such overflows (like using wrap-around 
semantics to avoid testing for negative values. I have done this 
myself some times).

I am not interested in taking a quite optimized 80_000 lines long 
C program and switching on the run-time integral overflow tests 
on it all, all at once. This is probably going to fail, as the 
paper says. Smaller D programs written from zero with run-time 
overflow tests are one example of what I was thinking about.


 I don't think you could do it without introducing a no-overflow 
 integer type. The compiler just doesn't have enough information.

This solution sounds acceptable for part of my purposes, thanks 
to D alias syntax. But I don't know if it's enough.

Bye,
bearophile

Gour <gour atmarama.net> writes:

On Sun, 24 Jun 2012 23:52:35 +0200
"bearophile" <bearophileHUGS lycos.com> wrote:

 - Python language is not fit because it's too much slow and=20
 because in certain cases I prefer a little stronger static type=20
 safety, that's useful to not waste time debugging the usage of=20
 intricate data structures.

Have you tried to use Cython which gives some 'static type safety' and
it is often used to speed up critical parts of the Python program.

I'd really curios to see results with Cython...


Sincerely,
Gour


--=20
Abandoning all attachment to the results of his activities,=20
ever satisfied and independent, he performs no fruitive action,=20
although engaged in all kinds of undertakings.

http://atmarama.net | Hlapicina (Croatia) | GPG: 52B5C810

David <d dav1d.de> writes:

Am 25.06.2012 14:56, schrieb Gour:
 On Sun, 24 Jun 2012 23:52:35 +0200
 "bearophile" <bearophileHUGS lycos.com> wrote:

 - Python language is not fit because it's too much slow and
 because in certain cases I prefer a little stronger static type
 safety, that's useful to not waste time debugging the usage of
 intricate data structures.

 Have you tried to use Cython which gives some 'static type safety' and
 it is often used to speed up critical parts of the Python program.

 I'd really curios to see results with Cython...


 Sincerely,
 Gour

I would like to see the result with PyPy, Cython is mostly not faster 
than CPython.