Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Tristan Seligmann]

On Sun, Jun 2, 2013 at 11:02 PM, Tommy Thorn  wrote:

> On Jun 2, 2013, at 12:52 , Henry Laxen  wrote:
>
> > Yes, that was it.  The dell was a 32 bit system, and the desktop a 64.  I
> > changed everything from Int to Integer, and now both agree.  Thanks for
> the
> > pointer.
>
> Isn't that just terrible? I hate the fact that Haskell was defined to
> neither trap the overflow
> or just treat everything as Integer [like Scheme]. A sacrifice of program
> safety in the name
> of efficiency.
>

If you want to use Integer for everything, just do that.
-- 
mithrandi, i Ainil en-Balandor, a faer Ambar
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Kata]

On Sunday, June 2, 2013 at 5:02 PM, Tommy Thorn wrote:
> On Jun 2, 2013, at 12:52 , Henry Laxen  (mailto:nadine.and.he...@pobox.com)> wrote:
> 
> > Yes, that was it. The dell was a 32 bit system, and the desktop a 64. I 
> > changed everything from Int to Integer, and now both agree. Thanks for the 
> > pointer.
> > 
> 
> 
> Isn't that just terrible? I hate the fact that Haskell was defined to neither 
> trap the overflow
> or just treat everything as Integer [like Scheme]. A sacrifice of program 
> safety in the name
> of efficiency.
> 
> I disagree with this choice and posit that a clever implementation can 
> minimize the cost
> of the overflow checking in most relevant cases.
> 
> I wish this fatal flaw would be reconsidered for the next major revision.
> 
> Tommy
In addition to Haskell already having an arbitrary-width integer type called 
Integer, consider the case where you have some program that basically boils 
down to 

f :: Int -> Int
f x = {- some super-complicated mathematical expression -}

f can only have bounds checks eliminated if the values of the inputs are known 
in advance. How often are you really going to know that? If you do something 
like

main = do
x <- read <$> getLine
print $ f x

then you have to put all the bounds checks in *anyway*.___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Tommy Thorn]

On Jun 2, 2013, at 14:13 , Kata  wrote:
> In addition to Haskell already having an arbitrary-width integer type called 
> Integer

But I wasn't asking for arbitrary-width. I was asking for explicit failures 
(overflow) rather
than C-like silent corruption.


> , consider the case where you have some program that basically boils down to 
> 
> f :: Int -> Int
> f x = {- some super-complicated mathematical expression -}
> 
> f can only have bounds checks eliminated if the values of the inputs are 
> known in advance. How often are you really going to know that? If you do 
> something like

1. I said "minimize the cost of the overflow checking", I didn't say anything 
about bounds checking elimination.
A conditional branch on the overflow from an add is nearly zero cost as it 
predicts perfectly and can be issued
in parallel with all other instructions. Even better, some architectures 
(eg. SPARC) have overflow checking
variants with zero overhead.

And yes, for many instances it's trivial to see that overflow can't happen.

2. Even if that wasn't the case, I never want to sacrifice safety for a trivial 
perf overhead (for that stuff I use C).

Tommy


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Stephen Tetley]

There was a quite long discussion here:

http://conal.net/blog/posts/notions-of-purity-in-haskell


On 2 June 2013 22:02, Tommy Thorn  wrote:
...
> I wish this fatal flaw would be reconsidered for the next major revision.
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Dan Doel]

There is a package that implements an Int that throws an exception on
overflow:

http://hackage.haskell.org/package/safeint

Since Int's existence is pretty much all about trading for performance, I
wouldn't recommend holding your breath on the above becoming the default.

If you want things to work like Scheme, that's exactly what Integer is (in
GHC, anyhow). And Integer is what you get by default(ing) unless you use
something else that is specifically defined to use Int, or specify it
yourself.



On Sun, Jun 2, 2013 at 5:02 PM, Tommy Thorn  wrote:

> On Jun 2, 2013, at 12:52 , Henry Laxen  wrote:
>
> > Yes, that was it.  The dell was a 32 bit system, and the desktop a 64.  I
> > changed everything from Int to Integer, and now both agree.  Thanks for
> the
> > pointer.
>
> Isn't that just terrible? I hate the fact that Haskell was defined to
> neither trap the overflow
> or just treat everything as Integer [like Scheme]. A sacrifice of program
> safety in the name
> of efficiency.
>
> I disagree with this choice and posit that a clever implementation can
> minimize the cost
> of the overflow checking in most relevant cases.
>
> I wish this fatal flaw would be reconsidered for the next major revision.
>
> Tommy
>
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Carter Schonwald]

