# Is accessing an \`undef\` array undefined behavior?

**URL:** <https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899>\
**Category:** General Usage\
**Created:** [July 21, 2023, 8:43am UTC](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899 "2023-07-21T08:43:17Z")\
**Posts on this page:** 8\
**Page:** 3

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [July 22, 2023, 7:53am UTC](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899/41 "2023-07-22T07:53:09Z")

</div>

And after some digging by @jar1 on slack, this article came up:

> **[UB Might Be a Wrong Term for Newer Languages](https://matklad.github.io/2023/04/02/ub-might-be-the-wrong-term-for-newer-languages.html)**
>
> A short note on undefined behavior, which assumes familiarity with the subject (see this article for the introduction).
> The TL;DR is that I think that carrying the wording from the C standard into newer languages, like Zig and Rust, might be a...

Which I wholeheartedly agree with & is why I don’t want to call this kind of thing “undefined behavior”.

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [July 22, 2023, 9:38am UTC](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899/42 "2023-07-22T09:38:08Z")

</div>

Unfortunately, that post is also sloppy and most standards distinguish between _undefined_, _unspecified_ and _implementation-dependent_ behaviour (see this [Stackoverflow](https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior) post for instance).  
The [Common Lisp Hyper Spec](http://clhs.lisp.se/Body/01_db.htm) – to quote from a standard of a non C-like language – gives a similar definition:

- Unspecified: `This means that the consequences are unpredictable but harmless. Implementations are permitted to specify the consequences of this situation. No conforming code may depend on the results or effects of this situation [...]`

- Undefined: `This means that the consequences are unpredictable. The consequences may range from harmless to fatal. No conforming code may depend on the results or effects. Conforming code must treat the consequences as unpredictable. [...] An implementation is permitted to signal an error in this case.`

Thus, given that the following program is unpredictable

```julia
v = Vector{Int16}(undef, 3)
if sum(v) > 0; "y" else "n" end

```

I guess that one could call it _undefined_ behaviour.

For most newer languages, which don’t have a standard and multiple more or less conforming implementations, the distinction between _unspecified_ and _undefined_ is less useful, but undefined in the sense that `No conforming code may depend on the results or effects` is certainly a valid terminology to warn and prevent usage of certain constructs in certain context. I.e., to be precise, in the above example, the undefined behaviour would not be in the construction of the array – which always gives a valid instance – but rather the access of its elements – as it cannot be relied on what properties those instances have.

Maybe adding to the confusion, the Rust documentation on [binary\_search\_by](https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search_by) states that `If the slice is not sorted [...], the returned result is unspecified and meaningless.`, i.e., uses unspecified to refer to a valid, yet unpredictable (and most likely incorrect) result.  
(Unfortunately, I’m currently unable to find in which thread and by whom the binary search example had been mentioned as requiring an invariance that cannot be checked by most compilers – except for some dependently typed languages which can enforce that a list must be sorted at compile time). In the end, it’s always a compromise on which programs slip through, either by the compiler as its unable to check this type of invariance or in dynamic languages by skipping a runtime check which might have raised an appropriate error.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [July 22, 2023, 12:05pm UTC](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899/43 "2023-07-22T12:05:26Z")

</div>

> [@bertschi](#):
>
> Unfortunately, that post is also sloppy and most standards distinguish between _undefined_, _unspecified_ and _implementation-dependent_ behaviour

Quite right - I just thought it prudent to use the short version instead of the more extensive three parter this is ultimately based on, because most users reading this thread likely won’t read the full nuances 🙂

Still, for completeness sake, here it is:

[https://blog.regehr.org/archives/213](https://blog.regehr.org/archives/213)

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [July 22, 2023, 9:22pm UTC](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899/44 "2023-07-22T21:22:11Z")

</div>

> [@Benny](#):
>
> 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!` `ccall`s (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.

There is some thinking about creating a lower level `Buffer` type that would back an Array, and I suppose this would probably resolve these issues if one really wanted to construct an array via `push!`.

> <https://github.com/JuliaLang/julia/pull/48728>
>
> \## Motivation
> 
> After a conversation on slack with @StefanKarpinski and @brenhi…nkeller it seemed like a lot of other PRs on improving arrays stalled out and the first fundamental step is having a generic buffer type. I still have crashes in the REPL with this current implementation and it appears I haven't fully implemented the GC side correctly, but I figured it was better to put this out there for someone else to start with then completely abandon this.
> 
> The goal here is to provide the core functionality for bare-bones storage of multiple repeated elements.
> 
> \## Implementation
> 
> There are three primary storage types this PR is intended to support:
> 
> \* \`Buffer{T}\`: has a fixed size and mutable elements
> 
> \* \`DynamicBuffer{T}\`: has a dynamic size and mutable elements.
> 
> \* \`ImmutableBuffer{T}\`: has a fixed size and immutable elements (not implemented here but should be as a future PR for with the \`freeze\`/\`thaw\` compiler optimizations worked on in prior \`ImmutableArray\` PRs).
> 
> The type layout is modeled after that of \`jl\_array\_t\` and is similar to the following native Julia structure:
> 
> \`\`\`julia
> struct MemoryChunk{T}
> length::Int
> data::Ptr{T}
> end
> \`\`\`
> 
> Just like \`Array\`, the number of bytes stored determines if \`data\` points to inline allocations that extends the size of \`MemoryChunk\` via \`jl\_gc\_alloc\` or a seperately stored chunk via \`jl\_gc\_managed\_malloc\` and \`jl\_gc\_track\_malloced\_buffer\`.
> 
> Storage of elements is similar as bit unions, bits, or pointers to boxed types is identical to that of \`Array\` or \`jl\_array\_t\`.
> 
> Note that there are not explicitly stored flags, offsets, additional dimensions, or element size. This means that:
> 
> \* Unlike \`jl\_array\_t\`, all information about the element type must be derived again everytime it's needed when running C code. Of course, this is not an issue once we are working with TBAA and that is all optimized away. However, I'm uncertain whether that will slow things down that don't often interact with TBAA directly (such as the garbage collector).
> 
> \* We don't have \`flags.how == 1\` to mark a julia-allocated buffer that needs to be marked or \`flags.isshared\`. I've tried to use the last two its of the data pointer to mark these (see \`jl\_buffer\_isshared\` and \`jl\_buffer\_isunmarked\`). It may make more sense to have a type that explicitly wraps a shared buffer, preserving that bit for some other future use and allowing more explicit representation of data storage through the type system. I've yet to spend much time grocking the unmarked allocated data aspect of this, so there may be a better approach that I've yet to consider.
> 
> \* The lack of an offset or maximum size means that resizing for \`DynamicBuffer\` will always result in a reallocation or new allocation. Feature parity with \`Vector\` is intended to be accomplished through Julia code with something like
> \`\`\`julia
> mutable struct DynamicVector{T} \<: DenseVector{T}
> buffer::DynamicBuffer{T}
> offset::Int
> length::Int
> end
> \`\`\`
> where the length of \`DynamicBuffer\` here is functionally equivalent to \`Array\`s maxsize.
> 
> I'm in the process of moving the implementation to native Julia. This is a bit challenging since this is essentially an attempt to rewrite large portions of "array.c" where a lot of things aren't implemented in native Julia code (interacting with the GC, traversing \`Union\`s) and sometimes working efficiently with a pointer get tricky (storing pointers to immutable types).
> 
> 
> \## Remaining Work
> 
> \* Names may not be sufficiently self documenting and may even be misleading. The term "buffer" is often used to refer to something more akin to what our current \`Vector\` is with offsets and resizing. Perhaps something that is more clearly describing a continuous chunk of memory such as \`MemoryChunk\`, \`ResizableMemoryChunk\`, and \`ImmutableMemoryChunk\`.
> 
> \* What needs to be done here to support better allocation practices? There's a lot of interest in providing users with the ability specify how things are allocated (allocating to the stack, bump allocators, smart pointers). I've assumed that most of that would be better addressed in future PRs by those who really understand how to optimize that sort of thing, but I'd also like to ensure that the implementation here is not prohibittive to future developments.
> 
> \* Could we provide better support for \`Bool\` here so that we don't need an explicit \`BitBuffer\` type?
> 
> \* More support for future implementation of \`DynamicVector\` with user friendly resizing methods
> 
> \* The assumed effects for methods should change based on the buffer variant. This is currently buggy. For example, the effects for \`length(::Buffer)\` should not be the same as \`length(::DynamicBuffer)\`, but currently are.
> 
> \* Would it make sense to implement \`ImmutableBuffer\` here without any of the \`thaw\`/\`freeze\` stuff that would complicate things?

> <https://gist.github.com/JeffBezanson/a25dde3bebb5a734af87bb5ddcf31fb0>

What I’m still confused about is if you know that the vector is going to be a certain size or least have some known upper bound, I’m still unsure why you would build an array using `push!`.

If you know you want to construct a vector of length `N` you could construct the array via

```julia
A = collect(f(i) for i in 1:N)
B = map(f, 1:N)

```

To me the `push!` case is really when the ultimate length is unknown. Even then, the strategy might be to allocate a large enough array and then return a view of the known elements. Importantly, the latter strategy also generalizes to `N` dimensions.

---

<div class="post-metadata">

**Author:** ![jameson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jameson/32/23_2.png) [@jameson](https://discourse.julialang.org/u/jameson)\
**Post date:** [July 23, 2023, 12:03am UTC](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899/45 "2023-07-23T00:03:45Z")

</div>

`push!` is a very efficient way to represent and implement that. Just because the current implementation is mediocre does not mean the whole concept is needing replacement, just the implementation of it.

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [July 23, 2023, 8:42pm UTC](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899/46 "2023-07-23T20:42:41Z")

</div>

Let’s build an `AbstractVector` to handle this case then.

```julia
julia> begin
           mutable struct BufferedVector{T} <: AbstractVector{T}
               buffer::Vector{T}
               length::Int
               BufferedVector{T}(len = 0; capacity = len) where T = new{T}(Vector{T}(undef, capacity), len)
           end
           Base.size(A::BufferedVector) = (A.length,)
           Base.getindex(A::BufferedVector, i::Int) = (checkbounds(A, i); @inbounds A.buffer[i])
           Base.IndexStyle(::Type{<: BufferedVector}) = IndexLinear()
           Base.setindex!(A::BufferedVector, v, i::Int) = (checkbounds(A, i); @inbounds A.buffer[i] = v)
           Base.length(A::BufferedVector) = A.length
           Base.resize!(A::BufferedVector, i::Int) = begin
               i > length(A.buffer) && resize!(A.buffer, i)
               A.length = i
           end
           Base.push!(A::BufferedVector, v) = begin
               A.length += 1
               A.buffer[A.length] = v
           end
       end

```

I then benchmarked this against a few different methods of general array initialization.

```julia
julia> function benchmark_alloc()
           n = 2^8
           m = 2^14

           @info "sizehint!"
           @btime for _ in 1:$n
               v = Int64[]
               sizehint!(v, $m)

               for i in 1:$m
                   push!(v, i^3)
               end
           end

           @info "undef"
           @btime for _ in 1:$n
               v = Vector{Int64}(undef, $m)

               for i in 1:$m
                   v[i] = i^3
               end
           end

           @info "BufferedVector"
           @btime for _ in 1:$n
               v = BufferedVector{Int64}(; capacity = $m)
               for i in 1:$m
                   push!(v, i^3)
               end
           end

           @info "Array comprehension"
           @btime for _ in 1:$n
               v = [i^3 for i in 1:$m]
           end

           @info "Map"
           @btime for _ in 1:$n
               v = map(1:$m) do i
                   i^3
               end
           end

           @info "Collect Generator"
           @btime for _ in 1:$n
               v = collect(i^3 for i in 1:$m)
           end
       end
benchmark_alloc (generic function with 1 method)

```

Here are the results:

```julia
julia> benchmark_alloc()
[ Info: sizehint!
  21.395 ms (512 allocations: 32.03 MiB)
[ Info: undef
  3.053 ms (512 allocations: 32.01 MiB)
[ Info: BufferedVector
  2.991 ms (512 allocations: 32.01 MiB)
[ Info: Array comprehension
  2.169 ms (512 allocations: 32.01 MiB)
[ Info: Map
  2.048 ms (512 allocations: 32.01 MiB)
[ Info: Collect Generator
  2.033 ms (512 allocations: 32.01 MiB)

```

---

<div class="post-metadata">

**Author:** ![Mo8it](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mo8it/32/32649_2.png) [@Mo8it](https://discourse.julialang.org/u/Mo8it)\
**Post date:** [July 23, 2023, 9:58pm UTC](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899/47 "2023-07-23T21:58:28Z")

</div>

Nice!

Some notes:

- You are missing a check in `push!` for the case that the length is equal to the capacity to increase it and maybe reallocate first.
- The length should not be an argument for the constructor, not even an optional one.
- You should not set the length equal to the new length in `resize!` if the new length is bigger than the old one.

Something like this should be used instead of the current arrays implementation to avoid ccalls.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [July 23, 2023, 11:18pm UTC](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899/48 "2023-07-23T23:18:40Z")

</div>

It’s a nice proof of concept but it’d be a lot smoother to edit `push!` or `:jl_array_grow_end`, the former requiring exposure of the equivalents of `length` and `capacity` to the Julia side. I grabbed the [Rust link from the other thread](https://github.com/rust-lang/rust/blob/399b068235ceea440540539b3bfd1aeb82214a28/library/alloc/src/vec/mod.rs#L1809-L1836C9) as an example of what it can look like. There is another function right below that one, `push_within_capacity`, that is only justified because `capacity` is exposed to the user, that’s about what your current version of `push!` does without the `length < capacity` check.

> [@Mo8it](#):
>
> The length should not be an argument for the constructor, not even an optional one.

I’d say I wouldn’t like this limitation but since the buffer starts off as an `undef` array with length of `capacity`, there’s little point to starting this new type with nonzero length. It’s not like this new type currently leverages `append!` or broadcasting to fill in some elements.

[Previous page](https://discourse.julialang.org/t/is-accessing-an-undef-array-undefined-behavior/101899.md?page=2)