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, ...
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.
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.
You can (at the cost of some additional complication) make this more deterministic by adding newly-dead objects to a "finalize this soon" queue and chewing through that when you have time (or on a different thread).
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").
void *malloc(size_t _) { return NULL; }
void free(void *ptr) {}
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().
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.
Now it may be that plugging in "300" into your pause time formula where log(n) appears leads to unacceptably long pauses. That's a separate discussion and if you're at that point you care not only about O(log n) vs O(1) but also about constants and non-asymptotic behavior and whatnot. An algorithm that gives you a running time of 1ms for all values of n except n == 1, when the running time is 1000ms, is O(1) and even has "1" as the relevant asymptotic constant, but in practice that 1000ms thing might be a problem.
The same argument really doesn't work for anything that is linear (or really most sorts of polynomial), simply because the range of possible values becomes so much larger. But if you're ok with your worst-case pause being two orders of magnitude longer than your best-case pause, then a log(n) algorithm works just fine.
proving you never exhaust the heap is probably harder than proving your allocator never takes more than X ns, once you've decided to do runtime allocation on your embedded RTOS.
You can claim that a log(n) algorithm runs quickly or almost always fast enough and I'll agree with you. But that is not the same as it being bounded.
In practice, log(n) is no guarantee for an algorithm being quick. A tree search is log(n) but for a big enough n it will begin to cause thousands of really slow page faults.
In other words it doesn't matter if you pick theory or practice, for strict enough real time guarantees and for large enough values of n, log(n) is too slow. Which is exactly the reason why many real time systems only use static memory.
Yes, but in _practice_ the difference in the bounds is gigantic. log(n) is not just bounded for all practical purposes, it's bounded by a constant that's just not that big. That is simply not true for n^n, or even just n.
> In practice, log(n) is no guarantee for an algorithm being quick.
Sure, the constant matters.
> cause thousands of really slow page faults.
Which means the constant is huge. I agree that this is a problem, sure.
> for strict enough real time guarantees and for large enough values of n, log(n) is too slow.
It really depends on what the operations are. log(n) randomly-distributed memory accesses are a problem, I agree. If you have to touch that much memory and have a paged memory system, you lose no matter whether your memory is dynamically or statically allocated. You're right that dynamic allocation can make it more necessary to touch that much memory.
By the way, I fully agree that if you want to do hard realtime and have any hope of actually shipping, sticking to no dynamic allocation is probably simpler than doing the analysis to prove that your dynamic allocations are OK.
And, as another person replied, it might not even matter at all or with a different choice of hardware.
http://www.businesswire.com/news/home/20050307005203/en/Aoni...
The first was in 2003 according to IBM work trying to improve on it in 2007:
http://researcher.watson.ibm.com/researcher/files/us-bacon/F...
I haven't checked on multicore research in a while. A quick Google implies that they're either there or part of the way there for one project on JamaicaVM:
https://www.researchgate.net/publication/221032857_Concurren...
So, yeah, you can do deterministic, hard-real-time GC's. They've been done since 2003 with products shipping since about 2005 for use in safety-critical applications. The DO-178B stuff in particular requires high rigour in how software is designed, coded, analyzed, and tested. That an implementation passed that indicates it can be built with high confidence. Research continues on them. Use in FOSS or popular embedded? Almost nothing.
There's no reason to doubt hard, real-time GC's exist or can work at this point. You should've moved to another goalpost like what tradeoffs were required as others did. You're either trolling us or dodging all evidence due to beliefs only rooted in faith. That is, ignoring all facts contrary to your belief that hard, real-time GC's don't exist or can't work in embedded. So, I'm done arguing with you since nobody can argue against religion that twists or dismisses real-world things to maintain its faith-based ones.
Often the cost of the extra complexity + specialized hardware outweighs the benefits of using a gc:ed language.
[1] Despite us sharing the same name, that's not me.
So suitable for soft realtime like games, but not actually non-deterministic.
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.
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.
Or just use real-time, garbage collection if its costs are acceptable:
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.
Yes, but perhaps it doesn't have to be an unpredictable amount of overhead.