Memory management question

[Serve La]

So it's essentially some reference counting scheme, right? I guess I'll
just stick with ref counting. Accomplishes the same thing, introduces very
little overhead (a dozen or two extra lines of code, maybe), and is
fully under my control.

No, reference counting is the naive approach. First of all it's slow plus it
will introduce problems when you put the code in different environments.
Think multithreaded and multiprocessor systems. I've just been in hell with
a reference counted system (the C++ stringstream class, not really the place
to discuss here). The code crashed totally completely and utterly randomly
on a hyperthreading processor. It turned out that the reference counting
caused the databus to lock up whenever you did a string operation. As it
happened, sometimes another processor was already pulling that line, but the
other processor went for it anyway and succeeded. It also succeeded in
crashing.
Ask in a java group about best schemes for garbage collection, there's been
a lot of research on it the last ten years.

 

[Chris Torek]

So [garbage collection is] essentially some reference counting
scheme, right?

No; in particular, reference-counters have problems with
looped data structures (how many references does an item
pointing to itself have? ). Some GC systems *do* use
refcounts as a "first level", but the most typical method
is called "mark and sweep". The drawback to mark-and-sweep
collectors is that, at some point, a "get new object"
allocation just ... seems ... to ... stop ... entirely,
and then goes on as if time had not stopped for a while.

Most truly high level languages (Lisp, ML, and the like)
have GC. Such languages are very "un-C-like", and my tastes
here match Chris Dollins': GC is great, but not in C.

 

[Daniel Haude]

On Tue, 19 Aug 2003 19:34:04 +0000 (UTC),

Consider what happens when you have a standard doubly-linked list made
up of two (or more) of these, and drop your last external reference to it.

There's really no cure against stupid programming. Of course it'd be easy
to implement that into a refcounting scheme as well, but it would require
looking through the entire list whenever an external reference is deleted
to look if any are left. Or you set up an extra register per list that
keeps track of all external references.

But then, what if list 1 contains a ref to list 2, and vice versa, and no
other external references are left? I can't see a garbage collection
system dealing with that kind of situation efficiently.

I think that losing all external references to a list is a serious
programming error anyway. But even if we wanted to protect a list against
this sort of thing happening, it'd be easier and more efficient to add the
few necessary lines of *dedicated* code to take care of it instead of
relying on a built-in GC system that may or may not do the job properly.

--Daniel

 

[Chris Dollin]

On Tue, 19 Aug 2003 19:34:04 +0000 (UTC),


There's really no cure against stupid programming.

It's not stupid programming - in a garbage-collected system.

But then, what if list 1 contains a ref to list 2, and vice versa, and no
other external references are left? I can't see a garbage collection
system dealing with that kind of situation efficiently.

Read the literature. This is off-topic in comp.lang.c, anyway.

I think that losing all external references to a list is a serious
programming error anyway.
Why?

But even if we wanted to protect a list against
this sort of thing happening, it'd be easier and more efficient to add the
few necessary lines of *dedicated* code to take care of it instead of
relying on a built-in GC system that may or may not do the job properly.

That turns out not to be true. Writing decoupled libraries is *much*
harder without GC. As for "may or may not do the job properly", well,
a GC may have bugs in it - as may the string library, the file system
library, malloc/free, the *printf family, etc. But this is not uncharted
territory, and garbage-collectors are not some opaque mystical ectoware
that drives people insane merely to contemplate. They do a job, and enable
a programming style, and some people find that style both conducive and
effective. It doesn't fit well with C; it's a minor miracle that it can
be made to fit at all.

I speak as one who has written in CG-ed languages during 30 years (Algol W,
Snobol 4, Algol 68, Pop11, Lisp, Smalltalk, Java) and written a garbage
collector [not for machine-compiled code, alas, nor used in anger, but
to the best of my ability working] three times now. There are places
where I wouldn't used a GCed language; but for the kind of stuff I usually
do, I'd *much* rather use one than not.

 

[CBFalconer]

(e-mail address removed) (Paul Hsieh) wrote in message
.... snip ...


it *doesn't* have bubble sort. it *does* have quicksort though.

In the interests of pervasive pedanticism, C doesn't have
quicksort either. It DOES have qsort, which may, in fact, be
bubble sort

 

[pete]

Why isn't there a bsort yet in the stdlib by the way?

The reason probably has something to do with pointlessness.
Here you go:

void bsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *last, *next, *middle;
unsigned char swap, *p1, *p2, *end;

if (nmemb > 1) {
last = base;
last += (nmemb - 1) * size;
do {
middle = next = base;
do {
if (compar(middle, middle + size) > 0) {
p1 = middle;
p2 = middle + size;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
next = middle;
}
middle += size;
} while (middle != last);
last = next;
} while (last != base);
}
}

 

[goose]

In the interests of pervasive pedanticism,

C doesn't have
quicksort either. It DOES have qsort, which may, in fact, be
bubble sort

<sigh>
I hate posting in haste, and then having to look with horror
at what I posted, just *knowing* that the cluefull out there
are currently circling like great whites, eyeing my comments
and thinking to themselves "breakfast!!!".

goose,
"seafood" is my middle name