Re: Red-black trees?

Richard Harter wrote:
On Fri, 21 Nov 2008 16:48:20 +0000, Jon Harrop
<jon@xxxxxxxxxxxxxxxxx> wrote:

Richard Harter wrote:

[snip sundry odd comments]

You are still assuming that malloc is O(1) which is only true in some
memory-constrained real-time embedded systems. So that certainly does not
apply to all GCless languages.

This comment is rather strange. Granted that there are quite a
few storage allocators out there (not all of them named malloc
btw) and some are rather inauspiciously designed. However few
are so poorly designed that their performance depends in any
significant way on the amount of storage requested. Commonly
there is a worst case time cost that is O(log #requests) or O(log amount of storage managed).

The issue that troubles me with this is the common operating system
rule that memory, including disk space, be in a fixed state, independent
of any prior contents, when initially allocated to a program or file.

There are two costs to not doing that. There could be inadvertent data
leaks from one program to an unrelated program that happens to be
assigned memory the first program released. A program could have bugs
that result from inappropriate dependence on the prior value of some
memory it allocates. The symptoms of those bugs would depend on what had
last used the memory in question, making them very different to debug.

I believe zeroing n bytes of storage is an Omega(n) operation. In order
to achieve O(log amount of storage managed) that step would have to be
skipped.

Patricia
.

Relevant Pages

  • Re: Red-black trees?
    ... significant way on the amount of storage requested. ... assigned memory the first program released. ... You're mixing up two different issues, initializing space used by ... Some storage allocators initialize allocated storage, ...
    (comp.programming)
  • Re: Lambda Calculus and Turing Equivalence
    ... memory of a TM exceeds the potential finite memory of a PC. ... principle compute problems that require greater storage than ... That is because the tape that Turing posited has no physical constraints. ... magically given an infinite amount of storage space." ...
    (comp.theory)
  • Re: Lambda Calculus and Turing Equivalence
    ... memory of a TM exceeds the potential finite memory of a PC. ... principle compute problems that require greater storage than ... That is because the tape that Turing posited has no physical constraints. ... magically given an infinite amount of storage space." ...
    (sci.math)
  • Re: REGION=0M and LSQA
    ... At the time, memory was very expensive, and we ... remaining storage and always issued a return code zero. ... programs actually worked in production, ... all of the resources used by the job up until that point ...
    (bit.listserv.ibm-main)
  • Re: Statement on Schildt submitted to wikipedia today
    ... storage is allocated from free ... free memory that is used for dynamic allocation is called the heap. ... storage area, and the stack. ...
    (comp.lang.c.moderated)