Both approaches are equivalent in terms of avoiding the billion dollar mistake - in neither Julia nor Rust can you get a Null reference to an object of some type T in a safe way. In both Rust and Julia, reading a value from an uninitialized array gives you a (potentially invalid) instance of that type - Rust just explicitly calls that out as undefined behavior, while Julia hasn’t quite defined that it is undefined. In both cases though, you can’t rely anymore on the guarantees a type is supposed to provide, so really, in neither language should it be done at all.
That doesn’t change the fact that at some point, the memory has to transition from “uninitialized” to “initialized”. It’s just a matter of whether there are some situations where it’s required to do that as a user of a language, instead of the language doing it for you (circling back to “do we require arrays to be instantiated with their values initialized or not”). This is quickly going to get very abstract/technical though, so in the interest of not giving an introduction to type theory, I’ll stop here
Yes, though probably not the kind that we’d exploit for optimization. We’d likely change the behavior of it to be defined if the compiler got to the point of being strong enough for this to be a problem (because then it could likely also optimize away the cases where it’s currently slow).
What could that look like? What would a stronger compiler be able to do and how is it related to guaranteeing reads of an uninitialized isbitstype will always give RAM bits thrown into it? I was under the impression that the current state of affairs is the fastest case, basically not doing any work to check or warn validity.
If we defined undef to zero-initialize, but the compiler was able to prove (in the common cases we care about) that all valid indices of the array are written to, then the compiler can elide the zero initialization without it ever being semantically visible.
So in other words, we could define undef initialization in the future like zeros now, but the compiler could make that like undef initialization now if it realizes those zeros are overwritten anyway?
Also shoutout to ArrayAllocators.jl for calloc substituting for undef for fast zero-initialization in some cases.
Zero initialization (whether with calloc or explicitly filling the array with zeros) doesn’t help us in avoiding the undefined behavior. I can just have a type which must have at least one 1 in its bitpattern and presto, zero initialization is not valid anymore.
Avoiding the undefined behavior is intricately linked to only giving out a reference to arrays whose elements have all been properly initialized, by going through their constructor. There’s no fancy trick around that.
The optimization that would allow removal of the zero initialization is IMO the same one we’d need for proving that the existing use of undef is safe.
There is a difference between an access being undefined behavior and an access violating constraints that may be imposed by a constructor. There is currently various ways to construct invalid objects, undef is only one of them. We’ve been talking about locking that down to support some of the formal verification ideas, but inner constructor reachability currently does not restrict the set of constructable objects.
julia> struct Foo
x::Int
Foo() = new(1)
end
julia> Foo()
Foo
julia> Base.show(io::IO, ::MIME"text/plain", x::Foo) = x.x == 1 ? print("Foo") : error("Invalid Foo Detected")
julia> using ArrayAllocators
julia> Vector{Foo}(calloc, 5)
5-element Vector{Foo}:
Error showing value of type Vector{Foo}:
ERROR: Invalid Foo Detected
In that case, one might want my other package, ArrayInitializers.jl.
julia> using ArrayInitializers
julia> A = Vector{Foo}(ArrayInitializers.fill!(Foo()), 5)
5-element Vector{Foo}:
Foo
Foo
Foo
Foo
Foo
I’m not really convinced the Rust situation is much better. You basically just do the same thing, use unsafe, and ask Rust to assume it’s initialized after some point.
The difference to me seems mostly to be we should have called undef to be unsafeinit to be very clear.
I don’t think so. What I’m saying is that if we treat accessing invalid instances that were created via undef in an array as undefined behavior, then we must also treat accessing invalid instances that come from a zero initializer as undefined behavior, because both break the semantics imposed by the type the same way. If our compiler ends up treating these two differently, I’d consider that a bug (raw malloc is permitted to give out zeroed pages, so having a difference there sounds extremely suspicious).
That example still permits construction of the invalid object and only errors once its displayed. That’s way too late and not even close to being safe. You can’t in general check post-creation whether an (immutable) object is valid, because that would mean no longer trusting types to give any guarantees at all. That’s squarely the job of a constructor.
In Rust, you don’t need an uninitialized state for collections contiguous in memory since push is not an expensive ccall like in Julia. You would just use with_capacity as shown in the blog post.
MaybeUninit is very low level. You would definitely put it behind a safe abstraction. It is not for “end users”.
Now that the solution was marked as it being undefined behavior, I will remove the note tomorrow. You can reply if you don’t agree with it being removed.
I’m assuming you didn’t mean it that way, but FWIW, this didn’t come across particularly well to me. I was trying to help out here, by giving an authoritative answer to people’s questions. Undefined behavior is a very specific thing, and some things are undefined behavior and some things are not. Could one imagine a world in which having an object that is “invalid” in various senses is undefined behavior, sure, but that’s not how things currently work. You could certainly argue for different semantics, but muddying the waters here is a disservice to the people who asked the question.
Yes, and I gave what I take to be the common definition in my first post in this thread At the very least, it’s not clear at all what the term “undefined behavior” means in the context of julia - the meaning from C doesn’t translate well, because Julia doesn’t quite have the same memory model (exposed to the user of the language) and doesn’t have a standard.
What would you say “undefined behavior” means in Julia, just so we’re all on the same page? I’ve got the feeling that it’s going to differ from what people up top in the thread (or heck, me) think it is.
Certainly not exposed semantically, but internally we surely do. That’s why we canonicalize booleans to truly only have the lowest bit set, right?
(as well as related issues/PRs with reinterpret, where much the same issue comes up)
I believe zero initialization here did refer to filling an array with proper Base.zero elements, not just filling all the bits with 0. That would be different from calloc finding zeroed pages.
That’s interesting. So take my earlier example of a type NeverZero whose inner constructor corrects inputs of 0, but I used an undef trick to make (instances printed as) NeverZero(0). Is it formally considered an instance of NeverZero? reinterpret(NeverZero, zeros(UInt8, 8))[1] isa NeverZero certainly is true.
In the other posts, I agreed that accessing an undef array that has not been initialized is undefined behavior. I concur with Keno.
I do not agree that using undef itself is undefined behavior though, which I believe was your original assertion. This is a different matter. As long as it is followed by an initialization routine, it’s fine. Once the array has been initialized, accessing it is not undefined behavior.
A couple years ago I did put forward a pull request to make undef easier to use by making a function undefs as an analog to zeros or ones.
This was rejected for a number of reasons. Between the discussion there and past discussions, it became clear that undef was meant to be relatively difficult to use. In other words, as you put it, it was also not meant for “end users”.
The other point you made is that undef was part of a performance recommendation. As far as I can tell all the performance examples using undef are followed by initialization, so I do not see any of those as exhibiting undefined behavior either.
Many of the safe ways of initializing an array are similiar to those in Rust. Essentially use an iterator with a known size. This could be used in a map or an array comprehension.
The push! kind of paradigm of building an array only really makes sense to me when I do not know the final size of the collection. I’m also not sure what you mean by “expensive ccall”. It’s just a call after compilation. The one issue perhaps is that it is difficult to inline this.
If we compile the following function foo().
julia> function foo()
A = Int[]
sizehint!(A, 5)
push!(A, 1)
end
foo (generic function with 1 method)
The “ccall” just becomes a call in LLVM IR in the same way a C routine would call another C routine. This does not seem extraordinarily expensive unless you are trying to build a very large vector this way in a tight for loop.
; │┌ @ array.jl:1014 within `_growend!`
call void inttoptr (i64 140705553961648 to void ({}*, i64)*)({}* nonnull %7, i64 1)
LLVM IR of foo()
```
julia> @code_llvm foo()
; @ REPL[476]:1 within `foo`
; Function Attrs: uwtable
define nonnull {}* @julia_foo_2906() #0 {
top:
%gcframe2 = alloca [3 x {}*], align 16
%gcframe2.sub = getelementptr inbounds [3 x {}*], [3 x {}*]* %gcframe2, i64 0, i64 0
%0 = bitcast [3 x {}*]* %gcframe2 to i8*
call void @llvm.memset.p0i8.i32(i8* noundef nonnull align 16 dereferenceable(24) %0, i8 0, i32 24, i1 false)
%1 = call {}*** inttoptr (i64 140705554136352 to {}*** ()*)() #4
; @ REPL[476]:2 within `foo`
; ┌ @ array.jl:400 within `getindex`
; │┌ @ boot.jl:477 within `Array`
%2 = bitcast [3 x {}*]* %gcframe2 to i64*
store i64 4, i64* %2, align 16
%3 = getelementptr inbounds [3 x {}*], [3 x {}*]* %gcframe2, i64 0, i64 1
%4 = bitcast {}** %3 to {}***
%5 = load {}**, {}*** %1, align 8
store {}** %5, {}*** %4, align 8
%6 = bitcast {}*** %1 to {}***
store {}** %gcframe2.sub, {}*** %6, align 8
%7 = call nonnull {}* inttoptr (i64 140705553955840 to {}* ({}*, i64)*)({}* inttoptr (i64 140705037065232 to {}*), i64 0)
%8 = getelementptr inbounds [3 x {}*], [3 x {}*]* %gcframe2, i64 0, i64 2
store {}* %7, {}** %8, align 16
; └└
; @ REPL[476]:3 within `foo`
; ┌ @ array.jl:1285 within `sizehint!`
call void inttoptr (i64 140705553963920 to void ({}*, i64)*)({}* nonnull %7, i64 5)
; └
; @ REPL[476]:4 within `foo`
; ┌ @ array.jl:1061 within `push!`
; │┌ @ array.jl:1014 within `_growend!`
call void inttoptr (i64 140705553961648 to void ({}*, i64)*)({}* nonnull %7, i64 1)
; │└
; │ @ array.jl:1062 within `push!`
; │┌ @ abstractarray.jl:419 within `lastindex`
; ││┌ @ abstractarray.jl:382 within `eachindex`
; │││┌ @ abstractarray.jl:133 within `axes1`
; ││││┌ @ abstractarray.jl:98 within `axes`
; │││││┌ @ array.jl:149 within `size`
%9 = bitcast {}* %7 to { i8*, i64, i16, i16, i32 }*
%10 = getelementptr inbounds { i8*, i64, i16, i16, i32 }, { i8*, i64, i16, i16, i32 }* %9, i64 0, i32 1
%11 = load i64, i64* %10, align 8
; │└└└└└
; │┌ @ array.jl:969 within `setindex!`
%12 = add nsw i64 %11, -1
%13 = bitcast {}* %7 to i64**
%14 = load i64*, i64** %13, align 8
%15 = getelementptr inbounds i64, i64* %14, i64 %12
store i64 1, i64* %15, align 8
%16 = load {}*, {}** %3, align 8
%17 = bitcast {}*** %1 to {}**
store {}* %16, {}** %17, align 8
; └└
ret {}* %7
}
```
In Julia, the capacity issue is a bit complicated since the Array type is supposed to represent an n-dimensional array, not just a one-dimensional vector. Vector is a special case which is allowed to act as a double ended queue.
One Base structure in Julia that does have the explicit concept of capacity is Channel:
Constructs a Channel with an internal buffer that can hold a maximum of size objects of type T.
This is perhaps a bit heavy since it also meant to be thread safe, but perhaps for the very large vector case we are discussing that may be useful.
Oh yeah we went over this as a more faithful but less used analog to Rust’s with_capacity in the original thread this was split from.
We also laid out that even after sizehint!, push! is quite a lot slower (comparing @btime, 57ish on my machine) than setindex!. I don’t recall if Mo8it benchmarked Rust’s analog of setindex for comparison (and I think it would need unsafe Rust for the uninitialized vector to start), but they did link Rust source code showing a vector checks if there’s more capacity to skip almost all the vector-lengthening work to just incrementing the semantic length and setindexing the last index. Squinting at the code that _growend!ccalls (as someone who doesn’t know C or Rust, C is way harder to read), I can’t make out a similar skip so I’m guessing that’s why there’s this discrepancy.
More importantly, a valid Int! All bitpatterns are well defined for this type after all. You’re not guaranteed any particular Int though. This is why I don’t want to call this undefined behavior.
At the very least, it’s not clear at all what the term “undefined behavior” means in the context of julia - the meaning from C doesn’t translate well, because Julia doesn’t quite have the same memory model (exposed to the user of the language) and doesn’t have a standard.