Re: [Chicken-users] length performance

[John Cowan]

Mario Domenech Goulart scripsit:

> I've noticed that the performance of the length function is a bit low
> for medium/large lists.  As far as I understand (from runtime.c
> C_i_length), Chicken counts the elements from the given list everytime
> length is invoked.  Is it like that?

It is.

> If so, wouldn't it be better to have a list attribute which keeps the
> number of elements?  So, the cost of invoking length would be nearly the
> cost of accessing a variable (of course, there is the cost of keeping
> the attribute up-to-date whenever an insertion/removal occurs and the
> memory usage).  I think Python uses this approach.

Lists are not a basic datatype in Scheme; they are sequences of more
primitive datatypes called pairs.  There is a pair for each element
of the list, containing pointers to (a) the item and (b) the pair for the
next item, or the special object '() if there is none.
Lists can and do share storage with other lists if their tail portions
are the same.

In order to keep counts as you suggest, it would be necessary to keep
a count with *each* pair, thus increasing the storage cost by 50%.

-- 
A witness cannot give evidence of his           John Cowan
age unless he can remember being born.          address@hidden
  --Judge Blagden                               http://www.ccil.org/~cowan