proposal: spec: change int to be arbitrary precision

An idea that has been kicking around for years, but never written down:
The current definition of int (and correspondingly uint) is that it is either 32 or 64 bits. This causes a variety of problems that are small but annoying and add up:

overflow when constants like math.MaxUint64 is automatically promoted to int type
maximum size of a byte slice is only half the address space on a 32-bit machine
int values can overflow silently, yet no one depends on this working. (Those who want overflow use sized types.)
great care must be taken with conversion between potentially large values, as information can be lost silently
many more

I propose that for Go 2 we make a profound change to the language and have int and uint be arbitrary precision. It can be done efficiently - many other languages have done so - and with the new compiler it should be possible to avoid the overhead completely in many cases. (The usual solution is to represent an integer as a word with one bit reserved; for instance if clear, the word points to a big.Int or equivalent, while if set the bit is just cleared or shifted out.)
The advantages are many:

int (and uint, but I'll stop mentioning it now) become very powerful types
overflow becomes impossible, simplifying and securing many calculations
the default type for len etc. can now capture any size without overflow
we could permit any integer type to be converted to int without ceremony, simplifying some arithmetical calculations

Most important, I think it makes Go a lot more interesting. No language in its domain has this feature, and the advantages of security and simplicity it would bring are significant.

I'm a big fan of this, myself. It would elevate int (and uint) to "unrestricted" (for lack of a better word) types, and only the types with explicit sizes (int16, int32, etc.) would be subject to wrap around.
In many cases (loop iteration variables) the compiler may be able to prove that an int is in a certain range and could produce optimal code. In many other cases, the use of int is not speed-critical.

Let's put this and #19624 in the Thunderdome!  Two proposals enter, one proposal leaves...

A minor related point about this: The int and uint types were intended to be of the "natural" size for a given platform, typically the register size. If we have true integers we loose that naturally sized type - yet we make use of it in a few places where we want integer algorithms to work well for a given platform (strconv.Itoa comes to mind). We may want to consider introducing an unsigned "word" type instead (in the past we have also used uintptr in that role, but that may not necessarily guaranteed to be of register size on all platforms).

Representing an int in a single machine word will be tricky.  We run across the same problem we had with scalars being in direct interfaces - the GC sees a word which is sometimes a pointer and sometimes isn't.
The only easy solution I see is to reserve some top bit(s) to set for raw integers and disallow those top bits for any pointer.

@randall77

Two proposals enter, one proposal leaves...

Actually, I think they're completely compatible.  I recommend both!

@randall77

the GC sees a word which is sometimes a pointer and sometimes isn't

Could we fix that with better stack or heap maps?  Instead of each word being "either a pointer or a non-pointer", it would be "a pointer, a non-pointer, or an int".  I suppose that would require two bits instead of one per address, though ― might bloat the maps a bit.
FWIW, the ML family of languages worked around that issue by making the native types int31 and int63 instead of int32 and int64.  I do not recommend that approach.

@bcmills Yes, two bits per word should work.  That just buys us more flexibility to put the distinguishing bits somewhere other than the top bits of the word - not sure if that is worth it.

I love this proposal in abstract, but I'm very concerned about the performance impact. I think it's not by chance that "no language in its domain has this feature".  If we use bound-checking elimination has a similar problem, Go compiler isn't very good at it even nowadays, it basically just handles obvious cases, and doesn't even have a proper VRP pass (the one proposed was abandoned because of compile time concerns). Stuff like a simple multiplication would become a call into the runtime in the general case, and I would surprised if the Go compiler could avoid them in most cases, if we exclude obvious cases like clearly bounded for loops.

@rasky Languages likes Smalltalk and Lisp (and more recently, JavaScript) have pioneered the implementation of such integers - they can be implemented surprisingly efficiently in the common case. A typical implementation reserves the 2 least significant bits as "tags" - making an int on a 64bit platform effectively 62bit in the common (small) case - which is likely more than plenty in most cases (and where it isn't it's either because we need very large integers, or we should be using int64).
One way of using the tag bits is as follows:
00 means small integer (smi)
01 means that the value is a pointer p to an arbitrary precision integer (at p-1)
10 typically the result of an operation (see below)
11 reserved for other uses or unused
Given this encoding, if we have two int values x and y, we can optimistically assume they are smis. For instance x + y would be translated into a single ADD machine instruction, followed by a test of the tag bits. If they are not 00, one (or both) of the operands were large ints and then a runtime call is needed. Also, if there was an overflow, a runtime call is needed. This does add 3 instructions in the fast path, but not more (one conditional jump if overflow, one test of tag bits, one conditional jump if tag bits are not 0 - perhaps more depending on how the runtime call is achieved or if there's a conditional call instruction). It's not cheap, but it's much less expensive than a runtime call in the common case. If both operands were smis, the tag bits remain 00, and the result doesn't need further work. The same is true for subtraction. Multiplication requires a bit more work but is also more expensive. Finally, division is the most complicated one, but also the most expensive operation in general.
It might be worthwhile performing a little experiment where one generates this additional code for each integer addition, using dummy conditional branches that will never be taken (or just jump to the end of the instruction sequence) and see what the performance impact is.

Not a fan of this proposal - currently its quite simple to argue about resulting code and its performance characteristics when doing simple arithmetics. Also - even if losing two bits on 64 bit platform is not important, on 32 bit one it is.
Maybe we could have an arbitrary precision ints implemented in new built-in type (like we do with complex currently)?

Can you discuss how such int variables would represented in mediums other than memory, and marshaled/unmarshaled?
Encoding to JSON should be easy and map really well. As far as I know, JSON spec does not place restrictions on size of numbers, so a really large int would encode as as base 10 number (and vice versa for decoding). E.g.:
{"number":<PHONE_NUMBER>3131231312312312312312321312313123123123123123123}

Would map to an int with value<PHONE_NUMBER>3131231312312312312312321312313123123123123123123.
What about something like encoding/gob or encoding/binary?

@shurcooL

printing is obvious (the usual human-readable forms) - applies to JSON
encoding/gob could use a private internal representation
encoding/binary is for fixed-width numbers at the moment, the proposed int's wouldn't be - but a var-int encoding could work (though the current format would probably be inefficient).

Re: 3, note that the compiler's import/export format already encodes arbitrary-sized integer values because of precise constants.

@shurcooL @griesemer I believe encoding/gob already uses a variable-length encoding for all integer types.

Go should have an arbitrary precision number type that is more convenient than math.Big. That type should not attempt to masquerade as int/uint, as these aren't just used semantically as "number" but more so as "number compatible with c/foolang code that uses the natural local word size".
The root problem here is that golang's design prevents a library from defining an arbitrary precision type that is as semantically and syntactically convenient as a type provided by the runtime with internal knowledge. Solve that problem with golang 2.0, or instead we will find ourselves 5 years from now with countless ad hoc accretions like this.

@jasonwatkinspdx
It's true that one of the roles of int in Go 1 is as an analogue to C's ssize_t.  But it doesn't actually matter whether int is exactly the size of the address space or merely sufficient to cover the address space.
Perhaps more importantly, C APIs don't actually use ssize_t all that often: they use size_t instead.
You have to range-check conversions from C.size_t to int, because the latter is potentially only half the range of the former.  Under this proposal, you'd need the range check in the other direction instead, because C.size_t would now be smaller than int.  The only way to avoid the need for a range check entirely is by making the Go "size" type have exactly the same range as C.size_t, and at that point you're looking at a fairly high risk of overflow bugs (especially from decrementing past zero).

@bcmills

But it doesn't actually matter whether int is exactly the size of the address space or merely sufficient to cover the address space.

It does matter. People make design decisions concerning the size of the address space and how indexes into it can be represented in serializations or other transformed values. Making the type that spans the address space arb precision offloads many complexities to anyone that wants to ship data to other systems.
What does a c abi compatible library consumer of golang look like in a world where int/uint is arb precision? Is it really better if the golang side is blind to any issue at the type level and the c side has no choice but panic?
I do see the value of these types, I just don't want them conflated with int/uint. I'm entirely in favor of a numeric tower in golang being the default numeric type, I just don't want it to pretend to have the same name as the 32bit/64bit machine/isa determined types.

People make design decisions concerning the size of the address space and how indexes into it can be represented in serializations or other transformed values.

Can you give some examples?  I'm having a hard time thinking of anything other than a syscall that spans a process boundary but should be sized to the address space, and raw syscalls generally need to validate their arguments anyway.

What does a c abi compatible library consumer of golang look like in a world where int/uint is arb precision?

The same thing it looks like today: using C.size_t instead of int.

@robpike
It looks harder to reduce CPU of golang program when ints become arbitrary precision. 😝

programs using raw syscalls generally need to validate their arguments anyway.

I want to capture that in the types, not in a dynamic value range check.

I honestly thought it's 11 days more than it really is.
I don't want to lose normal int performance. I don't believe there's a space/time effective way for an arbitrary precision int to be, in many cases,  comparable in performance to the fixed width int.
I have nothing against adding an arbitrary precision mpint type (name does not matter), which the compiler accepts mixed in expressions with normal ints providing the conversions as needed. IOW, it would be really nice to be able to use standard operators with arbitrary precision integers, yes, but please only explicitly. Please leave int alone.

What about floats? JSON can have values like<PHONE_NUMBER>1234567890.12345678901234567890, with many digits before and after the dot, but IIRC no Go type can accurately represent those. That is, no Go type can do maths with it, I know about json.Number.
Personally, I would keep int as it is and instead added a number type that could represent any number with or without a fractional part.

Please do not make int operation slower by default.
I do not need arbitrary precision ints by default, but I do need golang program to use less CPU to save my money with gce vm server.
I do not need some like mpint with Infix expression eithor, *big.Int is enough for me.

I don't understand the performance concerns - even if the performance hit would be noticeable in some scenarios, could you not use sized types like int32 or the unsigned word (like the current uint) mentioned by @griesemer?

I think this might be a good change, but I do have some concerns regarding bitwise operations and performance impact. In my experience, int tends to be the default type for numereic values which makes me a little hessitant without seening before and after numbers.

I am 100% for this proposal. Worrying about the performance impact of arbitrary precision ints is like worrying about the performance impact of array bounds checks, in my opinion. It's negligible if implemented correctly.
I also like this because of how inconvenient the big package is and how I always fall back to Python when I'm dealing with big integers.

For an arbitrary precision uint, what is uint(0)-1 ?
Maybe mpint is enough.

Imho mpint is a very bad idea. No one would use it, except for when they really need it, because int is nicer and feels more standard. Since the majority of libraries would still use int instead of mpint, integrating two libraries, one of which uses int and the other one uses mpint would become cumbersome.
Also, it would be entirely unclear whether to use int or mpint in common situations, which contradicts Go's philosophy, which empathizes clarity and tries to reduce programmer's mental overhead.

@faiface If we are talking about Go 2, by then we should have a better type system anyway. At the same time I would really glad if my arithmetic operations would not suddenly allocate memory if a combination of my integer inputs has resulted in N > n^64. Overflow I can live with - this is my problem.
Again - currently instance of something like ```
type MyIntCombination struct {
FirstInt      int
SecondInt int
ThirdInt     int
}

All of this can be solved using machine dependent int, but I fear that this change would cause fragmentation in our community between those who prefer explicitly sized ints and the ones who prefer the arbitrary precision. For me, It would mean the strict restriction on using `int` anywhere in my company code.

But, alas, without working prototype it's all just a speculation. We all remember how `alias` proposal went.

While the cost of doing an arithmetic operation on two arbitrary precision
ints is important there is also the cost to the garbage collector that
needs to be considered. We probably need an extra bit on each heap word to
indicate whether it is a tagged word. I suspect we can be clever and it
won't be a full bit per word but being clever has a way of complicating
things. Even if we are memory clever, if we have large arrays of arbitrary
precision ints the GC will need to visit each of them to verify that they
are immediates and not pointers. In dynamically typed languages like Lisp,
JavaScript, and Smalltalk this isn't a big deal because the GC had to visit
the words anyway so the GC's marginal cost was minimal.
Furthermore, the cost to the GC is somewhat amplified because it happens
during the mark phase when the GC is already using CPU otherwise available
to the application. The less time the GC is in the mark phase the easier it
is for the application to get the CPU it needs to meet its deadlines, the
less floating garbage, and so forth. This cost is hard to measure but it is
real.
Getting a sense of these systemic costs isn't intractable but needs to be
done before we can claim we know the full cost of arbitrary precision ints.
On Tue, Mar 21, 2017 at 7:49 AM, Tamás Gulácsi<EMAIL_ADDRESS>wrote:

For an arbitrary precision uint, what is uint(0)-1 ?
Maybe mpint is enough.
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/19623#issuecomment-288055090, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AA7Wn_Uq14yr57DLGVxTB0LPA0ubrdVcks5rn7lngaJpZM4Mi7Wo
.

I like the proposal as it's good for most of the cases and you're still able to use intX for special cases.
If I understood correctly, one problem I see is that now int can be either immutable or mutable.
It could lead to some hidden bugs that only appears when the number becomes a big integer with a simple function like this:
func addOne(a int) int {
    a = a+1
    return a
}

There is quite a lot of functions in the go code base that modify one of its parameter without expecting its value to be mutated.

@champioj It needs to be immutable, otherwise it's going to be impossible to use correctly.

@tgulacsi

For an arbitrary precision uint, what is uint(0)-1?

A very good question.  I would argue that that implies one of two things, and the choice depends on whether the difference between uint and int is one of space-efficiency or program invariants.
If the difference is due to space-efficiency, then uint should not exist.  An arbitrary-precision int is capable of representing all of the values of an arbitrary-precision uint without loss, so uint is redundant.
If the difference is due to program invariants — the ability to express "a nonnegative integer" — then subtracting a positive value from uint(0) should panic (and IMO that would argue for also adopting #19624 for consistency).

Being fast and close to the metal is a great advantage of Go1. Many other languages start with hard to optimize semantics and suffer bad performance forever, shackled by backward compatibility.
It's true that JIT compiled languages can get away with complex semantics and still be relatively fast: they speculate, profile, optimize and reoptimize at runtime. Yet they rarely if ever reach C speeds and always at a cost of great complexity.
Offline compiler can't speculate much, unlikely paths still have to be compiled. This extra code hanging off integer arithmetic ops will inhibit optimizations, bloat the binaries and slow everything down universally.
Hidden cost of int will be especially glaring if fast and unencumbered int64 is easily available, but unnecessarily ugly (casts).
Other languages in Go's domain don't have this feature because it's too expensive (C), few people need it (Java, JavaScript) and there are library types with overloaded operators (C++, C#, Scala, Rust, Swift, D).
Languages that do have built-in arbitrary-precision arithmetic are very high level, dynamically typed, relatively slow and often math focused (Python, Ruby, Erlang, Haskell, Scheme, Mathematica and other CAS).
Re: cited benefits.

Security and correctness: dangerous operations on int (overflow, truncation) should just trap, because they are likely to be bugs or fatal errors. Silently propagating astronomical values throughout the program isn't any better than silently truncating them. The underlying problem will be obscured either way. I'm sure many Python programmers will agree.

Representing object sizes: objects larger than half of address space should be simply forbidden. Maybe heaps larger than that should be forbidden too. It's not a big deal considering other GC limitations.

Safety of potentially overflowing operations: I'd reach for int128 or int256 first.

@nnemkin
If  I can easy disable this functional at program level or package level or function level,I think the arbitrary precision can add to golang 2.0 and make them default.
Bloat the binaries to 120% is not a big problem for me.

I like this idea.
I also think floats should be decimal and arbitrary precision by default, since so many programmers use binary fixed precision floats in inappropriate situations, such as for currency values. There should be binfloat64 and binfloat32 for the special purpose high speed approximate binary floating point numbers of IEEE 754.

@lpar I disagree about the floats. Decimal floats have the same, fundamentally unavoidable problem. You are just going to swap people being confused about f/10 with people being confused about f/3 (or sqrt(f), or…).
Computers just fundamentally can't handle real numbers and trying harder to pretend they can won't solve this.

@lpar What would it mean for floats to be arbitrary-precision?  In particular, how would you indicate the precision of a float literal?  (big.NewFloat in today's standard library implicitly uses the precision of float64.)
It's also worth noting that, unlike int, there is no float type in the language today: users of float must already choose float32 or float64.
Some other kind of floating-point representation — interval arithmetic or unums or some similar approach — might be interesting to consider as alternatives, but that belongs in a separate proposal: it's more-or-less independent of the choice of representation of the int type.

Sorry, didn't mean to imply that floats belonged in the same proposal. That was just an aside, I was floating the idea of decimal floats in case anyone else thinks it would be good to knock out another common source of error as a separate proposal.

Why make it Go2? Would it not be better to have that kind of numeric type today in Go1? Select a name ('integer' or 'bigint') that does not collide (often?) with existing go code and use it to introduce such type today. This way if and when Go2 happens we will have experience with dealing with such type :)

@tumdum, because we would only do this if we could do removals and simplifications at the same time to pay for its addition. We don't want to be a language that just keeps accreting features.

@bcmills One choices for arbitrary-precision floats is "Constructive Reals" which have become much harder to demo since browsers quit supporting Java.  See http://www.hboehm.info/crcalc/ .
Or also https://android.googlesource.com/platform/external/crcalc/
Basic idea is that a + b returns a function from requested precision to a string of digits.  Crcalc does lots more than just addition.  One slightly non-intuitive problem with constructive reals is that certain operations take longer than the naive programmer might expect -- if a and b are actually equal but in a way that the built-in hacks cannot determine, (full) comparison is a non-terminating operation.
I have made practical use of these; if you were interested in knowing things about the quality of floating point operations (e.g., transcendental functions) you can use constructive reals to obtain N digits of truth.  A real live numerical analysis prof (John Dennis, then at Rice U.) once proposed  using them in error term calculations, because checking the error often costs a factor of N fewer operations than computing the "answer", and using exact arithmetic to calculate the error counts out a layer of estimation, resulting in a tighter error bound.  We actually implemented this in a Fortran interpreter, and one amusing and not-too-surprising result is that constructive arithmetic on poorly conditioned matrices costs more (because you have to pull more bits out to prevent cancellation errors).

Please let's keep this focused on the subject at hand (arbitrary precision ints).

@typeless An arbitrary precision int type would always use one word (32 or 64bit) when passed as a parameter. See https://github.com/golang/go/issues/19623#issuecomment-287930352 for a possible implementation.
I think there will be a cost for programs overall, but I also think the fears of huge slow-down are overblown.

Is the following proposal feasible if this feature gets implemented.

make "range aChannel" also return two values, one message index and one message value, so that the forms of all "range aContainer" be consistent.

@Go101 No. The problem with index over channel is not there, it's just useless. If a channel emmited 1,000,000 messages a second, a int64 counter would overflow after ~300,000 years.

@faiface

a int64 counter would overflow after ~300,000 years.

Yes, I think this is one reason why "range channel" only return one value in Go1.
The type of the index returned by range is int, not int64.
So if this proposal is implemented, then there will be not the channel message index overflow problem any more.
The index is not totally useless. It is really useful sometimes.

@Go101 int is equivalent to int64 on most machines. When is it not useless?

For example, there are M senders and N receivers, when one of the receivers receives a K+th messages, it will notify all senders and receivers to stop messaging.

@Go101 Questions of overflow notwithstanding, assigning a unique index to every send and receive operation would introduce a sequential bottleneck (similar to the one in #17973).  The spec as it stands today only requires a happens-before relationship between sends and the corresponding receives, allowing for looser synchronization and better parallelism.
With a fixed-size int type you could at least hope for making the counter update an atomic instruction, but with arbitrary-precision int even that goes out the window.

@bcmills
I'm very understanding the issue your referred. But I think there is no needs to assign a unique index to every sends. Just adding a count field for the internal channel struct is ok.

Could you please discuss any range-expression changes for channels in a separate issue/thread? It's at most tangentially related to this proposal and thus adds noise for people who are subscribed because they are interested in the discussion of arbitrary precision ints.

same as @faiface, I also fall back to Python when deal with big numbers. Once I had a mind to extend the "math/big" package with an Eval function.
func Eval(s string) (*Float, error)

not good but at least clearer
// numbers here can be big numbers
n, err := Eval("(1 * 2 * 3 + 4 * 5) + 6")

If this can be done efficiently in language level, why not

Why does this new int need to be immutable?

I really like this suggestion, but if this is added I think native int's need to be added as well. Maybe something like nint and nuint or intn and uintn.

I really like this suggestion, but if this is added I think native int's need to be added as well. Maybe something like nint and nuint or intn and uintn.

If it was up to me I would name the arbitrary-precision integer types as:

aint
auint

Does it make sense to have "unsigned" integer if it's arbitrary precision ?

No. What is auint(0)-1 ?
Pierre Durand<EMAIL_ADDRESS>ezt írta (időpont: 2017. jún. 5.,
H 15:49):

Does it make sense to have "unsigned" integer if it's arbitrary precision ?
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/19623#issuecomment-306191784, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AAPoSkoYNpsKh-zq6Owiu2YBekMYrCkIks5sBAdigaJpZM4Mi7Wo
.

@pierrre, @tgulacsi, we've been over this already (https://github.com/golang/go/issues/19623#issuecomment-288229046).

@mahdix

Why does this new int need to be immutable?

Because all of the other numeric types are immutable. For all of the existing numeric types.
x := y
x++

does not change the value of y.  It would be surprising for that to be any different for arbitrary-precision ints.

I don't know what kind of software other people unknown to me are writing, but it seems to me that in most software in most use cases integer values never exceed 64 bits (32 bits). That is: integer values never exceed the bitwidth of the 64-bit address space (of the 32-bit address space).
The need for arbitrary precision integers is relatively small, especially in a performance-sensitive systems language compiled to machine code like Go, but it is nice if the language provides arbitrary precision integers.

It's not about need, it's about quality of language.

Presumably arbitrary precision constants would map nicely to ints/uints in Go 2.0 with this proposal. That would be certainly make the language more friendly, and do away with this caveat:

There is a caveat to constants of unusual size. Though the Go compiler utilizes the big package for untyped numeric constants, constants and big.Int values aren’t interchangeable. Listing 8.2 displayed a big.Int containing 24 quintillion, but you can’t display the distance constant due to an overflow error.
fmt.Println("Andromeda Galaxy is", distance, "km away.") // *

* constant<PHONE_NUMBER>0000000000 overflows int

- from Lesson 8, Get Programming with Go
Being able to pass a numeric constant or literal to a function and not worry about overflows or conversions would be very nice indeed.

The int and uint types were intended to be of the "natural" size for a given platform, typically the register size. If we have true integers we loose that naturally sized type - yet we make use of it in a few places where we want integer algorithms to work well for a given platform - @griesemer, https://github.com/golang/go/issues/19623#issuecomment-287903210

If needed, @wanton7's suggestion sounds good to me:

I really like this suggestion, but if this is added I think native int's need to be added as well. Maybe something like nint and nuint or intn and uintn. - @wanton7, https://github.com/golang/go/issues/19623#issuecomment-306189100

intn for "natural" and int32, int64, intn

Simply let int as it is but add a new type natural for explicit usage of it.

Why not introduce a new type instead?

@omeid Because to have more robust software in general (no overflows) you need to have it as default int type, so that everyone will use it. It's like vaccination, everyone needs to get on board to eradicate the disease.

Since the majority of libraries would still use int instead of mpint, integrating two libraries, one of which uses int and the other one uses mpint would become cumbersome.

@faiface Would #19412 address this concern? An addition to the type-system that lets a library accept both int and mpint could allow:
type integral union {
    int
    mpint
}
func acceptsEither(v integral)

@wanton7 Calling something with inconsistent, or generally slow, perfs robust is bold claim that requires bold justifications.

@omeid I'm not native english speaker so robust to me means more secure and stable software. I did write about overflowing so not sure how you could misunderstood me. Also I didn't write about performance at all and don't know what it has do to with software robustness, maybe you can explain it to me?

@wanton7 Robust generally has the connotation of efficiency and performance.

@omeid No. There is no strict definition that is universally accepted, but in software, ‘robust’ generally means ‘correct in the face of failure or adverse conditions’, ‘hard to break’ [WikiWikiWeb], ‘capable of performing without failure under a wide range of conditions’ [Merriam-Webster], ‘able to cope with errors during execution and cope with erroneous input’ [Wikipedia], ‘able to recover from errors; unlikely to fail, reliable’ [OED].
I don’t think there is any connotation of efficiency or high performance. In fact, it is common to assume that the safety checks required to make a system robust may incur a performance penalty.

I don't like the proposal, but i like its motivation which is important in its several aspects:

A way to deal with values having precisions or ranges outside the normal hardware ability
A way to naturally perform high-precision or arbitrary-precision math

Some of my software does extensive computations using extended precision real and complex numbers (via math.big). Much of my software does extensive computation using extended precision integers (my own assembler). Some of my software does unlimited precision integer computation using math.big. Based ion my own experience, it seems that this take on the proposal here could be better:

Add int128 as a supported type. (super simple, handy CPU instructions with carry/borrow, fixed size, easily passed on stack, etc.)

In fact...consider int (as in int8, int32, int128, int256) to have the following meaning: on machines where that's a natural hardware size, the natural code is generated, but on machines where that is not natural, then slower but still fast multiprecision code is generated. (Probably add/sub inline and mul/div via functions)

Add float128 as a supported type. This is not so simple in terms how to implement.

You can do a fast but imperfect job with doubled-precision. I have libraries for this, several exist. 4x slower for 128 bits using the normal FP hardware and paired doubles. the precision is perfect and all IEEE modes are right, but, the exponent range is less than IEEE 128-bit FP.
Better would be the slower but IEEE-perfect big.Float in the 128-bit precision size. This is notably slower, but still fast, and harder to fit in. Maybe the answer is a special less-general internal implementation of big.float that is a fixed structure amenable to passing as a value, works as rvalue or rvalue, etc.
and by extension, consider float (as in float32, float64, float128, float256, ...) to have the following meaning: on machines where that's a natural hardware size, the natural code is generated, but on machines where that is not natural, then slower call to math.Float is made, though perhaps reimplemented for thus purpose in a fixed-container of bytes form.

Instead of reinterpreting 'int', i propose this: int stays as the natural hardware int size and new types, 'integer', 'floating' (or 'real'), and 'rational' are added. integer means arbitrary precision integer, floating (or real) means arbitrary precision floating point, and rational means the ratio of arbitrary precision integers.

This is not a fast path. The use of unsized integer, floating, and rational variables is a siren that what is happening may not be super fast. However, it is understood that in exchange they will be super general. Such an integer is what I think Rob wanted for generality...it is the typed variable counterpart of the way numbers are parsed in Go1.
There are subtleties to this. They are a challenge but surmountable:
First, type conversions might "fail" so it is necessary to consider how "x:=int32(integer(1<<800))" should work. Same for floating or float128 and above to float64, since the exponent range may overflow--should they go to zeroes and infinity? should it fail? should some form of type switch be used so that you can say convert if applicable else do this other thing?
Second, what do naked numbers mean. is x:=1<<70 an int128? an integer? a failure? Any can work, 'integer' seems natural but that's not a proposal, just an example of a question that needs answers as part of the design.
Summary:
This modification to the proposal at issue yields a wonderful programming environment, allowing code with integer, rational, and floating variables to be used naturally; supports fast-path hardware friendly coding with float128 and int128 (and larger sizes, handy for crypto and other purposes), and changes no meaning for the existing variable type int.

OCaml internally uses 63 bit ints, with the last bit indicating whether the 64 bit value should be interpreted as an int or a header for some boxed value.  This is similar to some of the suggestions regarding how we should represent arbitrary precision ints in Go. Of course, such a choice has performance implications. We can learn from the experiences obtained using OCaml; for example, see:
https://blog.janestreet.com/what-is-gained-and-lost-with-63-bit-integers/
These benchmarks show that we can expect a slowdown of at least a factor of 2-3 on regular 64-bit arithmetic. Personally, I think it's worth it.

Should the encoding (2 or 3 bits or something else) to accomodate bigints be left up to the implementation? This is what Scheme/Lisp impls do.
To avoid surprises it may be worth adding types integer and uinteger for arbitrary precision that any integral type can be converted to "without ceremony". Note that current {,u}int{,8,16,32,64} essentially do modular arithmetic (even though normally we tend to ignore this fact) so fundamentally different from arbitrary precision ints.
Why have arbitrary precision unsigned integer type at all? Converting /to/ arb. prec requires no extra work. Converting /from/ arb. prec requires that such a number can be /narrowed/ to the lesser type, which can include sign checking.
Might as well as add rational types (e.g 355/113)! Point being, rather than just look at arb prec. int and possibly do piecemeal evolution, why not take another look at all the numeric types (the "numeric tower") and learn/steal from what CL and Scheme have done?

@bakul Regarding your point 1: Different implementations may choose different internal representations, and implementations may evolve. If we were to do anything here, the encoding absolutely should be left to the implementation.

@bakul

Why have arbitrary precision unsigned integer type at all?

See bullet point 3 of the initial comment: Current int types can silently overflow. This is a common source of severe bugs. There are two options for avoiding silent (u)int overflow:
(1) make ints and uints error out on overflows (difficult, creates new problems, e.g. the need for testing for errors after every addition or multiplication), or
(2) make them arbitrary precision (u)ints (easier & more intuitive for the user).
(Algorithms that require overflow as part of their logic should use the sized variants anyway (from (u)int8 to (u)int64.)

@christophberger

make ints and uints error out on overflows … e.g. the need for testing for errors after every addition or multiplication

My current proposal in #19624 would allow you to check for overflow on an entire “expression consisting of arithmetic operators and / or conversions between integer types” at once. You really only need one check for overflow anywhere in the expression, in much the same way that you can do arbitrarily many floating-point operations with only one NaN check at the end.
It's true that arbitrary-precision arithmetic lets you combine checks even more broadly (across function calls, for example), but that flexibility also increases the run-time overhead when values exceed the expected range.

@bcmills
Agreed, a behavior analogous to NaN (that is, allowing to postpone the overflow check until the end of a long calculation) simplifies handling overflow errors.
I also agree on the possible runtime overhead, but when calculations do exceed the range (which should occur pretty rarely in many common scenarios), I guess that most users would prefer observing a slowdown rather than errors.

@christophberger
To clarify, my point was that an arb prec. int would be a superset of arb prec uint so why have two types. Implementation wise I can see a difference (particularly if you use a tagged word). But I am coming at this from a different angle: adding bignums just to deal with overflow seems a big change for a little gain. Introducing bignums should be based on their overall usefulness. And from that perspective the rest of the numeric tower should also be considered (e.g. rationals and bigfloats). Finally from a user perspective unsigned bignum doesn't bring anything more useful (except that one more place you run into potential type mismatch).

@bakul
Thanks for clarifying, I missed the "unsigned" in your 3rd item somehow. Indeed, as per this comment, unsigned arbitrary precision integers are redundant and also fail when calculating uint(0)-1 (as the only sane result for this is a runtime panic).
Regarding signed arbitrary precision integers, I think the gain is more than just "little" - the initial comment already lists three advantages (the first one of the four-bullet list does not count).
In the end, it depends on whether this can be implemented with acceptable efforts and without complicating the runtime (the GC in particular) too much.

I don’t see this proposal and #19624 as mutually exclusive. Arbitrary precision integers would interop well with constants and avoid overflows as an easy to use numeric type. Meanwhile int64 and friends give more control over memory layout... and could be extended to give control over overflow behaviour (wrap, saturate, panic, error, etc.).

Possibly relevant: v8 just added an experimental BigInt type with first-class language support https://v8project.blogspot.com/2018/05/bigint.html
The announcement doesn't go too deep into implementation details, so it isn't clear whether they are using a tagged representation or not.

Don’t you need to do this for float/double as well then... analogous to BigInteger and BigDecimal in Java? Why does this need to be part of the language... could just copy those classes from the JDK, but sparse structs could be implemented to make them even more efficient.

@robaho IMO math.Log(x) is a natural operation to want to do for floating point numbers but not one that can be done with arbitrary precision. I.e. you won't get around the need to have a fixed precision "natural" floating point type.

No reason why you can't have math.Log(x, prec) to compute a log to specified precision using arbitrary precision values.

For that operation, yes. That's the point. A single operation being limited precision doesn't mean you have to cripple your data type to support it.

You'll have to "cripple your data type", as some numbers cannot be
represented with rational numbers or with finite number of digits / bits.
(Pi, 1/3, √2)
mathew<EMAIL_ADDRESS>ezt írta (időpont: 2018. aug. 16., Cs,
16:07):

For that operation, yes. That's the point. A single operation being
limited precision doesn't mean you have to cripple your data type to
support it.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/19623#issuecomment-413557329, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AAPoSu2ApCNArOT1HPhyVevuA76pZAllks5uRXydgaJpZM4Mi7Wo
.

By that argument, since we can't represent pi exactly as a BigDecimal, we should remove BigDecimal from the language and only have floats.
That's a silly argument against BigDecimal.

Let's please move the discussion about arbitrary size floating point types to a different issue.  This issue is about changing int to be an arbitrary sized integer type.  In particular note that the language has no float type.  Thanks.

@ianlancetaylor sorry, wasn't trying to hijack/confuse. I was only only trying to point out that why not have double and double64 then, with double being arbitrary sized. just seems wrong special casing it for int (rather than just using a BigInteger class). I would think operator overloading would be cleaner and more useful (although not a big fan of most uses of operator overloading...), but that is another can of worms

What would happen to big.Int if this gets accepted?

@TuomLarsen It's implementation would become trivial.  If we ever do a math/big/v2, it might be removed.

This issue was a concern about big in early Go days but the pool management
scheme suggests a new try is in order.
On Thu, Nov 29, 2018 at 3:30 PM TuomLarsen<EMAIL_ADDRESS>wrote:

@ianlancetaylor https://github.com/ianlancetaylor On the other hand, it
seems to me that one of the advantages of big.Int is that is provides
greater control for managing memory. What would be the equivalent of
Int.Set? Does = do deep or shallow copy? I'm asking because perhaps "dest
← op1, op2" of big.Int is more flexible but its functionality would overlap
somewhat with this proposal.
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/19623#issuecomment-443032772, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AHgypRSYph7CMslf5mAV9v4W_yWV_4egks5u0G4BgaJpZM4Mi7Wo
.

--
Michael T<EMAIL_ADDRESS><EMAIL_ADDRESS>

Upon reflection, I think this change would break to far from the languages C/system heritage. Better handled in libraries IMO.

maximum size of a byte slice is only half the address space on a 32-bit machine

Er, no, it's only 1/4294967296 of the address space.

@TuomLarsen I'd expect it'd work just like with strings today. Both strings and ints are immutable, so = would do a shallow copy, but all operations (+, +=, etc) would make a new instance by default. Of course, compiler would optimize cases where it's unnecessary to make a new instance and instead rewrite an old one.

@TuomLarsen It's implementation would become trivial. If we ever do a math/big/v2, it might be removed. https://github.com/golang/go/issues/19623#issuecomment-443023550

What is the interplay between this proposal and #20654 math/big: support for constant-time arithmetic?

@nathany  #20654 is about specialized large integer arithmetic where operations (such as +, *, etc.) always take the "same" amount of time independent of the input values. For instance, if huge represents a large integer value, huge + huge must take the same time as huge + 0 (even though in the latter the algorithm might be able to tell right away that there's nothing to do because one argument is 0). Making such operations' runtime independent of the arguments makes it impossible to "guess" arguments based on runtime. When such guessing is possible, this "side channel" (the timing of operations) becomes a valuable data source for crypto hackers.
There's no need for such constant-time operations in the language implementation. Just the opposite is true: we don't want constant-time operations because this proposal assumes that we can do all kinds of tricks to avoid the cost of a large integer operation: Most integers will be small, and in those cases the costs of operations should be close to what they are now (and inlined in the generated code).
I see #20654 as a proposal for a specialized library, built from the ground up (and tested as such) for crypto. I think it would be very hard to retro-fit big/int to support both (optimized and constant-time operations) and be sure to get it right in all cases.

i'd like to distinguish between two things that i think would both be useful:

an integer type which can be of arbitrary size.
the ability to declare arbitrarily-sized integer types.

i think these are both useful, and fill different needs. i have more than once wanted the ability to declare int128 or int256 objects and have them Just Work -- and that's much simpler than arbitrary-precision ints. and it might allow better performance, and work for many cases, but not solve some of the other cases.
both? both is good.

maybe allow every intxx/uintxx where xx has some constraints to it so the compiler can still generate code for it without needing a per-type implementation.

I've found myself often needing to do a single operation that overflows int64, and then immediately after, another that brings it back into the scope of int64, and I see this as being a reasonably common use case. I think operations such as
var int64 x,y, z
bigint(x) * bigint(y) % bigint(z)

could be optimised more than blindly converting to a big int, performing an operation, and then converting to int64 again. In this case, it can be assured at compile time that x*y will not overflow 128bits, and an algorithm using an upper and lower 64bit integer could be used. I really like this idea, but would hate to see operations that just slightly overflow int64 reduced to the speed of typical big ints.

Stewart, your statement is a common truth from the FORTH language. There,
in early days with 16-bit integer stacks, it was often desirable and
sufficient to compute scales and rotations as:
z := pop()
y := pop()
x := pop()
t := int32(int32(x)*int32(y))
t /= int32(x)
push int16(t)
This is so very useful that it has had an operator from day one "*/"
("Star-Slash") and most memorably, a character (human personification) in
the panoply of Forth, Inc. gods. Star-Slash is a Japanese ninja, with
katana at hand:
[image: image.png]
He does the big multiply, then, using his sword, chops the giant number
back down to normal size:
[image: image.png]
Star-Slash has a friend, Star-Slash-Mod, who leaves the chopped off part on
the stack. Read all about it here:
https://www.forth.com/starting-forth/5-fixed-point-arithmetic/
Now in Go we have this:
var x,y,z uint64
:
hi,lo := bits.Mul64(x, y)
quo,rem := bits.Div64(hi, lo, z)
// quo is Star-Slash
// quo,rem is Star-Slash-Mod
Is this two-step, four variable solution enough for you, or do you want it
to be as clean as in Forth?
func StarSlash(x,y,z uint64) uint64{
hi,lo := bits.Mul64(x, y)
quo,_:= bits.Div64(hi, lo, z)
return quo
}
func StarSlashMod(x,y,z uint64) (uint64,uint64) {
hi,lo := bits.Mul64(x, y)
quo,rem := bits.Div64(hi, lo, z)
return quo,rem
}
Michael
On Sun, May 26, 2019 at 2:17 AM Stewart Borle<EMAIL_ADDRESS>wrote:

I've found myself often needing to do a single operation that overflows
int64, and then immediately after, another that brings it back into the
scope of int64, and I see this as being a reasonably common use case. I
think operations such as
var int64 x,y, z
bigint(x) * bigint(y) % bigint(z)
could be optimised more than blindly converting to a big int, performing
an operation, and then converting to int64 again. In this case, it can be
assured at compile time that x*y will not overflow 128bits, and an
algorithm using an upper and lower 64bit integer could be used. I really
like this idea, but would hate to see operations that just slightly
overflow int64 reduced to the speed of typical big ints.
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/19623?email_source=notifications&email_token=AB4DFJKK7LK4VP3REQHBVITPXJISZA5CNFSM4DELWWUKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODWIBR6I#issuecomment-495982841,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AB4DFJPMPVYB3ZHJJVVGHPDPXJISZANCNFSM4DELWWUA
.

--
Michael T<EMAIL_ADDRESS><EMAIL_ADDRESS>

My additional(?) two cents: if we are not going to break stdlib compatibility in Go 2, then one reason to go through with this proposal would vanish: the weird inconsistency between uses of int and int64 when dealing with containers and I/O. Rob brought up containers in the original post when talking about len, so let me add the I/O bit:
Most interfaces of package io return an int, while others return an int64. This means there are type conversions involved when you try to use, for instance, one of the former inside the implementation of one of the latter. Actual example in code I'm working on while writing this: using io.ReadFull and io.Writer.Write in an implementation of io.WriterTo.WriteTo. (I can remediate some of this by using a bytes.Buffer or bytes.Reader, though.)
As with the proposal on removing complex types from the language, I would have to again ask whether doing this in the compiler would improve performance compared to keeping things as a library, assuming that math/big.Int takes advantage of special arbitrary-precision-integer CPU instructions where available (Intel ADX is one such for x86, although I will always remember the MC68000's addx family of instructions instead).
If math/big.Int doesn't use these yet, I would encourage experimenting with seeing how much improvement we can get by using it within the standard library, as a proof of concept of whether this proposal is a good idea. (Of course, for compatibility reasons, actually doing this for real in the standard library is likely not going to happen.)

I still believe the advantages of this change are significant but I admit it's not going to happen.
Although I still think making int a real integer would be a valuable change to make, it's clearly not happening, certainly not as it needs to be to be successful, which is making it really the default integer type. People are terrified of the small but largely avoidable expense of doing it, and it's just not the direction the language is going.
Maybe in the next language.  Maybe real integers will happen in the next one.

Upvote here for the 😢 (crying) reaction to the @robpike's comment, since that reaction is not available by GitHub.

Is it good to use an alternative name intn (or some alike names) to represent the arbitrary precision int?

@go101 If it's not the default integer type, it loses almost all its merit.

I still believe the advantages of this change are significant but I admit it's not going to happen.
Although I still think making int a real integer would be a valuable change to make, it's clearly not happening, certainly not as it needs to be to be successful, which is making it really the default integer type. People are terrified of the modest but largely avoidable expense of doing it, and it's just not the direction the language is going.
Maybe in the next language.  Maybe real integers will happen in the next one.

Certainly let's not stop thinking of alternative solutions!

People are terrified of the modest but largely avoidable expense of doing it, and it's just not the direction the language is going.

Erlang has seemingly been just fine with arbitrarily sized ints for decades, I'm pretty sure the computers today can handle it. I'd also consider the time spend tracking down over/underflows to be a counterargument to its "expense".
The people I see who are paranoid of integer overflow typically end up using explicit (u)int64, which not only doesn't fully solve the problem, but in the best case means an unnecessary mess of casts, or at worst even more annoying problems like effectively writing uint foo [...] foo = 0 [...] int(foo-1) < len(bar). At this point if I see a uint being used for anything other than bit fields I immediately assume there's a problem somewhere else.
I dropped C halfway through reading the CERT C Secure Coding stuff. I shouldn't have to write dozens of guard statements, we automate things for a reason. I'd hate to have to write similar SafeAdd or IsSafeToAdd functions in Go, and I dislike wishfully assuming I'll just never overflow.
With the usecases Go fills, already having a runtime that does much more complex tasks, and its tagline being "an open source programming language that makes it easy to build simple, reliable, and efficient software", leaving pitfalls like these just feels disappointing.
My specific arguments you could say are covered by #31500, but I feel this is a more general solution. Although I would settle for the other if this continues to be deemed too 'drastic' of a change.
With parametric polymorphism landing, it seems like a time for reconsideration here, considering both their implications for the type system.

Time has only strengthened my belief that this is the right thing to do. It's not as expensive to do as the worrywarts believe, and compiler tech today is so good that many, probably most use of ints in loops would be optimized back to a machine word, with the same performance as today. Outside loops, the cost is irrelevant. (Computers are only slow when they loop; an axiom of computing often forgotten.)
Maybe this is the reason to do a Go version 2.

Wouldn’t it be easier to allow generics to support operators and use a modified BigInt ?

Easier for whom? The goal of this proposal is to make the default integer type  capable of storing arbitrarily large values, to avoid security and overflow issues (and secondarily make programming more fun). If you make funny type that isn't the default for things like array indexes, you've missed the idea altogether.

@robpike I completely support this. I think that while 32/64-bit, fixed-width integers are necessary and useful for many applications, using them as the basic integer type is a relic of the past. The true integers are unbounded and the default integer type should provide this experience.

@robpike, can you explain a bit how compilers will optimize ints into native machine words in loop indices? Does this behavior depend on the assumption that all real-world arrays have less than 2^64 entries?

@robpike, can you explain a bit how compilers will optimize ints into native machine words in loop indices? Does this behavior depend on the assumption that all real-world arrays have less than 2^64 entries?

... it also depends on the fact that programming languages with native support for compressed arrays are extremely rare.

Easier for whom? The goal of this proposal is to make the default integer type capable of storing arbitrarily large values, to avoid security and overflow issues (and secondarily make programming more fun). If you make a funny integer type that isn't the default for things like array indexes, you've missed the idea altogether.

I don't think it will be easier in the end. All systems today are "networked" - so they need to interoperate - if you deal with arbitrary ints as a standard type - all you will do is delay the cognitive and programming effort when converting to a type that is a "known size" for transfer/ipc/etc. You will need to check every conversion from int -> int64/uint32/etc to ensure it fits - and then if it doesn't?
Most people will end up using fixed size ints with "known" overflow properties to avoid this.

Most people will end up using fixed size ints with "known" overflow properties to avoid this.

Ideally, manually specifying an integer type should still be allowed for this usecase (bitfields would be great  too), with free casting/promotion to the arbitrary-precision int.
Overflow checks would be simpler too; CERT's "safe add" in C is
  signed int sum;
  if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
      ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
    /* Handle error */
  } else {
    sum = si_a + si_b;
  }

With an int64 that's been promoted to an arbitrary-precision int in Go, that'd just be a if foo >= math.MaxInt64 before knowing you could safely cast it back to a uint64 to send back over the wire.
I think the big package could be repurposed to a num package, with convenience funcs returning ({,u}int{8,16,32,64}, err) for casting the new int type back into more specific types.

@robpike, can you explain a bit how compilers will optimize ints into native machine words in loop indices? Does this behavior depend on the assumption that all real-world arrays have less than 2^64 entries?

Yes, it does, but Go already limits the size of arrays (and hence slices) to that of the local int type. The only change required there would be to specify that limit more precisely, which is not a bad thing on its own. The language spec could in effect define that array indexing fits in a machine word, or even less (2^48 for 64-bit machines, for example), and compilers could exploit that for performance. It is purely an optimization, not a semantic change at all.

Since there was already a move from 32 to 64, in theory there could be future moves to 128 or whatever that would still be within the Go 1 compatibility promise. Would any properly written code be broken by a move to arbitrarily large ints? It seems like the only broken code would be things that wrongly assumed 64 bits, no?

@robaho

All systems today are "networked" - so they need to interoperate - if you deal with arbitrary ints as a standard type - all you will do is delay the cognitive and programming effort when converting to a type that is a "known size" for transfer/ipc/etc. You will need to check every conversion from int -> int64/uint32/etc to ensure it fits - and then if it doesn't?

int already has an indeterminate size. So you already need to make this consideration. And fixed-width integers would not go away.
It is true that you could no longer convert to int64 and assume there is no overflow. But, oh well.

Most people will end up using fixed size ints with "known" overflow properties to avoid this.

I don't think there is any data to support this assertion. On the contrary - the fact that most people today use int without knowing its size - and how common it is for such code to not consider overflows at all - seems a good argument against that.
Personally, I very much think Go would be a better language with this change. I'm less sure it's worth the churn to introduce it now, though.

@carlmjohnson

Would any properly written code be broken by a move to arbitrarily large ints? It seems like the only broken code would be things that wrongly assumed 64 bits, no?

As the Go spec guarantees that an int has either 32 or 64 bits, such code is properly written.
But really, that's besides the point. Our consideration should be (and that's the spirit of the Go 1 compatibility promise) if and how much code would be broken by a change, not where we can put the blame for that breakage. The goal of the compatibility promise is to minimize frustration from broken code, not to be technically correct (even if it's the best kind).

@Merovius If your code breaks as a result of this change, then you must have been relying on the overflows (or is there another way to break code with this?). But you have been relying on overflows of a type that can be 32-bit or 64-bit long. So it does seem like you have a bug already. Thus I think that almost no code would break due to this. But I might be very wrong, of course.

@faiface

But you have been relying on overflows of a type that can be 32-bit or 64-bit long. So it does seem like you have a bug already.

No. An implication of "it is 32 or 64 bit" is that converting to 64 bit is always possible without overflow. I know that I certainly have written code based on this assumption. It's categorically not a bug to do so.

I don't think it will be easier in the end. All systems today are "networked" - so they need to interoperate - if you deal with arbitrary ints as a standard type - all you will do is delay the cognitive and programming effort when converting to a type that is a "known size" for transfer/ipc/etc.

This is already the case for anything handling JSON, since JSON numbers are defined by the spec to be of unlimited size. This proposed change would make JSON-handling code in Go more robust and easier to write.

And anything not using JSON harder. JSON is not ubiquitous in system to system protocols. Eg no support for arbitrary precision numbers in protobufs - and/or lack of standards in this area in general.

Go protocol buffers already use int64 and int32 explicitly.

Exactly. So code that uses int and casts to int64 for transmission may be broken if int becomes arbitrary precision.

It's already the case that code that blindly casts int to int32 might get a bad result if it doesn't range check, I don't see that making that the case for int64 as well is a big deal. Given that int128 is being requested in #9455, I think it makes sense to stop assuming int = int64.

If it is blindly casting to int32 - it is already a bug. If it is blindly casting and int to int64 for protobufs it is not a bug, since an int must be 32 or 64 bits.
So this is a badly breaking change. If you really want arbitrary precision ints, create a new type 'intx' for compatibility sake.

@robaho You are correct that making int arbitrary precision would be a breaking change. You are incorrect to say that it becomes harder to write correct code for these scenarios in a hypothetical Go 2, which has this change. That claim just doesn't hold any water - you already have to be careful when converting to and from int, because its size is not clearly determined. Code in that hypothetical future would just have to be differently careful.
IMO, if anything, any change in hardship for the encoding side will be compensated by an equal and opposite easing on the decoding side. Because, after all, you can just decode into an int without having to worry about overflows. And checking if a decoded integer did overflow is easier, as you now has arbitrary precision to work with, so you can just check if it's larger than your threshold.
@lpar I don't think we can, under the Go 1 compatibility guarantee, change the language guarantee that int is an alias for int32 or int64. It would be a breaking change and it would be far too hard to detect. Whether or not you want to rely on that fact is, for this discussion, academical.

Merovius has convinced me that good code can innocently write myInt64 := int64(myInt) with the expectation that it cannot overflow today, and it would be breaking to change that expectation. OTOH, if myInt can get so large that it overflows, there's already an undiagnosed overflow issue. The problem is just that we shift where the overflow occurs from some code using myInt to some code using myInt64, which might break assumptions somewhere. I think realistically, all this does is shift the bugs around instead of creating totally new bugs, but it's definitely a subtle change, which are the hardest to reason about.
Also unlike some other features, I don't see how this could be put behind a go.mod gatekeeper. If package A expects an int and package B expects an int, they have to agree on whether ints are 32, 64, or bigInts.
Maybe the play here would be to add bigint to the language today, and then announce the intention to change the definition of int to type int bigint at some unspecified point in 5 or 10 years. That would give people time to start writing myBigInt := bigint(myInt) now and then eventually have that become a noop when the actual change to the default is made.

I don't think we can, under the Go 1 compatibility guarantee, change the language guarantee that int is an alias for int32 or int64.

The entire proposal is for Go 2.

@carlmjohnson

OTOH, if myInt can get so large that it overflows, there's already an undiagnosed overflow issue.

That's not true. There is no "undiagnosed overflow issue" here or here or here, for example. All of these are perfectly reasonable code, which would become incorrect if int could suddenly take values outside the range of int64.
But that's academic. Even if there always was an undiagnosed overflow issue - as long as the code as it exists today does the right thing in all cases, we can't just change the language to make it do the wrong thing for some.
@lpar Apologies, I was under the impression you where trying to argue that it could be done within Go 1. My bad. I was responding to

I think it makes sense to stop assuming int = int64.

which I'm disagreeing with, as that's a fine assumption to make (I mean, not =, but ∈{int32,int64}).

FWIW, to clarify my position - in my opinion:

Go would be a better language if int/uint where be arbitrary precision integers.
I strongly believe we can't reasonably do that within Go 1 - it would be a fully breaking change, requiring Go 2.
I'm not convinced that it's worth doing that, but if it happened, it's not like I wouldn't immediately jump on board

While I am all for this change in Go 2, the proposal should specify full semantics. If possible specify/provide a linter/converter that catches/suggests how to fix/fixes breaking changes in Go 1 code. May be a similar tool can be used to assess the impact of such a change. It would also be necessary to somehow flag the required Go version in Go code.
In Go 1 the cases where the semantics differ are when you have an int operation the result of which falls outside the [-2^63..2^63) range and gets folded down to within this range. Any code that relies on this behavior is likely to be pretty tricky and perhaps can be be dealt with by converting the type to int64 (similarly uint64).
By full semantics I mean specifying what should happen for every legal int operation. For example, fmt.Printf("%x\n", ^int64(0) ) prints ffffffffffffffff. What happens when you have a arb. precision uint type and you do ^uint(0)? How do you represent this value or how do you output it? Whatever choices are made, such a spec shouldn't be difficult but would need to be done.

I don't see the value of changing the semantics of 'int' (32 or 64) to using a 'bigint' or 'intx' type? Why does Go need (or want) 'int' to be arbitrary over having an additional first class numeric type?
I think the current int is more reasonably understood to be 'the most performant/convenient' numeric type for indexing. As the OP states, people use the size types when a size is needed - but leaves out that most people use int because they don't care if it is 32 or 64 as both are reasonable/usable and it reads easier.
There is no value in making 'int' different. Use another type.

I think the current int is more reasonably understood to be 'the most performant/convenient' numeric type for indexing. As the OP states, people use the size types when a size is needed - but leaves out that most people use int because they don't care if it is 32 or 64 as both are reasonable/usable and it reads easier.

I don't think "they don't care" is the reason most people use int. Or at least, it isn't the reason I do. Rather, it's because len and cap are defined to (usually) return values of type int that ultimately makes it the most convenient type to use in many basic APIs, and those basic APIs in turn influence the entire ecosystem.

I felt that is what "the most performant/convenient' numeric type for indexing" conveyed...

I think the current int is more reasonably understood to be 'the most performant/convenient' numeric type for indexing.

It's also, very (IMO most) importantly, the default type of integer-literals.

but leaves out that most people use int because they don't care if it is 32 or 64 as both are reasonable/usable and it reads easier.

The problem that we're trying to solve by making int arbitrary precision is to stop people who don't care enough if if's 32 or 64 bit from shooting themselves in the foot. All the arguments you mention - like ease of readability or just wanting some integer-type without worrying about its size - are really just arguments to make the most accessible integer data type the one which has arbitrary precision. If you don't care if int has 32 or 64 bits of precision, then clearly having it have arbitrary precision works strictly better - because you have to care even less.
I agree with @robpike, that most of the benefit of this proposal comes from making all the builtin functions and a lot of the stdlib take/use big integers transparently. That alone is a reason not to make it a different type - we can't change io.Reader or io.WriterTo to return a bigint, for example, without breaking compatibility, though that would be one of the places where an arbitrary precision integer would be the right thing to use.

A suggestion for overflow when casting which I think it would be Go idiomatic and reasonable to follow a strategy like type assertion or map access where the casting "function" could return 1 or 2 values in a "magic" manner
foo := int64(1<<65) // 0

foo1, ok := int64(1<<65) // 0, false
foo2, ok := int64(1<<64) // 1<<64, false
foo3, ok := int64(1<<63) // 1<<63, true

foo4, ok := uint64(1<<64) // 1<<64, true

Won't fit all use cases like fooInt64(int64(1<<65)) so it's not perfect but offers a workaround to the issue.
Perhaps the arbitrary precision int proposal could be combined with linter warnings to mitigate cases like the one mentioned above.

@Goodwine That is approximately #6815.  This issue is a different one, and on this issue we should avoid getting distracted by considerations of how to best handle numeric overflow.  The point of this issue is to eliminate overflow entirely, so there is no need to handle it.  See also #30613, #31500.  Thanks.

I agree with @robpike, that most of the benefit of this proposal comes from making all the builtin functions and a lot of the stdlib take/use big integers transparently. That alone is a reason not to make it a different type - we can't change io.Reader or io.WriterTo to return a bigint, for example, without breaking compatibility, though that would be one of the places where an arbitrary precision integer would be the right thing to use.

But that brings yet another issue. Most of the libraries and layers above end up dealing with system calls - which aren't going to accept arbitrary ints. So either they will need casts everywhere, or the Go authors will need to create wrappers around all system calls to emulate the syscall accepting a very large int - a ton of work for no gain.

That is approximately #6815. This issue is a different one, and on this issue we should avoid getting distracted by considerations of how to best handle numeric overflow. The point of this issue is to eliminate overflow entirely, so there is no need to handle it. See also #30613, #31500. Thanks.
The issue still exists for casting to specific-precision, something that would be needed for speaking over some protocols, and so needs to be handled eventually.

While a separate issue, still a relevant one that I don't think is covered by at least those issues mentioned.
I see @Goodwine's suggestion more as a "cast time check", although it might be possible to reuse type assertions/switches for this. Semantically they might be different, but the purpose seems close enough to not require new functionality.
eg: an API reads some int64 value -> int64 promotes to int for processing -> val, ok := i.(int64) for checking before stuffing into your response data.

I see @Goodwine's suggestion more as a "cast time check", although it might be possible to reuse type assertions/switches for this.

Fair enough.
To date the comma-ok syntax has been used for conditions that can't be checked in ordinary code.  We don't really need a new comma-ok syntax for overflow checks; we can write functions that do it.  Unless I'm missing something.

But that brings yet another issue. Most of the libraries and layers above end up dealing with system calls - which aren't going to accept arbitrary ints. So either they will need casts everywhere, or the Go authors will need to create wrappers around all system calls to emulate the syscall accepting a very large int - a ton of work for no gain.

Typically those would be hardcoded static values, and often ones taken from the syscall package itself like syscall.O_EXCL, no?
If you're passing some arbitrary input to syscalls, I would assume it's already bad practice to not at least be sanitizing.

To date the comma-ok syntax has been used for conditions that can't be checked in ordinary code. We don't really need a new comma-ok syntax for overflow checks; we can write functions that do it. Unless I'm missing something.

Sure, this would already simplify the process of bounds checking from (what I knew as the right way) doing a quad-conditional if before every arethmatic operation, to a single if foo >= math.MaxInt64 && foo <= math.MinInt64 { //overflow } after all your other processing.
In my mind at least, having a val, ok := foo.(int64) seems a bit cleaner than a call to some func Int64(int) (n int64, ok bool) though, and you can have it panic by passing foo.(int64), rather than if !ok { panic("overflow!") }.
I'd settle for the convenience func if having some type-assertion-like syntax is deemed too much or too confusing, but something should be provided to encourage safety when breaking out of int.

Typically those would be hardcoded static values, and often ones taken from the syscall package itself like syscall.O_EXCL, no?
If you're passing some arbitrary input to syscalls, I would assume it's already bad practice to not at least be sanitizing.

That's not what I am referring to. If you look at io.go you see a mixture of int and int64 argument types. Most of these are passed through to system calls (file reads, etc.) These all need to be changed and overflow checked at a minimum. Whereas, right now an int can be assumed to be at most an int64.
This is a lot off work for no gain. I would like to see any research that says integer overflow (and addressing it like this) causes/fixes any significant amount of bugs - especially when most int will be effectively int64 in the very near future.

That's not what I am referring to. If you look at io.go you see a mixture of int and int64 argument types. Most of these are passed through to system calls (file reads, etc.) These all need to be changed and overflow checked at a minimum. Whereas, right now an int can be assumed to be at most an int64.

MaxUint64 bytes would already be 18446 Petabytes, so I mean, there's already a fair likelihood you can have problems there.
No computer can handle an infinite amount of anything, and that's not the point of this, but one of the benefits of arbitrary-precision ints is that they can make bounds checking much less of a headache, as discussed above, and bounds checking is already a problem that's cropped up in the standard library a few times, and has been an issue for decades in other languages.

This is a lot off work for no gain. I would like to see any research that says integer overflow (and addressing it like this) causes/fixes any significant amount of bugs - especially when most int will be effectively int64 in the very near future.

For reference, in an earlier comment I (somewhat rudely, sorry) called out 1dd24ca; several variants of this have existed in other parts of Go. There are also several sections in the SEI CERT C Coding Standard dedicated to integer precision/overflow bugs, where C and Go handle overflow similarly as bad (although C compilers have -ftrapv these days). MITRE dedicates CWE-190 to overflow/wrapping issues alone, with plenty of results when searching for "integer overflow" in their CVE tracker. Wikipedia's Examples section also lists a few interesting and notable cases.
For the most part, you're right, when you have to cast back to some specific-precision integer type, you may run into bugs; this is the same when casting from any larger to smaller type (I believe linters usually warn you about this already, even).
Ideally however, this should eliminate some cases of casting annoyance (something which go already seemed to be trying with int where possible, including len and cap despite the fact they can't go negative, unsigned wrapping being even more of a pitfall as it required different handling from signed wrapping) and we would have a standard method of checking bounds when casting, something which was previously clunky and footgun-prone, and so unintuitive where many even get the mitigation wrong. In addition, instead of living in ignorant bliss that "we'll probably not overflow" we can now take a perf hit when we get close (afaik modern implementations only get noticeably "slow" once you get a few bits close to max) rather than crash or open up a vulnerability.
In the best case, more awareness is raised for bounds checking (eg. you probably don't actually need to be able to read several petabytes of data), and more convenient and standard methods of doing so may prevent say, the next heartbleed.

I must not be explaining this clearly.
The current calls accept an 'int' - and it is limited to int64 by definition - with unlimited ints ALL of these calls need to be changed to either 1) some chunking to the low-level syscall 2) bounds check / cast and report an error (which would be a new error).

The current calls accept an 'int' - and it is limited to int64 by definition - with unlimited ints ALL of these calls need to be changed to either 1) some chunking to the low-level syscall 2) bounds check / cast and report an error (which would be a new error).

From what I can see browsing through the public functions in io, syscall, and os, it seems most things already either have platform abstractions, take a specific (eg. int64) type, or use uintptr.
So for the rest, more uintptr? Maybe an os.Int? Not an amazing solution, but either way inputs should be checked and even os.Exit kinda just leaves it up to you: "For portability, the status code should be in the range [0, 125]." Casting at some bits of the lower levels feels unavoidable though.
I don't think Go doing some amount of "magic" would be too bad, but chunking is probably not one we need to worry about yet, since we're probably a bit far off from single files being larger than the amount of internet traffic generated by the US per day (although, Google...)
Also, aren't int, long, etc. only specified to have lower-bounds specifically for future-proofing? There's already small movement for 128-bit machine support in Linux, but I wouldn't be surprised if in 5-10 years we see 128-bit computers start to become common.

@robaho

But that brings yet another issue. Most of the libraries and layers above end up dealing with system calls - which aren't going to accept arbitrary ints. So either they will need casts everywhere, or the Go authors will need to create wrappers around all system calls to emulate the syscall accepting a very large int - a ton of work for no gain.

You are correct that there is some work here. Note that all the io function you are concerned about already have to contain significant logic around them, to handle asynchronicity and interrupts and the like. I don't think it's untenable to add a little more, especially if it happens at a relatively low level (so the logic can be shared). FWIW I think the correct thing would be to chunk, for Write (which already needs to contain retry-logic to guarantee its argument has been fully written) and truncate the argument slice for Read (which is already not guaranteed to fill the complete slice). Both of these seems pretty simple logic.
You are incorrect to assert that there is "no gain". The gains have been discussed above quite a bit and it's not helpful for the discussion to just deny that happened.

The current calls accept an 'int' - and it is limited to int64 by definition - with unlimited ints ALL of these calls need to be changed to either 1) some chunking to the low-level syscall 2) bounds check / cast and report an error (which would be a new error).

Or just change them to take an int64, since this is a Go2 proposal and breaking changes are permitted?

That would work - but I think that if those are the sort of lookarge-scale  breaking changes that would be acceptable in Go2 it will be DOA.

If we make this change then I would suggest that at the same time we make explicit conversions from int to other numeric types panic on overflow.  (It's easy enough to write code to avoid the overflow and panic for code that explicitly wants to truncate or saturate or whatever.)

If we make this change then I would suggest that at the same time we make explicit conversions from int to other numeric types panic on overflow.

var x auint = foo         // Arbitrary-precision unsigned integer
y := uint64(x)            // Potential loss of meaningful bits of information (panic?)
z := x & math.MaxUint64   // Same: Potential loss of meaningful bits of information (panic?)

Line "y" is semantically equivalent to line "z". Why would the runtime be checking for loss of information in case "y" and not be checking for loss of exactly the same information in case "z"?

@atomsymbol Because people casually write conversions between numeric types in order to call functions that take a different type, but they don't casually write & math.MaxUint64.

@atomsymbol Because people casually write conversions between numeric types in order to call functions that take a different type, but they don't casually write & math.MaxUint64.

I disagree with such an approach, but it gave me a cool idea of how to look at the design of a programming language. Thanks.

@atomsymbol

Line "y" is semantically equivalent to line "z".

FTR, it's not. The type of y is uint64, while the type of z is auint, so there is absolutely no reason for that to panic, as there's no overflow, this is a normal bitwise operation on an integer type. To become semantically equivalent, you'd have to do z := uint64(x & math.MaxUint64), which wouldn't panic, as there's no overflow - which makes sense and gives a pretty clear way to do a truncating conversion.

@atomsymbol

Line "y" is semantically equivalent to line "z".

FTR, it's not. The type of y is uint64, while the type of z is auint, so there is absolutely no reason for that to panic, as there's no overflow, this is a normal bitwise operation on an integer type. To become semantically equivalent, you'd have to do z := uint64(x & math.MaxUint64), which wouldn't panic, as there's no overflow - which makes sense and gives a pretty clear way to do a truncating conversion.

The part "FTR, isn't not" is invalid because you can convert "y" to auint using a new 4th line "y1 := auint(y)" which would make "y1" indistinguishable from "z". After the 4th line, you can scrap/forget "y" and use just "y1" and "z" from now on. Assuming that uint64+const is modulo 2**64, a subsequent expression like "y+5" would of course need to be replaced by its equivalent: "(y1+5) % (1 << 64)".
Two semantically equivalent source codes are allowed to use different syntaxes.
Or, instead of the above, on the 4th line you could write the following:
if random_boolean_value { y, z = uint64(z), y }   // Swap y and z

and the program will behave the same irrespective of whether random_boolean_value is true or false.
If you still want to persuade me that "y" and "z" aren't semantically equivalent, please post a more elaborate argument.

[edit] To be clear, by the logic "there is potential loss of information", every bitwise & and | with a value that is not ^T(0) or T(0) respectively (i.e. which is a NOP) leads to "potential loss of information".

What should math.MaxInt change to if this proposal is adopted?

@atomsymbol

you can convert "y" to auint using a new 4th line "y1 := auint(y)" which would make "y1" indistinguishable from "z".

T1(T2(x)) is not, in general, the same as T1(x) and that's okay. The interesting part is the original conversion to uint64 - what you do with the converted result is uninteresting for the discussion.

Two semantically equivalent source codes are allowed to use different syntaxes.

Of course they are. But your expectation that these two things are semantically equivalent does not seem natural to me. Binary & does not change the type and is meant to truncate the result. A conversion does change the type. There is no reason to assume that they should be equivalent.
If nothing else, all you observed is that under the proposed change, these two things would not be semantically equivalent, as one panics and one doesn't. And what's been demonstrated is that there is a cohesive way to explain that semantic difference - one is a conversion, which changes the type, the other is not.
@go101
Presumably it would go away again. As this would be a breaking change, that'd be fine.

2. I strongly believe we can't reasonably do that within Go 1 - it would be a fully breaking change, requiring Go 2.

@Merovius can you elaborate? In particular, it's not clear to me that this change can't be done on a per-module basis gated on the go language directive in go.mod, making the change backwards compatible. For mixing packages with different ints, I imagine call wrappers such as the ones for ABI0/ABI1 transitions.

@eliasnaur I am not clever enough to judge if that works. But I feel the semantic change is large enough and it seems hard enough (near impossible) to auto-detect/-fix, that I at least wouldn't feel comfortable making it in a minor release. I also think it should come with a bunch of library-changes. For example, I'd argue that io.ReaderFrom/WriterTo currently return an int64 because that's the largest integer type and they should instead return int.
But, sure, I'm fine re-stating that as "I feel very strongly that we shouldn't do that within Go 1".

If we make this change then I would suggest that at the same time we make explicit conversions from int to other numeric types panic on overflow.

var x auint = foo         // Arbitrary-precision unsigned integer
y := uint64(x)            // Potential loss of meaningful bits of information (panic?)
z := x & math.MaxUint64   // Same: Potential loss of meaningful bits of information (panic?)

Line "y" is semantically equivalent to line "z". Why would the runtime be checking for loss of information in case "y" and not be checking for loss of exactly the same information in case "z"?

If we do this, we might as well also panic on precision loss of division. This is an operation on the number made to 0 certain bits, its the whole point of the operation. If we panic on bitmasks we might as well remove the operation since it will be useless.

@go101, presumably math.MaxInt would be removed (or would have to be defined as a type other than int) if this proposal is adopted.

What should math.MaxInt change to if this proposal is adopted?

presumably math.MaxInt would be removed

I think for legacy purposes, it would be good to keep, as the value is determined by the machine's native bit width. For other purposes, I think that changing it to a function / lookup would be preferable. Eg. math.MaxInt(32) would return<PHONE_NUMBER>, and so on.

@Bjohnson131

math.MaxInt(32) would return<PHONE_NUMBER>, and so on.

Wouldn't that just be a bitshift, though? The function would be directly equivalent to just (1 << (n - 1)) - 1, wouldn't it?

@Bjohnson131

math.MaxInt(32) would return<PHONE_NUMBER>, and so on.

Wouldn't that just be a bitshift and a subtraction, though? The function would be directly equivalent to just (1 << (n - 1)) - 1, wouldn't it?

Yep! Just like now!

Except that right now it's a constant, so the calculation is done entirely at compile-time, but a function with an argument, though it could probably easily be inlined, would still require a runtime calculation. I can see the readability benefit, but other than that I don't see any particular reason to not just write that calculation manually when you need it.

Except that right now it's a constant, so the calculation is done entirely at compile-time, but a function with an argument, though it could probably easily be inlined, would still require a runtime calculation.
I can see the readability benefit, but other than that I don't see any particular reason to not just write that calculation manually when you need it.

We're kinda out into the weeds now, but It would ideally be a lookup table for integers that are powers of 2. Maybe instead of passing in an int, we pass in a type.

@Bjohnson131 What would the use-case be of that? Note that if you want to "just have a register-sized integer", int would serve you ~always just fine. That is, if your computation fits into an intN, where N is the register size, it will almost always take up just a machine word in an arbitrary precision int as well. IMO needing to know these limits would be sufficiently rare not to warrant a constant in the stdlib (currently it's useful for overflow checks, but that use becomes obsolete with this proposal).
Either way, calling such a constant MinInt/MaxInt would be a very confusing misnomer.
As for your function idea: We already have constants for those use-cases. Those wouldn't go away, as they apply to sized types, which would stay.

Using an int for a register sized int will be extremely inefficient. You need to use int32 int64.

On Jan 21, 2022, at 12:26 PM, Axel Wagner @.***> wrote:

@Bjohnson131 What would the use-case be of that? Note that if you want to "just have a register-sized integer", int would serve you ~always just fine. That is, if your computation fits into an intN, where N is the register size, it will almost always take up just a machine word in an arbitrary precision int as well. IMO needing to know these limits would be sufficiently rare not to warrant a constant in the stdlib (currently it's useful for overflow checks, but that use becomes obsolete with this proposal).
Either way, calling such a constant MinInt/MaxInt would be a very confusing misnomer.
As for your function idea: We already have constants for those use-cases. Those wouldn't go away, as they apply to sized types, which would stay.
—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications on the go with GitHub Mobile for iOS or Android.
You are receiving this because you were mentioned.

@robaho At this point, any claims about the actual performance of this proposal are purely speculative. Its proponents speculate that we can effectively eliminate the cost. You speculate that we won't be able to. Without an actual implementation and real benchmarks, both are just guesses (informed guesses, perhaps, but guesses nonetheless).
However, I believe it should be clear that if the cost do turn out to be prohibitive, we won't actually do this anyway. So for the sake of this discussion, the most productive thing to do, seems to be to assume that it won't be and focus on the semantic and usage implications of the proposal. Because if that assumption turns out to be wrong, we can always walk back the decision once we have the data.

I was not making the claim that the costs would be prohibitive. It is impossible to implement this without additional costs over a sized int if you only need a sized int - because it is impossible to determine what the int may hold ahead of time - so the implementation must use some sort of checking of the value.
If you can see a way that these checks won’t need to happen I’d be really interested to know what you are thinking.

On Jan 21, 2022, at 4:05 PM, Axel Wagner @.***> wrote:

@robaho At this point, any claims about the actual performance of this proposal are purely speculative. Its proponents speculate that we can effectively eliminate the cost. You speculate that we won't be able to. Without an actual implementation and real benchmarks, both are just guesses (informed guesses, perhaps, but guesses nonetheless).
However, I believe it should be clear that if the cost do turn out to be prohibitive, we won't actually do this anyway. So for the sake of this discussion, the most productive thing to do, seems to be to assume that it won't be and focus on the semantic and usage implications of the proposal. Because if that assumption turns out to be wrong, we can always walk back the decision once we have the data.
—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications on the go with GitHub Mobile for iOS or Android.
You are receiving this because you were mentioned.

To clarify, I’d like to understand how the compiler could ever compile a function that takes an int parameter and have the same performance profile as one that takes an int64 parameter. I am pretty sure it is not possible - because it is impossible to know all possible values of the parameter at compile time.

On Jan 21, 2022, at 4:25 PM, Robert Engels @.***> wrote:

I was not making the claim that the costs would be prohibitive. It is impossible to implement this without additional costs over a sized int if you only need a sized int - because it is impossible to determine what the int may hold ahead of time - so the implementation must use some sort of checking of the value.
If you can see a way that these checks won’t need to happen I’d be really interested to know what you are thinking.

On Jan 21, 2022, at 4:05 PM, Axel Wagner @.***> wrote:

@robaho At this point, any claims about the actual performance of this proposal are purely speculative. Its proponents speculate that we can effectively eliminate the cost. You speculate that we won't be able to. Without an actual implementation and real benchmarks, both are just guesses (informed guesses, perhaps, but guesses nonetheless).
However, I believe it should be clear that if the cost do turn out to be prohibitive, we won't actually do this anyway. So for the sake of this discussion, the most productive thing to do, seems to be to assume that it won't be and focus on the semantic and usage implications of the proposal. Because if that assumption turns out to be wrong, we can always walk back the decision once we have the data.
—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications on the go with GitHub Mobile for iOS or Android.
You are receiving this because you were mentioned.

There are a number of compilation strategies that we could employ in principle.  For example, one would be to compile two versions of most functions: one compiled to take a bigint and one compiled to take a int64.  Any time we know that the value fits in int64 (e.g., because we got the value as a range index, or from a call to len, or because we can apply some loop analysis, etc.) then we call the int64 version.
A reverse approach is to observe that if the function ever uses the integer parameter as a slice or array index, then the value must fit in int64.  Then we can add an initial overflow check, and compile the rest of the function using int64.
Of course these kinds of heuristics can't handle all cases.  The question is whether they can handle enough of the cases where performance matters.

Agreed, but you can’t even determine at compile time if the function itself might use more than 64 bits so there needs to be additional checks within the function.

On Jan 21, 2022, at 5:06 PM, Ian Lance Taylor @.***> wrote:

There are a number of compilation strategies that we could employ in principle. For example, one would be to compile two versions of most functions: one compiled to take a bigint and one compiled to take a int64. Any time we know that the value fits in int64 (e.g., because we got the value as a range index, or from a call to len, or because we can apply some loop analysis, etc.) then we call the int64 version.
A reverse approach is to observe that if the function ever uses the integer parameter as a slice or array index, then the value must fit in int64. Then we can add an initial overflow check, and compile the rest of the function using int64.
Of course these kinds of heuristics can't handle all cases. The question is whether they can handle enough of the cases where performance matters.
—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications on the go with GitHub Mobile for iOS or Android.
You are receiving this because you were mentioned.

Sometimes those overflow checks will be required, and sometimes the compiler will be able to prove that they are not required.  It's a exercise in value range propagation, which is a standard compiler analysis.  Sometimes it will be able to eliminate overflow checks, sometimes it won't.  What matters is how often it works in performance sensitive code.  At this point we don't know the answer to that.

@robaho
https://github.com/golang/go/issues/19623#issuecomment-287930352 near the beginning of the issue explains a possible implementation strategy. The cost is not zero, but as @Merovius explained, it may or may not be close enough to zero for practical purposes. Saying it might be expensive is repeating something we already know. Moreover, saying it "will be extremely inefficient" is something no one has proven.

I think the complex - yet common - case is going to be the function that has 'int' parameters or an 'int' result that calls out to other functions. The chain of complexity in determining where a bounded int could be used instead of unbounded one will cause any optimizations to be futile except in the most trivial cases (e.g. an 'int' used as a loop counter).
This is not typical 'range value propagation' because by definition an 'int' will be unbounded so it has infinite range so many of the techniques in this space cannot be applied, furthermore, vrp is designed mainly for static analysis which does not help in the above cited general case.
A decent summary:

Value Range Propagation
The idea behind this is simple. For each expression, a maximum and minimum value it can have is computed statically (during compilation). When exact values are not possible, a conservative estimate is computed. When it comes time for an implicit conversion, if the max and min value can fit in the converted type, then no complaint is issued. If not, a cast is still necessary.

This is not going to help in the common case cited above.

I think the complex - yet common - case is going to be the function that has 'int' parameters or an 'int' result that calls out to other functions. The chain of complexity in determining where a bounded int could be used instead of unbounded one will cause any optimizations to be futile except in the most trivial cases (e.g. an 'int' used as a loop counter).

If that was actually what is happening then most computations performed by apps in C/C++ would already be needing arbitrary precision integers. The fact/evidence is: most apps work fine with just 32-bit or 64-bit integers and the 32/64-bit limits are rarely exceeded. The chain of complexity is much smaller than what is being suggested above, optimizations aren't futile and are applicable to complex cases.

They work fine because that is the only option - and the compiler knows that. So the worst case scenario is a default platform int size which is 32/64 bits. With arbitrary sized ints there is no maximum - so the int receiver/return value must support an arbitrary sized int for a generalized function. As Ian points out - you could compile two different functions - but this quickly breaks down when the function calls another - you would have two functions for every in the chain AND need to ensure that at every step the bounds were not exceeded - which becomes extremely difficult if not impossible.
This can be "efficiently" implemented using a flag bit, but as I pointed out, you will need a mask and branch at a minimum (with unbounded or unable to determine to also require slow path function calls). This will be the default except for the trivial locally bounded case (loop index).
Consider an arbitrary function call that multiplies two 'int's. It cannot possibly know that every call will always pass two 'ints' that when multiplied will fit in a return int64 value (e.g. the input comes from a file). Even compiling two function calls won't work, because the calling code would need additional checks to understand that the called function might overflow so to call the other.

as another data point, you can look at BigInteger in Java. It uses a highly efficient storage (typically a native int), and even with Java's dynamic inlining and intrinsics - it is still orders of magnitude slower than using a native int (the object overhead can be factored out by comparing int/Integer).
You can compare ints/bigint in Go because most cases outside of loop indexes are going to degenerate and force the use of bigint. I think that is a bad tradeoff for having developers use a bigint when they need "big ints".
Most likely what everyone will end up doing is using int64 for everything - so all you will have done is changed the names and added verbosity...

@robaho

The chain of complexity in determining where a bounded int could be used instead of unbounded one will cause any optimizations to be futile except in the most trivial cases (e.g. an 'int' used as a loop counter).

This has been mentioned. In particular, the thesis is that this is not "the most trivial case", but the only important one.
Again, I would like to urge you to stop speculating on the performance of this, until we have actual data to talk about. If the performance impact turns out to be prohibitive, we won't do it. The argument should thus be assumed under consideration.

Most likely what everyone will end up doing is using int64 for everything

Do you have any evidence to support that? Because I believe we have pretty strong evidence that it won't be the case, by analogy to slice bounds-checking.
Bounds-checks can be eliminated using various techniques. You can a) do things like _ = a[42] at the top of your function, to consolidate them into a single check, or b) use unsafe.Pointer and arithmetic to avoid them altogether, or c) use -B when compiling, to have the compiler not emit them. Yet, in actual practice, we don't commonly see any of these techniques applied. The first two are used occasionally, in performance-sensitive code, but even there, they tend to be carefully applied not to leak out of the API boundary of the respective package. You just don't see code which accepts a struct{ p unsafe.Pointer; n int } instead of a slice.
This analogy is apt, because bounds-checks elimination and this proposal would use very similar optimization techniques and have very similar overhead in practice. It stands to reason, that people will react similarly to their cost.
Again, for the actual performance impact, we'd have to look at an actual implementation first. But I believe the evidence is thin, that Go programmers tend to work around language safeguards en-masse to avoid their performance impact.

That could very well be true. My Go exposure is in the systems and financial spaces and I think (right or wrong) the tendency is to optimize early (prematurely?).
I agree that the problem is similar to bounds checks - but the compiler is already pretty good at eliminating those - because they are local. The complexity of this change is going to occur at the call site - and my hunch (just a) is that this is going to prove to be very difficult to statically optimize - leading to a function that always needs type checks and conversions.

On Jan 27, 2022, at 12:25 AM, Axel Wagner @.***> wrote:

Most likely what everyone will end up doing is using int64 for everything
Do you have any evidence to support that? Because I believe we have pretty strong evidence that it won't be the case, by analogy to slice bounds-checking.
Bounds-checks can be eliminated using various techniques. You can a) do things like _ = a[42] at the top of your function, to consolidate them into a single check, or b) use unsafe.Pointer and arithmetic to avoid them altogether, or c) use -B when compiling, to have the compiler not emit them. Yet, in actual practice, we don't commonly see any of these techniques applied. The first two are used occasionally, in performance-sensitive code, but even there, they tend to be carefully applied not to leak out of the API boundary of the respective package. You just don't see code which accepts a struct{ p unsafe.Pointer; n int } instead of a slice.
This analogy is apt, because bounds-checks elimination and this proposal would use very similar optimization techniques and have very similar overhead in practice. It stands to reason, that people will react similarly to their cost.
Again, for the actual performance impact, we'd have to look at an actual implementation first. But I believe the evidence is thin, that Go programmers tend to work around language safeguards en-masse to avoid their performance impact.
—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications on the go with GitHub Mobile for iOS or Android.
You are receiving this because you were mentioned.

What would the memory layout of []int under this proposal?
I guess we have to think of the memory layout of []int as similar to that of []string?
I also second with @ianlancetaylor comment that this proposal should go with the idea that overflows result in panics https://github.com/golang/go/issues/19623#issuecomment-1005166291
I would also add that this proposal also removes bit shifts syntax altogether, people should simply write i * 2 instead of salads of < and >.
Another optimization this proposal would enable is to rearrange multiplications and divisions, so that multiplications always come before divisions.
Coming from a physics background, fixed size ints, bitwise syntax, and endianess has been the three most rediculous nonsense in programming. Imagine how much readable this line would be with this proposal https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/image/draw/draw.go;l=290
I also suggest that image processing to to be a great place to stress test performance issues of this proposal.
There are lots of ints and lots of types of ints in image processing, and as @robpike said, computers are slow only when there are loops, and in image processing there are lots of large loops.

I also suggest that image processing to to be a great place to stress test performance issues of this proposal. There are lots of ints and lots of types of ints in image processing, and as @robpike said, computers are slow only when there are loops, and in image processing there are lots of large loops.

What do you mean by "computers are slow only when there are loops"? CPUs in the near future will be able to process multiple iterations of a small loop in parallel in a single clock cycle, which is a natural consequence of the CPU being able to predict&execute multiple branch instructions per clock cycle and being able to execute multiple load-store instructions per cycle.

I guess we have to think of the memory layout of []int as similar to that of []string?

Arguably. I think there is a difference, in that a []string always contains "secondary indirections", unless the strings are empty, whereas []int will usually not have any and just be packed integers (unless there are very large ones). It's not strictly a qualitative difference - in both cases the layout is "a packed array which might contain pointers to more data" - but it's enough of a quantitative difference to make it a qualitative one.

I would also add that this proposal also removes bit shifts syntax altogether, people should simply write i * 2 instead of salads of < and >.

I find bit-shift syntax significantly easier to understand, if that's what you want. That is, I find a << 10 significantly easier to read than a * 1024. So, I disagree that bit-shifting (and other bitwise operators) should be disallowed for an arbitrary precision integer.

@atomsymbol Without a loop, a computer will terminate fast. It takes a loop to slow it down. Asserting that a slow program must have a loop, as I have said many times, is not the same as saying a loop cannot be fast.

If a new language doesn't make my development easier, I don't need to change languages at all. Therefore, I support boosting int to arbitrary precision.

I am 100% for this proposal. Worrying about the performance impact of arbitrary precision ints is like worrying about the performance impact of array bounds checks, in my opinion. It's negligible if implemented correctly.
I also like this because of how inconvenient the big package is and how I always fall back to Python when I'm dealing with big integers.

If a new language doesn't make my development easier, I don't need to change languages at all. Therefore, I support boosting int to arbitrary precision.

I propose that for Go 2 we make a profound change to the language and have int and uint be arbitrary precision.

If this proposal is implemented, would it be done in a way that existing packages would retain the existing behavior? If yes, is it known what that approach would be?
I assume that it wouldn't be possible to use the go.mod go directive approach (described in this talk by @rsc: https://youtu.be/v24wrd3RwGo) because the int values have to be passable between packages?
Or, would this be a change that could be applied to all programs without a compatibility feature gating access to it, because for all programs the int and unit types already have a flexible bit size depending on the machine?

Or, would this be a change that could be applied to all programs without a compatibility feature gating access to it, because for all programs the int and unit types already have a flexible bit size depending on the machine?

Given that math.MaxInt exists, I don't believe this argument holds. The precise size of int and uint might be implementation defined, but you can still rely on its overflow behavior in other ways. And that doesn't even mention build tags.

verygood

//Hand Error

func main() {

    f, err := os.Open("/test.txt") :e {
            fmt.Println( e )
    }

    f, err := os.Open("/test.txt") :e HandEorr( e )

    //or
    f, err := os.Open("/test.txt") e: {
        fmt.Println(e)
    }

    f, err := os.Open("/test.txt") e:

}

Re math.MaxInt: IMHO breaking compatibility in 2.0 for this would be worth the benefit. But if you must have it, given that an arb. precision ints would require a variable amount of space, I would use some bitpattern to mean +infinity (and similarly -infinity). They could even be the same bitpatterns as fl.pt. +/- infinity but of "type" int. :-)

Is this proposal still being considered? How does it play with the decision that there will be no Go2?

In order to be backwards compatible, it would require adding a new type (integer?). int cannot and will not change. I don't know whether it is still being seriously considered.

I strongly agree with your suggestion

very good

We can't change int to be arbitrary precision because backwards compatibility. But we could add a new type, which (imho) would be really useful.
Finding a name is hard, though. It should be short, memorable, etc. integer is too long. But but but but but. There's an obvious name for an Arbitrary precision Integer.
I give you: type ai.

FWIW, I believe this has been mentioned before, but adding u128/i128 and u256/i256, and maybe u512/i512 would satisfy 99% of what folks really want here.

Borrow from the Pascal/Modula world, and call it cardinal. Abbreviate to car. The only downside would be getting Lisp programmers' hopes up.

We could borrow from math/German and call it Zahlen, or Z for short. :P

This is a really interesting idea, but the change as proposed is very much an incompatible one: today, users can assume that x + y has finite fields semantics, with an implicit modulo operation, but if this proposal were implemented, any code that depends on that assumption would no longer work correctly.
More practical objections include:

cheap operations such as x+1 (a single CPU cycle today) become at the very least a (predictable) conditional branch, followed in the worst case by an allocation.
the ABI would be incompatibly changed and all assembly code would need to be audited and perhaps rewritten.
runtime contexts where allocation is prohibited would not be allowed to use int arithmetic.

Adding a new bigint built-in type would be a much more tractable problem, albeit less exciting.
Therefore this is a likely decline. Leaving open for a final four weeks for final comments.
@adonovan, for the language change review committee.

I don't fully agree with this assessment:

Any code relying on finite field semantics of int is likely incorrect because the size of an int is not fixed (it can be 32bit or 64bit). Code that relies on finite field semantics must use the sized types (int32, int64, etc.) for correct behavior across all platforms.
Cheap operations such as x+1 would become slightly more expensive. The only place where that really matters is in loops. For one, with Go's expanded range construct, typical for i := 0; i < n; i++ loops are not really needed anymore. Also, in many cases (and especially the before-mentioned case) the compiler can determine the bounds of such iteration variables and thus prove that they never exceed the efficient int range.
Assembly code operating with int/uint at the limits of the efficient int range should probably use sized ints. I note that the math/big assembly code works with sized integer types.
Likewise, runtime contexts where allocation is prohibited could use sized ints if the compiler cannot prove the limits of int ranges. I bet there's very few such places.

In short, I believe this change is possible; the primary unknown is the performance impact. That impact may be small with sufficient engineering effort.
The latter is perhaps the crux: we don't have the bandwidth/capacity for this engineering effort, so this may be our limiting factor.

Any code relying on finite field semantics of int is likely incorrect because the size of an int is not fixed (it can be 32bit or 64bit). Code that relies on finite field semantics must use the sized types (int32, int64, etc.) for correct behavior across all platforms.

The size of int may vary across architectures, but it's easy to know which size it is, and existing code may assume that the value is representable in a field of that size.

Cheap operations such as x+1 would become slightly more expensive. The only place where that really matters is in loops. For one, with Go's expanded range construct, typical for i := 0; i < n; i++ loops are not really needed anymore.

Any function may be called from inside the loop of another function (and perhaps inlined into it), so I don't really understand this argument. My point was that any arithmetic expression formerly as cheap as a single cycle now costs a conditional branch. The choice of looping construct is not important.

Assembly code operating with int/uint at the limits of the efficient int range should probably use sized ints.

I agree; still, it would require an audit and a clean-up of existing correct code.

Likewise, runtime contexts where allocation is prohibited could use sized ints if the compiler cannot prove the limits of int ranges.

Agreed; let's ignore this objection since the runtime is entirely within our control.

Had we but world enough and time, we could check some of these things empirically. Knowing the shape and frequency of the behavior and performance changes might provide clarity, even with a naive, relatively unoptimized implementation. We even have the GOEXPERIMENT mechanism to enable it.

The size of int may vary across architectures, but it's easy to know which size it is, and existing code may assume that the value is representable in a field of that size.

In particular, you can currently assume that int->int64 conversions don't lose precision. I use that all the time when encoding/decoding integer values.

As far as loop efficiency, independent of this proposal it would be good if you could declare the type of a loop index, like you can in other languages. e.g. in Java you can for (byte i=1; i<11; i++). That would allow efficient looping even if int was potentially expensive.

it would be good if you could declare the type of a loop index, like you can in other languages

You can achieve that desire by adding a type cast
package main

import "fmt"

func main() {
	var sum uint8 = 0
	for i := uint8(0); i < 10; i++ {
		sum += i
	}
	fmt.Println(sum)
}

Thanks, I don't think I've ever seen that done, though it's obvious in retrospect. (It would probably be worth mentioning in A Tour of Go or Effective Go.)
So that suggests that the possible loop performance issue doesn't have to be a deal-killer for this proposal.

Question- is this proposal for int to be as many bits as needed at run-time, or is it to add arbitrary length int types for any 2^n bit length, ie int128, int512, int1024, etc? I like one, and am not sure about the other.

This proposal is for the type int to represent any size of intege.
int128 is #9455.

Although there are reasons for making this change, it could break existing Go packages.  Any package that serializes an integer value, that takes an int and then converts to int64, would work reliably today but would fail silently for large values if we adopted this proposal.