Appeal for CORRECT, capable, future-proof math, pre-1.0

classic Classic list List threaded Threaded
69 messages Options
1234
Reply | Threaded
Open this post in threaded view
|

Appeal for CORRECT, capable, future-proof math, pre-1.0

Lee Braiden
This may be go nowhere, especially so late in Rust's development, but I feel like this is an important, relatively small change (though a high-profile one).  I believe it could have a large, positive impact in terms of targeting new developer communities, gaining more libraries and applications, giving a better impression of the language, AND on performance and futureproofing.

However, a lot of people who are interested in performance will probably baulk at this, on first sight.  If you're in that group, let me encourage you to keep reading, at least until the points on performance improvements.  Then baulk, if you like ;)

Also, I said it in the post as well, but it's late here, so apologies for any readability / editing issues.  I tried, but sleep beckons ;)


  http://blog.irukado.org/2014/01/an-appeal-for-correct-capable-future-proof-math-in-nascent-programming-languages/


--
Lee


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Corey Richardson
The current consensus on this subject, afaik, is the rename int/uint
to intptr/uintptr. They're awful names, but it frees up int for a
*fast* bigint type. Fast here is key. We can't have a suboptimal
numeric type be the recommended default. We need to perform at least
as well as GMP for me to even consider it. Additionally we'd have
generic numeric literals. I don't think anyone wants what we current
have for *numerics*. Fixed-size integers are necessary for some tasks,
but numerics is not one of them.

As long as we rename int/uint to intptr/uintptr and leave int etc
reserved, I think we can defer the language issues to post-1.0. It
should be entirely backwards compatible. Development of robust
numerics can happen outside the standard library. Talk to bjz about
this, he has some ideas :)

As an aside, you mention a "real" in your blog post like it's
something that exists. Rust does not have any such type.

On Sat, Jan 11, 2014 at 12:15 AM, Lee Braiden <[hidden email]> wrote:

> This may be go nowhere, especially so late in Rust's development, but I feel
> like this is an important, relatively small change (though a high-profile
> one).  I believe it could have a large, positive impact in terms of
> targeting new developer communities, gaining more libraries and
> applications, giving a better impression of the language, AND on performance
> and futureproofing.
>
> However, a lot of people who are interested in performance will probably
> baulk at this, on first sight.  If you're in that group, let me encourage
> you to keep reading, at least until the points on performance improvements.
> Then baulk, if you like ;)
>
> Also, I said it in the post as well, but it's late here, so apologies for
> any readability / editing issues.  I tried, but sleep beckons ;)
>
>
>
> http://blog.irukado.org/2014/01/an-appeal-for-correct-capable-future-proof-math-in-nascent-programming-languages/
>
>
> --
> Lee
>
>
> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev
>
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Patrick Walton-2
On 1/10/14 9:41 PM, Corey Richardson wrote:
> The current consensus on this subject, afaik, is the rename int/uint
> to intptr/uintptr. They're awful names, but it frees up int for a
> *fast* bigint type. Fast here is key. We can't have a suboptimal
> numeric type be the recommended default. We need to perform at least
> as well as GMP for me to even consider it. Additionally we'd have
> generic numeric literals. I don't think anyone wants what we current
> have for *numerics*. Fixed-size integers are necessary for some tasks,
> but numerics is not one of them.

I wasn't aware of this consensus. I'm not sure what I think; int and
uint as they are is pretty nice for array indexing.

Patrick

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Bob Ippolito
In reply to this post by Lee Braiden
On Friday, January 10, 2014, Lee Braiden wrote:
This may be go nowhere, especially so late in Rust's development, but I feel like this is an important, relatively small change (though a high-profile one).  I believe it could have a large, positive impact in terms of targeting new developer communities, gaining more libraries and applications, giving a better impression of the language, AND on performance and futureproofing.

However, a lot of people who are interested in performance will probably baulk at this, on first sight.  If you're in that group, let me encourage you to keep reading, at least until the points on performance improvements.  Then baulk, if you like ;)

Also, I said it in the post as well, but it's late here, so apologies for any readability / editing issues.  I tried, but sleep beckons ;)


  http://blog.irukado.org/2014/01/an-appeal-for-correct-capable-future-proof-math-in-nascent-programming-languages/

I think a pragmatic approach is to do what Haskell does and allow number literals to be used for any type that implements the right typeclasses. You can implement what you need to as a library, and if it solves problems then people will use it.

(rant below, feel free to ignore)

