[mercury-users] Structure reuse

[Ralph Becket]

Michael Day, Tuesday, 15 July 2003:
> 
> Hmm, what happens to garbage on the heap that has not yet been reclaimed,
> when the heap does not fit into real memory? Will it be swapped out? When
> the garbage collector runs, will it be swapped back in to be traversed?

If the heap is large enough then pages containing no live data will
eventually be paged out.

The GC only traverses live data, so in theory the pages of dead data
need not be paged back in.  However, the Boehm GC uses free lists and,
to the best of my knowledge, coalesces contiguous free blocks.  So the
dead data will be paged in.  But this probably isn't as big a cost as
you might imagine.

> Basically, will the current behaviour lead to unnecessary page faults and
> thrashing as well as CPU cache misses, when the heap contains a lot of
> garbage that could have been reclaimed earlier?

The trade off is this:
- frequent GCs mean you frequently traverse the entire live set (and,
  for the Boehm GC, the entire heap when reclaiming space);
- infrequent GCs mean you rarely traverse the entire live set (and,
  for the Boehm GC, the entire heap when reclaiming space), but may well
  end up paging more on a collection.

You can set the heap size by putting "--heap-size=2048", say, in your
MERCURY_OPTIONS environment variable, to limit the program to a 2MByte
heap.

> > Have you considered using a store and referencing subtrees via mutvars?
> 
> Yes, however then I'm programming in C++ again, albeit with a slightly
> more awkward syntax :)
> 
> Seriously, I've looked at that approach, but it does bulk out the code 
> significantly...

Them's the breaks!

> > One can't backtrack over these structures, but since you're interested
> > in destructive update that shouldn't be an issue.
> 
> ...as it also stops you backtracking in a read-only fashion and using 
> semidet predicates to match portions of the tree for updating.

That's fine: use predicates returning bool.

> Once you make all your predicates update the io state and return bool
> instead of failing Mercury becomes much more tiresome. Specifically,
> declarative languages make manipulating trees fun! I just want it to be
> efficient as well as fun :)

Well, state variables should make it a little less painful (and you'd
probably want to pass a store around rather than the IO state).

Nancy's optimization is what you want.  But if you really positively
have to manage your own pointers then you can't use full-on applicative
programming.

-- Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------