[HN Gopher] Pictures of a working garbage collector
___________________________________________________________________
Pictures of a working garbage collector
Author : todsacerdoti
Score : 146 points
Date : 2023-01-12 07:21 UTC (15 hours ago)
(HTM) web link (www.oilshell.org)
(TXT) w3m dump (www.oilshell.org)
| raverbashing wrote:
| At a given point it does look like ARC might be the easiest
| solution (sure it has problems, but they're a subset of GC's
| problems)
|
| Edit: this link posted by another commenter gives a nice overview
| of the tradeoffs between the methods and it has very nice graphs
| to boot https://spin.atomicobject.com/2014/09/03/visualizing-
| garbage...
| avgcorrection wrote:
| I presume that "arc" means "automatic rc".
|
| What's manual rc like?
| aidenn0 wrote:
| https://docs.gtk.org/glib/reference-counting.html
| deathanatos wrote:
| Normally I'd read "arc" as "atomic reference count", i.e., a
| refcount system where the increment and decrement operations
| are done with atomic increments/decrements. This permits the
| refcounted objects to be shared across threads that might
| mutate the refcount: they need to not corrupt the refcount,
| or UB ensues.
|
| E.g., the Arc type in Rust. Rust, for example, has a separate
| Rc type. Rc should outperform Arc, but cannot be shared
| across threads.
| simiones wrote:
| Like using std::shared_ptr<T> in C++ or Rc<T> (or Arc<T>,
| which in that case stands for atomic, not automatic) in Rust.
| That is, you as a programmer choose for which variables to
| use reference counting.
| nt591 wrote:
| You can manually increment and decrement reference counts
| with retain/release:
| https://stackoverflow.com/questions/6578/understanding-
| refer...
| tsimionescu wrote:
| ARC's problems are orthogonal to tracing/copying GC's problems.
| They are fundamentally different paradigms, since ARC mostly
| pays a cost for memory which is no longer in use, while
| tracing/copying GC pay a cost for memory which _is_ in use.
|
| That is, with ARC, the more garbage you generate, the more work
| will be spent on the GC vs normal program flow. In contrast,
| with tracing/copying, you can generate as much garbage as you
| want, without affecting GC time; but, the more memory you
| actually use, the more time you will spend in GC.
| kaba0 wrote:
| ARC (if 'A' means atomic) is simply not a good fit for modern
| hardware. With traditional tracing GCs you get blazing fast
| allocation and get to amortize the cost of deallocation,
| while you pay a price for ref counting on every usage (or at
| best on almost every usage with a good compiler).
| magicalhippo wrote:
| > ARC (if 'A' means atomic)
|
| A is for Automatic, as in the compiler adds the calls
| needed to manage the reference counting.
|
| If the language and compiler can guarantee a reference is
| strictly contained within a thread, it doesn't have to be
| atomic. Usually that is not the case, so atomic operations
| are used.
| zarzavat wrote:
| FWIW there is a clash of terminology here.
|
| - ARC (upper case): Automatic Reference Counting (in
| Swift/ObjC)
|
| - Arc (title case): Atomic reference counting (in Rust)
|
| I assume OP intended the former.
| magicalhippo wrote:
| Ah good to know. Never used Rust so haven't come across
| Arc, only ARC in various other languages.
| rwmj wrote:
| You need more than that. Reference counting amplifies
| reads into writes. To ameliorate that (somewhat) you need
| to keep the references separate from the data (a
| particular problem with Rust). Otherwise you end up with
| lots of writes scattered all over memory, causing false
| sharing and lots of unnecessary communication over buses
| between your cores. One way to do this is to keep the
| references together in separate cache lines or pages,
| away from the data. And this only partly alleviates the
| problem.
| zarzavat wrote:
| While this is true on a microscopic scale, the motivation
| for using RC is macroscopic: to release memory ASAP to
| get predictable, low memory usage. From the RC point of
| view the real enemy is swap and the memory management
| system's primary objective is to eliminate swap.
| rwmj wrote:
| To summarise:
|
| - your application is using close to 100% available RAM
|
| - you don't care about the impact of all those extra
| writes clogging up CPU caches and bouncing cache lines
| back and forth across internal buses
|
| - you can't afford to pay for a small amount of extra RAM
|
| In that case reference counting sounds ideal. Good luck!
| CyberDildonics wrote:
| _you pay a price for ref counting on every usage_
|
| What do you mean by 'usage'? References don't change when
| reading or writing the data being reference counted, they
| change when being passed to a function or returned from
| one. In C++ it's rare that you would even use reference
| counting, since that essentially means you don't know the
| lifetime of your value. Most variables are going to be on
| the stack and the vast majority of dynamic allocation is
| going to be referenced from a single scope at one time.
|
| The reality is that it takes gross incompetence to have a
| speed impact from reference counting.
| kaba0 wrote:
| Yeah I meant usage as "getting it into/out of scope".
|
| > In C++ it's rare that you would even use reference
| counting, since that essentially means you don't know the
| lifetime of your value
|
| Sure, because it is a manual memory managed language with
| RC being an escape hatch only. But there are plenty of
| problems/programs where you simply can't know the
| lifetime of your objects, e.g. Chrome uses a proper GC
| for C++ as well.
| CyberDildonics wrote:
| _with RC being an escape hatch only_
|
| I don't know what you mean by escape hatch, but it
| generally just isn't necessary and memory is managed
| automatically by scope. The bigger point here is that it
| just isn't a significant part of execution time.
|
| _But there are plenty of problems /programs where you
| simply can't know the lifetime of your objects_
|
| Like what? I can only think of one, which is passing
| memory allocated in one thread to another thread.
|
| _Chrome uses a proper GC for C++ as well_
|
| This is an anecdote, it doesn't prove or disprove
| anything in the bigger picture.
| kaba0 wrote:
| > managed automatically by scope
|
| That's just an implementation detail. The point is that
| the object's lifetime is only known at runtime and will
| be reclaimed when a counter reaches zero, this is
| reference counting. Whether you have to manually inc/dec
| that counter, or the language does it for you through
| some abstraction is besides the point, it is _automatic_
| memory management either way, as it.. manages memory
| automatically.
|
| > Like what? I can only think of one, which is passing
| memory allocated in one thread to another thread
|
| Any programming language, both parsing into an AST, AST
| manipulations, interpretation (and that is a very wide
| category, not only for things you would think of as
| proper languages). But even some games may want to use GC
| for some in-game objects, as the lifetime of those is
| fundamentally dependent on user action.
|
| Would the litany of managed languages and their
| widespread usage be less anecdotal?
| Gravityloss wrote:
| I was expecting to see something like what you would see on
| windows when running defrag....
| dayjaby wrote:
| I expected to see one of the big orange things you see on the
| street
| j0li0t wrote:
| Exactly my thoughts :D
| gnfargbl wrote:
| I was hoping for https://www.mrtrashwheel.com/.
| [deleted]
| gus_massa wrote:
| There is another site with graphics linked at the bottom of the
| article https://spin.atomicobject.com/2014/09/03/visualizing-
| garbage...
| kaba0 wrote:
| Wow, that's a very cool post!
| rightbyte wrote:
| I was expecting to see some sort of heat map gif of a GC filling
| and trashing slots and was kinda disappointed.
| thinking001001 wrote:
| [dead]
| uncletammy wrote:
| I was expecting to see a man in a dirty boiler suit and was
| pleasantly surprised.
|
| A thousand years from now when they're digging up texts and
| artifacts from this period, there's likely going to be a lot of
| confused academics.
| mark_undoio wrote:
| @chubot (author) I'm curious what the debug experience is like.
| It looks like you're generating C++ code that maps pretty closely
| onto your statically typed Python code - is it straightforward to
| say "aha, it's that variable in C++ so it'll be the same name in
| Python"?
|
| I'm wondering if it's possible to put some directives into the
| generated C++ code that would map its debug info directly back to
| source lines in the Python - I can't find any docs to confirm my
| feeling this should be possible.
|
| Edit: Maybe this? https://gcc.gnu.org/onlinedocs/cpp/Line-
| Control.html
| amayui wrote:
| This is very insightful! Good to see some low-level perf
| benchmarking as well.
| drmeister wrote:
| Get `udb` - the reversible/time-traveling debugger from Undo. I
| don't own any stock - I love their product. You can run your code
| within it, hit an error, set a watch-point, reverse-continue to
| where the watch-point memory was changed and then check the
| stack. udb will turn brain-melting, blood-freezing memory bugs
| into trivial problems that you can solve in a few minutes.
| wooosh wrote:
| A similar project is rr[0], which is freely available. Like you
| said, I find that reversible debuggers are a huge improvement
| over regular debuggers because of the ability to record an
| execution and then effectively bisect the trace for issues.
|
| [0]: https://rr-project.org/
| dleslie wrote:
| gdb has had reversible debugging since release 7, in 2009. What
| does udb offer that it lacks?
| leni536 wrote:
| I'm not familiar with udb, only with rr. Compared to rr,
| gdb's recording for reversible debugging is tremendously
| slower. However rr has strict requirements for the CPU
| (didn't work on AMD, the last time I looked) and requires
| some permissive perf_event_paranoid setting to run.
|
| In my experience rr's recording is around x2 slower for
| single threaded programs than running the program on its own.
|
| I think featurewise they are in parity.
|
| I heard that udb is like rr, but better on some fronts
| (except price and software freedom).
| mark_undoio wrote:
| (I work for Undo)
|
| > gdb has had reversible debugging since release 7, in 2009.
| What does udb offer that it lacks?
|
| GDB's built-in reversible debugging is cool (and it's helped
| raise awareness) but it doesn't scale well. We build on the
| same command set and serial protocol that GDB defined - UDB
| is GDB but with additional Python code hooking it up to our
| separate record/replay engine.
|
| For UDB, I'd say we offer: 1. Performance & efficiency
| (orders of magnitude faster at runtime and lower in memory
| requirements). 2. Recordings can be saved to portable files
| (share with colleagues, receive from customers, etc). 3.
| Library API so applications can self-record with control of
| when to capture and save. 4. Wider support of modern software
| (proactively tracking modern CPU features, shared memory and
| device maps, etc). 5. Correctness (in the past we've found
| the reverse operations in GDB don't have as strong semantics
| as we'd hoped, though I'd also be happy to be wrong here)
|
| FWIW, rr (https://rr-project.org/) also offers many similar
| benefits over GDB's built-in system (though not the library
| API in point 3) but with differences in what CPUs / systems
| are supported, ability to attach at runtime, etc.
|
| If you're looking for an open source solution, I'd choose rr
| over GDB's built-in approach.
| chubot wrote:
| (author here) Yes I tried reversible debugging a couple years
| ago, but at the time I didn't have any bugs that needed it :) I
| managed to get by here without it, but it's a technique I'd
| like to be more familiar with
|
| I'm on the Undo mailing list as well -- nice to see that it's
| effective!
|
| (Also should say that Clasp sounds very cool -- I'm a fan of
| anything that enables interop and reuse, rather than rebuilding
| the same thing in different languages, which may or may not be
| as good)
| drmeister wrote:
| Thanks! I'm very interested in a new garbage collector that
| works with C++. I have a long list of requirements we need
| that is currently satisfied by the Boehm garbage collector
| and were satisfied by the Memory Pool System before we moved
| away from it. I've been looking at the Memory Management
| Toolkit (MMTk). Where would you put Oil in that small club of
| memory managers?
| pebal wrote:
| You can look at this one: https://github.com/pebal/sgcl
| aidenn0 wrote:
| I've been following along the gc of oil.
|
| It succeeds because it only solves the GC problems that Oil
| has (and I mean this as a high complement).
|
| Oil is single threaded, code runs in loops that are well
| understood, and the code is generated from a strongly typed
| subset of Python.
|
| The GC then is run only between loop iterations, so there
| is no need for stack scanning. You never have to worry
| about a root being in a temporary (from the point of view
| of the C++ compiler) since there are just a few locals in
| the function running the loop, and any variables local to
| the loop are logically dead between iterations.
|
| Since a goal of Oil is portability, not scanning registers
| and stacks is very important. Getting this right when the
| GC could be invoked at any allocation is potentially
| intractable with mypy semantics at least.
| drmeister wrote:
| Ah - thank you. We are looking for a GC that supports (in
| no particular order): (1) conservative stack scanning,
| object pinning. (2) optionally conservative and precise
| on the heap. (3) compacting when precise. (3) weak
| pointers. (4) good multithreaded performance. (5)
| finalizers. (6) ability to create pools of different
| kinds of objects - especially cons cells (pairs).
| aidenn0 wrote:
| Probably not coincidentally, that sounds like SBCL's
| cgc...
| chubot wrote:
| So I'd say Oil's collector is highly unusual and not
| applicable most problems! (I now think that "every GC is a
| snowflake" -- it's such a multi-dimensional design space)
|
| It's unusual because it's a precise collector in C++, and
| what I slowly realized is that that problem is basically
| impossible for any non-trivial software, without changing
| the C++ language itself :)
|
| It seems like that hasn't happened, despite efforts over
| decades. I added this link about C++ GC support to the
| appendix, which also explains our unique constraints.
|
| _Garbage collection in the next C++ standard (Boehm 2009)_
|
| https://dl.acm.org/doi/abs/10.1145/1542431.1542437
|
| http://www.oilshell.org/blog/2023/01/garbage-
| collector.html#...
|
| ---
|
| The reason that precise GC can work for Oil is because it's
| a shell that links with extremely little 3rd-party code,
| and has relatively low perf requirements. We depend on libc
| and GNU readline, just like bash. And those libraries are
| basically old-school C functions which are easy to wrap
| with a GC.
|
| (Also as Aidenn mentioned, shells use process-based
| concurrency, which means we don't have threads. The fact
| that it's mostly generated C++ code is also important, as
| mentioned in the post)
|
| ---
|
| The funny thing is that one reason I started this project
| is because I worked with "big data" frameworks on clusters,
| but I found that you can do a lot on a single machine. (in
| spirit similar to the recent "Twitter on one machine post"
| https://news.ycombinator.com/item?id=34291191 )
|
| I would just use shell scripts to saturate ~64 cores / 128
| G of RAM, rather than dealing with slow schedulers and
| distributed file systems.
|
| But garbage collectors and memory management are a main
| reason you can't use all of a machine from one process.
| There's just so much room for contention. Also the hardware
| was trending toward NUMA at the time, and probably is even
| more now, so processes make even more sense.
|
| All of that is to say that I'm a little scared of multi-
| threaded GC ... especially when linking in lots of third
| party libraries.
|
| And AFAIK heaps with tens or hundreds of gigabytes are
| still in the "not practical" range ... or they would take a
| huge amount of engineering effort
|
| ---
|
| But of course there are many domains where you don't have
| embarrassingly parallel problems, and writing tight single-
| or multi-threaded code is the best solution.
|
| Some more color here: https://old.reddit.com/r/oilshell/com
| ments/109t7os/pictures_...
|
| I wonder if Clasp has any support for multi-process
| programming? Beyond Unix pipes, you could also use shared
| memory and maybe some semaphores to synchronize access, and
| avoid copying. I think of that as sort of "inverting" the
| problem. Certain kinds of data like pointer-rich data is
| probably annoying to deal with in shared memory, but there
| are lots of representations for data and I imagine Lisps
| could take advantage of some of them, e.g.
| https://github.com/oilshell/oil/wiki/Compact-AST-
| Representat...
| drmeister wrote:
| Thank you. We do precise GC in C++. I wrote a C++ static
| analyzer in Lisp that uses the Clang front end and
| analyzes all of our C++ code and generates maps of GC-
| managed pointers in all classes. We precisely update
| pointers in thousands of classes that way. We also use it
| to save the system's state to a file or relinked
| executable so we can start up quickly later. Startup
| times using that are under 2 seconds on a reasonable CPU.
| mark_undoio wrote:
| In our latest release of UDB we added the `last` command:
| https://docs.undo.io/TrackingValueChanges.html
|
| Which effectively combines a `watch -l`, plus a reverse-
| continue but also monitors when the underlying memory was
| allocated / freed.
|
| It's quite nice, basically "git blame" for your variables.
| mark_undoio wrote:
| Good to see GDB's watchpoints
| (https://sourceware.org/gdb/download/onlinedocs/gdb/Set-Watch...)
| get a mention. Often called Data Breakpoints in IDEs (which then,
| confusingly, often also use "Watch" for a different concept -
| argh).
|
| Watchpoints, when they're suitable, are an incredibly powerful
| way to query your program's runtime behaviour (When does this
| happen? Why does this value end up here?) instead of stepping
| through and printing things / logging stuff.
|
| They also fast, provided you watch values suitable for the CPU's
| logic to handle them directly. They need to be small-ish and
| located in memory for hardware support to handle it, otherwise
| GDB needs to single step.
|
| (the `-l` flag is also important here and even less well known -
| it tells GDB you really care about the memory address the
| expression is stored in, not the expression itself)
| [deleted]
| acqbu wrote:
| Did anyone else click on this expecting to see a photo
| documentary about the life of a bin/waste collector?
| hardware2win wrote:
| I did, but domain made me think about oil spill
| aitchnyu wrote:
| I expected to see a ship cleaning up a garbage island in the
| ocean.
| jb1991 wrote:
| if you google image search "garbage collector" as I just did,
| you will in fact see photos of these actual, pivotal, working
| members of our society.
___________________________________________________________________
(page generated 2023-01-12 23:01 UTC)