Floats aren't horrible, you just have to know a little bit of numerical analysis in order to use them properly (regardless of what base they are in!). Most of the science and finance computations that I know of fit just fine into the domain of fixed size floating point. The numbers have finite precision to begin with, and there's often a ton of them so performance matters. Having some arbitrary precision type where adding a really small number to a really big one can take up an arbitrarily large amount of memory and/or time probably isn't going to help much. Also, good luck actually supporting real numbers unless you intend for this type to work symbolically, and then you are building a computer algebra system. That's not likely the right course for a systems programming language. 

-bob

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Huon Wilson
In reply to this post by Patrick Walton-2
On 11/01/14 16:48, Patrick Walton wrote:

> On 1/10/14 9:41 PM, Corey Richardson wrote:
>> The current consensus on this subject, afaik, is the rename int/uint
>> to intptr/uintptr. They're awful names, but it frees up int for a
>> *fast* bigint type. Fast here is key. We can't have a suboptimal
>> numeric type be the recommended default. We need to perform at least
>> as well as GMP for me to even consider it. Additionally we'd have
>> generic numeric literals. I don't think anyone wants what we current
>> have for *numerics*. Fixed-size integers are necessary for some tasks,
>> but numerics is not one of them.
>
> I wasn't aware of this consensus. I'm not sure what I think; int and
> uint as they are is pretty nice for array indexing.

The RFC/issue is https://github.com/mozilla/rust/issues/9940


Huon

>
> Patrick
>
> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Isaac Dupree
In reply to this post by Lee Braiden
Scheme's numeric tower is one of the best in extant languages.  Take a
look at it.  Of course, its dynamic typing is poorly suited for Rust.

Arbitrary-precision arithmetic can get you mathematically perfect
integers and rational numbers, but not real numbers.  There are an
uncountably infinite number of real numbers and sophisticated computer
algebra systems are devoted the problem (or estimates are used, or you
become unable to compare two real numbers for equality).  The MPFR C
library implements arbitrarily high precision floating point, but that
still has all the pitfalls of floating-point that you complain about.
For starters, try representing sqrt(2) and testing its equality with
e^(0.5 ln 2).

In general, Rust is a systems language, so fixed-size integral types are
important to have.  They are better-behaved than in C and C++ in that
signed types are modulo, not undefined behaviour, on overflow.  It could
be nice to have integral types that are task-failure on overflow as an
option too.  As you note, bignum integers are important too; it's good
they're available.  I think bignum rationals would be a fine additional
choice to have (Haskell and GMP offer them, for example).

-Isaac


On 01/11/2014 12:15 AM, Lee Braiden wrote:

> This may be go nowhere, especially so late in Rust's development, but I
> feel like this is an important, relatively small change (though a
> high-profile one).  I believe it could have a large, positive impact in
> terms of targeting new developer communities, gaining more libraries and
> applications, giving a better impression of the language, AND on
> performance and futureproofing.
>
> However, a lot of people who are interested in performance will probably
> baulk at this, on first sight.  If you're in that group, let me
> encourage you to keep reading, at least until the points on performance
> /improvements/.  Then baulk, if you like ;)
>
> Also, I said it in the post as well, but it's late here, so apologies
> for any readability / editing issues.  I tried, but sleep beckons ;)
>
>
> http://blog.irukado.org/2014/01/an-appeal-for-correct-capable-future-proof-math-in-nascent-programming-languages/
>
>
> --
> Lee
>
>
>
> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev
>

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Daniel Micay
In reply to this post by Lee Braiden
On Sat, Jan 11, 2014 at 12:15 AM, Lee Braiden <[hidden email]> wrote:

> This may be go nowhere, especially so late in Rust's development, but I feel
> like this is an important, relatively small change (though a high-profile
> one).  I believe it could have a large, positive impact in terms of
> targeting new developer communities, gaining more libraries and
> applications, giving a better impression of the language, AND on performance
> and futureproofing.
>
> However, a lot of people who are interested in performance will probably
> baulk at this, on first sight.  If you're in that group, let me encourage
> you to keep reading, at least until the points on performance improvements.
> Then baulk, if you like ;)
>
> Also, I said it in the post as well, but it's late here, so apologies for
> any readability / editing issues.  I tried, but sleep beckons ;)
>
>
>
> http://blog.irukado.org/2014/01/an-appeal-for-correct-capable-future-proof-math-in-nascent-programming-languages/
>
>
> --
> Lee

> The wrongness of float

There is no lossless implementation of real numbers on a computer. You
assume arbitrary precision floating point can cover every real number,
but there's no such thing. Arbitrary precision means you can choose
the precision used by the numbers. It's certainly no replacement for
hardware floating point because it's many orders of magnitude slower.
You may not understand IEEE754 floating point arithmetic, but it's
certainly not *wrong*.

> The wrongness of machine ints

