Elf wrote:
> On Tue, 12 Aug 2008, Per Bothner wrote:
>
>> Elf wrote:
>>> creation of a new fixed-length vector is O(1).
>>
>> To be nit-picky: I don't see how that is possible.
>> After all, the member for the vector does at least
>> have to br zeroed out.
>>
>> Of course the constant factor is usually very low.
>>
>
> it doesnt have to be zeroed if the gc sets everything to the undefined
> value
> when dead.  vectors dont autoinitialise to zero, the initialise to
> undefined,
> so its just a matter of creating a single header on top of sufficient
> space.

Whether an element is set to "zero" or "the undefined value" it
takes just as long.  Whether this is done when allocating the
object, or when collecting whatever was previously there - it
still has to be done, and it's still O(N).  And you can't reuse
whatever junk happens to be in those memory cells, since that
would confuse the gc.

Imagine allocating an array of a million elements, and you need to
get fresh pages from the OS.  The OS will have zero'd out those
pages (at least a modern desktop or server OS), for safety reasons.
And doing so is proportional to the size of the vector.
--
	--Per Bothner
xxxxxx@bothner.com   http://per.bothner.com/