Serge D. Mechveliani wrote:
>
> * I was not aware of FlexibleArray.
> * In principle, when there are n items, does this FlexibleArray need
> a _continuous_ space in the memory of size O(n) ?
Yes. Are you worried by this continuity requirement? Note that
even when using nonrelocating garbage collector in worst
you need 2Nlog_2(N) memory to satisfy arbitrary sequence of
allocations and deallocation which at any given time sum
of allocated memory does not exceed N. For realistic sizes
log(N) is of order 30, which frequently is less than constants
hidden in big O notation. In practice on 64-bit machines
paging will reduce this worst case factor from 30 to something
like 8, and probablistically anything sigificantly bigger than 1
is unlikely.
And of Lisp we use only ecl uses non-relocating garbage collector.
BTW. If something like list (or a tree) os discontinuous, then
accessing new node is likely to cause cache misses. Excessive
cache misses may slow down program by factors of order 50-200.
So, you _really_ want to keep data in continuous space, because
otherwise you risk significat slowdown.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
