Re: Array.init (was [Caml-list] Gripes with array)

[Christophe Raffalli <Christophe.Raffalli@univ-savoie.fr>]

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

Christophe Raffalli wrote:
> 
>>
>>>> Also, can Array.init be made to fill the elements only once?
>>>
>>>
>>> No, that's impossible without breaking the GC invariants.
>>
>>
> 
> This is not true if the runtime maintains a list of array in 
> construction with the current position of the index. This list will stay
> rather small, but each addresse read by the GC will have to be checked 
> for membership in the list. If the list is rather small it will be in 
> the cache, but still I am afraid it will slow down noticably the GC.
> 
> Did someone tried to implement such a list of partially initialized 
> objects in the GC ? (I do not think it is worth it ?)

> You could also lie in the tag about the size of array (if the way the 
> runtime finds free block of memory does not use it). It will cost an 
> increment of integer at each step in the initialisation process which 
> should not be much since the beginning of array may stay in the cache if 
> the initialisation function is simple and this will be neggligeable if not.
> 
> 
This second solution is only for non copying GC, so not for OCaml

And yet another solution would have to have a tag with the total size + 
the number of non pointers at the end of the block. This would be 
usefull not only for Arrays. It just makes again a (too) strong limit on 
the size of arrays.

I am now wondering why the structure of a block does not allow a second 
tag word (and even a third tag word) for the tag in case of big objects 
? A cons cell keeps a tag of only one word (that's still too much :-), 
but an array (or even only an array of size > 2^n) uses a bigger tag. 
Moreover this extra tag word could be at address (p-1) if p is the 
address of the object so that some code like unsafe.get do not need to 
access it.

The Gc and few other function like Array.length, Array.get in the bound 
check,.. would have an extra test to do, but the GC would have less 
memory to scan (because it would have to scan not all word in a block).


-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]