Garbage Collection and Swap

Garbage Collection and Swap

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I've been researching garbage collection.

Let me first get it out in the open that I *despise* the concept of
garbage collection.  I worried when I first heard of a magical automatic
free()/delete[] that it would do one or more of two things:

~ - Create excessive overhead
~ - Free up ram I'm still using

I've learned that the first may or may not be true.  This means that
they've won on some accounts with that one.

The second may or may not occur as well.  It worries me that it may in
certain cases, due to the way GC works.  Most garbage collectors will
look in the heap, maybe the stack, maybe other places, for what looks
like pointers to allocated ram.  If they don't find any, they free the ram.

So, the first extremely obvious thing you'll notice is that GC may at
times miss things, especially if you use the XOR linked list trick or
use your own makeshift swap file (write pointers to disk, read back in).

After a while, a big one hit me.

THE GARBAGE COLLECTOR WANDERS AROUND IN THE ENTIRE HEAP, AND IN SOME
CASES IN OTHER PARTS OF RAM, LOOKING FOR WHAT LOOKS LIKE POINTERS TO
YOUR ALLOCATED DATA.

Read that.  It's in all caps, so you should read it.  It has meaning.

How about, everything is using Bohem GC.  Bohem wanders around in the
heap concurrently.  So all of your applications are wandering around
through their vm space everywhere, continuously.

You get low on ram.  Let's say an app is using 500M of ram (Mozilla).
What's going to happen?  Obvious.  It's going to yank shit out of swap.

If we all linked against a GC, what kinds of swap hell do you think we'd
encounter?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFA7zvMhDd4aOud5P8RAh8zAJ9zTAH2D+aJOpK60Gz2FiWfKE/iYQCfShG1
GuXdbh0ZRJuwCX2fLleOBbw=
=Glt1
-----END PGP SIGNATURE-----

Re: Garbage Collection and Swap

[William Lee Irwin III]

On Fri, Jul 09, 2004 at 08:43:57PM -0400, John Richard Moser wrote:
> Read that.  It's in all caps, so you should read it.  It has meaning.
> How about, everything is using Bohem GC.  Bohem wanders around in the
> heap concurrently.  So all of your applications are wandering around
> through their vm space everywhere, continuously.
> You get low on ram.  Let's say an app is using 500M of ram (Mozilla).
> What's going to happen?  Obvious.  It's going to yank shit out of swap.
> If we all linked against a GC, what kinds of swap hell do you think we'd
> encounter?

Ones almost as bad as the Hell of trolls going nuts over hypothetical
problems no one is stupid enough to cause in practice anyway.


-- wli

Re: Garbage Collection and Swap

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



William Lee Irwin III wrote:
| On Fri, Jul 09, 2004 at 08:43:57PM -0400, John Richard Moser wrote:
|
|>Read that.  It's in all caps, so you should read it.  It has meaning.
|>How about, everything is using Bohem GC.  Bohem wanders around in the
|>heap concurrently.  So all of your applications are wandering around
|>through their vm space everywhere, continuously.
|>You get low on ram.  Let's say an app is using 500M of ram (Mozilla).
|>What's going to happen?  Obvious.  It's going to yank shit out of swap.
|>If we all linked against a GC, what kinds of swap hell do you think we'd
|>encounter?
|
|
| Ones almost as bad as the Hell of trolls going nuts over hypothetical
| problems no one is stupid enough to cause in practice anyway.
|
|

I'm actually trying to get the boehm one up, but it keeps setting PaX
off for some odd reason.  I'd intended to have some test data right
about now. . . . >/  Firefox, gimp, hell vim can't run with boehm
LD_PRELOAD to redirect malloc().  Nano can.  A simple tester can.
fortune can't.  BASH doesn't seem to like it.

It's only hypothetical until I prove or disprove it; and I'm not afraid
to do either.