Indeed, as Dan says, theres the safeint library and the Integer type.

If the Int type had either of these semantics by default, many many
performance sensitive libraries would suddenly have substantially less
compelling performance.  Every single operation that was branchless before
would have a branch *every* operation. this would be BAD.

I'm actually quite happy with (ab)using Int as just a sequence of bits that
sometimes i treat as a number, and sometimes i treat as a bitvector. In
fact thats actually most of my work these days. GHC generates VERY nice
code for Ints and Words, similar to what i'd expect to be Generated by a
decent C compiler when not explicitly using SIMD operations.  This is a
good thing!

Additionally, theres work in progress to support "branchless" Bool
operations in GHC by having Bool be represented internally With 0,1 valued
Ints, http://hackage.haskell.org/trac/ghc/wiki/PrimBool

point being: its easy to have the safety with SafeInt, or Using Integer,
and fast inner loops can't have branches, and that actually matters in many
applications.

cheers
-Carter


On Sun, Jun 2, 2013 at 6:42 PM, Dan Doel  wrote:

> There is a package that implements an Int that throws an exception on
> overflow:
>
> http://hackage.haskell.org/package/safeint
>
> Since Int's existence is pretty much all about trading for performance, I
> wouldn't recommend holding your breath on the above becoming the default.
>
> If you want things to work like Scheme, that's exactly what Integer is (in
> GHC, anyhow). And Integer is what you get by default(ing) unless you use
> something else that is specifically defined to use Int, or specify it
> yourself.
>
>
>
> On Sun, Jun 2, 2013 at 5:02 PM, Tommy Thorn  wrote:
>
>> On Jun 2, 2013, at 12:52 , Henry Laxen 
>> wrote:
>>
>> > Yes, that was it.  The dell was a 32 bit system, and the desktop a 64.
>>  I
>> > changed everything from Int to Integer, and now both agree.  Thanks for
>> the
>> > pointer.
>>
>> Isn't that just terrible? I hate the fact that Haskell was defined to
>> neither trap the overflow
>> or just treat everything as Integer [like Scheme]. A sacrifice of program
>> safety in the name
>> of efficiency.
>>
>> I disagree with this choice and posit that a clever implementation can
>> minimize the cost
>> of the overflow checking in most relevant cases.
>>
>> I wish this fatal flaw would be reconsidered for the next major revision.
>>
>> Tommy
>>
>>
>> ___
>> Haskell-Cafe mailing list
>> Haskell-Cafe@haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Tommy Thorn]

On Jun 2, 2013, at 23:58 , Carter Schonwald  wrote:

> Indeed, as Dan says, theres the safeint library and the Integer type. 
> 
> If the Int type had either of these semantics by default, many many 
> performance sensitive libraries would suddenly have substantially less 
> compelling performance.  Every single operation that was branchless before 
> would have a branch *every* operation. this would be BAD.  

I'd like to see actual data, measurements of actual wall-time impact on real 
code on modern hardware,
not assumptions.

Tommy


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Carter Schonwald]

Tommy, respectfully,

I have quite a few bits of code where a bad branch predictor in a tight
inner loops makes code 10x slower.

you are welcome to do your own experimentation so that you too can learn by
branches are bad in tight loops.  (even if the branch predictor is doing
its job, there will be a measurable slow down, albeit less than 10x)

Please shift this conversation to the libraries list if you want to
actually make a concrete libraries change proposal. Otherwise I don't
understand your contentions. Int is "native register sized integer" not
"integer that i need to exception handle because I used int instead of
integer because of premature optimization in my web app or project euler
codes"

My opinions are based upon spending all of my time over the past year
working on writing robustly performant numerical codes. Some of them are
actually faster than the standard fortran ones.

My point being: as mentioned above, by others much more articulate than I,
unless you have performance related reasons, always use Integer instead of
Int. There is never a good reason to use Int instead of Integer unless it
will change the performance characteristics of your code. Asking for Int to
pretend to be Integer because you wanted to do premature optimization and
then it didn't behave like Integer is a no go.

I am happy to direct you towards further reading if you'd like to learn
about writing performance sensitive software:

