That isn’t “without allocating”
Right, this right there is what’ll break down on the julia side, without reaching for Ptr or RefArray yourself or having it be Any[]. To the compiler this may not be a safe operation, especially since a priori you don’t know whether the element type is stored inline or not, which you’d have to branch on in your reinterpreting/casting code. As such, it only works in this contained example because you’ve specified an int* and float* - keeping this as generic in julia as you’ve described would require more or less a void* input in C, I think.
I think this problem only comes from wanting to reuse the memory for potentially differently typed “buffers”, across different sorting routines, without knowing the types of the elements ahead of time. Do you have an example for such a sorting routing I could take a look at, to maybe help translate it to julia & integrate it with this approach (or finding a suitable replacement)?
1 Like
I think we’re not using the same terms here. If you were already using a vector of pointers, then you wouldn’t be getting an error when reinterpreting:
julia> A = Array{UInt8}(undef, 40);
julia> B = reinterpret(Float64, A) #This is fine
5-element reinterpret(Float64, ::Vector{UInt8}):
2.3142688836e-314
2.3142688915e-314
2.3142688994e-314
2.3142689073e-314
2.3142690654e-314
julia> B = reinterpret(Vector{Float64}, A) # This will never work
ERROR: ArgumentError: cannot reinterpret `UInt8` as `Vector{Float64}`, type `Vector{Float64}` is not a bits type
Stacktrace:
[1] (::Base.var"#throwbits#294")(S::Type, T::Type, U::Type)
@ Base ./reinterpretarray.jl:16
[2] reinterpret(#unused#::Type{Vector{Float64}}, a::Vector{UInt8})
@ Base ./reinterpretarray.jl:40
[3] top-level scope
@ none:1
julia> B = reinterpret(Ptr{Float64}, A) # But this is fine again
5-element reinterpret(Ptr{Float64}, ::Vector{UInt8}):
Ptr{Float64} @0x0000000117323010
Ptr{Float64} @0x0000000117323020
Ptr{Float64} @0x0000000117323030
Ptr{Float64} @0x0000000117323040
Ptr{Float64} @0x0000000117323180
Which you would then use like
julia> some_vector = [3.141592, 1.0, 2.0, 3.0]
4-element Vector{Float64}:
3.141592
1.0
2.0
3.0
julia> B[1] = pointer(some_vector)
Ptr{Float64} @0x00000001164b1780
julia> recovered_vector = Base.unsafe_wrap(Array, B[1], 4)
4-element Vector{Float64}:
3.141592
1.0
2.0
3.0
Though note that now you need to keep track of all the details like the length of some_vector, just like you would in a lower-level language
I’m okay with reaching for Ptr.
For example, this is almost what I’m looking for
julia> w = Vector{UInt8}(undef, 64);
julia> function loose_reinterpret(T::Type, x::Vector{UInt8})
unsafe_wrap(Vector{T}, Ptr{T}(pointer(x)), length(x) ÷ Base.aligned_sizeof(T))
end
loose_reinterpret (generic function with 1 method)
julia> r = loose_reinterpret(Vector{Int}, w);
julia> length(r)
8
julia> r[1] = []
Any[]
julia> eltype(r)
Vector{Int64} (alias for Array{Int64, 1})
julia> r[1]
Int64[]
julia> r[2] = [1,2]
2-element Vector{Int64}:
1
2
julia> r[2]
2-element Vector{Int64}:
1
2
julia> r[1]
Int64[]
I just need to worry about w getting garbage collected and I don’t want to have to deal with @gc.preserve whenever I pass r around.
Is there a particular reason the workspace = eltype(eltype(things_to_sort))[] (or Vector{eltype(eltype(things_to_sort))}[]) approach I proposed above won’t work? It seems MUCH safer to me than forcing the use of unsafe_wrap, just to avoid a single allocation (which you’ll have to do anyway, due to the need for resizing that vector).
Well, you won’t get around that as soon as you use pointers though. That’s literally the reason GC.@preserve exists, to make sure the garbage collector doesn’t free memory we still have a live pointer to. You can’t easily have r escape out of the function you allocated w in for example, since GC.@preserve does not cover objects that are returned. At the very least, you’ll always have to carry w around everywhere you decide to move r to. You can’t ever seperate them (except by GC.@preserve, but that only works deeper into the callstack, not up). Frankly, I’m not even 100% sure resizing w through r is legal, which you’d require to do in your inner routines, correct?
I really do think you’re making things harder for yourself than they have to be, by seemingly trying to 1:1 translate some C implementation to julia. The semantics are just different and, in contrast to C, we do have a more powerful type system to help us out here. I don’t think avoiding GC is the right solution here.
Maybe I’m still confused about why this reinterpreting of an opaque block of memory is required for the sorting algorithm itself to work though. Seems to me that’s just a C-side implementation detail, to silence the compiler a bit about type safety.
If all we want is a certain amount of memory, it seems more natural to store that as a Vector{UInt8} than as a Vector{T} where T is different for every sorted eltype.
FWIW I’m using this to develop Julia’s base libraries and have never written or seen anything similar in C until you asked me to translate this concept to C.
Thanks for your help.
1 Like
Ah, but what you’re asking for is not just a certain amount of untyped memory, is it? You actually do want type safety, to ensure performance stays up - I don’t think you’re getting around that, or with going waaay over the top and circumventing GC entirely and doing everything with pointers (which at the very least requires a switch based on whether the elements are stored inline or not).
As a followup to #45330, right?
The reason I’m asking is that I’m not aware of actually having a sorting function in Base that sorts the vectors inside a vector, not to mention one that shares allocated workspace between each individual sub-sorting. So I’m kinda curious what the motivation for this particular application of an untyped workspace is, since it seems kind of niche to me. Users of sort! generally know the types of objects they want to sort, after all. I don’t think they’d expect to be able to reuse a workspace across invocations of sort!.
One option would be to use a struct for the explicit purpose of exposing the “raw data” through a safe type, which presents its memory differently based on what you convert it to. The struct would hold onto the raw UInt8[] and handle all the pointer/storing operations for you, depending on a type parameter.
You’re welcome! Always happy to rubberduck a tricky problem.
Exactly, that is what I was thinking of.
Here’s a prototype:
struct Workspace5{T} <: AbstractVector{T}
data::Vector{UInt8}
wrapper::Vector{T}
function Workspace5(T::Type, data::Vector{UInt8}, len::Integer)
#length(data) < len*Base.aligned_sizeof(T) && error("Insufficient underlying data")
new{T}(data, unsafe_wrap(Vector{T}, Ptr{T}(pointer(data)), len))
end
end
function Workspace5(T, ::Nothing, len::Integer)
data = Vector{UInt8}(undef, len*Base.aligned_sizeof(T))
Workspace5(T, data, len)
end
function Workspace5(T, ::Workspace5, len::Integer)
length(w.data) < len*Base.aligned_sizeof(T) && resize!(w.data, len*Base.aligned_sizeof(T))
Workspace5(T, w.data, len)
end
Base.size(w::Workspace5) = size(w.wrapper)
Base.@propagate_inbounds Base.getindex(w::Workspace5, i::Int) = getindex(w.wrapper, i)
Base.@propagate_inbounds Base.setindex!(w::Workspace5, v, i::Int) = setindex!(w.wrapper, v, i)
Usage:
julia> w = Workspace5(Float64, nothing, 3)
3-element Workspace5{Float64}:
0.0
0.0
0.0
julia> w2 = Workspace5(Int, w, 3)
3-element Workspace5{Int64}:
0
0
0
julia> w3 = Workspace5(Char, w2, 17)
17-element Workspace5{Char}:
'\0': ASCII/Unicode U+0000 (category Cc: Other, control)
'\0': ASCII/Unicode U+0000 (category Cc: Other, control)
'\0': ASCII/Unicode U+0000 (category Cc: Other, control)
'\0': ASCII/Unicode U+0000 (category Cc: Other, control)
⋮
'\0': ASCII/Unicode U+0000 (category Cc: Other, control)
'\0': ASCII/Unicode U+0000 (category Cc: Other, control)
'\0': ASCII/Unicode U+0000 (category Cc: Other, control)
julia> w4 = Workspace5(Vector{Int}, w3, 2);
julia> w4[1] = [1,2,3]
3-element Vector{Int64}:
1
2
3
julia> w4[2] = []
Any[]
julia> w4
2-element Workspace5{Vector{Int64}}:
[1, 2, 3]
[]
Yes, something like that. I’d combine the constructors, to ensure your invariants hold and to make using it a little easier - no need for the explicit Nothing dispatch:
struct Workspace{T}
data::Vector{UInt8}
wrapper::Vector{T}
function Workspace{T}(len, data=Vector{UInt8}(undef, len*Base.aligned_sizeof(T))) where T
div(length(data), len) != Base.aligned_sizeof(T) && throw(ArgumentError("Backing buffer too small")) # or resize!
new{T}(data, unsafe_wrap(Vector{T}, Ptr{T}(pointer(data)), len))
end
end
function Workspace{T}(len, w::Workspace) where T
length(w.data) < len*Base.aligned_sizeof(T) && resize!(w.data, len*Base.aligned_sizeof(T))
Workspace{T}(len, w.data)
end
# further array wrappers...
To me at least it feels a bit cleaner to just specify the type parameter, like for Vector. The outer constructor may need some form of explicit ownership transfer off of the original Workspace data - wouldn’t want to have two live Workspace objects actually referencing the same exact memory 
Writing the above also felt a lot like a potential Buffer{T} type that e.g. @tkf and I think @jameson are thinking about. There are some notes in the multithreading BoF from May 4th, but nothing concrete yet I don’t think. At least at its core this feels very much like the sort of problems that type could encounter as well.
Either way, here’s an example of the kinds of problems I was thinking of with my comments about explicitly having to model the Ptr{T} and doing the (un)marshaling yourself:
julia> struct A
s::String # to force this struct to not be allocated inline
end
# works?
julia> w = Workspace{A}(5)
Workspace{A}(UInt8[0x20, 0x2b, 0xe2, 0xeb, 0x90, 0x7f, 0x00, 0x00, 0x50, 0x43 … 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00], A[A(Nothing), A(Any), #undef, #undef, #undef])
# horribly dies, due to the memory layout not being valid for `A` when accessing that in any way, i.e. no printing of this data allowed, at all.
julia> w = Workspace{A}(5)
Workspace{A}(UInt8[0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x77 … 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00], A[#undef, A(Core.Compiler.NewNodeInfo[]), A(
signal (11): Segmentation fault
in expression starting at none:0
sig_match_fast at /home/sukera/julia/src/gf.c:2411 [inlined]
sig_match_fast at /home/sukera/julia/src/gf.c:2402 [inlined]
jl_lookup_generic_ at /home/sukera/julia/src/gf.c:2491 [inlined]
ijl_apply_generic at /home/sukera/julia/src/gf.c:2570
_show_default at ./show.jl:465
show_default at ./show.jl:448 [inlined]
show at ./show.jl:443 [inlined]
show_delim_array at ./show.jl:1276
...
That particular segfault may be mitigated by using zeros(UInt8, len*Base.aligned_sizeof(T)) and making sure any resized vectors are zeroed as well, but there are bound to be more like this.
Those errors are fine. These buffers should never be read without writing first. (See my example usage above where I write to before reading when T = Vector{Int64}).
My style here was to match the stuff already in Sort.jl, where an explicit Nothing is helpful, but I plan to revise the interface as well.
I’m glad to hear that other people are looking for this same concept! Hopefully, there can be some reuse.
I’ve implemented it in Sort.jl, if you’d like to take a look
1 Like
“Don’t read without writing” is an invalid precondition that you are forbidden from expressing in Julia. It will not be preserved by the runtime (with or without optimizations) and will be modeled as undefined behavior (in optimizations) to be replaced with garbage or deleted. There are a large number of problems with this approach, which is why reinterpret tries to forbid it.
1 Like
Sorry, I’m having a hard time understanding. When I say don’t read without writing, I mean it in the same sense as you shouldn’t read from a Vector{Int}(under, 10) without writing to it first. It’s initialized to gibberish.
I would be using Workspace like this:
struct Workspace{T} <: AbstractVector{T}
data::Vector{UInt8}
wrapper::Vector{T}
function Workspace(T::Type, data::Vector{UInt8}, len::Integer)
length(data) < len*Base.aligned_sizeof(T) && resize!(data, len*Base.aligned_sizeof(T))
new{T}(data, unsafe_wrap(Vector{T}, Ptr{T}(pointer(data)), len))
end
end
workspace(v::AbstractVector, ::Nothing, len::Integer) = similar(v, len)
workspace(v::AbstractVector, data::Vector{UInt8}, len::Integer) = Workspace(eltype(v), data, len)
Base.size(w::Workspace) = size(w.wrapper)
Base.@propagate_inbounds Base.getindex(w::Workspace, i::Int) = getindex(w.wrapper, i)
Base.@propagate_inbounds Base.setindex!(w::Workspace, v, i::Int) = setindex!(w.wrapper, v, i)
floats = rand(100)
vectors = [rand(Int, 7) for _ in 1:48]
w = UInt8[]
w_floats = workspace(floats, w, 50)
merge_sort!(floats; workspace = w_floatss)
w_vectors = workspace(ints, w, 24)
merge_sort!(vectors; workspace = w_vectors)
Is there some unintuitive behavior that would take place here?
Again, I’m having a hard time understanding what those problems actually are. Would you give a few examples?
1 Like
The garbage collector is basically mark-sweep, which in the case of a Vector basically means it will read all the objects it contains in order to mark them. If the memory representation of the vector is garbage, you’re basically dereferencing garbage pointers, which is bad!
Since the GC is allowed to run at any time, semantically there is no such thing as an unread array.
It might be that zeroing the memory first means that all the elements are #undef but that’s an implementation detail.
You can use the Ptr{T} directly to reference some elements instead of wrapping it as a Vector{T} but you will need to ensure the items are also stored somewhere else so that they aren’t GC’d prematurely.
3 Likes
Thanks so much for that explanation!
Zeroing the memory in the case of non-is-bits-type T sounds like a good idea. If we don’t want to rely on it, we could also use unsafe_store!(Ptr{T}(pointer(data)), x, i) before constructing the unsafe_wrap.
The alternative you propose sounds great, but I can’t figure out how to deal with
without allocating a whole new array for them.
1 Like
If you want this to work for arbitrary T then I think you’re doomed because Julia can use some funky non-contiguous memory layouts.
For example, a Vector{Union{Int, Nothing}} is represented in memory as a block of Int values followed by a block of Bool values identifying which items are actually nothing. So the value of a single item in the vector is spread over two locations in memory. This is all implementation detail of course.
This means that unsafe_load(::Ptr{Union{Int,Nothing}}) throws an error (and unsafe_wrap).
I think you need your user-supplied buffer to be a Vector{T} from the start.
3 Likes
This, combined with
is what I was trying to say above! I still think a Vector{Ref{T}} could work, provided the references are all individually initialized properly and not just reinterpreted/wrapped from existing memory. For that case though, you might as well use a Vector{T}.
1 Like
How would a Vector{Ref{T}} work?
Nevermind, it does not - same limitations as any other non-inline-allocated type. I thought we could get around that, since Ref{T}() is a valid thing to have, to fill later on. It would then have to be Ref{Any} again, which defeats the purpose of trying to make it type stable.
2 Likes