Hacker News Reader

Comment by muth02446 | Hacker News Reader

I am surprised that not every large project uses this technique. If you are running on a 64bit system, the use of 32bit handles instead of pointer results in huge memory savings. You can also put the start addressed of the arrays (the handles are indexing into) anywhere in virtual memory and grow them as needed. Finally you can stripe the data for one object into multiple arrays and use the same handle to index each of them which can improve locality.

View on HN

> you can stripe the data for one object into multiple arrays and use the same handle to index each of them which can improve locality.

I wish programming languages made it easy to structure arrays of objects like this. I think Johnathan Blows’s JAI has some kind of transparent support for SoA.

This basically is how tables work in k. Tables are defined as a list of dictionaries, but in fact stored as an array for each element (ie. each column of the table is an array, but each row can be read as a dictionary).

It’s trivial to do this in C++ and often the caller doesn’t even realize.

do you have any pointers of such implementation ?

We have a mixin class that will allocate a subclass with its own array of handles (the handles overload * and -> so they act like pointers). If you have an instance variable you can choose to give it a different allocator, where that instance variable of object with handle `n` is the nth object in the new area. Then your instance method `barf& foo();`, instead of getting the instance variable `barf m_foo` Instead does some inlined arithmetic and gives the caller a reference to the object.

I don't know. The hugest saving from not malloc-ing small objects comes from the memory-chunk overhead I believe. You could do object pools and still use pointer as usual I think with no runtime cost of passing handles to getter-functions. The usual pattern of "wrapping" malloc/free.

What about CPU data cache misses due to the fact that malloc doesn't have a concept for how best to organize that data chunk of data based on your application's specific usage pattern?

That can definitely be a problem. Using handles makes it easier to swap out your allocation mechanism if you ever have to optimize your cache efficiency.

Hell, projects that need to squeeze out that level of performance will typically have multiple different memory allocation mechanisms.

Ye well then you'll need something fancy. The size saving is there though.

Object pools pale in comparison to striping the data into arrays (or as we call it in the game dev world a Struct of Arrays) when it comes to reduced cache misses.

Given that you iterate over the object fields in a "column like" manner, right? Random access should be slower since an object of say four elements would have to fetch four cache lines.

You're more likely to have the next object cached by the time you access it compared to separate allocations.

The more sequential the access pattern is and the smaller the objects are, the greater benefit.

Hell, you might even be able to go smaller. For example, if you know that you're going to have less than 256 instances of a given object, an 8-bit handle will do the job nicely at an eighth of the size of a full-blown 64-bit pointer.

Until you get too many objects. That can happy quickly nowadays

Reply on news.ycombinator.com