Handles Are the Better Pointers (2018)
floooh.github.com
floooh.github.com
There’s really no substitute for packing fixed-sized objects together in N big array chunks. If you can operate in a particular context (or entirely) with N=1, you can substitute handles for pointers. For any reasonable # of objects, those handles can be smaller than a pointer and provide even better compaction and thus cache effectiveness.
[1] https://people.eecs.berkeley.edu/~kubitron/courses/cs194-24-...
I write a mixture of R, Python, C and C++, in that order of prevalence, and mostly for data intensive tasks. After nearly two decades of unlearning loops and implementing instead with FP idioms, vectorization, and matrix multiplies to take advantage of R's strengths, I often have trouble recreating R's performance when I first reimplement in C or C++.
I think it would be beneficial to start with functional programming in more CS programs, they are a much better fit for modern CPU architectures in many ways.
It opens a wide array of exciting problems and possibilities, if you start thinking of that as something a language should let you twiddle with rather than hard coding it. It seems like a lot of high performance stuff is moving in a direction where this would be advantageous.
(For example, if you compress an array, you lose random access. The language would have to carefully build up capabilities from scratch so it can have a concept of "arrays" that can't be randomly accessed, can only be written in some very particular manner that may even require a "flush" concept, etc. My gut says it ought to be possible, since, after all, we can do it manually, but it would be a very careful operation to disentangle casual assumptions about what data structures can do based on the definition of what data they contain vs. how they are represented in memory, and what capabilities you get from that.)
Whether it gets too much attention is debatable. He has some good ideas, imo, worth exploring, although I don't agree with all of his opinions. He has a prominent enough profile that it will likely inspire others to incorporate features from Jai if they are seen to be desirable, even if Jai is not ultimately released. (Personally, I think it will eventually.)
Basically right on point with what the GP is saying.
But the questions at the end, and the resistance to these basic ideas, roughly "what about platform portability, programmer productivity, etc."; these questions were a bit shocking to me. Is this not a C++ conference? This was six years ago, so perhaps the machine constraints were not as well known back then, but it really shows how strongly the community culture will influence a language and its capabilities.
If I had a PPLTDHTWTPOAE (?) it'd have this capability for sure.
It's all easy in the simple struct case, gets more interesting when you start trying to manipulate them by putting them into arrays or associative maps, etc.
On the one hand, this is nearly revolutionary in some sense, but in another it's simply an incremental advance in a direction we're already going. "Object's are a poor man's closures, closures are a poor man's objects" being an old saying leaning in this direction, and it's hardly a new observation in Haskell that there's not a heck of a lot of practical difference between an associative array of X -> Y and a function (x -> y), at least when it comes to reading them.
I dunno... seems like you'd be combining all the hard bits of a nominative type system with all the hard bits of a polymorphic structural type subsystem.
The dream scenario is to write all of our libraries and application code using types that are the most straightforward (e.g. counting in unary, mapping over linked-lists, looking up values from lists of key/value pairs, etc.), then cast these to more efficient types (e.g. machine words, arrays, tries, etc.) for the final program. It's still ongoing, and a naive approach would simply lead to a bunch of conversion functions being scattered around (making the program even slower), so a smart approach would be needed, e.g. where compilers can fuse away these conversions.
Your usage of the word "cast" in the second paragraph is a misnomer, because no systems programmer is going to want to perform an expensive transporation in HoTT!
The problem, of course, is that we can't enforce this within the logic (since those expressions are indistinguishable), so we must rely on compiler optimisations (i.e. deforestation/fusion).
That link looks interesting, but appears to be more about re-using the same computational-content/runtime-representation for multiple compile-time/proof-context semantics (akin to McBride's "ornaments"), which seems more like a dual problem to that of swapping out slow representations for fast ones.
One of the things I only alluded to in my third paragraph, but very much had this sort of thing in mind, is that it's going to take a lot of type work and a lot of thinking in properties (like Traversable, Functor, etc. in Haskell) to make this work out well, because a lot of these rewrites to underlying representation will have manifestations at the property level (this array is now Traversable but no longer RandomAccessible, etc.).
Sure it might not be the most efficient implementation possible, but due to the ease of parallelizing, you are more likely to just try it out.
I remember debugging a regression with UNIX network sockets where valid connections were being killed, and the bug was only triggered under heavy load. Deadlines were approaching and as a desperate measure I did the exact opposite the article suggests: I wrapped all the socket calls to only accept pointers to an opaque struct with a single integer and made sure the int was set to a guardian value to indicate invalidation after an error. The culprit was a double-close that normal debugging tools such as Valgrind could not find but my unorthodox refactoring did.
Later I've learnt to love UUID's whenever performance allows. They're not pointers so they don't introduce memory handling issues and they can be easily tracked in e.g. distributed data pipelines and logging systems.
All of this applies to pointers as well.
I was writing an interpreter using shared ptrs all over the place.
Performance was fine until I linked pthreads, at which point it took a nosedive forcing me to refactor the entire project.
No one really tells you this. People will say don't use shared ptrs because they're slow, which is far from the whole truth. They're pretty darn fast as long as you don't enable threading.
The same thing goes for mutexes. Modern, uncontended mutexes are very fast. But they can start sucking resources when you're locking them from multiple threads at the same time.
I am doing that :/
In Object Pascal it is the standard memory management way. All strings and arrays are reference counted, and so I use it for all my own data structures as well
I have not even added threading and I doubt I will, but the reference counting is already the slowest part
Not sure what the alternative is
It would still need reference counting on the handles to know when the handle is not used anymore and the element in the array can be reused
Without reusing handles it would surely run out of memory. Unless a full GC is used
The article suggests a handle containing a "plain int" plus a "unique bit pattern", the latter acting like a watermark which is compared to the one in the private array of the corresponding module, preventing dangling accesses.
Apart from rare occasional collisions in the bit pattern causing a false negative on a dangling access, what other issues can be found with this approach?
The reason I went this way is because when writing my third ECS with various access pattern optimizations, I realized I'm hand-implementing database indices - so I may as well plug SQLite for now, nail the interface, and refactor it into Array-of-Struct implementation with handles later.
This is essentially the same as what the article suggests, just with a lot more spare bits for creating unique handles.
"This is where the ‘free bits’ in a handle come in: Let’s say our handles are 16-bits, but we only ever need 1024 items alive at the same time. Only 10 index bits are needed to address 1024 items, which leaves 6 bits free for something else.
If those 6 bits contain some sort of ‘unique pattern’, it’s possible to detect dangling accesses: [...]"
A pointer is just an integer index to a byte in memory in most computing architectures.
By using handles, "user code" is freed from having to know the base and the multiplier, which allows for a more compact locator that remains constant in case of base/multiplier changes.
Integers in a small array will get re-used; they have to.
So, just like a pointer then?
> "I wrapped all the socket calls to only accept pointers to an opaque struct with a single integer and made sure the int was set to a guardian value to indicate invalidation after an error."
This worked because after destroying the descriptor and storing the sentinel value, you didn't destroy the structure.
In production code, that would be a problem. You wouldn't want to leak these wrapper structures, so at some point they would have to be deleted.
And then you're back to the same problem: a structure containing a guardian int is freed while still in use, then the memory is re-allocated to some other purpose, and now the guardian checks are inappropriately testing memory they no longer own.
What works is garbage-collected handles: pointers to objects that wrap a manually-managed resource, but which themselves do not go away while they are referenced.
By the way, POSIX file descriptors could provide a sort of garbage-collected discipline, because they support reference counting. So that is to say, instead of passing around an integer descriptor, you can enforce that dup() must be used by anyone wanting to share the underlying object: everyone must share through their own integer descriptor, not by sharing the integer. Then if five objects or threads or whatever are sharing the same open file, they have five different integers. The object goes away when all five of those contexts separately issue a close on their integer. Nobody closes an integer that they got from somewhere else, always their own dup.
POSIX descriptors also lack the feature described in the article: tag bits. So that is to say, imagine a parallel universe with POSIX descriptors that are not simply non-negative integers clumped close to zero, but have two parts: the integer clumped close to zero, and some bits indicating a generation. For instance suppose descriptor 0x01FC means "generation 0, index 1FC". Then suppose you close(0x01FC) such that the 1FC slot is the lowest available position. Something opens a new descriptor. That results in 0x11FC, not 0x01FC. The generation has incremented. Now suppose a double close happens: another close(0x01FC). The kernel extracts the generation 0, and looks at object 1FC. It sees, hey that thing is generation 1! This is a stale handle! and returns an error.
Hell, projects that need to squeeze out that level of performance will typically have multiple different memory allocation mechanisms.
The more sequential the access pattern is and the smaller the objects are, the greater benefit.
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.
Since handles refer to offer rather than absolute addresses, this sort of scheme should allow for "serializing" data by memmapping chunks of memory to disk.
Obviously, this scheme wouldn't be useful for cross-platform save files, and might not even translate across builds.
Still, as long as you have a robust scheme for invalidating data when a new version is deployed, I could see this being useful for caching, and for saving state for short periods of time on mobile platforms that like to restart processes with little warning. (Rather than potentially losing your place within the game level any time you switch between apps, you only lose your place within the game level when an app update gets installed.)
So in case that module-private array is mmapped to disk, handles themselves can be serialised, unlike pointers. This can enable quick and easy storage of most of the program state, allowing for a fast recovery afterwards.
If you wanted pointers out of it after you loaded it you just had a fix-up phase that swapped the offsets for pointers.
We also used the non pointer mmap version on eMMC platforms for really easy ways to store large data while letting the kernel handle the paging with clean pages.
Also forces you to think about data locality which is a powerful thing.
Ideas are in a wheel, same ones always coming around again.
In ye olden days, addressing was probably physical, so being non-multi-tasking ensured the safety of using handles, ie if used properly. IOW the system process was free to clean up the heap and manipulate your pointers b/c your app would only yield at specific points where you aren't holding onto a dereferenced handle.
True, but it was also your job as a developer to not be holding onto those pointers when the memory manager ran.
Handles continued to be used all the way through Mac OS 9, as they were used by a ton of critical Toolbox APIs like the Resource Manager. A vestigal version even existed in Mac OS X -- handles still existed in Carbon, but I'm not sure they would ever be relocated by the system like they were previously.
> of course these later gen machines did have MMUs.
They did, but it was only used to simulate a system with more physical memory. Every process still saw the same view of a single "flat" memory space.
Handles by that definition have the usage the can be moved in memory to clear up fragmentation but they have none of the other benefits this particular post is talking about. Those benefits only come from their specific implementation, not from the idea of "handles".
https://devblogs.microsoft.com/oldnewthing/20041104-00/?p=37...
In later versions, heap memory handles were even implemented in Intel x86 hardware:
https://devblogs.microsoft.com/oldnewthing/20041105-00/?p=37...
typedef <platform-specific> gss_ctx_id_t;
typedef <platform-specific> gss_cred_id_t;
typedef <platform-specific> gss_name_t;
(Pretty painful trade-off in the long run, is what I think, having lived through that.)
This is often a really useful strategy to use in Rust code as well.
The original GC had handles. With Hotspot (JDK 1.2, IIRC?) those were gone, and by Java ~8 they were back again, but embedded in the object header, where the pointer indirection presumably hurts less.
In an alternate universe, Sun would have shrunk the memory size for Strings earlier and kept the overhead per object, in which case I suspect the GC stall around 1-2GB would never have happened. But I don't think they had admitted to themselves how Stringly Typed production Java code was, and how UTF-16 wasn't going to last forever.
— “Fundamental theorem of software engineering”
https://en.wikipedia.org/wiki/Fundamental_theorem_of_softwar...
In the code bases I've worked on, we have pushed hard to have unique ownership wherever possible and only use shared_ptr where there was a clear need. You can still have a huge object graph kept alive by a single unique_ptr, but it happens less often and it's easier to trace back and fix.
A nice thing about the handle approach is that it makes it a lot harder to build up these object graphs or in general to implement anything without being explicit about object lifetime.
I've seen parts of the handle/object pool approach misapplied and cause more trouble than it's worth, though. It's a good idea for self-contained subsystems where there are a limited number of object types that you would apply this to. I don't think it scales to 100s or 1000s of distinct types of objects because then you're going to have headaches dealing with the sheer number the object pools.
I've also seen object pooling be implemented proactively as an "optimisation" to avoid calling malloc() but then become a bottleneck because of lock contention in the object pool.
I'm not sure if the suggested generation counter approach is the optimal way to deal with the delayed release. Also, when it comes down to own memory managers, benchmarking is a must. Added complexities may eventually eat up the initial savings.
My understanding is that the dangling access conditions potentially arise due to the delayed release of deleted handles.
["... Instead the rendering system would only mark the resource object for destruction when the user code requests its destruction, but the actual destruction happens at a later time when the GPU no longer uses the resource."]