Re: Slowness in function 'open'

[John W. Eaton]

On 22-Jun-2007, Jordi Gutierrez Hermoso wrote:

| An std::list is almost always implemented as a doubly-linked list (the
| C++ standard specifies that finding an element in the list must be
| O(n), for example). This means that besides all the doubles it has to
| store, it has two store 2n pointers to doubles. On a 64-bit system
| where I think pointers are the size of doubles, this may mean that the
| list itself occupies 3 times the size of the matrix data it's storing.
| Perhaps this is unacceptable, but on the other hand, you can pop
| elements from the list as you're reading it, so it's only a temporary
| storage space.

It may be OK these days, but at one time it probably would have been
unacceptable.  Also, you still have to copy the data once after
reading it.  But, you only have to copy it once, not multiple times as
might happen if you are guessing the size and then force to resize a
few times.

| Can you give me a quick description of how Octave matrices are
| represented internally? Are they contiguous in memory? Column-major
| Fortran order? Is reshaping a matrix O(1)?

Yes, yes, yes, and yes.

If you go the guess and resize route, you will want to do something
like

  Matrix m (guess_size, 1);

  double *pm = m.fortran_vec ();

Then work with pm.  If you run out of space, you can do:

  m.resize (new_guess, 1);

  pm = m.fortran_vec ();

and keep adding elements where you left off in the array (but pm will
have a new value, so be careful to use an index and not a pointer
here).  In the end, you will need to resize to the actual number of
elements read, then rehape to (nc, nr) and then transpose (you read by
rows but stored by columns).  The final resize will force a copy as
will the transpoe operation.  Or, you could combine those operations
by doing your own with a new result matrix of the appropriate size and
transpose as you copy.  Or, you could use a std::vector object for the
temporary storage and only use the Octave matrix object when you
create the final result.  So maybe the std::list idea is competitive
here.  Multiple resizes could chew up some memory too as the reclaimed
chunks may not be large enough for immediate reuse.

Finally, and in case it is not already obvious, I'd just like to ask
everyone who sees bad performance and then thinks "hey, what was jwe
smoking when he wrote that code?  I'm sure I can do much better than
that", to remember that it is not always as simple as it seems at
first.  I'll admit that the performace is bad in this case and that it
could certainly be better (two passes looked like a good idea at the
time, but all the work to look for comments and check sizes is
duplicated, and that is definitely bad).  But perhaps now you see that
there are a few extra gotchas that were not immediately obvious and
that can have an impact on performace.  And we can't just throw out
those requirements because then we'll see some other new user
complaining that "Octave sucks because it can't read my file but
Matlab can".

Also please remember that the Octave community has limited resources 
and is made up of almost 100% volunteers.  So the first requirement
for me is always to make it work and worry about performance later.

Thanks,

jwe