Re: [Caml-list] Gripes with array

[skaller <skaller@users.sourceforge.net>]

On Sat, 2004-09-11 at 11:43, skaller wrote:
> On Fri, 2004-09-10 at 23:45, Damien Doligez wrote:
> 
> >  An intermediate solution would
> > be to make a "Array.unsafe_make" primitive, which would use memset 
> > instead of initialising the array properly.  

> 
> AFAICS tracking how much of an array is initialised
> with an index the GC can use costs a single
> comparison when you're not initialising arrays.

Specifically: I assume there is some GC 'object'
containing the state data for the collector.

Suppose we add a doubly linked list
of the type

struct pia { 
  pia *next; 
  pia *prev; 
  caml_heap_block *block; 
  unsigned long index; 
} *pial;

to the GC state data. pial means
'pointer to initialising array list'

In order to sweep a block *p for pointers,
you'd need to do this:

if (pial == NULL) usual_scan(p)
else {
  unsigned long index = find_index(pias,p);
  if (index) scan_array(p,index));
  else usual_scan(p);
} 

usual_scan() is the usual scanning algorithm
for a heap block, array_scan is a special
one where the initialised block length is
tracked. The index is incremented when filling
in the array. If the fill is using a fixed value,
every 4K elements, if a function, each element.

All the scan calls are tail recurisve.
I imagine usual_scan and array_scan would
be the different entry points to the same
routine. Clearly the array initialiser
has to be able to add and remove a the pia descriptor
from the list. In addition, the compactor would
need to adjust the heap pointers in the list.

So in the case we're not currently initialising
an array, we require one memory fetch, a load
of the value 'pial'.

Perhaps 'pial' would reside in the cache,
even if it does it is displacing one other value.
So there is a definite cost for all code with
this technique.

BTW: the Felix collector has an array index count
in every heap header block. The actual block
size is independent of this count. As I understand
it the block size indicator in Ocaml is *also* used
to determine string and array sizes which prevents
it being adjusted dynamically during initialisation?

This would be in case there is an exception thrown 
and the array become prematurely unreachable,
since otherwise the array can't be disposed until
it is initialised, and the disparity between
the dynamic and static length would not matter.
The static length is required to free the memory.

This suggests an alternate solution with zero
impact on the sweep: swap the meaning of the
length count in the heap block and pial list.

This means the 'free' routine that disposes
of unreachable heap memory would have to check
the list to find the real memory length.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners