Oh, I remember what’s going on! I’m using the selectable/unselectable CSS attributes to get reasonable behavior, I.e. article text is selectable but not the space around it. IIRC those attributes aren’t totally standardized yet and I may need to add some variants to support all browsers. So far I’ve just been using Safari and WKWebView as this layout has mostly been used in an app, but now that I’m publishing as a blog I need to test more broadly! Thanks for the bug report, I’ll fix it soon.
slow clap — the song is wonderful! Thanks for this.
I’ve also been thinking a lot about similar things. I’m not sure that I’ll use smol_world directly, but it’s certainly along the same lines of where I’ve been going with some of my little language experiments. I’ll definitely read through it!
Regarding Handles, I experimented with them, but never got them to work well in the context of Oil. I tried to pick Erik Corry’s brain a little before the second try, and got this interesting feedback:
The big advantage is no handles, no smart pointers, just plain C++ pointers and references living in the moment :-)
I don’t know exactly what it means :) But they used Handles in a long line of VMs, and seemingly came back around to raw pointers. (I’d be interested in more details.)
All I know is that I much prefer non-moving GC and raw pointers to the moving GC. It’s not quite as fast, but you can debug it like a normal C++ program, and all your performance tools work!
It was EXTREMELY disorienting to debug C++ code where objects are flying around. This was exacerbated by the fact that our collector is at the C++ level (collecting structs and classes), but I think it’s pretty much the same issue in a VM.
And after instrumenting Oil’s workload and writing some R scripts, I have a design for a pool allocator that integrates with the GC (and our separate mark bitmap), that should take over 75% of allocations. The pool should “approximate” a bump allocator. It may not be as fast, but I think it will be very simple and robust.
Performance comes from many places, and I think having all the normal C++ tools working is extremely important.
I don’t really “trust” moving GC in C++ … I think the language has to be changed so that the compiler can be aware of moving pointers.
Also, lazy sweeping in mark and sweep gives you the O(num live objects) runtime of Cheney, rather than the O(heap size) runtime of eager sweeping. This should matter a lot for many workloads.
FWIW I stumbled across their most recent GC when writing a blog post back in May:
Just to be clear: the joke here is that we are basically suggesting layering our own semi-automated memory management system on top of a third-party automated memory management system. We should be striving to reduce our problems to smaller subproblems, not reproducing them.
This is the problem I found with handles – I don’t know what safety they really provide. My feeling is that they sit in an awkward spot between static and dynamic. It’s impossible to express handles in C, so obviously they are extraneous in some sense.
The garbage collector is already a dynamic mechanism for ensuring memory safety at runtime. It ensures there aren’t dangling references.
It doesn’t really make sense to me to recapitulate that in a Handle mechanism, but just for roots. As far as I know,
it’s impossible to write a Handle that enforces correct usage statically. You always end up with a bunch of compromises between performance and safety.
Again I think the real solution is to not have 500,000 lines of C++ in your language implementation. Like GC, handles are global to the program, because reachability is a global property. Once you start using them, you have to use them everywhere. They’re not modular.
Also, some people advocated handles, but there isn’t a single design, and I never found a good explanation of the tradeoffs. I think even the “professional” GC implementers are struggling with this issue, and the state of the art keeps changing. Someone should write an overview, but I think nobody is quite satisfied with what they currently have, because of fundamental limitations of C++.
Regarding 24 bits, the initial version of Oil’s GC had that hard-coded limit, basically to support the separate mark bitmap. But a few weeks ago, with not much effort, @abathur managed to make Oil allocate over 16 Mi objects and crash. So I just changed it to 30 bits :)
Also reminds me that have been thinking about serializing heaps for a long time as well, and the prototype in this post used 24 bit pointers as well!
That design was more read-only, and I never implemented the graph part – it was a tree. Right now I’m actually back on that horse, experimenting with Python’s pickle as a better format for a graph. It’s a nice format once you get rid of all the insecurity with Python code execution – i.e. making it pure data with lists and dicts, not Python classes and constructors. It’s a stack-based VM with object identity and no control flow.
It’s impossible to express handles in C, so obviously they are extraneous in some sense.
In C a handle is just a pointer to a pointer, where the second pointer is owned by the memory manager and is updated when the object moves. For example a Window**, which you access like (**w).title.
Handles like these were ubiquitous in the “classic” MacOS; they existed to counter the problem of heap fragmentation in very small heaps (128KB and smaller!) When the heap filled up the memory manager would relocate moveable blocks to make room. All kinds of system data was accessed through handles (although strangely, not windows.)
And yeah, every developer at some point fell victim to half-dereferencing a handle into a pointer to the object, and then repeatedly using that pointer. It was faster and cleaner. But if you accidentally called something that could allocate memory, your pointer could become invalid and then you were in for a bad time.
It kind of sucked and I’m glad those “dumb” handles are gone, but there was nothing about them that C or C++ couldn’t handle.
Right, so a couple contributors thought that handles in C++ would provide some kind of static guarantees about correct usage. That didn’t seem possible to me, and never materialized.
In reality I think you have the possibility for the exact same bugs in C++ as you do in C – that is what I was getting at. Or at least I would like to see someone explain otherwise :)
I think C++ handles, that encapsulate the double-dereference in a -> operator, would be safe if used consistently. The dangerous part is hanging onto the dereference pointer, and they wouldn’t do that. Even the optimizer knows it can’t assume the value of that pointer stays the same across a function call.
I haven’t tried it, but you might be able to use the lifetime bound attribute to mark raw pointers as having a lifetime coupled to an RAII wrapper that pinned an object, so you wouldn’t expose operator* directly, you’d have a pin() that pinned the object (in the simple case just disabling the GC for its lifetime) and implemented a lifetime-bound operator*. The compiler would complain if the raw pointer outlasted the Pinned.
It’s not feasible with the collector I’m using. All live objects must be moved, because the entire old heap (often called a “semispace”) gets discarded at the end of collection.
I know of a recent hybrid collector that generally leaves objects in place but periodically compacts them, and still manages to use a bump allocator. It’s very cool but more complex than I wanted to go.
I think your collector could just refuse to GC while pinned objects exist and maybe give you some debugging info about where they are. I’d expect correct use of the Pinned wrapper to all be short-lived on-stack objects, so users might not notice.
Good point; I hadn’t thought about that because currently smol_world doesn’t GC until it can’t satisfy an allocation request, and it has no innate ability to grow the heap, so it’s GC-or-fail.
Have you looked at integrating with LLVM’s stack map stuff? Google did it for an experiment in Oilpan. I’ll have to go find it when I’m not on my phone but it’s probably on https://bernsteinbear.com/pl-resources/
Interesting … but my collector can’t use that knowledge to “pin” objects on the stack, because it’s a simple Cheney collector that throws away the entire old heap afterwards. And if it updated the addresses on the stack to point to the moved objects, it be afraid it would break optimized code.
annoying that i can’t copy and paste from the page
Oh? That’s odd. I haven’t done anything to prevent that, or anything weird to the HTML. What OS did this happen on?
Same 🧐 (Firefox 110.0 on MacOS 13.2.1)
Oh, I remember what’s going on! I’m using the selectable/unselectable CSS attributes to get reasonable behavior, I.e. article text is selectable but not the space around it. IIRC those attributes aren’t totally standardized yet and I may need to add some variants to support all browsers. So far I’ve just been using Safari and WKWebView as this layout has mostly been used in an app, but now that I’m publishing as a blog I need to test more broadly! Thanks for the bug report, I’ll fix it soon.
slow clap — the song is wonderful! Thanks for this.
I’ve also been thinking a lot about similar things. I’m not sure that I’ll use smol_world directly, but it’s certainly along the same lines of where I’ve been going with some of my little language experiments. I’ll definitely read through it!
Thanks! Finally someone compliments the song — I’ve been secretly proud of it for a month.
As someone who had the idea to fork the Janet programming language, call it Brad, and make a Rocky Horror joke…
… it was the first thing I noticed!
/me throws a roll of toilet paper at the screen
Regarding Handles, I experimented with them, but never got them to work well in the context of Oil. I tried to pick Erik Corry’s brain a little before the second try, and got this interesting feedback:
https://old.reddit.com/r/cpp/comments/v1vkce/a_garbagecollected_heap_in_c_shaped_like_typed/id1b0mo/
I don’t know exactly what it means :) But they used Handles in a long line of VMs, and seemingly came back around to raw pointers. (I’d be interested in more details.)
All I know is that I much prefer non-moving GC and raw pointers to the moving GC. It’s not quite as fast, but you can debug it like a normal C++ program, and all your performance tools work!
It was EXTREMELY disorienting to debug C++ code where objects are flying around. This was exacerbated by the fact that our collector is at the C++ level (collecting structs and classes), but I think it’s pretty much the same issue in a VM.
And after instrumenting Oil’s workload and writing some R scripts, I have a design for a pool allocator that integrates with the GC (and our separate mark bitmap), that should take over 75% of allocations. The pool should “approximate” a bump allocator. It may not be as fast, but I think it will be very simple and robust.
Performance comes from many places, and I think having all the normal C++ tools working is extremely important.
I don’t really “trust” moving GC in C++ … I think the language has to be changed so that the compiler can be aware of moving pointers.
Also, lazy sweeping in mark and sweep gives you the O(num live objects) runtime of Cheney, rather than the O(heap size) runtime of eager sweeping. This should matter a lot for many workloads.
FWIW I stumbled across their most recent GC when writing a blog post back in May:
https://github.com/toitlang/toit/tree/master/src/third_party/dartino
https://www.oilshell.org/blog/2022/05/gc-heap.html
I also found this a comment from a post about Rust and rooting interesting:
http://blog.pnkfx.org/blog/2016/01/01/gc-and-rust-part-2-roots-of-the-problem/
This is the problem I found with handles – I don’t know what safety they really provide. My feeling is that they sit in an awkward spot between static and dynamic. It’s impossible to express handles in C, so obviously they are extraneous in some sense.
The garbage collector is already a dynamic mechanism for ensuring memory safety at runtime. It ensures there aren’t dangling references.
It doesn’t really make sense to me to recapitulate that in a Handle mechanism, but just for roots. As far as I know, it’s impossible to write a Handle that enforces correct usage statically. You always end up with a bunch of compromises between performance and safety.
Again I think the real solution is to not have 500,000 lines of C++ in your language implementation. Like GC, handles are global to the program, because reachability is a global property. Once you start using them, you have to use them everywhere. They’re not modular.
Also, some people advocated handles, but there isn’t a single design, and I never found a good explanation of the tradeoffs. I think even the “professional” GC implementers are struggling with this issue, and the state of the art keeps changing. Someone should write an overview, but I think nobody is quite satisfied with what they currently have, because of fundamental limitations of C++.
Regarding 24 bits, the initial version of Oil’s GC had that hard-coded limit, basically to support the separate mark bitmap. But a few weeks ago, with not much effort, @abathur managed to make Oil allocate over 16 Mi objects and crash. So I just changed it to 30 bits :)
Also reminds me that have been thinking about serializing heaps for a long time as well, and the prototype in this post used 24 bit pointers as well!
https://www.oilshell.org/blog/2017/01/09.html
That design was more read-only, and I never implemented the graph part – it was a tree. Right now I’m actually back on that horse, experimenting with Python’s pickle as a better format for a graph. It’s a nice format once you get rid of all the insecurity with Python code execution – i.e. making it pure data with lists and dicts, not Python classes and constructors. It’s a stack-based VM with object identity and no control flow.
In C a handle is just a pointer to a pointer, where the second pointer is owned by the memory manager and is updated when the object moves. For example a
Window**, which you access like(**w).title.Handles like these were ubiquitous in the “classic” MacOS; they existed to counter the problem of heap fragmentation in very small heaps (128KB and smaller!) When the heap filled up the memory manager would relocate moveable blocks to make room. All kinds of system data was accessed through handles (although strangely, not windows.)
And yeah, every developer at some point fell victim to half-dereferencing a handle into a pointer to the object, and then repeatedly using that pointer. It was faster and cleaner. But if you accidentally called something that could allocate memory, your pointer could become invalid and then you were in for a bad time.
It kind of sucked and I’m glad those “dumb” handles are gone, but there was nothing about them that C or C++ couldn’t handle.
[Update: That pun was unintentional!]
Right, so a couple contributors thought that handles in C++ would provide some kind of static guarantees about correct usage. That didn’t seem possible to me, and never materialized.
In reality I think you have the possibility for the exact same bugs in C++ as you do in C – that is what I was getting at. Or at least I would like to see someone explain otherwise :)
To get some any more static guarantees in C++ than C, I think you need your own static analysis, outside what the compiler can provide, e.g. https://firefox-source-docs.mozilla.org/js/HazardAnalysis/index.html
I think C++ handles, that encapsulate the double-dereference in a
->operator, would be safe if used consistently. The dangerous part is hanging onto the dereference pointer, and they wouldn’t do that. Even the optimizer knows it can’t assume the value of that pointer stays the same across a function call.I haven’t tried it, but you might be able to use the lifetime bound attribute to mark raw pointers as having a lifetime coupled to an RAII wrapper that pinned an object, so you wouldn’t expose operator* directly, you’d have a pin() that pinned the object (in the simple case just disabling the GC for its lifetime) and implemented a lifetime-bound operator*. The compiler would complain if the raw pointer outlasted the Pinned.
It’s not feasible with the collector I’m using. All live objects must be moved, because the entire old heap (often called a “semispace”) gets discarded at the end of collection.
I know of a recent hybrid collector that generally leaves objects in place but periodically compacts them, and still manages to use a bump allocator. It’s very cool but more complex than I wanted to go.
I think your collector could just refuse to GC while pinned objects exist and maybe give you some debugging info about where they are. I’d expect correct use of the Pinned wrapper to all be short-lived on-stack objects, so users might not notice.
Good point; I hadn’t thought about that because currently smol_world doesn’t GC until it can’t satisfy an allocation request, and it has no innate ability to grow the heap, so it’s GC-or-fail.
Have you looked at integrating with LLVM’s stack map stuff? Google did it for an experiment in Oilpan. I’ll have to go find it when I’m not on my phone but it’s probably on https://bernsteinbear.com/pl-resources/
Interesting … but my collector can’t use that knowledge to “pin” objects on the stack, because it’s a simple Cheney collector that throws away the entire old heap afterwards. And if it updated the addresses on the stack to point to the moved objects, it be afraid it would break optimized code.
I think you have to use it with the double dereference Handle/HandleScope situation, but it provides you with faster root finding during GC, I think.
I don’t know if I’m missing something, but it should be “torn”.