violation of GC safety

[vtjnash]

the MVector violates gc safety when it contains non-bitstypes (it lacks a write barrier), resulting in the possibility that the gc will lose the object and delete the objects in the array while still in-use:

StaticArrays.jl/src/MVector.jl

Lines 49 to 50 in 1e18069

	else # TODO check that this isn't crazy. Also, check it doesn't cause problems with GC...
	unsafe_store!(Base.unsafe_convert(Ptr{Ptr{Void}}, Base.data_pointer_from_objref(v.data)), Base.data_pointer_from_objref(val), i)

[andyferris]

Thank you very much Jameson! I was quite worried about this, and was hoping someone more knowledgeable/cleverer than I would take a look someday. (You might be able to tell from the comment).

Can you point me somewhere that explains the correct procedure, or an example of where the correct procedure is implemented? Otherwise I'll have to make that branch an error for now (it's probably not used in the wild).

[vtjnash]

I don't think it's possible to implement correctly, maybe @yuyichao can say for certain?

[yuyichao]

In additional to gc safety issue, this also violate the immutability since the tuple is not inlined if the type is not a bits type so this is not really fixable.

The GC safety can be worked around (does not apply here due to the immutable issue) by writing llvm code using llvmcall that triggers the write barrier manually. (Do note that the llvm code is different on 0.4 and 0.5). This is not recommended for obvious reasons.

[andyferris]

In additional to gc safety issue, this also violate the immutability since the tuple is not inlined if the type is not a bits type so this is not really fixable.

I don't understand this. I'm not sure what you mean by inlined. I think I've found the correct bit of memory to write the pointers to. MVector is not an immutable type - it's immutable fields can be replaced (wholly, or partially as an optimization, right?). setindex! is not defined on SVector.

The GC safety can be worked around (does not apply here due to the immutable issue) by writing llvm code using llvmcall that triggers the write barrier manually. (Do note that the llvm code is different on 0.4 and 0.5). This is not recommended for obvious reasons.

Or calling an appropriate C function, I assume? Maybe there is something I'm missing.

[yuyichao]

AFAICT MVector is a mutable type and the field cannot be partially replace if not inlined.

Or calling an appropriate C function

Sure, if you write your own.

[yuyichao]

Inlined means the memory of the field is, .... well ...., inlined and the field is not a reference to another piece of memory.

[andyferris]

Inlined means the memory of the field is, .... well ...., inlined and the field is not a reference to another piece of memory.

Right. From playing it seems that the pointer to my MVector is like a C-array of pointers to the elements, if T isn't isbits but is concrete (i.e. a heap-allocated NTuple of references/pointers). Currently it just copies the pointer across to the new location, and I figured the GC would find it on its next scan.

Is the problem with GC that some of my code might be executed in-between this GC scan and the actual deletion? During this function a reference to the new data should exist on the stack, so at all times there should be at least one or at least two references to the to-be copied value. But if the function exits and my MVector is not rescanned is there a moment the GC thinks no reference exists? Sorry, I'd just like to understand better... I don't even know what the write barrier is used for (what exactly do we not want to be written to?). My understanding of GC is pretty simplistic - it scans the stack and its references and all their references and so-on, and deletes all the stuff it doesn't find - and obviously execution has to be paused somehow while this occurs.

[yuyichao]

There are two problems immutability and GC safety. The inlining of the field has nothing to do with the GC, only the immutability.

1. Immutability

   It is not allowed to modify immutable memory after it's created. Immuable memory is memory that is allocated for a immutable object (i.e. object of immuable type). For non isbits type, the data field is immutable memory and must not be modified.

2. GC safety

   Simply speaking, updating a field need to do more than just storing to the memory location for a generation GC (or most GC except the most naive ones) to work correctly, i.e. unsafe_store! may not be enough to make the GC discover the mutation.

[andyferris]

It is not allowed to modify immutable memory after it's created. Immutable memory is memory that is allocated for a immutable object (i.e. object of immuable type).

Definitely true on the stack. It is possible to mutate global consts even if they are immutable, but I suspect that is not "allowed" by the language and constitutes undefined behaviour. Julia is successful at stopping you getting stack pointers to immutables, which is really nice that we can enforce the language semantic there but it is damn frustrating when you want to pass a small stack-allocated vector to BLAS without slow allocation/GC.

But I have to disagree when the immutable thing descends from a mutable type somewhere. An obvious case: I can always reinterpret a Vector{NTuple{N,Float64}} as a Matrix{Float64} with N rows. I can create the vector as immutable tuples. and according to your statement, I must only replace entire tuples since each is "immutable memory that is allocated for an immutable object", and never mutate their elements. But after the reinterpretation into a matrix, I can happily replace one Float64 at a time, and the original Vector has changed accordingly. Quite useful, especially for large N.

This idea must generalize to mutables with immutable fields, because (a) it would be super weird if Array was special and (b) those fields can always be mutated in practice (e.g. you can pass a pointer to the mutable to a C function) and I would say consequentially we should not be trying to maintain their immutability when they live on the heap like that. Only immutable fields of immutable objects (of immutable objects, etc, all the way to global scope consts or the stack) should be assumed constant by the compiler/user.

The idea of reinterpreting a length-1 Vector of an NTuple{N,Float64} as a length-N Vector{Float64} is exactly what I'm going for in MVector{N,Float64} in this package.

[yuyichao]

Definitely true on the stack.

What do you mean? On the stack or not is totally irrelevant. Whether it is inlined into mutable object is.

It is possible to mutate global consts even if they are immutable

What do you mean by global consts? And again global consts has nothing to do with this.

An obvious case: I can always reinterpret a Vector{NTuple{N,Float64}} as a Matrix{Float64} with N rows. I can create the vector as immutable tuples.

Correct.

and according to your statement, I must only replace entire tuples since each is "immutable memory that is allocated for an immutable object", and never mutate their elements.

No this is NOT what I'm saying. For isbits type, the immutable type is inlined into mutable memory, which is why mutating it is OK. This is what JuliaLang/julia#17115 is all about.

This idea must generalize to mutables with immutable fields,

Not in general. Again, only when the immutable field is inlined.

because (a) it would be super weird if Array was special and

Therefore you can't do that when the immutable object is not inlined into the array either.

(b) those fields can always be mutated in practice

For non-inline object the memory holding the immutable object is never mutated. Only the reference to the memory (the pointer stored in the field).

(e.g. you can pass a pointer to the mutable to a C function)

FWIW, this is a really bad way to tell if it's okay to mutate the memory. You can generally pass pointers to immutable memory using Any ccall parameter type but that's a contract that the called code understands julia and won't do things that violate the julia semantics, including not mutating immutable memory.

and I would say consequentially we should not be trying to maintain their immutability when they live on the heap like that.

Only when inlined.

The idea of reinterpreting a length-1 Vector of an NTuple{N,Float64} as a length-N Vector{Float64} is exactly what I'm going for in MVector{N,Float64} in this package.

isbits type is fine since they are inlined. Non-isbits type is not since they are not inlined. Please read JuliaLang/julia#17115 to understand when mutating is ok and when it is not.

As an unrelated piece of information what you might need to know before hitting it yourself, it is undefined if you creates an actual array from the memory belongs to a non-array object (i.e. call unsafe_wrap on a pointer you get from pointer_from_objref) and julia will actually return the wrong result if you do it that way. I didn't check if you are doing it, just mentioning it.

[andyferris]

First, thank you @yuyichao for a thorough response. Sorry if I've seemed a little slow, or perhaps assertive, but I prefer my misconceptions to be corrected :)

I think I finally figured out where we are getting our wires crossed. My mental model of T in MVector{N,T} was either isbits immutable, or mutable. So the case in interest is an MVector{T} where T is mutable, i.e. a mutable type MVector with an immutable field of Tuple (comprising of a memory-consecutive list of pointers?) which has mutable fields of type T. The immutable I was referring to was definitely the Tuple, not T. The code I've got attempts to update the references/pointers to mutable T and I now fully appreciate that quite possibly won't work the same for non-isbits immutable T.

