3 ms·

Nonsense. Here is one implementation of the pair of functions which have deterministic running times, and may even comply with the C standard: void *mallo

by jepler 10y ago

Nonsense. 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 ago
Notice 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.
- bzbarsky 10y ago
  While that's true in theory, in practice n, if it's your memory size, is bounded above by things like "number of atoms in the universe". In other words, log(n) < 300 (doing log base 2 here). 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.
  - jepler 10y ago
    Yup, a hidden assumption that I didn't state is that 'n' is modest and of course 'log n' is very modest. For example, n = 256 might be the case on a microcontroller doing realtime activities. 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.
  - bjourne 10y ago
    If n is bounded, then log(n) is bounded, yes. But so is n^n. 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.
    - bzbarsky 10y ago
      > If n is bounded, then log(n) is bounded, yes. But so is n^n. 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.

by jepler 10y ago

bjourne 10y ago

Notice 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.

bzbarsky 10y ago
While that's true in theory, in practice n, if it's your memory size, is bounded above by things like "number of atoms in the universe". In other words, log(n) < 300 (doing log base 2 here). 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.
- jepler 10y ago
  Yup, a hidden assumption that I didn't state is that 'n' is modest and of course 'log n' is very modest. For example, n = 256 might be the case on a microcontroller doing realtime activities. 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.
- bjourne 10y ago
  If n is bounded, then log(n) is bounded, yes. But so is n^n. 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.
  - bzbarsky 10y ago
    > If n is bounded, then log(n) is bounded, yes. But so is n^n. 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.