256-bit and 512-bit integers

Just a quick mention of some prior art:

zig uses arbitrary width integers:

const byte: u8 = 8;
const ascii: u7 = 7;
const big: u512 = 512;
const max_int: i65535 = 65535;
const PackedStruct = struct {
   packed1: u38,
   packed2: u17,
   packed3: u9,
};
4 Likes

Not sure about the type, but the compiler running out of memory is a hard upper limit! :wink:

How is it not a zero cost abstraction? We just need a good enough software emulation implemented in the compiler that you can't practically beat by writing the emulation yourself in the Rust code.

I'm guessing @yigal100 meant zero-cost in the way eg newtype are zero-cost: they don't exist at runtime and so cost nothing at runtime. Using that definition emulation Indeed isn't zero cost.

1 Like

By that definition adding two i32 is not zero cost either, the computation takes a while at runtime. I can't see how this definition is useful while discussing proper hardware support for integer types. If the hardware doesn't directly supports 256 byte integer operations the only way of performing them is some kind of emulation.

1 Like

Bignum arithmetic is challenging to optimize, even just on integers, and it often needs to be re-tuned for each processor generation. I invite you to peruse GMP developers' corner to get an idea of how much work it can be. Pay attention to the last-modification dates on each page; GMP is chronically understaffed.

Having bignums built into the language is a tempting idea, but I'm leery of dumping this much additional work on the stdlib team.

7 Likes

The generally accepted definition of a "zero cost abstraction" or a "zero overhead abstraction" is one where you do not pay for what you don't use and it is not possible to write it more efficiently by hand.

3 Likes

No doubt it is. I kind of assumed LLVM would already have some optimizations around arbitrary size integers since I remember reading that LLVM IR supports integer types in the form of i[0-9]+. Obviously I don't have much knowledge about how all of that plays out in the generated code.

I know, this is the reason I wrote my first reply.

12 posts were split to a new topic: Glob imports can shadow built-in types

FWIW RustCrypto has been working on a crate like that:

https://github.com/RustCrypto/utils/tree/master/crypto-bigint

As a general observation it's tricky. Many algorithms (e.g. for modular arithmetic) need direct access to "limbs" and are optimized for certain limb sizes. Effectively leveraging things like SIMD in the context of such algorithms can be quite nuanced.

I wouldn't necessarily be opposed to there being a general purpose type for this in core/std, but IMO I probably wouldn't use it and would expect crates can do a better job entirely at the library level.

1 Like

@Tom-Phinney suggested to me that I should drop the proposal of reserving (i|u|f)(8|16|32|64|128|size) in a PM (that he graciously allowed me to reference here to the group as a whole); I'm inclined to agree with him, as others have shown that there are good reasons to keep the current behavior. However, since @mbrubeck split this topic and created the Glob imports can shadow built-in types, I'll post my thoughts on shadowing over there, and limit my comments here to be about bit integers.

@bascule reminded me of a serious issue concerning larger numbers that I'd completely forgotten about; the 'best' algorithm to use for a big integer library depends on the values that are being computed, as well as the environment and conditions that they're being computed within. A pure scientific application might only care about speed, but cryptographic applications may need to do a tradeoff between speed and designs that defeat sidechannel attacks that leak the keys, while embedded systems that are operating on battery might choose slower, but less power-hungry implementations to increase their battery life. Selecting which algorithm to use (including the choice of using hardware-provided operations, or emulating them in software) requires domain knowledge that we as rust-internals members lack.

To make things worse, these choices may be mixed within the same code. One part of the code may be handling cryptographic secrets, while another part might be doing pure science, so we can't really select a single algorithm.

Long story short, I'm now convinced that the only practical way forwards would be via crates that the user can select amongst.

3 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.