6 ms·
"Garbage collection, for example, introduces nondeterministic delays. Automatic memory allocators complicate common kernel optimizations such as slab allocation
by rwmj 10y ago
"Garbage collection, for example, introduces nondeterministic
delays. Automatic memory allocators complicate common kernel
optimizations such as slab allocation"
No no no. Badly designed GC, for sure. But for any modern, thought-through GC this is not true.
And in any case, the Linux kernel uses ref-counting all over the place, which is the worst form of GC - slow, hard to debug, full of potential places to trip you up and cause a leak or a security bug, ...
- striking 10y agoFor reference, some previous discussion on GC here on HN: https://news.ycombinator.com/item?id=12821586 https://news.ycombinator.com/item?id=12821586
- Kenji 10y agoNo no no. Garbage collection has some mandatory overhead. Sure you can do an amortised analysis. Just like pushing into the back of a C++ vector is O(1) amortised... except that every once in a while, the entire vector has to be copied over into a larger block of memory, costing O(n) for that particular operation. You can mislead people, but you cannot trick the computer and hard realtime constraints.
- rwmj 10y agoDo you think your malloc/free (or kmalloc) implementation has no non-deterministic delays? I hate to break it to you, but malloc/free is not magical and O(1). It's complex, even reaching into the cache and operating system, and non-deterministic.
- monocasa 10y agoYep, hard real time code tends not to malloc and free for that reason. Most hard real time systems only allow dynamic memory management at system initialization, not at normal runtime.
- Kenji 10y ago>I hate to break it to you, but malloc/free is not magical and O(1). Trust me, I know more about it than I'd like to. I work on embedded software with hard realtime constraints and we had to remove all malloc/free calls from the critical paths. What I don't like is people claiming garbage collection is free. It annoys me to no end. Garbage collection comes at a clear cost and you need to make a cost/benefit analysis. For your average chat application, this is okay. For video games, it might be, but it's probably already noticeable. For anything remotely realtime, forget garbage collection.
- nickpsecurity 10y ago"For anything remotely realtime, forget garbage collection." Or just use real-time, garbage collection if its costs are acceptable: https://news.ycombinator.com/item?id=14108543 https://news.ycombinator.com/item?id=14108543 At least one is deployed in DO-178B-certified systems in industry that require highest confidence and testing. That's as opposite of your implication as possible.
- wtetzner 10y ago> Garbage collection has some mandatory overhead. Yes, but perhaps it doesn't have to be an unpredictable amount of overhead.
- Kenji 10y agoEverything is predictable, given enough information. Except for Laplace's Demon, that's not possible. Aah, I love my daily fix of pedantry, which I reliably find on hackernews.
- gmfawcett 10y agoKnocking down strawman arguments isn't pedantry, and there's no need to be rude. You were replying to a comment that said GC could have deterministic overhead; and you replied that "no, GC has mandatory overhead" -- which is a different concern. Wtetzner just pointed out, rightly so, that mandatory doesn't mean non-deterministic.
- nickpsecurity 10y agoExactly. That commenter and some others in threads like these are going out of their way to ignore all evidence that deterministic GC's exist with costs that are acceptable for various types of applications. Their myth needs to disappear so real-time GC's get more attention by those who might use or improve on them.
- Kenji 10y agoI meant it had a mandatory nondeterministic overhead. I even made an example with the nondeterministic overhead of C++ vectors. Come on, now you're really putting effort into misunderstanding me.
- learc83 10y agoCan you give me an example of a language with GC that doesn't introduce non-deterministic delays?
- rwmj 10y agoI can reference Richard Jones's[1] Garbage Collection Handbook (http://gchandbook.org/contents.html http://gchandbook.org/contents.html) which has a whole chapter on Real Time Garbage Collectors. [1] Despite us sharing the same name, that's not me.
- dom96 10y agoThe Nim programming language's default GC[1] allows you to specify an upper bound delay time that it should not exceed. 1: https://nim-lang.org/docs/gc.html#realtime-support https://nim-lang.org/docs/gc.html#realtime-support
- learc83 10y agoAccording to the docs "These procs provide a 'best effort' realtime guarantee...Tests show that a 2ms max pause time will be met in almost all cases on modern CPUs" So suitable for soft realtime like games, but not actually non-deterministic.
- nickpsecurity 10y agoI did here: https://news.ycombinator.com/item?id=14108543 https://news.ycombinator.com/item?id=14108543 It's the GC rather than the language you have to focus on unless it's a dynamic language supporting features like LISP. One like Java or Rust can use the most predictable subset of the language combined with hard, real-time GC. Many of those exist & at least one had plenty of commercial deployment with a Java subset.
- bjourne 10y agoThe delay is still non-deterministic, meaning that there is no upper bound that the pause can be guaranteed not to exceed.
- rwmj 10y agoThis is simply not true! There exist deterministic garbage collectors suitable for realtime applications. For hard real time you probably don't want to be using dynamic allocation at all -- after all, malloc/free (or kmalloc) is non-deterministic too (unless you're using something like TLSF).
- bjourne 10y agoCorrect, malloc and free (one or both) have non-deterministic running times. A gc, which is a malloc/free + a lot of extras, exacerbates the problem.
- jepler 10y agoNonsense. Here is one implementation of the pair of functions which have deterministic running times, and may even comply with the C standard: void *malloc(size_t _) { return NULL; } void free(void *ptr) {} More seriously, I bet there are useful allocators that have bounded runtimes; for instance, if you use a multimap to track free blocks as {size: base address} you can find the best-fit block in O(log n) time for malloc (but this doesn't solve the problem of coalescing adjacent blocks in free, you'll need a different, hopefully log-time structure, for this; and you'll need to keep the two in synch; etc). In the kind of embedded I typically think of, there's no need to worry that malloc() has to call sbrk(), which might do things like need to access disk to swap out pages from another process. You're right, if you have sbrk() that takes unbounded time, malloc() will have to take unbounded time if it sometimes calls sbrk().
- bjourne 10y agoNotice how your suggested algorithm's complexity is a function of the amount of memory available. In other words, it is not any more deterministic than the absolutely worst O(n^n) mark&sweep collector you can find. Unless you impose a bound on n, both n^n and log(n) -> inf as n-> inf. In other words, no upper bound on the pause time.
- openasocket 10y agoDepends on your requirements. A hard real-time system discourages any form of dynamic memory management, let alone GC. There are soft real-time GC implementations, but they are fairly special beasts. I wouldn't consider any non-soft-real-time GC implementation "badly designed". I get the point about reference counting, but I should point out it depends on the data structure you are dealing with. If you've got a tree-like or list-like data structure with reference counted pointers everywhere, then yes that can cause nondeterministic delays. But if you're reference counting a flat structure containing no reference-counted pointers, or contains some reference counted pointers, but doesn't allow for arbitrarily deep data structures, reference counting delays are completely deterministic. In many cases that can be faster than GC, and definitely uses less memory. Point still stands about the safety issue, there are quite a few CVEs having to do with not properly decrementing the reference count, though C++ shared_pointer and Rusts Rc<> make that safer.
- fiddlerwoaroof 10y agoEven in the flat structure case, doesn't reference counting turn referencing an object into a synchronization point? For example if I try to use several threads to make a million objects reference a single object, I'll have to lock every time I add a reference, reducing parallelism.
- openasocket 10y agoWell yes and no. In the multi-threaded case you'd use ARC (atomic reference count) pointers. These use atomic instructions to increment and decrement references, and are thus lock-free. There's still contention, but only on the data bus and the cache coherency protocol for the atomic instructions. Under contention, you're looking at latency for access less than 80-100ns. Of course, if all of these threads are accessing an object at once you're going to have contentions no matter what, unless all of the threads are read-only.
- kazinator 10y agoReference counting is a form of GC. It has nondeterministic delays. You don't know which dropref() operation will just decrement and which will finalize. Moreover, when refcounted objects finalize, they recursively drop the refs they hold. Of course, in some trivial cases it is obvious. But in those cases, you could use manual memory management. For instance, trivial case: making an object and then dropping it in the same scope.
- mirekrusin 10y agoYes, also they say that performance is not important so it's kind of weird argument - but it's just 64kB of RAM to juggle, GC is not a good idea, no?
- rwmj 10y agoFunnily enough I'm thinking about this because I'm currently writing a garbage collected ML-/LISP-ish mini-operating system for the BBC Micro:bit. It has only 16K of RAM, which is quite a challenge for GC. Given a naive implementation, just my minor heap would occupy far more than available RAM. But it's a good way to focus the mind on the problems, and (if I pull it off) much more fun than having to use manual memory allocation.
- kazinator 10y agoThe Linux kernel uses manual ref-counting in C. Ref-counting in C++ with smart pointers is much more robust. It can also be partially optimized. You can use const references to pass smart pointers into helper functions, which means that the refcounts don't have to be bumped. You can do that sort of thing manually too, but then you hav e to be careful about tracking which functions are sharing ownership with the caller (and so must not drop a reference, nor allow the reference to "escape").
- pekk 10y agoAre typical Java GCs "badly designed"? The issue with nondeterminism and complexity is well known... you trade other things off when you optimize for throughput