I guess I think of non-inline immutables as anomalies that will go away in Julia v0.6 (fingers crossed). I'm happy not to support them for now. Some responses:

Definitely true on the stack.

What do you mean? On the stack or not is totally irrelevant. Whether it is inlined into mutable object is.

Right. Inlined == T is isbits immutable == T would be on the stack if it is a variable in a function, unless it is a global const immutable, in which case it appears to be unboxed on the heap. I can get a pointer to the latter but never the former. I think this fact is an implementation detail rather than anything else.

and according to your statement, I must only replace entire tuples since each is "immutable memory that is allocated for an immutable object", and never mutate their elements.

No this is NOT what I'm saying. For isbits type, the immutable type is inlined into mutable memory, which is why mutating it is OK. This is what JuliaLang/julia#17115 is all about.

This idea must generalize to mutables with immutable fields,

Not in general. Again, only when the immutable field is inlined.

because (a) it would be super weird if Array was special and

Therefore you can't do that when the immutable object is not inlined into the array either.

(b) those fields can always be mutated in practice

For non-inline object the memory holding the immutable object is never mutated. Only the reference to the memory (the pointer stored in the field).

and I would say consequentially we should not be trying to maintain their immutability when they live on the heap like that.

Only when inlined.

I think here I'm talking about isbits immutables and mutables, and you're talking about non-isbits immutables. :) Does that seem right?

(e.g. you can pass a pointer to the mutable to a C function)

FWIW, this is a really bad way to tell if it's okay to mutate the memory. You can generally pass pointers to immutable memory using Any ccall parameter type but that's a contract that the called code understands julia and won't do things that violate the julia semantics, including not mutating immutable memory.

I assume using Any will return a pointer to a Julia box on the heap, right? I'm trying to avoid allocations, and I can't ccall a pointer to the stack frame of an isbits immutable. (as an aside, I want to use mutating C functions to instantiate an SVector on the stack of a Julia function, but this seems impossible. I could do it with extra C functions or hand-written llvmcall but I'd still probably have to copy the stack frame object unnecessarily at least once). I agree that this a bad way to tell if its "okay" by the language standard but Julia is young language with a history of quite successful and useful hacks (I always think of FastAnonymous.jl) that were probably only possible due to unintended implementation details.

As an unrelated piece of information what you might need to know before hitting it yourself, it is undefined if you creates an actual array from the memory belongs to a non-array object (i.e. call unsafe_wrap on a pointer you get from pointer_from_objref) and julia will actually return the wrong result if you do it that way. I didn't check if you are doing it, just mentioning it.

OK now you have really piqued my interest. I was considering this kind of thing for the future. What is going on here?

Thanks again for all the information! :)

[andyferris]

Also, to be clear, what I'm not trying to do is update the memory references in SVector{N,T} for mutable (or non-isbits) T, which would clearly violate the immutability contract.

[yuyichao]

immutable field of Tuple

The field is mutable in that the you can reassign the field. The object referenced by/stored in the field is not. This is possible to guess what you mean but it's confusing.

I guess I think of non-inline immutables as anomalies that will go away in Julia v0.6 (fingers crossed).

There will still be cases a immutable can't be inlined.

Right. Inlined == T is isbits immutable == T would be on the stack if it is a variable in a function, unless it is a global const immutable, in which case it appears to be unboxed on the heap.

No. It is not necessarily unboxed on the stack and it's not unboxed on the heap as const global. It's NOT OK to overwrite the memory of a global const immutable since it's nothing different from any immutable object.

I can get a pointer to the latter but never the former. I think this fact is an implementation detail rather than anything else.

You get a pointer to both with pointer_to_objref, which is unsafe to use in either case.

I think here I'm talking about isbits immutables and mutables, and you're talking about non-isbits immutables. :) Does that seem right?

I'm talking about immutable objects in general. You can't overwrite the memory owned by a immutable object. A immutable object inlined into another (possibly mutable) object (or array if it matters) doesn't own the memory.

I assume using Any will return a pointer to a Julia box on the heap, right?

I'm talking about function argument, not return value.

I agree that this a bad way to tell if its "okay" by the language standard but Julia is young language with a history of quite successful and useful hacks (I always think of FastAnonymous.jl) that were probably only possible due to unintended implementation details.

FastAnonymous.jl is reasonably defined. Direct memory access bypassing julia's runtime is totally different.

OK now you have really piqued my interest. I was considering this kind of thing for the future. What is going on here?

Arrays are not allowed to alias memory of normal object, that's all.

[yuyichao]

Also, to be clear, what I'm not trying to do is update the memory references in SVector{N,T} for mutable (or non-isbits) T, which would clearly violate the immutability contract.

FWIW, I never talked anything about your SVector. I'm only talking about the code Jameson linked above which is the setindex! of MVector.

[c42f]

So to summarize, this isn't fixable, except by replacing the MVector's data with an entirely new tuple with the associated ith element swapped out. Why don't we just do that? MVector will presumably then be quite slow for non-isbits, but do we care about this for any use case right now?

Presumably JuliaLang/julia#17115 or something equivalent will then come along make all this just work nicely.

[timholy]

For reference, a safe way to update individual elements in an immutable is to replace the entire immutable. One might hope that LLVM might generate optimized code that does the equivalent of your unsafe manipulation when it can prove that it will cause no harm to do so.

Example:
https://github.com/JuliaImages/ImagesCore.jl/blob/5a01eb2119d275a0eeff888aded02165ce2066a9/src/colorchannels.jl#L82-L89
https://github.com/JuliaImages/ImagesCore.jl/blob/5a01eb2119d275a0eeff888aded02165ce2066a9/src/colorchannels.jl#L312-L340

For obvious reasons, this has non-optimal performance, but that might not affect you here.

[andyferris]

OK, all this is rather interesting and I confess I need some more time to digest it all. But thank you everyone for all the responses.

