Re: slow char({str})

[Jaroslav Hajek]

On Wed, Jun 24, 2009 at 5:31 AM, Daniel J Sebald<address@hidden> wrote:
> Jaroslav Hajek wrote:
>>
>> On Sun, Jun 21, 2009 at 7:33 PM, Ben Abbott<address@hidden> wrote:
>>
>>> I noticed a substantial amount of time is needed to convert a cell string
>>> into a string
>>>
>>> octave:50> tic; char ({repmat("a", [1, 100000])}); toc
>>> Elapsed time is 11.9 seconds.
>>>
>>> but ...
>>>
>>> octave:51> tic; char ({repmat("a", [1, 100000])}{1}); toc
>>> Elapsed time is 0.001117 seconds.
>>>
>>> Can someone with skilled in c++ take a look?
>>>
>>> Ben
>>>
>>
>>
>> Please check
>> http://hg.savannah.gnu.org/hgweb/octave/rev/4ff6f8efdda2
>>
>> also transplanted into 3.2.x.
>>
>> thanks
>
> Very nice Jaroslav.  Which of these changes is the speedup coming from?
>  This hunk
>
> -       elem (i, j) = s[i][j];
> +       elem (i, j) = si[j];
>
> shouldn't have been too much as there is only a little extra computation in
> the indexing before the change.

No. In fact, this *was* the bottleneck, changing a linear complexity
operation to quadratic one. Welcome to the world of COW magic. The
expression s[i][j] forces a copy of the whole string, *for each j*.
This could be avoided if Array<T>::elem () const returned const T or
const T& rather than just T. Only Array<std::string> has this issue,
though.
Many Octave classes are COW, and carry similar dangers. They are
mostly avoided by using const qualifiers wherever possible. This is a
good idea anyway, so I don't regard the current state as really bad.
If you ignore const-ness, things will work, but you may lose
performance.

>  From the looks of all_strings, I'd guess
> this is the important change:
>
> -      string_vector s = matrix(i).all_strings ();
> +      const string_vector s = strvec_queue.front ();
> +      strvec_queue.pop ();
>
> The member function ::all_strings() isn't used too often.  Would it make
> sense to remove ::all_strings() and replace it's use with similar mods?
>
> Dan
>

The queue is to prevent the all_strings() conversion being called
twice. Yes, it is a bit unfortunate that joining a cell containing
only character arrays requires converting them to strings and then
converting back. The problem is that all_strings() is actually used
for two different purposes - converting a variable to a vector of
strings, and joining+padding. Improvements are surely welcome.

-- 
RNDr. Jaroslav Hajek
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz