6 ms·
Handles are the better pointers
- duskwuff 8y agoI wonder if there's anyone who'd argue for bringing back the other kind of handles: https://developer.apple.com/library/archive/documentation/mac/Memory/Memory-11.html https://developer.apple.com/library/archive/documentation/ma... I hope not.
- pavlov 8y agoThis was my first thought too. For extra confusion, Mac handles were pointers to pointers managed by the OS while on Windows, a "handle" just meant a pointer to a struct.
- Koshkin 8y ago> Windows Originally, a handle was an index in a table of allocated memory blocks; the idea was to be able to move these blocks around without affecting the program.
- pavlov 8y agoOk, like handles on Mac OS then. Maybe they saw that this idea didn't work out so great on the Mac.
- brandonbloom 8y agoIt worked out fine for 16 bit systems and the like, just as it did on the Mac. As machines became more powerful, the need for this technique disappeared.
- johntb86 8y agoThey didn't have much choice at the time: https://blogs.msdn.microsoft.com/oldnewthing/20041104-00/?p=37393 https://blogs.msdn.microsoft.com/oldnewthing/20041104-00/?p=...
- lactoferment 8y agoThese books always reminded me of the Dungeons and Dragons manuals...
- coldcode 8y agoGiven the fixed amount of memory available back then, handles were the only way to avoid fragmentation, although you had to be careful if you required locking them temporarily. I even wrote a tech note on this when I was at Apple back then. How far we have come since then.
- Taniwha 8y agoyes this was my immediate thought after reading about handles with upper bits used for meta-data .... right before a shudder passed down my spine .... it brought back all those early bad mac memories
- wruza 8y agoIf you care to remember, please, why was it bad? Did modern hardware/software solve it or prove it okay?
- duskwuff 8y agoEarly versions of Mac OS ran on the 68000 and 68010, which had a 24-bit address bus. The upper 8 bits of the address were completely ignored, so some parts of the Memory Manager (documented in my link above!) would use those bits to store flags for handles, like "locked", "purgeable", and "resource". Seeing that Apple used these bits, some third-party developers followed suit in their own applications (or accessed those bits directly as a questionable optimization). When Apple released computers which used 68030 processors, which had a 32-bit address bus, this trick stopped working. There was an awkward period where "32-bit addressing" was an option which could be turned on and off in the Memory control panel for compatibility with older software (and hardware!) which wasn't yet "32-bit clean".
- Taniwha 8y agosure they used upper bits of addresses that the hardware of the day ignored, pretty predictably the very next hardware release (68020) supported 32-bit addresses potentially breaking just about every mac binary (initially they faked it out with a PAL in the address path, they eventually faked this out in the MMU resulting in a bit of TLB thrashing) This was definitely a case of someone not planning to be successful and not looking far enough into the future
- MattHeard 8y agoCentralised memory management doesn't inherently conflict with a decentralised OO design. If you refactor your object construction into factory functions, you can make the factory responsible for implementing the memory management, and the objects themselves responsible for implementing the memory use. The objects can be ignorant about the handle array. The objects can delegate any memory-related functions to the factory methods.
- Koshkin 8y agoBut the factory pattern has nothing to do with memory management, it serves a different purpose; memory management is a separate concern.
- EpicEng 8y agoIt's an abstraction used to create objects and manage their lifetime. There is no inherent opposition to managing memory in that pattern. Also, it's been done before and it works, so what is the issue specifically (i.e. not some religious nonsense about separation of concerns)?
- maccard 8y ago> If you refactor your object construction into factory functions Given this article is about c++, no need for factory patterns or anything like that. You can overload the new operator on a global, and a per type basis and do it that way.
- majewsky 8y agoA potential problem with "operator new" is that it you can only have one allocator per type for the entire process. When you explicitly pass a factory, you can have separate factory instances.
- AstralStorm 8y agoOr if you template your types on an allocator, like STL does in some cases.
- pavlov 8y agoCentralized resource management, public index handles... So basically OpenGL? (They're called "object names" rather than "index handles" in OpenGL, but the principle seems to be the same.)
- mpweiher 8y agoSo an object table, like in early Smalltalks? http://www.mirandabanda.org/bluebook/bluebook_chapter30.html#TheObjectTable30 http://www.mirandabanda.org/bluebook/bluebook_chapter30.html... I've always wondered what the performance impact would be on 64 bit, assuming 32 bit indexes: on the one hand, half-size for most pointers, on the other hand extra indirection and the size of the table.
- drblast 8y agoA few years ago I wanted to make a shoot-em-up game using C# and XNA I could play with my kids on an Xbox. It worked fine except for slight pauses for GC every once in a while which ruined the experience. The best solution I found was to get rid of objects and allocation entirely and instead store the state of the game in per-type tables like in this article. Then I realized that I didn't need per-type tables at all, and if I used what amounted to a union of all types I could store all the game state in a single table, excluding graphical data and textures. Next I realized that since most objects had properties like position and velocity, I could update those with a single method by iterating through the table. That led to each "object" being a collection of various properties acted on by independent methods which were things like gravity and collision detection. I could specify that a particular game entity was subject to gravity or not, etc. The resulting performance was fantastic and I found I could have many thousands of on-screen objects at the time with no hiccups. The design also made it really easy to save and replay game state; just save or serialize the single state table and input for each frame. The final optimization would have been to write a language that would define game entities in terms of the game components they were subject to and automatically generate the single class that was union of all possible types and would be a "row" in the table. I didn't get around to that because it just wasn't necessary for the simple game I made. I was inspired to do this from various articles about "component based game design" published at the time that were variations on this technique, and the common thread was that a hierarchical OO structure ended up adding a lot of unneeded complexity for games that hindered flexibility as requirements changed or different behaviors for in-game entities were added. Edit: This is a good article on the approach. http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/ http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy...
- IshKebab 8y agoSounds like you discovered the Entity-Component System.
- drblast 8y agoPretty much. The fact that it solved a specific performance problem (avoiding GC pauses) in a tiny game I was making, along with the ease of reasoning about and debugging game state was really interesting to me. Most of the articles about it were about managing large code bases which didn't apply to my little toy game project. I then took it to the furthest extreme I could (everything in a single table) just to see if it would work well, and it did. Almost a purely functional approach to game architecture. Frame State 0 -> Collection of composable functions to modify state -> Frame State 1 I found that to be vastly simpler and more effective than the OO approach of segregating state and functions into individual opaque objects. At that point OO seemed like such a brain-dead way to make things more difficult for myself I wondered if the entity-component idea wouldn't be more universally applicable to systems other than games. It is. This was one of those rare cases where taking something to a logical extreme had an architectural benefit (all state in one easy-to-reason about table) that matched up really well with the performance benefit (memory locality). For systems where the system state is too large or varied to fit in a human's head, the benefits wouldn't be as apparent. But game states are, by definition, something that should be fairly easy to reason about because that's what the player is seeing and interacting with.
- lostmsu 8y agoI am actually trying to implement generic pointers in Rust, that could safely work with object pools and/or preallocated memory regions of arbitrary bitness. My struggles are here: https://github.com/lostmsu/mem_bitness https://github.com/lostmsu/mem_bitness
- the_mitsuhiko 8y agoI use handles quite a bit in some rust code because you can't have self referential objects yet since rust does not have have immovable objects. While it felt like a huge hack in the beginning I really warmed up to the idea now.
- majewsky 8y agoUsing handles instead of proper references is still a huge hack IMO, because you lose all the soundness checks that the compiler can do for references. It's a good thing that immovable objects are coming soon.
- tomp 8y agoWhy can’t you just wrap handles into unique/referenced types?
- habitue 8y agoYou can, but that only solves part of the problem: keeping pointer types from being used as the wrong type. You still have the equivalent of use-after-free to guard against which the lifetime system tracks for you for pointers, but not for handles.
- the_mitsuhiko 8y agoYou can associate lifetimes with handles just fine.
- Animats 8y agoI've done this when I've had heavily interlinked structures. I had a 3D physics engine with elaborate data structures for all the polyhedra objects. Vertices link to edges, edges link to faces, faces link to edges and vertices, and the collision detection system follows those links to compute the closest points on two nearby objects efficiently. All those data items were structures in arrays, part of the "Polyhedron" object. All interconnections between them were array indices. The Polyhedron object owned everything for that polyhedron. Delete that and all the parts went away.
- myWindoonn 8y agoOh hey, I recognize this memory pattern; it's also used in capability-aware software sometimes to implement capabilities, as a "capability list" or "c-list": https://en.wikipedia.org/wiki/C-list_(computer_security) https://en.wikipedia.org/wiki/C-list_(computer_security)
- jnwatson 8y agoThe file descriptor table too.
- rcthompson 8y agoThe method of filling spare bits with random values to guard against stale object access seems like it would probably work well in practice, but is there a way to make it 100% air-tight and guarantee that stale object access will always be prevented? Otherwise it seems like that could end up as the basis of a security vulnerability in a program that uses this pattern.
- backpropaganda 8y agoIt's only a security vulnerability if there is a bug already present in the code. This mechanism is not introducing the vulnerability. In fact, it's helping find out the bug during development. At release runtime, the spare bits should always match.
- rcthompson 8y agoI mean that if an object is deleted and its space in the array is reused for a new object, there's a small but non-zero chance that the spare bits will be identical, in which case the code would gain access to the new object when it is not supposed to. Or am I misunderstanding how the handle concept works?
- backpropaganda 8y agoYeah, I think you are misunderstanding something here. Yes, there is a non-zero chance that spare bits will be identical. But that's only relevant, if you have a bug in your code wherein you are trying to use a destroyed handle. If you are never using a destroyed handle, then the spare bits being identical is completely okay. Another way to think of this is that the spare bits are optional. The interface is good even if there were no spare bits. The spare bits only add an additional probabilistic security check.
- naasking 8y agoThe fact that it's probabilistic is what makes it unreliable as a real security check. That's how I understood the original poster's concern. It might also lend a false sense of security, like most other solutions that don't actually solve the full problem.
- Randgalt 8y agoI'm old enough to remember programming for the original Macintosh which used handles and relocatable memory. It was a nightmare. Constantly locking, unlocking handles was a chore and error prone. I also remember early Windows APIs that had opaque handle-based memory allocations. Sometimes in life it's useful to check your history books and understand why some things were consigned to history.
- taeric 8y agoAnd sometimes, the reasons themselves are historical and the technique can get a resurgence. Specifically, this can easily be used to create a narrative for many functional idioms. The cost of memory and compute has been a large part of the ride in many modern tricks.
- perl4ever 8y agoConstantly locking and unlocking handles was the problem. The whole point of having handles was so they could be moved around, and locking them defeated the purpose. People just created their own problems by dereferencing a handle and then wondering why their pointer became invalid and then locking stuff willy-nilly to prevent it.
- scotty79 8y agoI think OO would be way faster if instead of keeping all of the object properties together in memory and dealing with one object at a time you'd have object collection as you base type (you rarely have one of anything in you program). It would have array for each object property and you would never access change or pass whole one object, just specific properties of specific object. This should be very cache friendly.
- tome 8y agoThen how would subtype polymorphism work?
- scotty79 8y agoIf you just want to inherit from the object collection you already have to have new object collection that behaves slightly differently then it should work exactly the same way as usual. If you wanted to have different types of objects in one collection first you'd have to ask yourself if you really need to keep them together. But if so I suppose you'd just put base fields in one collection and new additional fields in another. Then handle to derived object would consist of two indexes, one in the base collection and the other in the collection of additional fields. Methods that access base field would need to use first index for them, and second index for additional fields. Not sure if I'm being clear enough. Imagine you want to store collection of various subtyped objects in the database. This is pretty much the same problem. You keep base fields in one table, and specific fields in other tables (one for each subtype), and if you want to operate just on base fields you use base table, but if you want to operate on fields specific for a subtype you join base table with table that contains fields specific for that subtype.
- woolvalley 8y agoThis feels like your recreating something equivalent to database tables with a numeric id index.
- duneroadrunner 8y ago> Most of the following blog post is written from a game developer’s perspective, but should also apply to other areas ... Video games are a special case where allocations and deallocations are often well scheduled and predictable. For the more general case, using a data type like ivector[1] for the object arrays would provide the desired memory safety. It gives you the flexibility of safely accessing an object via index, iterator or (zero-overhead smart) pointer. Even though it's a vector (like std::vector) its iterators behave like list iterators. That is, after an insertion or removal operation, unlike indexes, they continue to point to the same item (not necessarily the same position) and they only become invalid when the item they point to is removed. In particular, they don't become invalid after a resize/reallocation operation. So using ivector's iterators instead of index handles would allow you to safely perform insertion/removal operations if necessary. Also, for performance reasons you may sometimes want to temporarily obtain a direct pointer to the item. ivector allows you to obtain a zero-overhead smart pointer to the item that is guaranteed not to become invalid. [2] It does this by disabling "resize" operations on the vector while it exists. [1] shameless plug: https://github.com/duneroadrunner/SaferCPlusPlus#vectors https://github.com/duneroadrunner/SaferCPlusPlus#vectors [2] https://github.com/duneroadrunner/SaferCPlusPlus#make_xscope_vector_size_change_lock_guard https://github.com/duneroadrunner/SaferCPlusPlus#make_xscope...
- AstralStorm 8y agoThe next step is to use the old structure called gap buffer, piece table or the more general zipper... And drop the pretense you are inventing something new. :)
- duneroadrunner 8y agoPretense not intended, thanks for clarifying. :) Rather than algorithmic novelty, the point is more that ivector has an API and implementation that is memory safe (memory safety seemed to be an emphasis of the blog post). As for those next steps, I'm under the vague impression that they aren't as popular these days because larger cpu caches have greatly reduced the cost of moving contiguous data in most real-world scenarios. So that more often than not the cache coherency benefits of simple contiguous data outweigh the avoidance of shifting some of that (contiguous) data.[1] [1] simple microbenchmark of contiguous vs non-contiguous containers near the end of the article: https://www.codeproject.com/articles/1087021/stable-iterators-for-cplusplus-vectors-and-why-you https://www.codeproject.com/articles/1087021/stable-iterator...
- jmts 8y agoOne downside to this approach as far as I interpret it, widget_handle widget = widget_manager_new_widget(manager); is that it appears to require the user to either remember two values, widget_tweak(manager, widget); or the developer to push a variable into (at least) file scope, widget_tweak(widget) { actual_widget = widget_manager_lookup_widget(manager, widget); } That's not super nice. Most of the benefits described can be had by using pools rather than a naive heap allocator. Seem like a nice way to hide bugs, though.
- hcs 8y agoI think there is meant to be only one "manager" per object (thus, handle) type.
- jmts 8y agoI had envisaged my 'manager' variable above as type widget_manager. Having a global manager of all things, or independent manager makes no difference to my argument. The manager has to live in file-scope or above since there is no room in the handle to save a reference to it. At that point, you're creating a singleton and reducing the flexibility of the module. You now have all the usual issues with globals and singletons. Unless of course you're passing around structures containing a handle and pointer to its manager...
- fsloth 8y agoThere is nothing wrong with globals and singletons. They are very good patterns. Some areas of code deal with global state, and there is no sense in pretending it is not so. On the other hand some other areas definetly need a closure of their own (like a workload dumped to a worker thread). The usual issues with globals pop up when people whant to run shortcuts and never implement the data separation from global to local when they should, think they can be used to replace a database like system, or - the horrors - use some multi level stack based system to push and pop global state as they merrily progress along the call stack - i.e run computations while using the global state as some sort of auxiliary storage unit.
- asavinov 8y ago> However, the underlying design philosophy doesn’t fit very well into a classical OOP world These problems indeed belong to a non-OOP view of programming. In OOP, the behavior is concentrated in objects while here a significant part of the behavior is concentrated in references. I have been working on one possible generic solution which is called concept-oriented programming [1] and where references are first-class elements of the program where a great deal of the program behavior is performed during object access using these references. One of the main ideas is that each object class is accompanied with a reference class. Such a couple is referred to as a concept (hence the name of the model). If reference class is empty then we get normal OOP. If object class is empty then we can model normal values (which are passed by copy). Of course, we can build a hierarchy by inheriting the behavior of references and objects (which is different from the classical inheritance but generalizes it in case we have only object classes). COP is still on early stage and cannot be used just because there are other quite serious unsolved problems. But I see that the problems described in this post are not exceptions - describing how objects are represented and how they are accessed is an important piece of custom functionality in any complex system and it is precisely COP tries to formalize (along with some other tricky problems). [1] http://conceptoriented.org http://conceptoriented.org Links on concept-oriented programming (COP)
- beaconstudios 8y agoAre we seeing the emergence of a generic software best practice of centralised state management emergence across the industry? This table based storage pattern is now common to: - functional frontend apps via redux - classical apps and server backends via relational databases - game engines like the one mentioned here, and Unity's Entity Component System - probably more systems I don't know about It seems to me like separation of state and behaviours is one of those fundamental rules that should apply to most large software applications.
- M_Bakhtiari 8y agoHow does shared_ptr work? Reference counting? No wonder that's slow and wasteful of both cache and branch prediction. What's wrong with using a proper generational moving garbage collector?
- saagarjha 8y ago> How does shared_ptr work? Reference counting? Yep. > What's wrong with using a proper generational moving garbage collector? Because then you don't have deterministic performance which is necessary in certain contexts–or am I misunderstanding you here?
- M_Bakhtiari 8y agoDeterministic performance hasn't been a thing since the early 90s. I'll settle for just performance. But sure, there are cases where you want the level of predictability of reference counting, in which case I'd rather take the performance penalty than spend time and pollute the codebase doing a lot of tricks to arrange memory as a compacting garbage collector would.
- jkabrg 8y agoFrom what I can tell: that while this memory-management strategy can stop a program from seg-faulting or from executing remote code, the style of programming is the same as with `malloc` and `free`. You still have to `alloc_texture()` and `free_texture()` in your code even if those functions return a handle instead of a raw pointer. Some observations about the strategy based on the article: - It does *not* prevent memory leaks. It uses fixed size arrays, so once you allocate more memory than there is room in the array, then the program has to exit. - It does not prevent use after free. It just makes it easier to detect when this has happened. This could make debugging easier in some situations. I do wonder though how it interacts with code analyzers. Also this could work in any language. I wonder if it's common in game development for Android, because of Java and garbage collection spikes. Oh, and another observation: I think this strategy is fully compatible with RAII and smart pointers. Smart pointers are implemented using malloc/free, and this strategy is isomorphic to malloc/free, so combining them should work fine.
- naasking 8y agoThe program doesn't need to exit, it can simply allocate a larger space, and it knows exactly what slots are in use and can preserve those indices.
- sacado2 8y agoI starting using rust recently and I noticed my programs tend to use the techniques described in this article. Using an "object" pool that is responsible for the creation / management / destruction of values and their referencing is a good way to reason about lifetimes when you need to manage DAGs or graphs (where reference ownerships and lifecycles are hard to reason about).
- Too 8y ago* >A good example for this ‘system domain knowledge’ is the destruction of rendering resource objects with modern 3D APIs: a resource object can not simply be destroyed immediately when the user code says so because the resource might still be referenced in a command list waiting to be consumed by the GPU. 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.* This is exactly the same behavior you get with shared_ptr, both the user code AND the rendering system would hold a reference to the object and it would only be deallocated once BOTH of them destory their shared_ptr. weak_ptr allows even more fine grained control. You still need to manage your resource lifetime somehow, with either some equivalent of unique_ptr or shared_ptr. Otherwise you've just reinvented global variables. How else would you know when to free an object from your object pool? A "least-used" pattern could be useful in some scenarios but then you also need to be able to reconstruct the object again in case someone asks for it after a long time of being idle (like swapping to disk).
- deleted 8y ago[deleted]
- jkabrg 8y agoAn implementation: https://github.com/jkabrg/type-segregated-pools https://github.com/jkabrg/type-segregated-pools