| -- wli
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFA7145hDd4aOud5P8RAkTCAJ9onJMZS5bFzu8ppfvyWg8vOE5SzQCeL5SR
NZPBU5gMs/ZSl0iXuJmvnYQ=
=UVWv
-----END PGP SIGNATURE-----

Re: Garbage Collection and Swap

[Rik van Riel]

On Fri, 9 Jul 2004, John Richard Moser wrote:

> I've been researching garbage collection.

Look up "generational garbage collection".

I suspect that, when tuned right, generational garbage
collection could actually be quite VM friendly...

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: Garbage Collection and Swap

[Rik van Riel]

On Sat, 10 Jul 2004, Rik van Riel wrote:

> 

... and of course the guy has one of those broken
challenge-response authentication protocol (CRAP)
systems in front of his mailbox.

Last time I'll ever help him out...

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: Garbage Collection and Swap

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Rik van Riel wrote:
| On Sat, 10 Jul 2004, Rik van Riel wrote:
|
|
|
| ... and of course the guy has one of those broken
| challenge-response authentication protocol (CRAP)

hum?

| systems in front of his mailbox.
|
| Last time I'll ever help him out...
|
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFA8KGnhDd4aOud5P8RAkCuAJ9mM8UfpgZ73pMoJzMDIW/aWvU/hACgjA0c
4fTJmFghiE7QMd7riRRQX/I=
=9cfV
-----END PGP SIGNATURE-----

Re: Garbage Collection and Swap

[Timothy Miller]

John Richard Moser wrote:

> 
> THE GARBAGE COLLECTOR WANDERS AROUND IN THE ENTIRE HEAP, AND IN SOME
> CASES IN OTHER PARTS OF RAM, LOOKING FOR WHAT LOOKS LIKE POINTERS TO
> YOUR ALLOCATED DATA.
> 

Whose GC does this?

I get the impression that the Java VM, for instance, knows what 
variables are pointers (well, references) and only considers those.  It 
also knows every object that has even been allocated.  It scans over 
every pointer it knows about (the "mark" phase), and then it scans over 
every dynamically allocated memory block (the "sweep" phase) and removes 
all that have no references.

There is anecdotal evidence that this approach sometimes can improve 
performance over "manual" freeing because freeing can be done in bulk.

Java GC works very well, and it's a huge improvement over the "manual" 
method, because it almost completely eliminates memory leaks (if you 
really want a memory leak, you can find a way to make it happen).

Now, if you're talking about trying to apply GC to C code, it's an 
entirely different matter.  C wasn't designed with GC in mind.  The very 
fact that you can do MATH on pointers in C makes reliable GC nearly 
impossible, although any reasonable attempt would certainly be better 
than your assumption that something would "go scanning through memory 
looking for things that look like pointers."  That would be horribly 
stupid.  Better would be to have the compiler emit code that registers 
pointers with something that keeps track of them, but that's still a 
huge can of worms when you consider someone malloc'ing N bytes, storing 
a (void *), and then later assigning that value to a struct pointer.

No, I don't think GC in C is feasible.

Re: Garbage Collection and Swap

[John Richard Moser]

