Re: Garbage Collection - The Trash Begins To Pile Up
Lourens Veen wrote:
I think I understand what you're saying, but I'm not entirely clear on
its ramifications. Consider this scenario:
You are making a drawing application. It can open one or more images,
which are stored in a tiled fashion. Each image therefore consists of
a collection of tiles. The programme has a "Duplicate Image"
function. To avoid uneccesary copying, which can be expensive on
large images, you want the two copies to share as many tiles as
possible, in a copy-on-write fashion.
How would you implement this? You can't put tiles in a container in
the image, because they may be part of more than one image. But if
you put them in a container at global scope, how do you determine
when to delete them? Only deleting them when the programme is stopped
is unacceptable because it is effectively a memory leak. It seems to
me that you would need either GC or reference counting for this.
Yes, reference counting and one level of indirection would work nicely
in this application.
I would approach this problem as follows:
I would let a Pixmap contain the pixels of one tile:
struct Pixmap {} ;
I would let a Tile contain a Pixmap, as well as a reference count.
Constructor of a Tile would set the reference_count to 1. I would
*identify* a tile by taking a hash of the pixels of its Pixmap. I
choose my hasher to be MD5, an overhead of 16 bytes. If that is too
much, I could use another that would cost 8 bytes or even 4 bytes. 2
bytes would be somewhat dangerous, but that could work if the risk is
acceptable. There would be a function for dereferencing the Tile that
returns the reference_count after it has been reduced. When reference
count goes to zero, we know it is time for the tile to go away.
struct Tile
{
typedef Hasher_MD5::Digest Identifier;
unsigned int reference_count;
Pixmap pixmap;
Tile () : reference_count(1U) {}
unsigned int dereference () {--reference_count; return
reference_count;}
} ;
An Image would consist of tiles at specific positions on the screen, so
I would need a Position struct:
struct Position {int x; int y; Position() : x(0), y(0) {}} ;
An image would be an association between tiles and positions of those
tiles on the screen. I would call this association the Image's
tile_list. I would maintain a static, shared (protected by mutex) map
call the tile_map that maps Tile::Identifier to Tile for the image. To
draw an image, one would iterate through the tile list. When it is
time for an Image to die, its destructor would:
1. Lock the global static shared tile_map;
2. Locate all tiles in tile_map that form its image, one by one,
dereferencing them.
3. If a dereferenced tile assumes reference_count = 0, remove it from
tile_map.
3. Unlock the global static shared tile_map;
struct Image
{
static Shared<Red_Black::Associative_Set<Tile::Identifier, Tile> >
tile_map;
Associative_List<Tile::Identifier, Position> tile_list;
~Image ()
{
if (tile_list.seek_first())
{
tile_map.acquire();
do
{
tile_map.locate(tile_list.LHE());
if (!tile_map.RHE().dereference())
tile_map.remove();
}
while (tile_list.seek_forward());
tile_map.release();
}
}
} ;
Note that, in all of this code, there is no mention of new or delete or
heaps or garbage collection, or smart pointers or weak pointers shared
pointers or auto pointers or anything like that. Just plain old
constructor/destructor behavior. And, on the assumption that there is
no bug in your basic libraries (that you have been using for 5+ years),
you can eyeball the code and know with certainty that there is no
possibility for memory leaks.
This is what we mean by giving the heap a rest. :)
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]