Big integers are many orders of magnitude slower than hardware integer
arithmetic. It's not a replacement for it, but rather an alternative
when you need a larger range. You still need to validate inputs
because it's very easy to go out-of-memory, and that's going to bring
down the whole process or even other processes on the system.

> For those looking to reject this idea on the basis of optimisation: consider that abstracting away from 32-bit integers or 64-bit floats, or 256-bit ints, can potentially lead to better optimisation, if the compiler can then figure out that it’s on a 256-bit machine (or indeed, is targeting a 256-bit GPU) and is free to optimise accordingly.

This isn't how hardware works. Smaller floating point numbers are
faster than higher precision, because they're smaller. An array of
32-bit floating point numbers will always be half the size as the same
array of 64-bit floating point numbers. Double the amount of data can
fit into the layers of caches, and you can fit twice as many into SIMD
registers so there's double the amount of theoretical throughput.

> real becomes, not a 32-bit float (as I understand it currently is), but what it sounds like: a real number, covering all numbers in the real number range, using an arbitrary precision type.

Rust doesn't have a `real` type. It has `f32` and `f64`, which are an
explicit opt-in to IEEE754 binary floating point. If you don't want
this, you don't have to use them. Anyway, covering all numbers in the
real number range isn't possible. You can have the user pass the
desired precision in the constructor and then handle two inputs of
varying precision in a sensible way.

> int is not (misleadingly) a machine word, but represents what it sounds like: the entire range of integers, using a bigint type. The Big int type in extra would probably be fine, if it were optimised more. I noticed that there were pull requests for large performance improvements in bigint, but they were rejected for lack of comments. I suspect, if it where given its rightful place as the only fully capable integer type in the libraries, then it would rapidly gain performance through patches, too.

A pointer-size integer type is required. A big integer type cannot be
implemented without library support, and will always be significantly
slower than hardware integer types. A Rust big integer implementation
is not going to be competitive with libraries like `gmp` for at least
a decade. An enormous amount of work is required to implement the
whole range of algorithms with better asymptomatic performance, then
optimize with per-platform assembly and figure out the heuristics for
selecting the algorithms.

Placing a huge performance burden on all Rust code and pushing it far
behind Java in performance is not going to result in a fantasy world
where big integers are the same speed.

> Range checking be implemented in debug and optimisation compiler modes, to support the above, and for the general (ada-like) safety benefits that range-checking of numbers would provide. If it’s REALLY such a compilation-speed turn-off, it could be enabled with specific compiler flags.

Range checking also results in significant performance overhead. Two's
complement arithmetic is also often desired, especially in
cryptography and hashing algorithms. Checked overflow is already
provided in the standard library and alternate types handling overflow
in a different way than two's complement arithmetic could be added.
Pretty much the only useful thing here would be implementing an enum
using a hardware integer for small values, and overflowing to a big
integer.

> Rust compilers can optimise int to i32 etc. _automatically_, iff it knows there are no problems doing so, because of the number ranges involved in calculations.

This isn't going to happen in the real-world. Compilers are not magic,
and can't just go changing the size of a type across the program and
somehow figure out where all of the pointers go.

> Likewise, f64, etc. are considered optimisations of real, and can either be optimised by hand, or — potentially, if the compiler work is done — automatically.

Real number precision is always going to be a compromise. There is no
such thing as perfect precision, and Rust doesn't need to choose a
default. The only time I can imagine you would be able to lower the
precision is if someone casts a 32-bit floating point number to
64-bit, performs an operation and then stores it back as a 32-bit
number. It's not going to scale.

> equality comparisons are accurate for math by default

They are already accurate.

> number range checking would be available, either by default or as an optional compiler feature / optimisation flag

It's already available and you can write an integer type with checked
overflow. The performance is not impressive, and there's nothing Rust
can do about it. It's outputting the checked overflow intrinsics and
you can choose to handle the overflow flag however you wish.

> New x86_64 CPUs will (may already) implement decimal types in hardware — in a way that’s compatible with C++’s new decimal types

AFAIK this isn't implemented in hardware. Anyway, IEEE754 decimal
floats have the same caveats as binary floats except that they won't
have lower precision than literals written as decimals.

> Slower math by default. A compiler flag could override this, or people could manually specify a faster f32/f64/i64 type, for example, if they care. I do not think this is a significant problem.

This isn't a significant problem? Rust is a systems language, and as a
systems language it is going to expose the fast low-level primitive
types. If it doesn't offer C level performance, then it's not a very
useful language. Brushing aside performance issues by pretending
optimizing compilers are omnipresent, magical tools does not work. The
language you're looking for isn't Rust, because you don't care at all
about performance.

# What can actually be done?

I have already opened an issue about removing the fallback of integer
literals to `int` when another type can be inferred. If there's no
fallback, then it's only a matter of adding support for generic
literals like Haskell to have all integer types as first-class
citizens. Rust doesn't need a default integer type.