[-- Attachment #1: Type: text/plain, Size: 3439 bytes --]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Timothy Miller wrote:
|
|
| John Richard Moser wrote:
|
|>
|> THE GARBAGE COLLECTOR WANDERS AROUND IN THE ENTIRE HEAP, AND IN SOME
|> CASES IN OTHER PARTS OF RAM, LOOKING FOR WHAT LOOKS LIKE POINTERS TO
|> YOUR ALLOCATED DATA.
|>
|
| Whose GC does this?
|

http://www.iecc.com/gclist/GC-faq.html


## C-compatible garbage collectors know where pointers may generally be
## found (e.g., "bss", "data", and stack), and maintain heap data
## structures that allow them to quickly determine what bit patterns
## might be pointers. Pointers, of course, look like pointers, so this
## heuristic traces out all memory reachable through pointers. What
## isn't reached, is reclaimed.

This just sticks out in my face
| I get the impression that the Java VM, for instance, knows what
[...]

blah blah java blah blah

Yeah Java was built around garbage collection, let's not talk about
this; I was talking about C.

|
| There is anecdotal evidence that this approach sometimes can improve
| performance over "manual" freeing because freeing can be done in bulk.
|

Dude.

if (check_for_tons_of_crap_that_says_I_am_not_used(p))
free(p);

Yeah.  It's a pain in the ass to check every time you turn around for
conditions that indicate that p is unused.  In some cases, it's a best
effort; you can't always tell.  I can believe that GC would be more
passive; hell, if it's not, just slow the GC down a bit.  Garbage
collection doesn't make sure there's no allocated ram that's not in use;
it only frees things it can determine as such.

| Java GC works very well, and it's a huge improvement over the "manual"

[...]

blah blah java blah blah

Everything is an improvement over manual mm.

|
| Now, if you're talking about trying to apply GC to C code, it's an
| entirely different matter.  C wasn't designed with GC in mind.  The very

[...huge paragraph that makes sense...]

Yeah my thoughts exactly.

|
| No, I don't think GC in C is feasible.

See above.

|

Incidently, I've compiled a list of pros/cons from legacy/refct/mm.

I'm going to point something out here though, about comparing these.

When you compare manual mm and reference counting, you're in the same
field:  Both of these set up deterministic points in program flow where
allocated blocks will be freed if it is determined that they are no
longer in use.  Both of these occur immediately when a specific body of
code is finished with a block of memory.

With garbage collection, it's different.  The garbage collector finds
out on its own at some undefined point after the block is no longer
needed that it can free it, and does so.  The GC is in no way obligated
to free the block as soon as it is no longer in use; it only does this
when it discovers this.  As such, a GC is not the same class of
operation as the other two.  You can show me a GC that imposes less
overhead than the other two methods; and I can retune that same GC to
use 99% of your CPU.

That being said, don't argue about the overhead of a GC, because it's
completely managable.

Attached is my list of pros/cons of each system.  It's just some scrap
for data I'm collecting, not presentation material.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFA9HX5hDd4aOud5P8RAjyjAJ9bOxGUoRzGg66dgLHSEC7z5yUScgCfdc6+
cPaxYGWDN4Tx5IFA3bJgFIA=
=n2yk
-----END PGP SIGNATURE-----

[-- Attachment #2: mmanagment.txt --]
[-- Type: text/plain, Size: 4682 bytes --]

Manual
malloc() your ram manually
free() your memory manually

Pros:
High level of control
Autofreeing of temporary data is possible:  Dump pointers to temporary data into a pool that is deallocated later, and is destructed immediately before deallocation by deallocating all held pointers; then destruct and deallocate the pool before leaving the code body

Cons:
Have to determine when not using something before free()ing it
Can free stuff you're not done with easily
Can lose track of stuff without free()ing it easily

Con Caveats:
None

Reference Counting
Create objects holding your data
Retain those objects when using them
Release those objects when not using them

Pros:
Maintain high level of control over memory management
References are held within immediate code bodies such as companion functions, single functions, or objects; thus, when the end of the object's usefulness for that code is reached, it may be released.
Increased chance of properly freeing data:  Companion function to that which allocated it releases it; atomic functions retain/release in their own right
Lower chances of freeing in-use data:  Once all references to an object are gone, via releasing it, nobody can access it anymore anyway, and it is thus deallocated; threaded environments retain before splitting off into new thread to avoid race conditions of create-create_thread-release-retain-release, instead using create-retain-create_thread-release-release.
Autoreleasing temporary data is possible:  Add retained objects to the autorelease pool, which releases them for each time they're entered into it as it is destructed.

Cons:
Requires some level of object orientation, at least by encapsulating data into a structure with a reference count
Minor overhead from the retain counting and locking around retain counts
True, permenant circular references between objects retaining a reference to eachother causes orphanage

Con Caveats:
It's not that much more complex to code with this
Overhead is arguable versus the other two methods' needed checks
Good coding will avoid circular references where one object won't normally be aware of and tell the other to let go of it, thus causing the mutual deallocation of both

Garbage Collection
malloc() your ram manually
The garbage collector determines when you aren't using it anymore

Pros:
Recovers from memory leaks, where data is unreachable and thus freeing it is harmless anyway
Takes the job of freeing up ram off the programmer
Conservative garbage collectors usually don't free in-use data

Pro Caveats:
Freeing up memory when leaking doesn't make that memory any less important; if you lose critical data that you just can't get back (I.e. by clobbering a pointer), you simply lose it.
Taking the job of freing up ram off the programmer is significant versus manual memory management; however, it's a trivial task with reference counting, as even bugs caused by mistakes here are easily tracked down and fixed
Certain programming techniques like the XOR Linked LIst tirck or those which write pointers to files will have problems with the garbage collector; similar things may happen with object oriented programming in which a class member gets a thread and then references to the class are lost, depending on how the language implements things.  Objects may even have a permenant reference to self, which makes them never free.

Cons:
Takes most control away from the programmer
Even conservative garbage collectors free up things still in use, especially in strange situations such as where the pointers to the data aren't where the GC expects them to be; or when they're mangled or encoded
Minor overhead in the form of a second thread, or periodic pauses, depending on implementation
Collector may lag behind, allowing large numbers of small, temporary allocations to build into large amounts of used but unfreed memory
Not sane for Object Oriented Programming, unless it specifically can identify the language in use and its constructs

Con Caveats:
Control over memory management is usually a security blanket, although this is not always true
Conservative garbage collectors usually make the grade, although they do miss in many useful situations
Overhead is usually comparable to reference counting or explicite malloc()/free(), but grows with vm size (especially heap size)
Ram is usually cheap, unless you're wasting hundreds of megabytes from being in a long-running (3-4 seconds even) tight loop that allocates and frees ram repetedly
Garbage collectors exist for C and C++, but they don't work for Objective-C for example; similarly, there are garbage-collected Objective-C objects using a specially made collector

array size 1 ?

[Anshuman S. Rawat]

Hi,
What does an array of size 1 mean? or maybe I might be putting it wrong, so
here's the declaration -

struct option_state {
    int refcnt;
    int universe_count;
    int site_universe;
    int site_code_min;
    VOIDPTR universes[1];
};

(code from ISC DHCP sources includes/dhcpd.h)

What does universes[1] mean here?

Thanks.
-Anshu

Re: array size 1 ?

[Luiz Fernando N. Capitulino]

 Hi Anshuman,

Em Tue, 20 Jul 2004 12:47:27 -0400
"Anshuman S. Rawat" <asr@cs.columbia.edu> screveu:

| Hi,
| What does an array of size 1 mean? or maybe I might be putting it wrong, so
| here's the declaration -
| 
| struct option_state {
|     int refcnt;
|     int universe_count;
|     int site_universe;
|     int site_code_min;
|     VOIDPTR universes[1];
| };
| 
| (code from ISC DHCP sources includes/dhcpd.h)
| 
| What does universes[1] mean here?

 I think is best to ask for the author, seems to me it is not usual.

-- 
Luiz Fernando

Re: array size 1 ?

[Glynn Clements]

Anshuman S. Rawat wrote:

> What does an array of size 1 mean? or maybe I might be putting it wrong, so
> here's the declaration -
> 
> struct option_state {
>     int refcnt;
>     int universe_count;
>     int site_universe;
>     int site_code_min;
>     VOIDPTR universes[1];
> };
> 
> (code from ISC DHCP sources includes/dhcpd.h)
> 
> What does universes[1] mean here?

It means an array of size one.

However, an array of size one at the end of a structure is often a
clue that the structure is intended to be a "header" for a larger
block of data, where the rest of the block is an array whose size
isn't fixed at compile time.

Given the names of the fields, I would guess that the universe_count
field holds the actual number of elements in the array.

C doesn't support variable-sized arrays directly (actually, C99
supports variable-sized arrays, but C89 doesn't). However, you can do
something like:

	struct option_state *p;
	int i;

	p = malloc(sizeof(struct option_state) + (count-1) * sizeof(VOIDPTR));
	...
	p->universe_count = count;
	...
	for (i = 0; i < count; i++)
		p->universes[i] = ...;

Also, gcc supports zero-length arrays for exactly this purpose. The
"Zero Length" node in the gcc Info file (under "C Extensions") says:

	Zero-length arrays are allowed in GNU C.  They are very useful as the
	last element of a structure which is really a header for a
	variable-length object:

	     struct line {
	       int length;
	       char contents[0];
	     };

	     struct line *thisline = (struct line *)
	       malloc (sizeof (struct line) + this_length);
	     thisline->length = this_length;

In practice, it's probably better to just use an array of length one
(which will work with all compilers) and just subtract one when
computing the size.

-- 
Glynn Clements <glynn.clements@virgin.net>

Re: array size 1 ?

[Sascha Retzki]

Am Di, 2004-07-20 um 18.47 schrieb Anshuman S. Rawat:
> Hi,
> What does an array of size 1 mean? or maybe I might be putting it wrong, so
> here's the declaration -
> 
> struct option_state {
>     int refcnt;
>     int universe_count;
>     int site_universe;
>     int site_code_min;
>     VOIDPTR universes[1];
> };
> 
> (code from ISC DHCP sources includes/dhcpd.h)
> 
> What does universes[1] mean here?
> 
> Thanks.
> -Anshu
> 


Came across this:
http://www.eskimo.com/~scs/C-faq/q2.6.html

Re: Garbage Collection and Swap

[IVAN DE JESUS DERAS TABORA]

Timothy Miller wrote:

>
>
> John Richard Moser wrote:
>
>>
>> THE GARBAGE COLLECTOR WANDERS AROUND IN THE ENTIRE HEAP, AND IN SOME
>> CASES IN OTHER PARTS OF RAM, LOOKING FOR WHAT LOOKS LIKE POINTERS TO
>> YOUR ALLOCATED DATA.
>>
>
> Whose GC does this?
>
> I get the impression that the Java VM, for instance, knows what 
> variables are pointers (well, references) and only considers those.  
> It also knows every object that has even been allocated.  It scans 
> over every pointer it knows about (the "mark" phase), and then it 
> scans over every dynamically allocated memory block (the "sweep" 
> phase) and removes all that have no references.
>
> There is anecdotal evidence that this approach sometimes can improve 
> performance over "manual" freeing because freeing can be done in bulk.
>
> Java GC works very well, and it's a huge improvement over the "manual" 
> method, because it almost completely eliminates memory leaks (if you 
> really want a memory leak, you can find a way to make it happen).
>
> Now, if you're talking about trying to apply GC to C code, it's an 
> entirely different matter.  C wasn't designed with GC in mind.  The 
> very fact that you can do MATH on pointers in C makes reliable GC 
> nearly impossible, although any reasonable attempt would certainly be 
> better than your assumption that something would "go scanning through 
> memory looking for things that look like pointers."  That would be 
> horribly stupid.  Better would be to have the compiler emit code that 
> registers pointers with something that keeps track of them, but that's 
> still a huge can of worms when you consider someone malloc'ing N 
> bytes, storing a (void *), and then later assigning that value to a 
> struct pointer.
>
> No, I don't think GC in C is feasible.

A garbage collector for C and C++
http://www.hpl.hp.com/personal/Hans_Boehm/gc/