Get rid of reinterpret in its current form

[Keno]

I don't like the way reinterpret is currently implemented. It puns on the notion of an array. One problem we recently had to deal with is that alignment guarantees are different between different types (those are now disallowed). Another is that it prevents us from doing more strict TBAA on array element types. I think we should get rid of reinterpret completely and replace it with a ReinterpretArray type, who's getindex method performs the appropriate load from the original array. That way we never have an Array with incorrectly typed storage, but can retain the convenience (and once again allow reinterpret for types with mismatched alignment).

[vtjnash]

I think the issue we have is that we allow reinterpret to cast between types that a method like ReinterpretArray couldn't. For example, between structs and bytes (allowing it to observe padding bytes and alignment, for example).

However, do we still need that capability in general? In the parts of the IO system that used to use this, I've largely switched them to using Ref and doing unsafe_ byte IO (by casting to a Ptr{UInt8}) and recommending marking them noinline (for both the gc-root and as a TBAA barrier).

[Keno]

I'm fine with implementing ReinterpretArray's getindex by copying out enough elements to on-stack storage and then reinterpreting there. LLVM will fold any unnecessary copies easily enough. My only problem is with Array here.

[vtjnash]

Right, but how would you express that? Currently we don't allow any sort of struct-type-punning in reinterpret for values, just for Arrays (as a special case).

If copy the elements to stack, wouldn't that still imply that the source and destination TBAA are different, inhibiting optimization around it (since LLVM doesn't have a TBAA union type)?

[Keno]

The fact that source and destination TBAA can't be different is a limitation of the current memcpy implementation, not of the underlying semantics. I plan to fix that. That's an optimization however. The reinterpret changes would be breaking and would have to be done pre-1.0.

[lobingera]

So do you mean to change the implementation of reinterpret, or the syntax?

[Keno]

implementation. But the return type would change, so it's breaking.

[lobingera]

Then i'd like to see a better motivation than "I don't like the way reinterpret is currently implemented."

[Keno]

It's in the original post. It violates alignment guarantees (so you now get errors unless you know about alignment issues) and it prevents us from strengthening TBAA.

[iamed2]

I would love to see this. As a user I appreciate this interface.

[vtjnash]

Cross-ref additional issues with reinterpret: #16652

[StefanKarpinski]

What about this API:

• you can declare an alighnment for an array when you create it
• alignment can be computed from a given set of element types
• you can reinterpret to any element type for which an arrays alignment is valid

This requires a little forethought but it should be doable.

Another possible API for when that's not possible is to extract elements of a different type from an array without reinterpreting it, as if it had a different element type. That would potentially be slow of the alignment disagrees, but it wouldn't be wrong at least. We can have both as they're somewhat complementary.

[yuyichao]

you can declare an alighnment for an array when you create it

Will this be in the type or in the value?

[StefanKarpinski]

One should also be able to query the maximal alignment of an array.

[yuyichao]

• you can declare an alighnment for an array when you create it
• alignment can be computed from a given set of element types

I'm still confused by what you mean. Do you mean the alignment is determined by the array or the eltype?

[StefanKarpinski]

The alignment would have to be a property of the array. The original element type would determine the minimal alignment that an array must have, but the idea is that you could request coarser alignment if you know it's going to be needed. Something like this:

a = Array{UInt8}(n)
b = reinterpret(UInt128, a) # illegal

a = Array{UInt8}(2^20, alignment=128)
b = reinterpret(UInt128, b) # legal

For the second suggestion, I had something like this in mind:

reinterpret(UInt128, a, i) # reinterpret(UInt128, a)[i] but legal

Keno's idea of having a ReinterpretArray that can deal with misalignment issues is essentially a wrapper type that does that via a wrapper instead. Perhaps that's better anyway. We are increasingly moving away from arrays invisibly sharing memory and toward them explicitly sharing memory by having one array type wrap another. Of course reshape on Arrays still does the invisible memory sharing thing. But we have Base.ReshapedArray for cases where that can't work.

[vtjnash]

I should perhaps clarify that Yichao is "confused" because it is utterly useless to have alignment be part of the data. We can already compute the information for free from the pointer itself. However, only alignments that are guaranteed at compile time (for various combinations of register types and hardware) are performant. Everything else (especially testing for runtime alignment properties) is potentially a substantial performance penalty.

[yuyichao]

It's not really useless since the concern of not allowing accidentally aligned array to be reinterpreted is that it'll hide the errors until someone get's unlucky. If the property has to be explicitly specified this won't be an issue anymore.

That said, such an object-specific property will make shift!/unshift! much more expensive (for aligned arrays) and it seems that all what it can do is already covered by a ReinterpretedArray backed by reinterpret(T, a, i) so it doesn't really seem necessary.

[StefanKarpinski]

The point is to make it possible to allocate an array of one size in a way that can be safely reinterpreted later to a larger size – which we can currently only do by allocating in the bigger size first and then reinterpreting the other way. There are no runtime checks on element access since you never allow an array to be reinterpreted to a size that's not safe and pre-requested. There is a runtime check on reinterpret, but that doesn't matter.

The ReinterpretedArray approach seems fine if one only cares about element access performance for Arrays but not for ReinterpretedArrays – which may not always be the case. Of course, maybe that's good enough, since you can always do copy(reinterpret(T, a)). But that forces copying the entire array. We might want a way to realign an array in place, which can be done shifting an array in-place in memory, after which it can be efficiently accessed via two different sizes until someone does a shift! or unshift! operation in the smaller size.

[Keno]

Accessing a non-reinterpreted array should in all cases be preferred to the reinterpreted case, performance tradeoff wise. LLVM will do a fine job folding everything to give decent performance with the ReinterpretedArray approach as well.

[StefanKarpinski]

LLVM will do a fine job folding everything to give decent performance with the ReinterpretedArray approach as well.

How is that possible? You're still accessing an array with the wrong alignment? If this were no slower why would we bother insisting on alignment in the first place? Or by "decent performance" do you mean, not optimal, but as good as one can get with potentially misaligned storage?

[Keno]

Or by "decent performance" do you mean, not optimal, but as good as one can get with potentially misaligned storage?

Yes, which is really the best you can hope for without pessimizing everything else.

[StefanKarpinski]

Decided: we're going to do the ReinterpretedArray thing.

[Keno]

Note to self: get rid of this as part of this: https://github.com/JuliaLang/julia/blob/master/base/bitarray.jl#L292

[mschauer]

For myself, and maybe others with the same initial reception of this:

• TBAA is "type-based alias analysis", https://en.wikipedia.org/wiki/Alias_analysis
• If two variables of different types cannot share the same memory location simultaneously, code can optimised in a different way.
• The old reinterpret implementation breaks this, its existence prevents those optimisations and makes thus completely unrelated code slower.