It doesn't need to make any choices about this at all. It can offer
32-bit, 64-bit and eventually 128-bit IEEE754 floating point numbers.
It can offer 8-bit, 16-bit, 32-bit and 64-bit variants of two's
complement arithmetic integers. It can offer big integers, rational
numbers, arbitrary precision binary floats and arbitrary precision
decimal floats. You can use the suitable tool for the job without
burdening everyone with significant performance overhead and turning
Rust into something that's not a systems language.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Huon Wilson
In reply to this post by Isaac Dupree
On 11/01/14 16:58, Isaac Dupree wrote:

> Scheme's numeric tower is one of the best in extant languages.  Take a
> look at it.  Of course, its dynamic typing is poorly suited for Rust.
>
> Arbitrary-precision arithmetic can get you mathematically perfect
> integers and rational numbers, but not real numbers.  There are an
> uncountably infinite number of real numbers and sophisticated computer
> algebra systems are devoted the problem (or estimates are used, or you
> become unable to compare two real numbers for equality).  The MPFR C
> library implements arbitrarily high precision floating point, but that
> still has all the pitfalls of floating-point that you complain about.
> For starters, try representing sqrt(2) and testing its equality with
> e^(0.5 ln 2).
>
> In general, Rust is a systems language, so fixed-size integral types
> are important to have.  They are better-behaved than in C and C++ in
> that signed types are modulo, not undefined behaviour, on overflow.  
> It could be nice to have integral types that are task-failure on
> overflow as an option too.

We do already have some Checked* traits (using the LLVM intrinsics
internally), which let you have task failure as one possibility on
overflow. e.g.
http://static.rust-lang.org/doc/master/std/num/trait.CheckedAdd.html 
(and Mul, Sub, Div too).


Huon


> As you note, bignum integers are important too; it's good they're
> available.  I think bignum rationals would be a fine additional choice
> to have (Haskell and GMP offer them, for example).
>
> -Isaac
>
>
> On 01/11/2014 12:15 AM, Lee Braiden wrote:
>> This may be go nowhere, especially so late in Rust's development, but I
>> feel like this is an important, relatively small change (though a
>> high-profile one).  I believe it could have a large, positive impact in
>> terms of targeting new developer communities, gaining more libraries and
>> applications, giving a better impression of the language, AND on
>> performance and futureproofing.
>>
>> However, a lot of people who are interested in performance will probably
>> baulk at this, on first sight.  If you're in that group, let me
>> encourage you to keep reading, at least until the points on performance
>> /improvements/.  Then baulk, if you like ;)
>>
>> Also, I said it in the post as well, but it's late here, so apologies
>> for any readability / editing issues.  I tried, but sleep beckons ;)
>>
>>
>> http://blog.irukado.org/2014/01/an-appeal-for-correct-capable-future-proof-math-in-nascent-programming-languages/ 
>>
>>
>>
>> --
>> Lee
>>
>>
>>
>> _______________________________________________
>> Rust-dev mailing list
>> [hidden email]
>> https://mail.mozilla.org/listinfo/rust-dev
>>
>
> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Daniel Micay
In reply to this post by Patrick Walton-2
On Sat, Jan 11, 2014 at 12:48 AM, Patrick Walton <[hidden email]> wrote:

> On 1/10/14 9:41 PM, Corey Richardson wrote:
>>
>> The current consensus on this subject, afaik, is the rename int/uint
>> to intptr/uintptr. They're awful names, but it frees up int for a
>> *fast* bigint type. Fast here is key. We can't have a suboptimal
>> numeric type be the recommended default. We need to perform at least
>> as well as GMP for me to even consider it. Additionally we'd have
>> generic numeric literals. I don't think anyone wants what we current
>> have for *numerics*. Fixed-size integers are necessary for some tasks,
>> but numerics is not one of them.
>
> I wasn't aware of this consensus. I'm not sure what I think; int and uint as
> they are is pretty nice for array indexing.
>
> Patrick

I think it's very important to remove the default fallback to `int` so
Rust can leave this as an explicit choice for the programmer. It's too
easy to accidentally fall back to a fixed-size signed integer and
since the length varies based on the pointer-size, you may not run
into the bugs on the platform you're developing on.

It would be nice to name them based on what they are instead of making
them out as good defaults, because this should really be an explicit
choice. High-level logic will often (but not always) want a big
integer type, and it's too easy to just use `int` because it's the
"default".
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Daniel Micay
In reply to this post by Huon Wilson
On Sat, Jan 11, 2014 at 1:05 AM, Huon Wilson <[hidden email]> wrote:

> On 11/01/14 16:58, Isaac Dupree wrote:
>>
>> Scheme's numeric tower is one of the best in extant languages.  Take a
>> look at it.  Of course, its dynamic typing is poorly suited for Rust.
>>
>> Arbitrary-precision arithmetic can get you mathematically perfect integers
>> and rational numbers, but not real numbers.  There are an uncountably
>> infinite number of real numbers and sophisticated computer algebra systems
>> are devoted the problem (or estimates are used, or you become unable to
>> compare two real numbers for equality).  The MPFR C library implements
>> arbitrarily high precision floating point, but that still has all the
>> pitfalls of floating-point that you complain about. For starters, try
>> representing sqrt(2) and testing its equality with e^(0.5 ln 2).
>>
>> In general, Rust is a systems language, so fixed-size integral types are
>> important to have.  They are better-behaved than in C and C++ in that signed
>> types are modulo, not undefined behaviour, on overflow.  It could be nice to
>> have integral types that are task-failure on overflow as an option too.
>
>
> We do already have some Checked* traits (using the LLVM intrinsics
> internally), which let you have task failure as one possibility on overflow.
> e.g. http://static.rust-lang.org/doc/master/std/num/trait.CheckedAdd.html
> (and Mul, Sub, Div too).

I don't think failure on overflow is very useful. It's still a bug if
you overflow when you don't intend it. If we did have a fast big
integer type, it would make sense to wrap it with an enum heading down
a separate branch for small and large integers, and branching on the
overflow flag to expand to a big integer. I think this is how Python's
integers are implemented.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Brian Anderson
On 01/10/2014 10:08 PM, Daniel Micay wrote:

> On Sat, Jan 11, 2014 at 1:05 AM, Huon Wilson <[hidden email]> wrote:
>> On 11/01/14 16:58, Isaac Dupree wrote:
>>> Scheme's numeric tower is one of the best in extant languages.  Take a
>>> look at it.  Of course, its dynamic typing is poorly suited for Rust.
>>>
>>> Arbitrary-precision arithmetic can get you mathematically perfect integers
>>> and rational numbers, but not real numbers.  There are an uncountably
>>> infinite number of real numbers and sophisticated computer algebra systems
>>> are devoted the problem (or estimates are used, or you become unable to
>>> compare two real numbers for equality).  The MPFR C library implements
>>> arbitrarily high precision floating point, but that still has all the
>>> pitfalls of floating-point that you complain about. For starters, try
>>> representing sqrt(2) and testing its equality with e^(0.5 ln 2).
>>>
>>> In general, Rust is a systems language, so fixed-size integral types are
>>> important to have.  They are better-behaved than in C and C++ in that signed
>>> types are modulo, not undefined behaviour, on overflow.  It could be nice to
>>> have integral types that are task-failure on overflow as an option too.
>>
>> We do already have some Checked* traits (using the LLVM intrinsics
>> internally), which let you have task failure as one possibility on overflow.
>> e.g. http://static.rust-lang.org/doc/master/std/num/trait.CheckedAdd.html
>> (and Mul, Sub, Div too).
> I don't think failure on overflow is very useful. It's still a bug if
> you overflow when you don't intend it. If we did have a fast big
> integer type, it would make sense to wrap it with an enum heading down
> a separate branch for small and large integers, and branching on the
> overflow flag to expand to a big integer. I think this is how Python's
> integers are implemented.

I do think it's useful and is potentially a good compromise for the
performance of the default integer type. Overflow with failure is a bug
that tells you there's a bug. Wrapping is a bug that pretends it's not a
bug.

Hitting a slow path unexpectedly on overflow seems to me like a recipe
for unpredictable performance, which doesn't seem inline with Rust's
usual goals.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Daniel Micay
On Sat, Jan 11, 2014 at 1:18 AM, Brian Anderson <[hidden email]> wrote:

> On 01/10/2014 10:08 PM, Daniel Micay wrote:
>>
>> On Sat, Jan 11, 2014 at 1:05 AM, Huon Wilson <[hidden email]> wrote:
>>>
>>> On 11/01/14 16:58, Isaac Dupree wrote:
>>>>
>>>> Scheme's numeric tower is one of the best in extant languages.  Take a
>>>> look at it.  Of course, its dynamic typing is poorly suited for Rust.
>>>>
>>>> Arbitrary-precision arithmetic can get you mathematically perfect
>>>> integers
>>>> and rational numbers, but not real numbers.  There are an uncountably
>>>> infinite number of real numbers and sophisticated computer algebra
>>>> systems
>>>> are devoted the problem (or estimates are used, or you become unable to
>>>> compare two real numbers for equality).  The MPFR C library implements
>>>> arbitrarily high precision floating point, but that still has all the
>>>> pitfalls of floating-point that you complain about. For starters, try
>>>> representing sqrt(2) and testing its equality with e^(0.5 ln 2).
>>>>
>>>> In general, Rust is a systems language, so fixed-size integral types are
>>>> important to have.  They are better-behaved than in C and C++ in that
>>>> signed
>>>> types are modulo, not undefined behaviour, on overflow.  It could be
>>>> nice to
>>>> have integral types that are task-failure on overflow as an option too.
>>>
>>>
>>> We do already have some Checked* traits (using the LLVM intrinsics
>>> internally), which let you have task failure as one possibility on
>>> overflow.
>>> e.g. http://static.rust-lang.org/doc/master/std/num/trait.CheckedAdd.html
>>> (and Mul, Sub, Div too).
>>
>> I don't think failure on overflow is very useful. It's still a bug if
>> you overflow when you don't intend it. If we did have a fast big
>> integer type, it would make sense to wrap it with an enum heading down
>> a separate branch for small and large integers, and branching on the
>> overflow flag to expand to a big integer. I think this is how Python's
>> integers are implemented.
>
>
> I do think it's useful and is potentially a good compromise for the
> performance of the default integer type. Overflow with failure is a bug that
> tells you there's a bug. Wrapping is a bug that pretends it's not a bug.
>
> Hitting a slow path unexpectedly on overflow seems to me like a recipe for
> unpredictable performance, which doesn't seem inline with Rust's usual
> goals.

The branch on the overflow flag results in a very significant loss in
performance. For example, I had to carefully write the vector `push`
method for my `Vec<T>` type to only perform one overflow check. With
two checks, it's over 5 times slower due to failed branch predictions.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Paul Nathan
In reply to this post by Daniel Micay
On 1/10/14 10:05 PM, Daniel Micay wrote:

> On Sat, Jan 11, 2014 at 12:48 AM, Patrick Walton <[hidden email]> wrote:
>> On 1/10/14 9:41 PM, Corey Richardson wrote:
>>>
>>> The current consensus on this subject, afaik, is the rename int/uint
>>> to intptr/uintptr. They're awful names, but it frees up int for a
>>> *fast* bigint type. Fast here is key. We can't have a suboptimal
>>> numeric type be the recommended default. We need to perform at least
>>> as well as GMP for me to even consider it. Additionally we'd have
>>> generic numeric literals. I don't think anyone wants what we current
>>> have for *numerics*. Fixed-size integers are necessary for some tasks,
>>> but numerics is not one of them.
>>
>> I wasn't aware of this consensus. I'm not sure what I think; int and uint as
>> they are is pretty nice for array indexing.
>>
>> Patrick
>
> I think it's very important to remove the default fallback to `int` so
> Rust can leave this as an explicit choice for the programmer. It's too
> easy to accidentally fall back to a fixed-size signed integer and
> since the length varies based on the pointer-size, you may not run
> into the bugs on the platform you're developing on.
>
> It would be nice to name them based on what they are instead of making
> them out as good defaults, because this should really be an explicit
> choice. High-level logic will often (but not always) want a big
> integer type, and it's too easy to just use `int` because it's the
> "default".
> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev
> .
>

One of the common style rules in C/C++ codebases (IME and from what I've
read) is to have an explicit typedef'd int<intsize> type:

i.e.,

typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned long uint32;
// and so forth.

This way it's clearly seen what the width is in the code.

It would seem to me to be an obvious choice of "optimize for the correct
case" to remove "int" and require choosing the width as part of the type
declaration (much like has been done for floats).


Note - I have zero experience in numerical analysis; my experience here
largely lies in the embedded/low-level space. A numerical analyst may
disagree 100% and prefer a generic "bigint" type for correctness of
computation. No idea. Not my area so far.

--
Regards,
Paul


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev

signature.asc (965 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Daniel Micay
In reply to this post by Corey Richardson
On Sat, Jan 11, 2014 at 12:41 AM, Corey Richardson <[hidden email]> wrote:
>
> We need to perform at least as well as GMP for me to even consider it.

The only realistic way to accomplish this is using GMP. Lots of other
big integer implementations exist with lots of work put into them and
the performance is not even in the same ballpark. It's difficult just
to implement all of the required algorithms:

https://gmplib.org/manual/Division-Algorithms.html#Division-Algorithms

Then, consider that you're going to need to write the low-level code
by hand in assembly so you're going to need domain experts for several
architectures. Processors and compilers are terrible at dealing with
the side effects like carry/overflow flags and can't deal with this
kind of code well.

You'll need versions for different revisions of the CPU instruction
set too, since useful features are added all of the time. For example,
Haswell introduces the `MULX` instruction (among others) and Broadwell
will introduce `ADCX` and `ADOX`.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Daniel Micay
In reply to this post by Paul Nathan
C and C++ have a `stdint.h` header defining fixed-size integers.

Rust doesn't have any arbitrarily defined integer types like C. It has
8/16/32/64-bit variants of both signed and unsigned integers, along
with pointer-size integers covering the address space (int and uint).
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Corey Richardson
In reply to this post by Daniel Micay
Simple answer: then it shouldn't be our default numeric type. You say
earlier that we don't need a default, and that is a case I hadn't
considered before. But I'm growing to like it.

On Sat, Jan 11, 2014 at 1:23 AM, Daniel Micay <[hidden email]> wrote:

> On Sat, Jan 11, 2014 at 12:41 AM, Corey Richardson <[hidden email]> wrote:
>>
>> We need to perform at least as well as GMP for me to even consider it.
>
> The only realistic way to accomplish this is using GMP. Lots of other
> big integer implementations exist with lots of work put into them and
> the performance is not even in the same ballpark. It's difficult just
> to implement all of the required algorithms:
>
> https://gmplib.org/manual/Division-Algorithms.html#Division-Algorithms
>
> Then, consider that you're going to need to write the low-level code
> by hand in assembly so you're going to need domain experts for several
> architectures. Processors and compilers are terrible at dealing with
> the side effects like carry/overflow flags and can't deal with this
> kind of code well.
>
> You'll need versions for different revisions of the CPU instruction
> set too, since useful features are added all of the time. For example,
> Haswell introduces the `MULX` instruction (among others) and Broadwell
> will introduce `ADCX` and `ADOX`.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Vadim Chugunov
In reply to this post by Daniel Micay

The branch on the overflow flag results in a very significant loss in
performance. For example, I had to carefully write the vector `push`
method for my `Vec<T>` type to only perform one overflow check. With
two checks, it's over 5 times slower due to failed branch predictions.

Huh, that's a bit surprising.   I'd have expected branch predictor to learn really quick that the branch is never taken.

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Carter Schonwald
In reply to this post by Corey Richardson
corey, those would be very very nice refinments and a healthy progressive yet conservative stance that leaves the room for evolving healthy defaults (I've a slow boil program to bring breaking changes to fix numerical warts in haskell over the next 2-3 years, )

@corey, one example of a "Real" number type can be found in mpfr http://www.mpfr.org/ (C library for multiple-precision floating-point computations with correct rounding), though note its LGPL,

on the rational number front, i believe theres 1-2 decent bsd/mit style such libs, and i know in haskell, GHC devs are evaluating how to move away from GMP (though this may not have any impact till whenver ghc 7.10 happens)

@patrick
yes, (u)int types that are the same size as pointers are good for indexing into in memory arrays!

 What int type is suitable for indexing into larger than ram sized arrays that are memmapped in regions in a demand driven way? 
 (this is actually a problem i'm trying to figure out generally for some of my own engineering work currently, and it really needs a way that lets one talk about larger than ram arrays on 16, 32 and 64 bit systems, because those exist! Also similar problems come up when working with distributed arrays too! The latter perhaps using something like openmpi or infiniband as the management layer)

@Bob, well said! Even ignoring floating point imprecision, numerical computing still has to deal with rounding, well conditioned / wellposed-ness of the problem being solved, and  to some extent performance! Any "exact real" type either is unbounded (and thus provides unbounded performance woes if used carelessly) or bounded and will eventually suffer some precision issues in some example along with being several orders of slower. 

@bob also good point about generic support for integer/rational/floating point literal support. Providing good literal support for those via a suitable trait would probably help this become a much less contentious issue (though if done poorly it does create some lockin woes)

anyways: numerical library design is very hard, and all i can say is I hope that at least for the near term that rust errs on the side of avoiding lockin on a bad design. And any call to action needs to have very concrete worked out details, because the devil is in those details (well, recursively even!)

keep up the great work! 
-Carter



On Sat, Jan 11, 2014 at 12:41 AM, Corey Richardson <[hidden email]> wrote:
The current consensus on this subject, afaik, is the rename int/uint
to intptr/uintptr. They're awful names, but it frees up int for a
*fast* bigint type. Fast here is key. We can't have a suboptimal
numeric type be the recommended default. We need to perform at least
as well as GMP for me to even consider it. Additionally we'd have
generic numeric literals. I don't think anyone wants what we current
have for *numerics*. Fixed-size integers are necessary for some tasks,
but numerics is not one of them.

As long as we rename int/uint to intptr/uintptr and leave int etc
reserved, I think we can defer the language issues to post-1.0. It
should be entirely backwards compatible. Development of robust
numerics can happen outside the standard library. Talk to bjz about
this, he has some ideas :)

As an aside, you mention a "real" in your blog post like it's
something that exists. Rust does not have any such type.

On Sat, Jan 11, 2014 at 12:15 AM, Lee Braiden <[hidden email]> wrote:
> This may be go nowhere, especially so late in Rust's development, but I feel
> like this is an important, relatively small change (though a high-profile
> one).  I believe it could have a large, positive impact in terms of
> targeting new developer communities, gaining more libraries and
> applications, giving a better impression of the language, AND on performance
> and futureproofing.
>
> However, a lot of people who are interested in performance will probably
> baulk at this, on first sight.  If you're in that group, let me encourage
> you to keep reading, at least until the points on performance improvements.
> Then baulk, if you like ;)
>
> Also, I said it in the post as well, but it's late here, so apologies for
> any readability / editing issues.  I tried, but sleep beckons ;)
>
>
>
> http://blog.irukado.org/2014/01/an-appeal-for-correct-capable-future-proof-math-in-nascent-programming-languages/
>
>
> --
> Lee
>
>
> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev
>
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Daniel Micay
On Sat, Jan 11, 2014 at 2:06 AM, Carter Schonwald
<[hidden email]> wrote:
> corey, those would be very very nice refinments and a healthy progressive
> yet conservative stance that leaves the room for evolving healthy defaults
> (I've a slow boil program to bring breaking changes to fix numerical warts
> in haskell over the next 2-3 years, )
>
> @corey, one example of a "Real" number type can be found in mpfr
> http://www.mpfr.org/ (C library for multiple-precision floating-point
> computations with correct rounding), though note its LGPL,

