Re: Graphics and memory opinions

[Jordi Gutiérrez Hermoso]

2008/12/14 John W. Eaton <address@hidden>:
> On 14-Dec-2008, Jordi Gutiérrez Hermoso wrote:
>
> | Right, std::list triples the storage size. Clearly std::deque or
>
> I don't see how a deque helps, it is just another variant of a list,
> with overhead for each element.

No, it's not implemented as a linked list. I don't quite understand
its optimisations, but it's faster than a vector or a list to do
push_back 1e8 times on a deque than on a vector or a list, and the
deque's storage size is only slightly larger than vector, instead of
three times larger as happens with a list. I do know that deque
doesn't have contiguous allocation in memory, which may be a problem.

> | std::vector are the ones to use here.
>
> Then you will just have to copy them into an Octave Array<> object.

Hm... is there a way to avoid this? Loading everything into
std::vector guarantees the data is stored contiguously in memory, and
&thevec[0] gives me a pointer to this data... this data is ready to be
cast into Matrix, but the only problem is that it's still owned by
thevec. Can this be fixed?

> So why not just use that to begin with?

Because stdlib vectors and deques are optimised to be resized on the
fly. I believe that doing push_back n times on an initially empty
vector results in O(log n) resizes, since each push_back beyond the
currently allocated storage just doubles the allocation storage in the
GNU implementation, which overall ends up being cheap and allows you
to eliminate the double parse.

>  trick is efficiently approximating the the
> size of the matrix so you can minimize the number of times you have to
> resize and copy.

>From a few random tests I've made, the speed bottleneck isn't in
resizing and copying memory, but in parsing the data to and from
ASCII, so the double pass is the big culprit. Anyways, doing only
O(log n) resize and copy operations however std::vector and std::deque
do it, it's not a big deal.

Thanks for the hint on what file to look at. I still have a really
hard time finding my way around the sources.

- Jordi G. H.