save -v7 problem

[David Bateman]

Gunnar Raetsch wrote:
> Hi David,
>
>> What is your default save format? Basically I wonder of the problem 
>> is the matlab file format in this case or the fact that the file is 
>> compressed with the -v7 option. Have you tried the -v6 option and see 
>> if the same issue occurs.. That will at least isolate the issue to 
>> the matlab file handling or the compression... I don't know when I'll 
>> have time to look at this issue further, but will if I get the time
> I tried -v6 and the same problem occurred. I also tried -v4 but it 
> does not support structures and it failed.
> I tried -hdf5 and it was very slow as well (-binary was fast, 
> -float-hdf5 slow).
> So, essentially, any format except octaves text or binary format was 
> very slow.
>
> Cheers, Gunnar
>
>
Ok looking at this quickly I see that the variable blocks is a 1x11477 
structure with 17 fields... Using the code

tic; save("/tmp/xxx3.mat", "blocks(1:n)","-v6"); toc

and varying "n" it is easy to see that the save function in the -v6 
format has a speed that is proportional to the square of the number of 
elements in the structure. The code that loops over the elements of  the 
structure to save them in this case is

    int len = m.numel ();

    for (int j = 0; j < len; j++)
      {
        // write the data of each element

        // Iterating over the list of keys will preserve the order
        // of the fields.
        for (octave_idx_type i = 0; i < nf; i++)
          {
        Cell elts = m.contents (keys(i));

        bool retval2 = save_mat5_binary_element (os, elts(j), "",
                             mark_as_global,
                             false,
                             save_as_floats);
        if (! retval2)
          goto error_cleanup;
          }
      }
 
and in the octave ascii and binary formats the order of the loops is 
reversed, so that the cell array "elts" is only formed nf times rather 
than n*nf times as in the code above.. Fixing this by forming a 
temporary vector of the cell arrays with the fields contents



    // Create temporary copy of structure contents to avoid multiple
    // calls of the contents method
    std::vector<const octave_value *> elts (nf);
    for (octave_idx_type i = 0; i < nf; i++)
      elts[i] = m.contents (keys(i)).fortran_vec ();

    for (octave_idx_type j = 0; j < len; j++)
      {
        // write the data of each element

        // Iterating over the list of keys will preserve the order
        // of the fields.
        for (octave_idx_type i = 0; i < nf; i++)
          {
        bool retval2 = save_mat5_binary_element (os, elts[i][j], "",
                             mark_as_global,
                             false,
                             save_as_floats);
        if (! retval2)
          goto error_cleanup;
          }
      }

basically doubles the speed, but the O(n^2) speed remains. I used a 
const octave_value* vector to avoid any potential issues with boundary 
checking in the above.. For the life of me I can't see where the remain 
O(n^2) dependency is in the above code.. Maybe someone else might see 
where the issue is..

D.

-- 
David Bateman                                dbateman at dbateman.org
35 rue Gambetta                              +33 1 46 04 02 18 (Home)
92100 Boulogne-Billancourt FRANCE            +33 6 72 01 06 33 (Mob)