You choose a precision upon construction of a floating point value.
You also have to choose the precision for the output values. The
correct rounding is in comparison to the raw `mpf_t` offered by GMP
that I think it uses under the hood.

> on the rational number front, i believe theres 1-2 decent bsd/mit style such
> libs, and i know in haskell, GHC devs are evaluating how to move away from
> GMP (though this may not have any impact till whenver ghc 7.10 happens)

None of which are comparable in performance for anything but small
integers. LGPL isn't really that big a deal, because the implication
for closed-source projects is that they have to ship linkable object
files.
>
> @Bob, well said! Even ignoring floating point imprecision, numerical
> computing still has to deal with rounding, well conditioned / wellposed-ness
> of the problem being solved, and  to some extent performance! Any "exact
> real" type either is unbounded (and thus provides unbounded performance woes
> if used carelessly) or bounded and will eventually suffer some precision
> issues in some example along with being several orders of slower.

No real number type has unbounded precision. Arbitrary precision means
the user passes the precision they desire up-front.

On the other hand, a rational number type implemented with big
integers will never lose any precision. However, you don't get `sqrt`,
`sin`, `cos`, etc.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Appeal for CORRECT, capable, future-proof math, pre-1.0

Carter Schonwald
sounds like we agree!  (and thanks for clarifying some of the detail points i neglected)


On Sat, Jan 11, 2014 at 2:27 AM, Daniel Micay <[hidden email]> wrote:
On Sat, Jan 11, 2014 at 2:06 AM, Carter Schonwald
<[hidden email]> wrote:
> corey, those would be very very nice refinments and a healthy progressive
> yet conservative stance that leaves the room for evolving healthy defaults
> (I've a slow boil program to bring breaking changes to fix numerical warts
> in haskell over the next 2-3 years, )
>
> @corey, one example of a "Real" number type can be found in mpfr
> http://www.mpfr.org/ (C library for multiple-precision floating-point
> computations with correct rounding), though note its LGPL,

You choose a precision upon construction of a floating point value.
You also have to choose the precision for the output values. The
correct rounding is in comparison to the raw `mpf_t` offered by GMP
that I think it uses under the hood.

> on the rational number front, i believe theres 1-2 decent bsd/mit style such
> libs, and i know in haskell, GHC devs are evaluating how to move away from
> GMP (though this may not have any impact till whenver ghc 7.10 happens)

None of which are comparable in performance for anything but small
integers. LGPL isn't really that big a deal, because the implication
for closed-source projects is that they have to ship linkable object
files.
>
> @Bob, well said! Even ignoring floating point imprecision, numerical
> computing still has to deal with rounding, well conditioned / wellposed-ness
> of the problem being solved, and  to some extent performance! Any "exact
> real" type either is unbounded (and thus provides unbounded performance woes
> if used carelessly) or bounded and will eventually suffer some precision
> issues in some example along with being several orders of slower.

No real number type has unbounded precision. Arbitrary precision means
the user passes the precision they desire up-front.

On the other hand, a rational number type implemented with big
integers will never lose any precision. However, you don't get `sqrt`,
`sin`, `cos`, etc.


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
1234