Gee Some improvements to ArrayList and LinkedList, Iterators I have in mind.

[Quikee <quikee gmail com>]

Hi,

I have some improvements in mind that could increase performance and
reduce memory footprint for ArrayList and LinkedList.

A problem with ArrayList is that when it hits the limit of the number
of elements its array can hold it needs to resize the whole array
which can be very time consuming. Currently the ArrayLists underlying
array has always the size of 10 when initialised and doubles the
capacity when it needs to extend. It would be nice if it would be
possible to say what the beginning capacity is as in some cases we
know the approximate number of elements but we are still safe if the
list exceeds this number. With only this we have the possibility to
minimise the number of resizes the ArrayList needs to do. Another
problem that can impact the memory usage is that the capacity doubles
- this works fine when the numbers of elements are small but it is not
so nice when the number of elements is large. For example if we have
the number of elements 20.000.000 and we exceed only by 1 element the
allocated array will increase to the size 40.000.000. In this case it
would be nice to have control over how many elements to grow the
internal array when we exceed capacity not just blindly double the
capacity in such case.

Current implementation of LinkedList uses an previous and next
pointers in a node which means that for every element we use 2
additional pointers. In case we have 1 million number of elements on
an 64-bit OS this means that ~16MB of memory will be used just to
store the previous/next poiners. There is a known XOR trick to just
use one pointer per node for double-linked list which would put the
memory consumption down by 1/3 and I would like to try to implement
this.

For quite some time I think that Iterator should also include
implement an Iterable interface by default as it makes possible to do
a lot of things that previously were not. For example an List could
also include a "reverse" iterator by default and could be conveniently
used like this:
foreach (Element element in list.reverse_iterator()) {...}
Now such iterators are not possible just because an iterator itself is
not iterable.

Additionally to this it would be nice to have a SimpleIterator
interface with only methods needed by Vala to iterate (I think only
iterator, get and next are needed). Current iterator in libgee
provides a lot of additional methods and if you want to use libgee
iterator interface you also need to implement all  those methods even
if you don't need them.

Regards,
Tomaž