I'm a little confused why if I could replace an entire tuple I couldn't replace just one item as an optimization, except for the possibility the the GC isn't built to expect that to ever happen (or that codegen might possibly make an optimization that is inconsistent with the change, but as far as I've seen codegen doesn't make many assumptions about things on the heap). A Ref{Tuple} seems to be just a reference to some memory that stores a tuple - but I have a very C way of thinking of things. It suffices to say at minimum that the existing code "sometimes works" but it is clear that we need to disable it in case it sometimes doesn't (I'd also love to see a real-world example and an explanation of precisely what goes wrong).

There will still be cases a immutable can't be inlined.

Bugger. In the case all types/fields were concrete, I was expecting them to work like C-structs (immutables) or pointers to C-structs (mutables).

[yuyichao]

I'm a little confused why if I could replace an entire tuple I couldn't replace just one item as an optimization,

What's the confusion? The GC is irrelevant here. The single most important property is the type layout, i.e. whether the tuple is inlined (in another word, which heap box owns the memory)

A Ref{Tuple} seems to be just a reference to some memory that stores a tuple

This is essentially meaningless. Any object is a reference to some memory, even isbits immutables. They can be optimized to not be if the compiler can prove that's find to do and the optimization is irrelevant here.

as far as I've seen codegen doesn't make many assumptions about things on the heap

It does all the time.

I was expecting them to work like C-structs (immutables) or pointers to C-structs (mutables).

You can't have recursive inlined struct in C either.

[yuyichao]

I'm a little confused why if I could replace an entire tuple I couldn't replace just one item as an optimization,

And in another word, for non inlined tuple when you replace the tuple you replaced the pointer that reference the tuple. When you replaced an element you mutate the tuple itself. They are completely different and these are not optimizations.

[andyferris]

Hmm... I think I've had an insight: the first thing in your mind is the mutable/immutable reference model while the optimizations to the stack, allocations to the heap, and so on are just optimizations. Whereas I'm still thinking like a C/C++ programmer, and pretending as if Julia is using pointers and stack allocated objects as its way of implement mutable and immutable things, because I spend a lot of time staring at @code_llvm/native (and since a lot of my work is performance critical I never want to see any abstract types or unnecessary allocations or pointer-chasing).

Still, aren't the suggestions in JuliaLang/julia#17115 and JuliaLang/julia#11902 all about mutating fields in a chain of things where something is immutable and something is mutable? Like changing one element of a ref of a tuple?

[yuyichao]

Still, aren't the suggestions in JuliaLang/julia#17115 and JuliaLang/julia#11902 all about mutating fields in a chain of things where something is immutable and something is mutable? Like changing one element of a ref of a tuple?

Yes, and those are impossible with non-inlined immutables

[yuyichao]

Whereas I'm still thinking like a C/C++ programmer, and pretending as if Julia is using pointers and stack allocated objects as its way of implement mutable and immutable things,

That's fine. But please pay attention to when I said inlining and discuss based on that. A inlined field is just like a struct in C, a non-inlined one is just a pointer.

[andyferris]

Okay, now I'm wondering what is a good way forward. I can think of several options. Let's say for the moment I want to support T as isbits immutable or as a mutable and skip the non-inlined immutables for the moment in case they add unnecessary difficulties. If T is isbits immutable, then it is safe to ignore the immutability contract on the tuple and just go and replace the required element. To all intents and purposes it's as-if we had replaced the entire tuple, which is always allowed. But for mutable T, we could:

1. Just replace the entire tuple. It will be slow.

2. Attempt for a similar optimization as the isbits case and do everything necessary to trick Julia into thinking we have replaced the entire tuple. I'm not sure if this is just implementing the GC write barrier, or if this is impossible because of assumptions in codegen about immutable memory. I am fully aware that this is a complete hack and would need to be updated as Julia changes (we are only targetting v0.5 with StaticArrays)

3. This one @vtjnash really won't like: implement MVector with a generated type (RFC: staged / meta / generated types ? JuliaLang/julia#8472). If we have a mutable type with N distinct fields (where N is a type parameter) then Julia can already handle replacing just one of those, independent if they are mutable, isbits, etc. The SVector takes advantage of the fact that there is one type in Julia with variable numbers of fields, and that is Tuple, but since there is no mutable version of that we might need to implement our own type with variable numbers of fields. This is currently blocked by Regression: Can't make a generated type in v0.5, but I can in v0.4 JuliaLang/julia#16806

4. Implement in Base Julia a "mutable tuple" which allows us to have N fields which can be changed individually (and maybe future optimizations could be targeted at getting this onto the stack where it's OK to do so).

5. Use malloc, RefArray, finalizers and/or some other combination of partially manually managed memory or pointer usage. Probably adds an extra indirection for the isbits(T) case.

6. Have MVector only support isbits immutables.

Any opinions on which ones are possible/preferable?

You can't have recursive inlined struct in C either.

Can we do that in Julia? In C/C++ the recursion is achieved via a pointer/reference field, right?. I assumed I would need a Ref in Julia for the same reason.

[yuyichao]

Only 1 and 5 are options. None of the others are.

Can we do that in Julia?

No, that's why there's always something that's not inlineable.

I assumed I would need a Ref in Julia for the same reason.

No that's totally irrelevant.

[andyferris]

Only 1 and 5 are options.

While a little unadventurous, it may have to do for now.

None of the others are.

If you consider a multiple-year timescale as Julia evolves I suspect we can do a good MVector and things like option 3 and even option 2 might appear (edit: I see there are two number 2's in my list... I meant the latter). Or perhaps you guys will come up with even better things. :)

[andyferris]

I've made a commit that disables this completely, for now.

Does anyone here want to use the non-isbits case, even if it is a bit slow? It would just be another @generated function, so not too hard.

One thing I do plan on doing is make map!, broadcast!, A_mul_B! all work by constructing the tuple on the stack and copy it back over. It will be interesting to measure how this affects runtime on isbits element types (there can always be a switch).

[Jollywatt]

Does anyone here want to use the non-isbits case, even if it is a bit slow?

FWIW, I wanted to do this today.

What’s the status, six years on? It seems innocent enough to expect…

m = MVector(1, 2, missing, 4)
m[3] = 3

to work. Alas, it doesn’t, and I followed the comment in the source code to this issue.

---

P.S. I was able to get around this and move on by doing:

m = MVector(1, 2, missing, 4)
m = setindex(m, 3, 3) # makes a copy

since I wasn’t too worried about making a new copy.

[andyferris]

Without an ABI for unions or GC-managed references similar it's difficult to support this in a package without possibly invoking undefined behavior resulting in bugs. One thing that might be useful is if Julia exposed "mutable tuples" and we could build on those.

@Jollywatt note that if you are using static arrays in a specific & known context (where you know the length of the arrays) you can create your own mutable FieldVector as a mutable struct and everything would work perfectly fine. This is more a limitation of parametrically sized Tuple-backed MVectors. (Creating a subtype of StaticArray, similar to any AbstractArray, isn't actually very hard).

[PatrickHaecker]

Only 1 and 5 are options. None of the others are.

@yuyichao would you please be so kind to explain why the third option does not work? Or was that a limitation of an older Julia version and is not relevant anymore?

[andyferris]

It's the opposite. When the Julia compiler was very simple (Julia 0.4 maybe? Or 0.3?) you could get it to create new types during the code generation phase. This was never officially supported, but was a really fun hack :)

Since then, the compiler does more, especially in terms of caching work that is already done for fast recompilation while keeping everything neatly up-to-date when a definition changes, in a series of self-consistent "worlds". However, the system doesn't allow (because it doesn't make sense) to inject a new type when compiling in existing world (since new types more-or-less define the new world) so the "hack" won't (and can't) work.

These days I favour adding a mutable tuple (like a tuple but with mutable fields and invariant type parameters). It would be a fair bit of work to introduce a new fundamental datatype to Julia though (like the recent Memory) and might not be deemed worth the effort.

[PatrickHaecker]

Thanks for the answer, @andyferris.

These days I favour adding a mutable tuple (like a tuple but with mutable fields and invariant type parameters).

Indeed, mutable inline structs and mutable tuples seem to be the two missing basic data structures.

However, the system doesn't allow (because it doesn't make sense) to inject a new type when compiling in existing world

But does it need to be in an existing world? At least for a static type, this seems to set the bar too high, as other types are typically defined in global space as well. While the new memory type would be the cleanest solution, I am currently experimenting with something along these lines:

using StaticArrays

abstract type WritableVector{N, T} <: FieldVector{N, T} end

macro define_wvector(N)
    :(mutable struct $(Symbol("WVector", N)){T} <: WritableVector{$N, T}
        $(Expr(:block, (:($(Symbol("_", i))::T) for i in 1:N)...))
    end) |> esc
end

@define_wvector 16

a = 101:116 .|> Int8 |> WVector16

julia> a[13]
113

julia> a[13] = Int8(2); a[13]
2

Granted, this does not avoid using the reference for non-isbits types, but @cstjean's macro might pave the way for a workaround.
But even without that, I think, that the issue of this ticket could be solved in principle. Maybe I miss something – but I understood that @yuyichao's comment was probably referring to something else. Continuing the code from above and using Ref as a simple non-isbits type:

b = 101:116 .|> Int8 .|> Ref{Int8} |> WVector16

julia> b[13]
Base.RefValue{Int8}(113)

julia> b[13] = Ref{Int8}(2); b[13]
Base.RefValue{Int8}(2)

If this works, maybe we do not need a mutable tuple, but could benefit from an NStruct as an optimization of a struct similar to NTuple vs. Tuple ;-).

Do you have benchmarks which can be used to compare a WVector with an MVector? The scaling behavior would be especially interesting.

[andyferris]

Yes - that is a perfectly cromulent approach. I believe older packages like ImmutableArrays.jl and FixedSizedArrays.jl did stuff like this.

Honestly it probably has fewer downsides than the current MVector. When originally writing this one goal was to get rid of the "artificial" bounds on large N. Conversely, this expands the bounds on valid T while reducing the range of valid N.

We'd really have to confer with the various communities (including autodiff) to see whether this is a realistic approach for them.