Re: Red-black trees?

On Fri, 21 Nov 2008 12:01:57 -0800, Patricia Shanahan
<pats@xxxxxxx> wrote:

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.

You're mixing up two different issues, initializing space used by
a program and initializing space supplied by an allocator within
the program. You (might) get repeatability by initializing the
space provided to a program by the OS. This is generally
considered to be a good thing.

This does not affect the cost of storage allocation within the
program. Some storage allocators initialize allocated storage,
some have it as an option, and some don't. The cost is usually
relatively low, but the advantages are debatable - initialization
can conceal bugs.

Initialization need not be done in one swell foop - there are
various techniques for handling it incrementally, but that seems
to me to outside the scope of the current discussion.

Be that as it may, most good allocators either use a combination
of a size indexed table of free lists with a tree of blocks not
in the table or some variant of a buddy system. The former is
O(1) on average and O(log # requests) worst case; the latter is
(can be) O(1) on average and O(log managed space) worst case.




Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.