In the talk “What’s Bad in Julia” from JuliaCon 2019, one thing briefly mentioned from 4:40 to 5:13 is how users cannot define new types that use the memory layout tricks of Array, String, and Symbol, which makes these types uncomfortably special [JuliaCon 2019 | What's Bad About Julia | Jeff Bezanson - YouTube].
At first I thought he meant something like how we can define primitive types, but that logic collapsed the more I thought about it. Whenever I needed a type like an array but not quite, I always made a composite type containing an array. Similarly, the documentation suggests wrapping existing primitive types in composite types instead of making new primitives.
So what sort of situations can’t be solved by wrapping these types in structs? I don’t actually know the memory layout tricks mentioned in the video, does that have something to do with this?
One thing that’s special about arrays is memory alignment.
Modern computers work by running through a list of instructions which operate on some data the CPU has loaded from RAM. Some amount of that data is cached closer to the CPU, which speeds up accessing that data. The smallest data that can be loaded is usually a so called “word”. On 64 bit systems, a word consists of 8 bytes, on 32 bit systems of 4 bytes. Each datapoint you want to load lives at some place in memory, which is addressed by a pointer (basically a fancy unsigned integer). Here’s the catch: if the data you want to load sits at an address that isn’t a multiple of 8 (or 4 in case of 32 bit), the CPU has to do a lot more work to load that data, because (usually) only multiples of 8 are addressable. In that case, the CPU has to do 2 loads and retrieve the data from the two words. The same goes for storing the data back into memory. Since julia doesn’t expose this reality of caches and memory and how computers actually work, you can’t ensure memory alignment through julias semantics. The implementation of the memory allocator julia uses is done in C, which does expose this, at the expense of it being opaque for regular julia code.
Further, some instructions can operate on more than one word at the same time or split up words into smaller chunks and operate on all of the chunks at the same time. In those cases, you want your data to be aligned to even more than 8 bytes - julia by default uses (if I recall correctly) 16 bytes. This allows for SIMD on already aligned data.
As far as I know, this is the biggest reason arrays are not done in pure julia.
I’m not a core developer and I’ve only glossed over the array.c implementation, so take what I’ve written above with a big spoonful of salt There are also a lot of details missing. It’s just something that came up when I thought about what would be needed to implement a pure julia array from scratch.
If you want to have a (small) primer on data alignment and related problems, check out the wikipedia article, it’s a fairly nice introduction (which again ignores a lot of details).
No it has nothing to do with alignment. Arrays are simply not implemented as structs with fixed number of field and that’s it. Same with String, Symbol etc.
I stand corrected! As is often the case, the best way to get the right answer on the internet is to post a wrong one and be corrected, so thank you I somehow thought manual alignment of arbitrary containertypes can’t be done in julia itself and is something the compiler/memory layouting has to take care of
Still, from a pure julia perspective without relying on array, tuple, etc. - what would Array look like? Surely, growing an Array would not be possible if it was implemented as a struct with a fixed number of fields
Right, but what would back that memory buffer? Conceptually, there has to be some mapping to actual memory at some point, which (if I recall correctly) is currently done in array.c via calls to the julia allocator (which isn’t exposed inside julia itself, as far as I’m aware).
A memory buffer would be more flexible, so it would be more flexible of an abstraction for other types to be built on as well. Then Array would just be one thing built on it, but other non-array like memory-backed objects would be able to be built.
It would essentially be a lower level interface to an allocator in a GC-aware way.
…minus a few specifics, like number of dimensions and size of each dimension. And presumably it will not pull special tricks like struct-of-arrays, leaving any such tricks to the Julia-implemented array type.
No it has to be typed. There’s no way to implement references safely in julia, or if that was possible there’ll also be no need for any struct type in julia either (which may or may not be a good thing, I doubt it, but is definitely not in the scope of a buffer type). And since it has to be typed there’s little point to implement a bitsunion layout that’s incompatible with the one we want.
Based on the conversation so far, am I right in thinking the idea is that we could have more fundamental data types using the memory layouts that Array, String, or Symbol are built on? I still can’t think of a situation where I need to have a memory buffer type instead of Array, or whatever types instead of a String or Symbol.
Maybe something that lets us intern stuff like Symbols are? Still, we already have InternedStrings, and I’ve never heard of anything besides strings being interned.
One example where current arrays are too high level for some applications is resizing. Since Arrays automatically resize, there isn’t a great way to experiment with arrays that have different growth strategies. The other part of the answer is that this is a niche feature. That’s why it hasn’t been done.
This is expected since the buffer type will be very similar to what array is as I said. String is already partially what the buffer type will look like and Symbol will almost certainly remain as is.
Just as an example, you could implement a very basic memory buffer in Julia like this:
julia> mutable struct Buf
ptr::Ptr{UInt8}
len::Int
function Buf(ptr::Ptr, len::Int)
x = new(ptr, len)
finalizer(x) do x
ccall(:free, Cvoid, (Ptr{UInt8},), x.ptr)
end
return x
end
end
julia> function Buf(len::Int)
ptr = ccall(:malloc, Ptr{UInt8}, (Csize_t,), len)
return Buf(ptr, len)
end
Buf
julia> let buf = Buf(1)
unsafe_store!(buf.ptr, 0x01, 1)
@show unsafe_load(buf.ptr, 1)
end
unsafe_load(buf.ptr, 1) = 0x01
0x01
If you want to put arbitrary Julia types into the buffer, it’s a little more complicated, since you want to make sure, you always hold a reference to all objects in the array, but you could use an IdDict, for example, to keep track of those.
The part that’s missing, though, is the ability to embed a variable-length payload inline with your struct. You’d want this for extreme performance hacking. A theoretical Julia-native Array struct looks something like this:
mutable struct Array{T,N} <: DenseArray{T,N}
data::Buffer{T} # <-- Buffer is a lower level 1-d vector type
length::Int
flags::UInt16 # some details about allocation, etc.
elsize::UInt16
offset::Int32 # <-- for vectors that got pushfirst!'ed
size::NTuple{N, Int}
@MAGIC_INLINE_BYTES[] # <-- this is sometimes where small Buffers live
end
The magic part that’s missing in Julia is that the buffer can sometimes point to an inline chunk of memory that gets allocated as part of the header. That’s a huge benefit for small objects — it means that Julia only needs to allocate one thing instead of two. It also is a benefit for usage, too, as the header is stored in memory directly adjacent to the data, allowing for more efficient caching.
As far as how this could help performance hacking, one concrete example is in Base itself. BitArray (like many custom arrays) leans on an Array as part of its implementation:
This means that when you allocate a BitArray, you’re actually allocating two or three objects. This little header definition and the header for the Vector{UInt64} (and sometimes a pointer to its data separately). It could just as easily manage the data inline itself, avoiding an allocation, ~64 bytes of overhead, and similarly improving cache locality.
If I’m not mistaken, String is special in the following ways:
It’s an immutable, yet variable length struct. E.g. it’s not possible to implement a String type backed by Vector for where "foo" === "foo". It could be possible in the future to have truly immutable variable length types.
Its underlying implementation is much simpler than Vector, and so cannot be implemented in terms of Vector. If we imagine we had the MemBuf type, I believe a String would be simply
No the String should remain as is. This implementation is much more expensive than the current one and is basically the same as the old implementation.
And this is also not going to work as is. This has to be a pointer instead and there must be no condition when accessing the array pointer. I think the hope is that if the array itself can be optimized out the inline optimization may be unnecessary.
There are also a lot of details missing. It’s just something that came up when I thought about what would be needed to implement a pure julia array from scratch.
As is often the case, the best way to get the right answer on the internet is to post a wrong one and be corrected, so thank you 
