News for hackers. Stuff that matters.
Re:Linear Address Spaces: Unsafe at any speed by dragontamer on Wednesday June 29, 2022 @05:50PM (#31926137)
> Why do we even have linear physical and virtual addresses in the first place, when pretty much everything today is object-oriented?

Well, GPU code is certainly not object-oriented, and I hope it never becomes that. SIMD code won't be able to jump between objects like typical CPU-oriented OOP does (unless all objects within a warp/workgroup jump to the same function pointers?)

GPU code is common in video games. DirectX needs to lay out its memory very specifically as you write out the triangles and other vertex/pixel data for the GPU to later process. This memory layout is then memcopy'd over to PCIe using the linear address space mechanism, and GPUs are now cohesive with this space (thanks to Shared Virtual Memory).

So today, thanks to shared virtual memory and advanced atomics, we can have atomic compare-and-swap coordinate CPU and GPU code operating over the same data (and copies of that data can be cached in CPU-ram or GPU-VRAM and transferred over automatically with PCIe memory barriers and whatnot).

----------

Similarly, shared linear address spaces operate over rDMA (remote direct memory access), a protocol built on top of Ethernet. This means that your linear memory space is mmap'd on your CPU, but then asks for access to someone else's RAM over the network. The mmap then causes this whole "inefficient pointer-traversals" to then get turned into Ethernet packets to share RAM between CPUs.

Ultimately, when you start dealing with high-speed data-sharing between "external" compute units (ie: a GPU, or a ethernet-connected far-away CPU), rather than "just" a NUMA-node or other nearby CPU, the linear address space seems ideal.

--------

Even the most basic laptop, or even Cell Phone, these days, is a distributed system consisting of a CPU + GPU. Apple chips even have a DSP and a few other elements. Passing data between all of these things makes sense in a distributed linear address space (albeit really wonky with PCIe, mmaps, base address pointers and all sorts of complications... but they are figured out, and it does work every day)

I/O devices working directly in memory is going to only become more common. 100Gbps network connections exist in supercomputer labs, 10Gbps Ethernet is around the corner for consumers. NVMe drives are pushing I/O to such high bandwidths that'd make DDR2 RAM blush. GPUs are growing more complicated and are rumored to start turning into distributed chiplets soon. USB3.0 and beyond are high-speed links that directly drop off data into linear address spaces (or so I've been told). Etc. etc.