the intel optimization
manualhas
many good ideas (eg Structure of Arrays, which is essentially used by
the haskell Vector lib) that are actually realized by the more performant
haskell libraries.

 Likewise, for an informative idea of the cost models for various
operations on the CPU, the agner fog
 manuals
are actually very educational.

merry hacking
-Carter



On Mon, Jun 3, 2013 at 3:07 AM, Tommy Thorn  wrote:

> On Jun 2, 2013, at 23:58 , Carter Schonwald 
> wrote:
>
> > Indeed, as Dan says, theres the safeint library and the Integer type.
> >
> > If the Int type had either of these semantics by default, many many
> performance sensitive libraries would suddenly have substantially less
> compelling performance.  Every single operation that was branchless before
> would have a branch *every* operation. this would be BAD.
>
> I'd like to see actual data, measurements of actual wall-time impact on
> real code on modern hardware,
> not assumptions.
>
> Tommy
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Tommy Thorn]

On Jun 3, 2013, at 00:23 , Carter Schonwald  wrote:

> Int is "native register sized integer"

Actually it's not. Read the definition. Int is only guaranteed to be 29 bits.

Here's *one* _actual_ data point (from a 2.8 GHz i7, 64-bit code):

time ./fib
fib(43) = 701408733
3.27 real 3.27 user 0.00 sys
time ./fib-safe
fib(43) = 701408733
3.45 real 3.45 user 0.00 sys

(NB: I do not check the n-1 and n-2 as it's trivial to see from a data flow 
analysis
that the proceeding conditional guarantees that those can't overflow.
The empty asm() is necessary to get GCC to generate comparable code).



fib.c
Description: Binary data


Obviously, for some examples this will be much worse, for others, much better, 
but without
this implemented in GHC it will be difficult to measure.

Tommy

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Carter Schonwald]

GHC is not the spec, I am talking about GHC Haskell, not Haskell the
standard that I don't use.

On 32bit machines, GHC Int is 32bits. On 64bit GHC on 64bit machines Int is
64 bits.

If you have another well engineered suitable for wide use Haskell compiler
in mind, I'd love to try it out, but with interesting software you will be
using none portable features per target platform. And thats OK. Its a
tradeoff thats sometimes worth making.
On Jun 3, 2013 4:19 AM, "Tommy Thorn"  wrote:

> On Jun 3, 2013, at 00:23 , Carter Schonwald 
> wrote:
>
> > Int is "native register sized integer"
>
> Actually it's not. Read the definition. Int is only guaranteed to be 29
> bits.
>
> Here's *one* _actual_ data point (from a 2.8 GHz i7, 64-bit code):
>
> time ./fib
> fib(43) = 701408733
> 3.27 real 3.27 user 0.00 sys
> time ./fib-safe
> fib(43) = 701408733
> 3.45 real 3.45 user 0.00 sys
>
> (NB: I do not check the n-1 and n-2 as it's trivial to see from a data
> flow analysis
> that the proceeding conditional guarantees that those can't overflow.
> The empty asm() is necessary to get GCC to generate comparable code).
>
>
>
>
> Obviously, for some examples this will be much worse, for others, much
> better, but without
> this implemented in GHC it will be difficult to measure.
>
> Tommy
>
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Richard A. O'Keefe]

On 3/06/2013, at 6:58 PM, Carter Schonwald wrote:
> If the Int type had either of these semantics by default, many many 
> performance sensitive libraries would suddenly have substantially less 
> compelling performance.  Every single operation that was branchless before 
> would have a branch *every* operation. this would be BAD. 

Actually, the x86 can be configured to trap integer overflows,
so on that not entirely unpopular platform, there need be NO
extra branches.

Alternatively, and more portably, there could be separate
Int and UnsafeInt types, and the performance sensitive libraries
could be rewritten to use UnsafeInt.

For just one week, I had the joy of using a C compiler where
signed integer overflow was trapped.  It was *wonderful*.


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Rustom Mody]

On Tue, Jun 4, 2013 at 7:35 AM, Richard A. O'Keefe wrote:

>
> On 3/06/2013, at 6:58 PM, Carter Schonwald wrote:
> > If the Int type had either of these semantics by default, many many
> performance sensitive libraries would suddenly have substantially less
> compelling performance.  Every single operation that was branchless before
> would have a branch *every* operation. this would be BAD.
>
> Actually, the x86 can be configured to trap integer overflows,
> so on that not entirely unpopular platform, there need be NO
> extra branches.
>

