[Octave-bug-tracker] [bug #61674] deconv much slower than conv

[Arun Giridhar]

Follow-up Comment #2, bug #61674 (project octave):

I cannot replicate OP's test reliably, because those tests take only a
millisecond or less, as Kai also saw.

It is known that deconv is roughly 10x slower than conv2 for large N though.
But I do not consider this a bug, just the behavior of conv2 and filter, which
is called by deconv.

Here is a demo with cyclotomic polynomials that I edited to highlight the
difference (two functions attached).

If you are benchmarking these functions, you will need to run each with a
fresh Octave session because they use memoization, so any subsequent calls
with the same input from the same Octave session will be instant.

Only 4.3 seconds for the fast version that prefers conv2 over deconv:

octave:1> N = 40320; profile clear; tic; profile on; P =
cyclotomicpolynomial_conv (N); profile off; toc, T = profile("info"); profshow
(T)
Elapsed time is 4.31985 seconds.
   #                  Function Attr     Time (s)   Time (%)        Calls
------------------------------------------------------------------------
  52                     conv2             3.481      80.68         1844
  58                    filter             0.742      17.20           91
   1 cyclotomicpolynomial_conv    R        0.064       1.48           96
  11                   isprime             0.007       0.16           95
  51                      find             0.004       0.10         3779
  54                    deconv             0.003       0.08           91
  23                    primes             0.002       0.05           73
   9                 binary ==             0.002       0.04         3876
  29                      cast             0.002       0.04           73
  10                       any             0.001       0.03         2108
  41                     zeros             0.001       0.02          207
  47                       end             0.001       0.02         4163
  18                    lookup             0.000       0.01          168
  44                 binary ./             0.000       0.01           91
  49                      size             0.000       0.01          328
   3                  prefix !             0.000       0.00          889
  30                    strcmp             0.000       0.00          146
  46                 binary .*             0.000       0.00           91
  33                     feval             0.000       0.00           73
  45                     round             0.000       0.00           91


Compared with 34.8 seconds for the version that calls only deconv and not
conv2:

octave:1> N = 40320; profile clear; tic; profile on; P =
cyclotomicpolynomial_deconv (N); profile off; toc, T = profile("info");
profshow (T)
Elapsed time is 34.8092 seconds.
   #                    Function Attr     Time (s)   Time (%)        Calls
--------------------------------------------------------------------------
  59                      filter            34.586      99.39         1844
   1 cyclotomicpolynomial_deconv    R        0.104       0.30           96
  55                      deconv             0.067       0.19         1844
  11                     isprime             0.007       0.02           95
  54                        find             0.006       0.02         3688
  41                       zeros             0.003       0.01         1945
  23                      primes             0.002       0.01           73
  52                        size             0.002       0.01         3804
   9                   binary ==             0.002       0.01         3876
  29                        cast             0.002       0.00           73
  10                         any             0.001       0.00         2108
  60                    isargout             0.001       0.00         1844
  53                    binary -             0.001       0.00         3794
  56                    isvector             0.001       0.00         3688
  58                    iscolumn             0.001       0.00         3688
  47                         end             0.001       0.00         4163
  40                    binary +             0.001       0.00         4158
   3                    prefix !             0.001       0.00         2642
  51                      length             0.001       0.00         3890
  57                       isrow             0.001       0.00         1844


Both codes call either conv2 or filter the same 1844 times, but for conv2 it
takes 3.5 seconds and for deconv it takes 35 seconds.

The only workaround I see is to reduce the number of polynomial divisions in
one's code. This just seems to be the nature of those functions, not a bug
necessarily.

(file #52505, file #52506)
    _______________________________________________________

Additional Item Attachment:

File name: cyclotomicpolynomial_conv.m    Size:1 KB
   
<https://file.savannah.gnu.org/file/cyclotomicpolynomial_conv.m?file_id=52505>

File name: cyclotomicpolynomial_deconv.m  Size:1 KB
   
<https://file.savannah.gnu.org/file/cyclotomicpolynomial_deconv.m?file_id=52506>



    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?61674>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/