The delay is still non-deterministic, meaning that there is no upper bound that the pause can be guaranteed not to exceed.
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.
Often the cost of the extra complexity + specialized hardware outweighs the benefits of using a gc:ed language.
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.
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.
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.
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.
And, as another person replied, it might not even matter at all or with a different choice of hardware.