Re:Linear Address Spaces: Unsafe at any speed by cmrdporcupine on Wednesday June 29, 2022 @08:39PM (#31927485)
Thing is that I think TFA author isn't speaking of "object-oriented" in the typical sense. I believe it's more about how the VM paging system and cache and etc. is really working with abstract segment "objects" that are blobs of memory but presented to the process as a single linear address space. I don't think the author means OO as in "Smalltalk" or "Java" [methods + objects + inheritance] but more "object based" in a more generic sense of "there's blobs of stuff with abstract handles pointing to them" that then gets painted to the process as if it's a single linear sequence of bytes when in the actual machine... it's not.
Re:Linear Address Spaces: Unsafe at any speed by roelschroeven on Thursday June 30, 2022 @04:37AM (#31930044)
Since "pretty much everything today is object-oriented" is such an important point in the article, I feel the author does his readers and himself a disservice by not defining what he means by object-oriented, especially if he uses it in a different sense than everybody else.
Re:Linear Address Spaces: Unsafe at any speed by cmrdporcupine on Thursday June 30, 2022 @10:12AM (#31932554)
Maybe. But in the OS world "object" does have an established meaning.

I think the broader point is that you can build an "object-oriented" system in the sense that you're expecting overtop of the "object-based" systems he is describing and it will give you much of the base level semantics of an OO system (object allocation, tagging, encapsulation) without enforcing any particular OO language semantics (inheritance, typing, methods, etc.) and while also allowing for non-OO (blob of memory) semantics if you need it.

Think of each C allocation via malloc/free as an object. It's just in his system the pointers that point to those allocations are not describable as a series of integer offsets into a big linear memory, but really are handles or unique IDs which map directly into the VM subsystem of the OS and to some action happening in the MMU.

In essence most object-oriented language VMs/runtimes are doing this themselves, essentially building abstract handles (object references, etc.) overtop of the "linear memory" abstraction that the OS provides. If I understand his gist he's really just talking about cutting out the middleman.

I suspect, though, that there's not really a lot of efficiency gains anyways. This path has been so heavily optimized (in both hardware and software) over the decades that it likely matters little.

The security argument maybe is more compelling. There's good argument for the concept of never being able to turn an integer into a pointer or into an integer and back again. Except this would break probably the majority of C programs out there.

Maybe the middle road is for the OS to present a sandboxed "legacy" or "emulation" environment for programs that do pointer arithmetic and to provide enhanced compilers that flag these kinds of things and encourage/offer alternatives.

Given the prevalence of virtualization tech now, there's probably more room for experimentation in this type of thing these days without breaking compat...

Re:Linear Address Spaces: Unsafe at any speed by teddyh on Thursday June 30, 2022 @09:35AM (#31932153)
Yes, see for instance the GNU C Library “obstacks” facility; It’s clearly not object-oriented:

https://www.gnu.org/software/libc/manual/html_node/Obstacks....

“An obstack is a pool of memory containing a stack of objects. You can create any number of separate obstacks, and then allocate objects in specified obstacks. Within each obstack, the last object allocated must always be the first one freed, but distinct obstacks are independent of each other.

Aside from this one constraint of order of freeing, obstacks are totally general: an obstack can contain any number of objects of any size. They are implemented with macros, so allocation is usually very fast as long as the objects are usually small. And the only space overhead per object is the padding needed to start each object on a suitable boundary.”

Re:Linear Address Spaces: Unsafe at any speed by cmrdporcupine on Thursday June 30, 2022 @09:47AM (#31932292)
I love obstacks, after a lead at a job I was at a decade ago pointed them out to me I always look for a chance to use them, but haven't really had much of a chance.

There isn't a lot of info about them though. Go hunting for performance metrics on them, or discussion of them generally and you won't find much. The glibc pages themselves don't give much justification why you would use them vs malloc, or an arena allocator, etc.

Re:Linear Address Spaces: Unsafe at any speed by kevingadd on Wednesday June 29, 2022 @10:27PM (#31928144)
GPU stuff has been "object oriented" for a long time. The ability to just arbitrarily address data as bytes from shaders is relatively new and modern and still constrained.

If you want to talk to a GPU via vulkan or d3d12 you're going to navigate a maze of descriptor sets, pipeline objects, buffers of various types, samplers, etc. These are all Objects with distinct types and data and the GPU hardware will interact with them in specific ways, even if it's also a general purpose computing device that will run some shader code you throw at it. When I was writing bare-metal graphics code for the PS4 there was still a lot of Object Orientation there too even if there weren't vtables or a garbage collector involved.

Re:Linear Address Spaces: Unsafe at any speed by dragontamer on Thursday June 30, 2022 @09:50AM (#31932320)
> relatively new and modern

Seeing RAM as a collection of linear addresses on GPUs (especially as shared virtual memory, pinned memory, or other such GPU/CPU virtual memory sharing features) is a feature from 2010-era, be it from OpenCL, DirectCompute, or CUDA.

DirectCompute just sees the data as a collection of bytes.

Re:Linear Address Spaces: Unsafe at any speed by hinkley on Wednesday June 29, 2022 @09:17PM (#31927687)
> Well, GPU code is certainly not object-oriented, and I hope it never becomes that.

Jonathan Blow has been experimenting a lot with arrays of structs versus structs of arrays, particularly in making them both first class instead of assuming one and ignoring the other. This is essentially the column- versus row-oriented data question answered with a question: why not both?

I think if you had a first class language that supported both, that you wouldn't mind so much if GPU code became object oriented.

Re:Linear Address Spaces: Unsafe at any speed by dahart on Wednesday June 29, 2022 @09:40PM (#31927836)
I haven’t heard much about JAI for a few years, is this idea catching on?

I don’t know why not both, is it maybe because one of the two layouts will almost always have worse performance for any given access pattern? I can see uses for having both for the non-critical-path parts, though maybe once you’re indexing it in the awkward but perf-friendly way, you’ve already done the hard work and there’s little point to proving the other style of indexing? (Isn’t the best perf always found using whatever layout & indexing is the most difficult… there must be some eponymous law for this, right?) I guess it is possible to have multiple critical paths each favoring a different layout. Not sure how often I’ve ever seen that in practice, I would guess it’s probably rather rare.

Re:Linear Address Spaces: Unsafe at any speed by moonchild on Wednesday June 29, 2022 @11:37PM (#31928493)
As far as I can tell, the 'structure of arrays' design pattern appeared in the game development world some time around 1998-2005. Columnar layouts have been known for upwards of 50 years now, as has the general notion that the way you lay out and represent your data matters and can be adjusted at will for your use cases. Many different layouts and optimisation structures are known and have been used, esp. in databases.
Re:Linear Address Spaces: Unsafe at any speed by hinkley on Thursday June 30, 2022 @12:42PM (#31935117)
Blow isn’t inventing structs of arrays. It’s as you say a common gaming idiom and one he’s used before. What he was doing is trying to make it a first class citizen. Very few languages do anything for these. None of the language I use have iterator that work for this. You have to write your own bookkeeping logic every time.
Re:Linear Address Spaces: Unsafe at any speed by marcinjachymiak on Wednesday June 29, 2022 @11:52PM (#31928568)
The memory layout can be better this way depending on how the fields of a strict are laid out. It also gives the data better locality.

Let's say you're iterating over position coordinates of some set of objects in a game. With an array-of-structs you can lose ou on cache locality if unrelated fields are nearby. If you use a struct-of-arrays you get cache locality advantages anytime you do something like "iterate over this 1 field for each object"

The latter approach is called data oriented programming btw, and seems to have been around for a while. Andrew Kelley gave a good talk about it recently while using Zig: https://media.handmade-seattle.com/practical-data-oriented-d...

Re:Linear Address Spaces: Unsafe at any speed by hinkley on Wednesday June 29, 2022 @11:29PM (#31928466)
The most obvious one to me is what if you change your mind?

What if 90% of these objects should be compactly slab allocated, but you also run small, very disjointed numbers of them through an editor or an undo list or whatever and so they need to live separate from this array?

I don't know what the answer is, but I feel like a few good candidates will come out of the conversations started by Rust. You can't replace an object with a new object while it's globally readable. But if you own the parent object, you can rewrite it however you want, or whichever ways are compatible with the other invariants you want for the system, like max time per frame or response time.

Re:Linear Address Spaces: Unsafe at any speed by moonchild on Wednesday June 29, 2022 @11:42PM (#31928513)
> You can't replace an object with a new object while it's globally readable

Sure you can. This is the whole point of smalltalk become: and common lisp CHANGE-CLASS.

Re:Linear Address Spaces: Unsafe at any speed by hinkley on Thursday June 30, 2022 @12:28PM (#31934900)
Those change the type annotations for a memory location. Also if you tell me there are no concurrency gotchas for this then I’ll tell you that you have a single threaded interpreter or you’re lying.

We are talking about retaining the type and swapping the pointers from an independent object to a set of offsets into a struct of arrays.

Re:Linear Address Spaces: Unsafe at any speed by moonchild on Thursday June 30, 2022 @02:50PM (#31936825)
> if you tell me there are no concurrency gotchas for this then I’ll tell you that you have a single threaded interpreter or you’re lying

You are making a big assumption. Neither common lisp nor smalltalk specify the semantics of concurrent programs, but it is certainly possible to implement such a feature without, as you say, concurrency gotchas. Perhaps a better example is concurrently compacting gcs for java.

Re:Linear Address Spaces: Unsafe at any speed by fulafel on Saturday July 02, 2022 @08:21AM (#31958429)
And AOS/SOA are not the only organiations, textures eg are often stored in a zig zag or tile style (traditionally called "swizzling" there).
Re:Linear Address Spaces: Unsafe at any speed by kllrnohj on Wednesday June 29, 2022 @10:16PM (#31928080)
In this case GPUs are actually the perfect argument in favor of the article. GPUs only speak in objects, never linear addresses. You allocate a type of object and that allocation just now is that type. eg, a texture is always a texture, never a vertex buffer. Which is a different object altogether. And you never work with addresses. You can point objects at other objects. You can point at an offset from an object. But you can never do arbitrary pointer manipulation, and you never have any idea if the address space is linear or not.
Re:Linear Address Spaces: Unsafe at any speed by dragontamer on Thursday June 30, 2022 @12:26AM (#31928720)
> GPUs only speak in objects, never linear addresses.

Shared Virtual Memory is literally "GPU sees X region the same as the CPU sees it". And is implemented on all desktop GPUs today: https://www.intel.com/content/www/us/en/developer/articles/t...

By making pointers treated the same on CPU or GPU (by allowing their 64-address spaces to be identical by sharing the same memory regions + using PCIe to keep those memory regions in sync), you can perform high-speed CPU / GPU communications of even linked data structures (linked lists, trees, graphs).

GPUs utilize many linked data-structures. Oct-trees accelerate bounds testing, BVH trees help raytracing. Etc. etc. The GPU addresses must be linear because they're synchronized to the CPU's memory space.