Well yes and no. See http://software.intel.com/en-us/forums/topic/306156
Using instructions like cmovo "Conditional MOve on Overflow" we can test
without a branch -- so in that sense yes.

No, because the use of the word 'trap' is a bit misleading. If we
understand 'trap' as synchronous interrupt, then intel provides the
infrastructure to literally trap floating point errors but for integers
such a 'trap' only works if the instruction stream contains instructions
like INTO or CMOVO etc.


>
> Alternatively, and more portably, there could be separate
> Int and UnsafeInt types, and the performance sensitive libraries
> could be rewritten to use UnsafeInt.
>
> For just one week, I had the joy of using a C compiler where
> signed integer overflow was trapped.  It was *wonderful*.
>
>
In Discipline of Programming (in 1976!) Dijkstra exactly described this
problem, and squarely put the blame on poorly engineered machines.
He introduced 3 concepts/terms:
UM : unbounded machine
SLM : sufficiently large machine
HSLM : hopefully sufficiently large machine

The UM -- like a Turing machine -- has no messy restrictions of finiteness
like wordsize and is therefore pleasant to reason with and impossible to
physically build.

The SLM is like most of our actual machines -- actual finite state machines
approximating our conceptually nice unbounded machines. The problem is when
the approximation fails, the SLM behaves unpredictably.

So we have the HSLM, which (I quote):

The HSLM is two things merged into one. Besides acting as the largest SLM
we can afford, it checks, when called to execute a program, as the
computation proceeds, whether this SLM is large enough for the current
computation.  If so, it proceeds with the simulation of the UM's behaviour,
otherwise it refuses to continue.

There exist, regretfully enough,in which the continuous check that the
simulation of the behaviour of the UM is not beyond their capacity is so
time-consuming, that the check is suppressed for the sake of efficiency.

It is very difficult to use such machines… and we ignore them in the
sequel!!

In short the problem is our machines: if catching errors involves checking
and checking involves a cost, some program(ers) will sometimes seek to
avoid that.
Moving the check to the hardware -- ie synchronous trap on errors --
removes the cost and the temptation to avoid.

Until we get such machines, these arguments will continue to be there!
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Int is broken [Was: Different answers on different machines]

[Richard A. O'Keefe]

On 4/06/2013, at 4:22 PM, Rustom Mody wrote:

> 
> 
> On Tue, Jun 4, 2013 at 7:35 AM, Richard A. O'Keefe  
> wrote:
> 
> On 3/06/2013, at 6:58 PM, Carter Schonwald wrote:
> > If the Int type had either of these semantics by default, many many 
> > performance sensitive libraries would suddenly have substantially less 
> > compelling performance.  Every single operation that was branchless before 
> > would have a branch *every* operation. this would be BAD.
> 
> Actually, the x86 can be configured to trap integer overflows,
> so on that not entirely unpopular platform, there need be NO
> extra branches.
> 
> Well yes and no. See http://software.intel.com/en-us/forums/topic/306156

I made a mistake, for which I apologise.
There were two things I wanted the x86 to trap, several years ago,
and I found that one of them *could* be trapped and the other could
not.  The one that couldn't was integer overflow.

I do note that the page cited answers a *different* question
which is "does the Intel COMPILER support integer overflow trapping."
The question I answered wrongly was "does the Intel HARDWARE support
integer overflow trapping (by raising an exception on integer
overflow if a bit is set in a certain control register)."

Having apologised for my error, I close with the observation that
Jacob Navia, developer of lcc-win32 (he started with the LCC compiler
but added serious x86-specific optimisation and other Windows goodness),
claims that sticking JO after signed integer operations adds very little
to run time because it is predicted very well by the branch prediction
hardware, since it is almost never taken.

> In Discipline of Programming (in 1976!) Dijkstra exactly described this 
> problem, and squarely put the blame on poorly engineered machines.
> He introduced 3 concepts/terms:
> UM : unbounded machine
> SLM : sufficiently large machine
> HSLM : hopefully sufficiently large machine

Dijkstra was a Burroughs Research Fellow, and the B6700 was a textbook
example of an HSLM.  I couldn't believe how primitive other systems
were after using that.  The signed-integer-overflow-trapping C compiler
I mentioned was a MIPS one (MIPS distinguishing between ADD and ADDU, &c).


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe