As discussed above, at least Span will need to support UInt, that means that the length stored in the Span needs to be UInt, that means len() needs to be able to return UInt.
There are use cases where you want to return the same type the user enter like doing enumerate(lst, start=BigInt(really big starting number)) would be nice to make it return BigInt, limiting it to Int would be less ergonomic as you would have to add it to the big number yourself every iteration.
I donât understand this - why? Are you concerned about embedded / 32-bit targets where youâre writing code against an array that is more than half the address space? If so, then the right balance (as discussed above) is to use other lower-level types for such a specialized use case.
It may be that this is the crux of the confusion in this thread. Please letâs make this a non-goal - any design that makes Span.len return a UInt isnât going to be acceptable.
I think Indexer should be extremely rare, e.g. on low level apis like unsafepointer to support the use-case above.
Keep in mind that aliases like Index are not free - these show up in the LSP and they impact compile time and error messages.
To reiterate, I donât consider this design point to be controversial. This is exactly what Swift used, it worked very well at scale, and I am not aware of a downside. Using a consolidated integer type as âthe default currency type unless you have a very specialized needâ worked out extremely well, and prevented casting back and forth. This is a major benefit over languages like Rust and today-Mojo. I would expect the same benefits to accrue to future-Mojo.
-Chris
Agree on 1, 3 with no comments.
To +1 Nickâs point,
len(x)-1returning some huge number or trapping is a pretty big non-starter for usability. Furthermore,lenneeds to work on theLenabletrait (or some other name, which is out of scope for this thread), so we need a consistent type across conforming collections. It needs to be signed.
On this point, I think that code which has overflow in this situation is likely going to be erroneous even with Int. If that len is being used for indexing, List()[-1] will raise a range error. Many other functions that you would want to pass a list length to, such as realloc (if resizing the list), donât have a reasonable behavior when handed -1.
What I see is the largest advantage of UInt for cases like this is that it lets the user turn on -fmake_my_code_slow_but_help_me_debug or whatever we decide to call it. The compiler canât automatically insert âdid this go negative?â checks after every subtraction of Int because there will be many places where that behavior is what the programmer wanted, but it can insert code to check for unsigned int overflow and underflow, made more efficient on x86 and ARM using hardware support (RISC-V gets asm version of the portable C code). We can do what Rust does and make overflow checks the default in optimized mode, meaning that the default behavior for Mojo is still wrapping, but leave debug mode as a place where you accept that code runs slow but the compiler will help you with debugging.
On 4 + 6, I think that having a type called Int may be the problem. We have generations of programmers trained to use that as the default data type for everything, even when itâs arguably not appropriate such as for a value between 0 and 100. Rust managed to completely avoid the the problems you are concerned about, and I think that not having an int type is how Rust did it. If we take the way Rust handles things, and then use requires to make safe, widening casts implicit (potentially non-sign changing to avoid ambiguity), we shouldnât have a lot of extra casts from devs using the datatype that fits the expected range of their data, devs can get help from the compiler in tracking down when those invariants are violated, and we can get rid of a lot of x >= 0 bounds checks in functions. The data showing datatype usage is my attempt to show that systems programmers are mostly using unsigned values where sizes are concerned, and that using Int for that will add friction to people who want to use the type system express invariants.
After reading more, I also have a new concern. Some code may simply stop working on 32 bit targets if the default integer type is not fixed-width (or decaying to fixed with, see below) or some form of arbitrary precision. Ex: var world_population = 8142000000 will compile on a 64 bit system but not a 32 bit one.
As pointed out above, Mojo already has a default integer type, it is
Int. Using things other than that will require casting, and that casting should have to pay for itself.
We could also make the default type something has both a materialized value and a parameter value, and will implicitly cast to any integer type which can represent it.
fn _value_fits_in_dtype[dtype: DType, value: IntLiteral]() -> Bool:
return Scalar[dtype].MIN <= value and Scalar[dtype].MAX >= value
fn _minimum_dtype_for_value[value: IntLiteral]() -> DType:
alias dtypes = [
DType._uint1, DType._uint2, DType._uint4, DType.uint8, DType.uint16, DType.uint32, DType.uint64, DType.uint128, DType.uint256,
DType.int8, DType.int16, DType.int32, DType.int64, DType.int128, DType.int256
]
@parameter
for dtype in dtypes:
if _value_fits_in_dtype[dtype, value]():
return dtype
constrained[UInt256.MAX >= value and Int256.MIN <= value, "Unpresentable value"]()
return DType.bool # make the compiler happy
struct MaterializedIntLiteral[value: IntLiteral]:
alias BackingType = _minimum_dtype_for_value[value]()
var backing: Scalar[Self.BackingType]
fn __init__(out self):
self.backing = value
fn into[dtype: DType](self) -> Scalar[dtype]: # Used in constructors for SIMD, UInt and Int that take MaterializedIntLiteral
constrained[_value_fits_in_dtype[dtype, value](), "Unable to safely cast to dtype"]()
return self.backing.cast[dtype]()
I think that having a type like this, which acts as an IntLiteral that is not arbitrary precision, is worthwhile to reconsider once we have restrict and can use implicit constructors to give good error messages if someone tries to put a value somewhere it doesnât fit. Doing this also means no casts when you have var x = 10 and try to pass it to something like a String.find_ascii_char. I think that users may find this level of âcompiler just does the right thingâ desirable.
I donât see a reason to /remove/ Indexer, but we shouldnât use Some[Indexer] everywhere as âthe input integer typeâ for reasons stated above.
I know you arenât a fan of syntactic sugar, but I think that this may be a good use-case for it. âThing which implements these traitsâ is something that I think will come up a lot, and even if Some shows that we technically can do it in library code, perhaps we shouldnât, in the same way that we can technically implement structs in Library code using StaticTuple but really should. Rust has found impl to be reasonably acceptable for static dispatch, with dyn for dynamic dispatch. The involvement of a keyword also signals that something different from a normal type bound is happening.
To reiterate, I donât consider this design point to be controversial.
In my opinion, using Int for places where there is not good behavior when it is negative goes against the idea of making invalid states unrepresentable. It also has performance considerations as every function that wants a user-defined index must now check that value is not negative or risk UB/crashes. Right now, despite taking Int in many places, LayoutTensor considers values less than zero to be invalid in many cases, representing this with comments, which puts Mojo exactly back to where C++ is as far as type safety, or even worse since many C++ libraries use size_t.
This combination of âless type correctnessâ, and a choice between less performance (double the comparison ops) or less memory safety (unchecked indexing in one direction), and being harder to debug when things go wrong makes this an supremely unattractive idea from my point of view. To me, given all of this, if all of the indexing in Mojo uses Int, that is not only a type correctness regression from Rust, itâs a regression from C and C++ where libraries generally indicate that negative values are not allowed using unsigned or size_t. Then, Mojo code gets to choose whether to be a memory safety regression or a performance regression vs Rust code in whether it checks negative values or not. You say that checked operations are expensive on the GPU, but so is doubling the number of compares needed to uphold memory safety, since memory safe indexing is going to need to stall the whole lane for an extra 2 operations (cmp + and) compared to unsigned indexing.
In my opinion, writing .cast[dtype]() or Int(len(arr)) once every ~70 lines of code is a much better option than forcing the whole ecosystem to face more than doubled overhead for memory safety.
I was just referring to what you said about Span supporting UInt:
Are you saying that only UnsafePointer should use Indexer, i.e. List.__getitem__ will just support Int?
What about negative Indexing runtime performance overhead? Swift doesnât have negative indexing right?
Do you value compile time performance over runtime performance in this case?
What about ergonomics if Iâm using UInt indexes I will have to explicitly cast them into an Int every time I index into a List, Span, âŚ
I didnât not see you address these 2 points, and these are the main reasons Indexer was added in the first place.
Error messages and LSP can be improved over time, and will need to be improved regardless for other use cases. I donât see this as a good argument long term.
Affecting compile time performance is very surprising to me, there arenât that many __getitem__ functions, why does it affect compile times significantly?
I think this the example youâve been waiting for @clattner. You say Swift hasnât suffered from making the default Int type a platform-specific size, but Swift (like Go) is only used on 64-bit platforms in practice, so I wouldnât expect many people to have battle-tested just how portable Swift code is.
What should happen when a Mojo program/library contains a statement such as var world_population = 8142000000? Is that program/library going to compile and behave correctly all platforms? If it doesnât, then Mojo programs are arguably portable in theory rather than in practice, because the moment a Mojo user wants to compile such a library for a 32-bit target, they are going to have find all of the potential overflows and/or compile-time errors associated with the Int type having suddenly changed size across the library, and they will either have to fork the library or submit PRs (assuming the library is open source), or just give up.
The most insidious bugs are those where the integer values are computed rather than constants, because computed values canât be detected by a linter, e.g. var world_population = sum(country.population for country in all_countries).
This is a very real problem that we need to address if Mojo is truly meant to be portable across platforms. This is the crux of what my earlier posts were about.
Yes, thatâs exactly what Iâm suggesting. The use of Indexer should be exceptionally rare, used by low-level code like UnsafePointer, but not by common application level types like List.
There is an active discussion about what to do about that. Iâm not sure the final outcome and I believe the discussion hasnât converged, but I find it likely that it will be removed entirely. It is an active performance problem for signed types as you say, and signed types arenât going away even if unsigned types were to be allowed.
The point is that you shouldnât be using UInt for random integer values that are positive-only. Where did you get something of UInt type if everything returns Int.
Thatâs not the case: Apple watch is 32-bit (specifically âILP32â where sizeof(Int) and sizeof(pointer) is 32-bit), even when the CPU is 64-bit (more nerdery if youâre interested). Beyond that, Swift has other supported (now obsolete) 32-bit devices. Swift also supports 32-bit linux and other systems.
The answer is no, the behavior changes, just like when you use ssize_t in C/C++. This isnât related to the discussion or Int vs UInt though - UInt has the same behavior just at different thresholds.
-Chris
Have you considered solutions like ECMA scriptâs Array.prototype.at or C++'s std::vector::at. Both use a function to change the semantics of indexing. I think it would be unfortunate to abandon negative indexing, as it is iconic of Python.
Are you saying that only
UnsafePointershould useIndexer, i.e.List.__getitem__will just supportInt?Yes, thatâs exactly what Iâm suggesting. The use of Indexer should be exceptionally rare, used by low-level code like UnsafePointer, but not by common application level types like List.
Do you have data on how much Indexer costs in compile time? Iâm struggling to think of how it would be much more expensive given that both List.__getitem__ and UnsafePointer.__getitem__ will already need to be elaborated and monomorphized. Is @parameter if the cause of the overhead?
What about negative Indexing runtime performance overhead? Swift doesnât have negative indexing right?
There is an active discussion about what to do about that. Iâm not sure the final outcome and I believe the discussion hasnât converged, but I find it likely that it will be removed entirely. It is an active performance problem for signed types as you say, and signed types arenât going away even if unsigned types were to be allowed.
This first time the Mojo community had this debate resulted in the creation of Indexer as a way to get rid of overloading on Int and UInt for every indexing function.
From what I can see, there are our options:
from sys.intrinsics import assume
struct HeapArray[LengthType: Indexer]:
var ptr: UnsafePointer[UInt8]
var length: LengthType
# All functions return -1 on error for the sake of simplicity
fn index_signed_negative_allowed(ref arr: HeapArray[Int], var index: Int) -> Int16:
if index < 0:
index += arr.length
if index < 0: # out of bounds
return -1
if index >= arr.length:
return -1
return arr.ptr[index].cast[DType.int16]()
fn index_signed_negative_forbidden(ref arr: HeapArray[Int], var index: Int) -> Int16:
if index >= arr.length or index < 0:
return -1
return arr.ptr[index].cast[DType.int16]()
fn index_signed_negative_forbidden_with_assume(ref arr: HeapArray[Int], var index: Int) -> Int16:
assume(index > 0)
if index >= arr.length:
return -1
return arr.ptr[index].cast[DType.int16]()
fn index_unsigned(ref arr: HeapArray[UInt], var index: UInt) -> Int16:
if index >= arr.length:
return -1
return arr.ptr[index].cast[DType.int16]()
I would provide this as a godbolt link but compiler explorer, --emit=object, and compile.compile_info all seem to be broken right now.
This shows that you can get signed indexing down to the same cost as unsigned, if you insert UB into one of the most common operations in programming. While extremely performance sensitive code may opt to turn off bounds checking entirely or use a get_unchecked function, I think there is room for cutting a bit of overhead without introducing the potential for UB, especially since indexing a list is a hot-loop activity for many programs and a fairly common action.
What about ergonomics if Iâm using
UIntindexes I will have to explicitly cast them into anIntevery time I index into aList,Span, âŚThe point is that you shouldnât be using
UIntfor random integer values that are positive-only. Where did you get something ofUInttype if everything returns Int.
All of those C and C++ libraries which use size_t. Hereâs a few C functions that Mojo might want to call which use size_t:
fread/fwrite, which are some of the only actually portable ways to do file operations, and without which weâre stuck special casing blocking IO by OS family, and return a size_t which you would likely want to slice a buffer with.malloc/realloc/free/reallocarray, especially on platforms not supported by tcmalloc, like macOS, or Windows, but also for any case where a C library will free the memory.cudaMallocWhat should happen when a Mojo program/library contains a statement such as
var world_population = 8142000000? Is that program/library going to compile and behave correctly all platforms?The answer is no, the behavior changes, just like when you use
ssize_tin C/C++. This isnât related to the discussion or Int vs UInt though -UInthas the same behavior just at different thresholds.
My intention with this was to point out that having a default integer type which changes width by platform can cause some headaches. Rust solved this issue by having the default integer type be something like an IntLiteral and letting it implicitly cast to any datatype which fits it, and thatâs my preferred solution to that problem.
As I said earlier, I think youâve made some inaccurate assumptions. When youâre doing sequential iteration (or have a constant stride) you can use an iterator, and the iterator doesnât need to perform a >= 0 test every iteration, because its internal offset/pointer is monotonically increasing.
If youâre doing random access, rather than sequential, itâs true you canât use an iterator, but youâre usually going to be missing L1, so the >= 0 check has no real cost.
The above two cases are the most common.
Occasionally, you might be doing repeated random access on a small data set that is already in L1. Those are the cases where the >= 0 might have a cost, as you say. But itâs only going to cost something if the ALU is already saturated with instructions. (As Bjarne has written about.)
Finally, Mojo already offers an unsafe_get(i) method on List etc, so if you âknowâ that your index is in bounds, and youâve benchmarked that unsafe_get improves performance, you can always use that.
Programmers also have the option to use Pointer instead of indices. Pointers are already âprovenâ to be in bounds, so dereferencing doesnât require any runtime checks. (Whereas even UInt indexing requires a runtime check.)
That seems to cover mostly everything?
It would be silly for us to launch into debates about how to avoid the overhead of >= 0 without first coming up with a concrete set of examples of where this operation will have non-negligible overhead and where unsafe_get or Pointer are not reasonable options. I will leave it to others to identify those examples.
On this point specifically, there is talk and work on consolidating both Int and UInt to be SIMD aliases with their own DTypes which would help alleviate this specific problem.
I think thatâs also a perfectly good solution to that problem.
Which only leaves what sizeof and similar functions should use up for a debate.
Right, but in C/C++, int is the default integer type, and in practice, itâs 32 bits on the vast majority of platforms. Mojo is instead proposing that ssize_t be the default integer type. That is a much riskier alternative.
Letâs forget about whether or not Swift programmers have encountered overflow bugs on the Apple watch. Youâre correct that Int is 32 bits thereâI didnât know that. However, the Apple watch is a very specific (and simple) domain, so I donât think itâs fair to say that because Int being 32 bits has sufficed for Apple watch, that it will work well for Mojo. Iâm really not comfortable making that assumption, especially when itâs very easily to come up with examples of Mojo programs that are clearly going to break if they are compiled for a 32-bit target.
If you âsteelmanâ the issue for a while, it becomes clear that if Mojo programs are plastered with Int variablesâparticularly in places where the integers being stored have no relationship to the size of the address spaceâusers are going to encounter âworks on my machineâ issues, where a library has been tested to death on its authorâs 64-bit computer, and been proven robust in that context, but then a few months/years down the line, somebody tries to use the library on a 32-bit platform, and suddenly the library is laced with subtle overflow bugs that were never tested, because the libraryâs author wasnât really thinking much about 32-bit support.
I want Mojo code to be truly portable, rather than just portable in theory. If a statement as simple as var world_population = 8142000000 makes a Mojo library non-portable, thatâs a massive red flag that maybe something isnât right. We shouldnât ignore this issue. This is something that we need to get right early, before Mojo has millions of users relying on a specific behaviour.
Yes, I think something like this would be worth exploring. Itâs probably sufficient for an var x = <literal> declaration to infer x as being Int32, unless the âcontextâ around x indicates that an Int64 is needed, for example:
x += <some Int64>, which only type-checks if x is an Int64.Some notes:
Indexer trait, this approach still allows x to be passed to getitem, regardless of whether it resolves to an Int32 or an Int64. So this approach wonât force Mojo users to manually convert i indices to a different type, etc.x is as small as it can be, even on 64-bit platforms. This resolves Chrisâs concerns about performance. In fact, it will likely improve performance (very slightly) on 64-bit platforms, by shrinking the size of coroutines etc.And of course, the major benefit of this approach is that Mojo programs would be more portable, because the type of integer local vars is no longer determined by which platform they are being compiled on! This means that for those integers, if they behave correctly on the developerâs machine, they will behave correctly on everybodyâs machine!
I think the Solomonic solution is to:
DType.uindex and DType.sindex (or some other name)Int defaultism by renaming it like both Owen and Nick proposedfn some_fn(v: Scalar) requires v.dtype.is_integral(): ...UInt__getitem__(self, idx: Scalar) or other overloads for specific indexing kindsConcerns to be addressed:
Scalar[dtype] as the path forward.Scalar from Int is not safe, Iâve already shot myself in the foot by implicitly building a UInt8 from an Int instead of the other way around like I wanted to.Int not be the default. We make the developer think about what width they want to use and in which direction they wish to cast. We educate our consumer instead of holding their hand. We might add some safe and ergonomic defaults and implicit casts later on.Personal note:
While I like the dream of having a single unifying type that we can use for all APIs, I believe we need to enforce correctness above ergonomics. We cannot allow potential UB in the form of negative values where functions donât expect them as an acceptable state for a program; it could lead to massive vulnerabilities and/or crashes that Iâm not comfortable with.
None. Letâs not index on this (groan). Compile time shouldnât be the guiding principle here, Iâm sorry I confused things. My concern is if this trait went pervasive and replaced all âIntâ arguments, not for getitem specifically.
Yes, but thatâs what I want to avoid. I think that pretty much every getitem (other than specific things like UnsafePointer) would just take Int. Rationale: getitem isnât special, it is just like any other function that needs to take an integer value, so it should follow the same standard.
I may be missing your intention here, but the standard way of implementing indexing checks with signed indices is something like assert(UInt(idx) < UInt(size)) which is a single unsigned comparison (the casts are just bitwise conversions so they donât do anything) and this check is enough to catch negative numbers and out-of-range positive numbers in one step - just like for unsigned.
Use of signed integers definitely does not introduce new UB or other problems.
Like Swift it is very important strong goal for Mojo to be able to directly call existing C libraries/functions, but that will never make them ânativeâ to the programming style of the language. The standard way to handle this (in both languages) is to define a language native wrapper struct/function that does the adaptation and contains the casts. The practical outcome is that we get to define our convention without being beholden to IO functions from 1970.
Yes, I definitely agree with you, but also note that using a type that disagrees with the machine word size is a huge performance problem. The major reason why C has UB on overflow is because of this - I wrote about this 14 years ago but didnât know the conclusion. The conclusion that I realized since. then is that standardizing on an integer that is the machine word size is the sweet spot: it enables performance optimizations (eg unblocking loop transformations), provides a predictable programming model for the things that matter, and biases towards a â64 bit computers are obviousâ world. This is what Swift, Go and many many other languages have used without problems, and I donât think Mojo needs to innovate beyond this.
Right, this is the key idea. C is a very old language, and new languages default to âssize_tâ for the integer type.
Respectfully, I think youâre looking at this from a very specific lens. Go as a language has been used across a wide range of different targets and devices as well. Swift wasnât innovative here - I chose to follow this in Swift after evaluating a lot of other options and finding them to be worse tradeoffs.
Your world_population isnât an issue in practice - when building for a 32-bit platform, that generates an error. Your general point is right though that lots of people build and test on 64-bit architectures, and can encounter overflow issues on 32-bit ones. This happens, but is very rare, and when they come up, people can switch to Int64.
In practice, type systems never prevent all bugs - theyâre a tradeoff between expressiveness/usability and pedantic enforcement. In this case, Mojo users everywhere shouldnât have to suffer for people targeting 32-bit platforms with outlier integer sizes.
-Chris
I donât mean to keep drawing this conversation out, but I donât think this conversation is fully grounded in facts. I am compelled to at least ensure that whatever decision is made, it is made based on facts and evidence.
This isnât true. Iâm only aware of 3 languages that do this: your languages (Swift and Mojo), and Go, which was the language that inspired you. I mean no offenseâI think the languages youâve created are amazing and well-designed in many waysâbut we need to ground the conversation in facts, or weâre not going to make good decisions.
Notably, Rust and Zig are newer than Swift and Go, and neither of them default to ssize_t. Rust defaults to Int32, and Zig doesnât have a defaultâyou are required to specify the type explicitly.
In both cases, this means that a statement akin to var x = 0 has the same type on all targets, so such statements are âcross platformâ, i.e. their meaning is the same on all targets.
Of course, Iâm not saying that we should copy Rust and Zig just because they are newer languages. Iâm only saying that:
var x = 0 should have a platform-dependent meaning. (Counter to your claim.)var x = 0 have a platform-dependent meaning is a good/desirable idea. Iâve only seen an argument that the downsides may be minimal, because the Swift and Go communities seem to be doing just fine. That is a valid argument, but itâs not a very convincing one IMO.var x = 0 have a platform-dependent meaning is a bad thing, even if the magnitude of the problem is unclear. I agree that I havenât yet put together a large corpus of examples, but coming up with examples seems to be easy, and Iâm sure I can keep doing that if I really need to. (If others could chip in, that would be valuable, because I donât have much time to spend on this.)Mojo could work this way, for sure. But this would mean Mojo programs arenât portable by default. If the author of a Mojo library needs to test it specifically on a 32-bit platform just to verify that it isnât full of subtle breakages, that doesnât sound like portability to me.
The equivalent Rust and Zig programs donât have this problem. So the solution to this problem has already been discovered. Mojo can be portable, if it wants to be. We just have to agree that is worth doing.
Maybe the point Iâm missing is that 32-bit Mojo and 64-bit Mojo are meant to be treated as different programming languages with their own ecosystems, and that designing Mojo such that every program can be compiled for both 32-bit and 64-bit targets is an explicit non-goal.
I think we would all find this conversation more productive if it was focused on evaluating alternative proposals for how var x = 0 should be handled.
So letâs do that.
Below is what I am calling proposal A. I have also written a proposal B later in the thread. @clattner I expect you would prefer proposal B.
First, letâs assume that all of Mojoâs integer types (including âIntâ, i.e. ssize_t) are modelled as Scalar[DType.<blah>].
Whenever the compiler encounters an integer literal in a position where a specific Scalar type cannot be immediately inferred, e.g. var x = 0 or var nums = [3, 4, 5], it will assume the literal is being converted to a Scalar of unknown DType, e.g:
Scalar[DType.int8]Scalar[DType.int16]Scalar[DType.index]Because all of these types are special cases of SIMD, when the compiler sees var x = 0, it already has enough information to resolve statements such as x += 1 to the right implementation of __iadd__, and so on. This keeps the subsequent inference algorithm small and simple.
All the compiler needs to do is figure out which DType values are compatible with the manner in which x is being used. Or said another way: it needs to filter out the DType values that would cause the program to fail to type check.
In many cases the filtering will happen naturally. For example, if x is used in the expression nums[x], and the implementation of __getitem__ requires a DType.index, then x is immediately resolved to a Scalar[DType.index].
As another example, given var c: Int64, if x is used in the expression x += c, then x must be of DType.int64 or larger, because those are the only alternatives where x += c type checks. (You canât increment an Int8 by an Int64.)
Also very important: The compiler should filter out DTypes that are incapable of storing the literal! So if the number is 1000, the smallest valid DType is int16, and if the number is 8142000000 (the worldâs population), the smallest valid DType is int64.
Once all of the uses of x have been analyzed, we will be in one of the following situations:
x has a unique DType, in which case we are done.x has several valid DTypes, in which case the compiler should default to DType.int64 if itâs valid, or otherwise the largest valid DType that is a signed integer. (The unsigned alternatives are prone to overflow so they are not good defaults.) We could also consider defaulting to DType.index, if itâs valid.x has no valid DType. This will only happen if the programmer has made a mistake. Itâs worth thinking about what a good error message would be, but the simplest error message would be âCannot infer an integer type: no integer type satisfies all uses of x.â If we wanted to be more helpful, we could list the operation(s) that caused DType.index and DType.int64 to be excluded as possibilities.I think this approach is very promising. In particular, this means that:
__getitem__ is defined to take a DType.index, all integer variables used for indexing will be inferred as being 32 bits on 32-bit platforms, and 64 bits on 64-bit platforms. @clattner , I think this addresses one of your main concerns!var world_population = 8142000000 would be inferred as DType.int64 (because its literal value requires >32 bits), and therefore the statement compiles on all platforms.Finally, Iâd like to emphasise that this proposed inference algorithm would be very fast and simple. This is no full blown âbidirectional type checkingâ or anything like that. We are just considering a handful of DTypes.
And the average Mojo user doesnât need to think about any of this. They can write var x = 0, and everything will âjust workâ. When they hover over x, the type will typically Int64 or Int (naming aside). And in the Mojo tutorial, we will just tell people that âMojo chooses the right size for your integersâ. (We will also explain what those sizes are, and how they are chosen.)
I expect some readers will dislike proposal A, owing to the fact that var x = 0 has a type that is decided by âspooky action at a distanceâ. If thatâs you, you might prefer proposal B. Please check it out. 
mov rax, rdx
sar rax, 63
and rax, rsi
add rax, rdx
cmp rsi, rax
jbe .crash
movzx eax, byte ptr [rdi + rax]
Do you see the problem that if every API takes Int, index normalization will be required which has a non negligible impact on code size and latency?
Now tell me:
Is [UInt(a)] better than at(a) ?
This is interesting, there is also negative slicing.
Once you make a choice, please explain the rational and philosophy on performance vs python compatibility, and what it means for the future mojo vs python. There have been many changes how on that lately and Iâm not sure exactly where you stand with regards to python compatibility.
There are 2 more options:
list lower case type which support negative indexing.BigInt which support negative indexing, (where BigInt is the default in def)alias Integer[d: Dtype] = Simd[d, 1] requires d.is_integral()
trait Indexer:
alias IndexType: Integer
fn __index__(self) -> Self.IndexType: ...
fn __index__(self, length: Int) -> Int:
"normalize index default implementation which can be overridden"
struct SIMD(Indexer):
fn __index__(self) -> Self requires Self.dtype.is_integral():
return self
fn __index__(self, length: Int) -> Int:
"SIMD is performant type which doesn't support negative indexing"
debug_assert(...)
return Int(self)
I recommend we keep an Indexer trait so other types (line BigInt) can implement it and get native indexing ergonomics without explicit casting and without unsafe implicit casting to Int.
This is orthogonal to Int vs UInt and negative indexing decision.
I agree with Chris, I think defaulting to the machine size makes sense performance wise. Mojo is more performance oriented than rust.
var x = 0 # you can't infer this value as Int8
while some condition:
if some other condition:
x += 1
print(x)
My comment above was only addressing the specific question Owen had about needing to write 3 overload sets for Int, Uint, and SIMD[...] and how making (U)Int an alias of SIMD will simplify that.
Do you have data on how much
Indexercosts in compile time?None. Letâs not index on this (groan). Compile time shouldnât be the guiding principle here, Iâm sorry I confused things. My concern is if this trait went pervasive and replaced all âIntâ arguments, not for getitem specifically.
If it were use pervasively for all Int arguments, I agree that would be bad. If it stays as a trait (not a restricted alias of SIMD), users will run into ergonomics issues since Indexer doesnât have addition, subtraction, or lots of other things you would often do with an Int or UInt. We canât stop developers from following through with a bad idea, but I donât expect many people to write Absable & Boolable & CeilDivable & Comparable & Copyable & Defaultable & DivModable & ExplicitlyCopyable & Hashable & Indexer & Intable & KeyElement & Movable & Representable & Stringable & Writable in order to do that.
Rationale: getitem isnât special, it is just like any other function that needs to take an integer value, so it should follow the same standard.
I think this is where our disagreement stems from. I see size_t and ssize_t as tied very directly to the address space of the machine, and thus to indexing/pointer offsets, and Mojoâs Int/UInt as an extension of that. When Iâm making I function, I think about what values a parameter can accept that would occur in a correct program. So, for a number between 0 and 100, Iâll use UInt8, and -100 to 100 Iâll use Int8, since a checked cast will ensure that the most clear violations of that part of the API contract are caught. I tend to use 64 bit integers as a default even on 32 bit platforms unless Iâm in hot loop code, since if I want to represent âany integerâ, those come close enough, and then the sign is determined by whether it being negative means I have bug or not.
I may be missing your intention here, but the standard way of implementing indexing checks with signed indices is something like
assert(UInt(idx) < UInt(size))which is a single unsigned comparison (the casts are just bitwise conversions so they donât do anything) and this check is enough to catch
negative numbers and out-of-range positive numbers in one step - just like for unsigned.
This still can cause UB if size < 0. It probably isnât, but if we want to do this trick Iâd prefer to store size as a UInt so that the compiler can help (via checked arithmetic) catch problems.
ack on not making C interop feel native.
Yes, I definitely agree with you, but also note that using a type that disagrees with the machine word size is a huge performance problem. The major reason why C has UB on overflow is because of this - I wrote about this 14 years ago but didnât know the conclusion. The conclusion that I realized since. then is that standardizing on an integer that is the machine word size is the sweet spot: it enables performance optimizations (eg unblocking loop transformations), provides a predictable programming model for the things that matter, and biases towards a â64 bit computers are obviousâ world. This is what Swift, Go and many many other languages have used without problems, and I donât think Mojo needs to innovate beyond this.
Is that particular issue of loop transformations relevant to Mojo? It seems like Mojo could have a FiniteIterator trait and then know that for loops for any iterator which implements that trait will terminate, making it UB to not do so, or make it another âcompile-observed aliasâ like you did for trivial. We can even make it to True, since there shouldnât be many iterators which are infinite. Alternatively, once Mojo gets generators, make it so that infinite generators return a Never type. Mojo could also assume that for loops terminate, forcing users with infinite loops to use a while loop, but I donât know enough about how LLVMâs optimizer works to know the full consequences of that decision.
As for â64 bit computers are obviousâ, I can think of a lot of ML hardware where the designers decided that having a 64 bit address space for a few MB of SRAM was also unimportant, so they use cores with 64-bit integer registers but a 32-bit address space, or have you pass along an âupperâ and âlowerâ argument to get 64 bits from a fully 32-bit core in order to issue explicit NoC requests or DMAs to grab data from a larger memory pool. Some of this appears to be coming from the idea that trying to make prefetchers which can handle new kernels without overshooting (wasting membw) isnât worth the silicon area, since a lot of kernels already try to have memory movement be manual, or that implicit memory movement may be unwelcome in many cases. If you remember Xeon Phi, Intel added PREFETCHWT0 and PREFETCHWT1 because of this cost, moving closer to manual data movement, and others have taken note and pushed that further, which is actually one of my big concerns for MAXâs portability aside from 32-bit.
In practice, type systems never prevent all bugs - theyâre a tradeoff between expressiveness/usability and pedantic enforcement.
I agree, but I also want them to help developers as much as possible. Using Int to represent something which will only go negative if I have a bug means that the compiler is missing information and if that problem ever happens it canât help me track down where the problem was if I have a reproducer for the issue. I could also follow Rustâs borrow checker algorithm by hand, but doing that would be very annoying, so we have Origins. The goal isnât to prevent all bugs, itâs to prevent as many as possible with acceptable trade-offs and to help the developer deal with the remaining ones. I donât understand the desire to ignore things that Mojo can express in favor of getting rid of an operation which, based on all of the data Iâve seen, is fairly infrequent. Even in Rust, with mandatory explicit casts everywhere, when I used isize so I could stuff a -1 for invalid into a wire protocol, for a type which is used to index almost every array in the program, it was a mild annoyance at worst to cast to usize before indexing and after the check for negative values, and I could have written a wrapper type to handle that for me if I really wanted to. This is exactly the same problem Mojo would have if everyone used Int for values they wanted to index with and the entire ecosystem forced using UInt for indexing. My view of the tradeoff of forcing Int is that we are making the compiler unable to help users debug many types of problems, or making the language more annoying for those who want to have access to that help by using UInt. If we use SIMD restricted to integer types, that issue goes away, which is why Iâm in support of that path, since it also lines up with using SIMD basically everywhere else in Mojo for being generic over the kind of datatype you want.
In this case, Mojo users everywhere shouldnât have to suffer for people targeting 32-bit platforms with outlier integer sizes.
Rust encourages users to use fixed-bit-width types for as much as possible. In my experience, most developers end up using u32 or i32 because they are large enough that overflowing them often indicates a bug. This results in targeting 32-bit platforms mostly being an issue of missing OS features, not bit widths. A few warnings from the compiler about large constants and using Int64/UInt64 can fix the world_population issue and people who donât care about portability can silence that. 16 bit is probably rare enough for Mojo to not care, but 32 bit is very much not dead and I suspect the number of 32-bit cores in existence is actually growing right now.