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 heap 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 RAM, 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": 12312323123131231312312312312312321312313123123123123123123}

Would map to an int with value 12312323123131231312312312312312321312313123123123123123123.

What about something like encoding/gob or encoding/binary?

@shurcooL

1. printing is obvious (the usual human-readable forms) - applies to JSON
2. encoding/gob could use a private internal representation
3. 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/compiler with internal knowledge and cludges. Solve that problem with golang 2.0, or instead we will find ourselves years from now with countless ad hoc accretions like this.

Edit: I'm a fan of this design/feature in scripting languages. I don't see how it works as the base int type in a systems language to replace c/c++/java. I absolutely think we should have a great and convenient arbitrary precision number type, and think the road to that is a golang where library defined types are not second class to ad hoc boundary flaunting extensions of the runtime and compiler provided types.

@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 programs using 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. 😝
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.

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 don't think this is an unreasonable expectation of a language that markets itself as a replacement for c/c++/java for systems programming.

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 12345678901234567890.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 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.

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 common 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.

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 #19623 (comment)
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.

@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.

(1) Does an event-loop count? Each iteration of an event-loop might be computing something very different from other iterations of the event-loop.

(2) @robpike The slowest computations on any machine are searches through vast spaces. Some purely-recursive search algorithms do not contain any loops, not counting the CPU's own/internal fetchInstruction-loadInputs-executeInstruction-saveResults loop. Thus, the claim that "a slow program must [by necessity] have a loop" is false.

@atomsymbol ISTM that discussion is off-topic here. The statement "computers are only slow in loops" is certainly pithy, but I think we all understand what it means and the limits of its accuracy. It's not helpful to nitpick it here.

ISTM that discussion is off-topic here. The statement "computers are only slow in loops" is certainly pithy, but I think we all understand what it means and the limits of its accuracy. It's not helpful to nitpick it here.

@Merovius I believe in the existence of what I read with my own eyes. I don't believe in the existence of a hypothetical object indirectly mentioned in a text. In other words, if you truly knew "what it means" and understood "the limits of its accuracy" then you would have posted a formal math-like description of the meaning and of the limitations, or would have posted a link to such a description.

Sorry for being so direct/harsh.

I will try to avoid posting another message on the topic of the relationship between program slowness and loops, because this discussion is about arbitrary precision integers.

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 uint 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.

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.

“There will not be a Go 2 that breaks Go 1 programs.” — Backward Compatibility

How does this statement impact this proposal?

I assume that it wouldn't be possible to use the go.mod go directive approach - #19623 (comment)

I'm wondering the same in light of Go 1.21's new forward compatibility features.

A few people have suggested a distinct integer type (or bigint or some other name). This would alleviate any concerns over serialization, performance, or breaking existing programs -- but may require explicit conversion to/from int and uint.

For cases where arbitrary precision math is important, what @griesemer outlined with 2 reserved bits should be faster than the current big.Int in many cases. Correct me if I'm wrong?

If that is possible to build as a library, we would be one step closer to making this proposal a reality. The further step of providing a built-in type in the language would make arbitrary precision math more ergonomic for complex calculations. As a thought experiment, let's imagine we do that.

"An untyped constant has a default type which is the type to which the constant is implicitly converted in contexts where a typed value is required" - spec

Then, would it be possible, down the road, to modify the type inference to make bigint/integer the default type instead of int, but without changing the meaning of int and uint?

If that change was restricted to a module based on go.mod (e.g. go 1.24.0), what would that mean for compiling modules together? It seems to me that many function definitions would continue to explicitly use int, would could make adoption of bigint/integer as a default quite challenging.

If this is feasible, the transition could be done if/when we are satisfied with the performance of the bigint/integer implementation.

If it turned out to work really well, then perhaps we could even deprecate int and uint eventually, arriving with a very similar outcome to the original proposal (but without ever altering their meaning).

I'm sure there are things I haven't thought of, so I look forward to your thoughts.

@nathany

How does this statement impact this proposal?

It means it is extremely unlikely to happen. The value of the proposal only really becomes realized if we'd change how int works. But we can't do that, as it would be a redefinition, which we don't want to do.

If that is possible to build as a library, we would be one step closer to making this proposal a reality.

I don't think it is practical to build that as a library. It requires interaction with the garbage collector, which has to know which memory contains pointers and which doesn't. So, at the very least, the compiler has to "magically" recognize if you use that type and insert instrumentation for the GC. Given that you could then also do type MyBigInt bigint.Int, I'm not sure how that would work in practice.

Then, would it be possible, down the road, to modify the type inference to make bigint/integer the default type instead of int, but without changing the meaning of int and uint?

I don't think so. For example

func main() {
    for v := (1<<63)-1; v > 0; v++ {
    }
}

Currently (when int has 64 bits) this terminates, but if v was bigint, it would loop forever. Thus that change would be a redefinition, which is disallowed even with a go.mod guard.

If it turned out to work really well, then perhaps we could even deprecate int and uint eventually, arriving with a very similar outcome to the original proposal (but without ever altering their meaning).

I agree with @robpike that a lot (probably most) of the value comes from redefining what len returns as well. And what io.Reader.Read etc. return. I don't think just changing the default type of untyped integer literals really would be that similar to the original proposal in outcome.

Thanks @Merovius.

I think there may still be some value in arbitrary precision integers being first class as a separate type (e.g. bigint) with all the usual operators. Even if only for the ergonomics. But perhaps that is a different proposal.

If this proposal isn't feasible, here's hoping for checked integers. #30613