bugGNU Octave - Bugs: bug #67653, deconv is slower than interpreted...

 
 

bug #67653: deconv is slower than interpreted code for inputs with zeros

Submitter:  Arun Giridhar <arungiridhar>
Submitted:  Fri 31 Oct 2025 03:55:07 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Post a Comment

Add a New Comment Rich Markup
   

Discussion

Jump to the original submission

Thu 06 Nov 2025 10:50:06 PM UTC, comment #7: 

Crosslinking the discussion at bug #61674.

Arun Giridhar <arungiridhar>
Group Member
Tue 04 Nov 2025 06:43:29 PM UTC, comment #6: 

I used the attached version of "filter.cc"

(file filter.cc)

Dmitri.
--


(file #57777)

Dmitri A. Sergatskov <dasergatskov>
Tue 04 Nov 2025 03:56:03 PM UTC, comment #5: 

Thanks for testing the options. I've pushed the change in comment #1 on a trial basis but hopefully there's a cleaner way to do it than splitting into cases.

Btw how did you get BLAS axpy to work on such serial code? I'm just surprised it allowed overwriting the result vector by one place to the left without causing trouble in parallelization.

I came across std::transform and std::inner_product that might do the same thing in native C++ STL but I have no idea of the overhead they might take.

Arun Giridhar <arungiridhar>
Group Member
Mon 03 Nov 2025 08:53:11 PM UTC, comment #4: 

I did try patching it with BLAS. With OpenBlas it matches your patched performance at your polynomial test case, but is ~2 slower than original for more "normal" filters examples I tried.

(The 1 thread was the fastest.) I guess the improvements were due to memory access pattern.

Your simple patch seems to be about the same for those test samples and about 1.8 times faster for your test case (than the original one).

I also tested some other sygnal functions that rely on "filter" and they all pass. So I propose to push you diff for now and see if we can detect/improve sparse cases.

Just FYI.

Dmitri.
--


Dmitri A. Sergatskov <dasergatskov>
Sat 01 Nov 2025 01:29:51 AM UTC, comment #3: 

I'm dubious about using BLAS for filter. The code inside the tightest for-loop looks fully serial:


// Inner loop, no interruption
for (octave_idx_type j = lo; j <= hi; j++)
  psi[j] = psi[j+1] - pa[j+1] * py[idx] + pb[j+1] * px[idx];


So each (jth) element of psi is calculated from the next (j+1-th) one. Can that even be parallelized at all?

Arun Giridhar <arungiridhar>
Group Member
Fri 31 Oct 2025 10:14:32 PM UTC, comment #2: 

At first glance "filter" could use BLAS axpy (similar to oct-convn.cc).

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Fri 31 Oct 2025 09:44:22 PM UTC, comment #1: 

The attached patch speeds up filter.cc by a factor of 2, but I have no idea if this is the right way to do it.



(file #57758)

Arun Giridhar <arungiridhar>
Group Member
Fri 31 Oct 2025 03:55:07 PM UTC, original submission:  

While working with cyclotomic polynomials, I found that doing polynomial division with the compiled function deconv() is some 150 times slower than using interpreted code.

Test:

## Dividend is the polynomial  x^362880 - 1
a = zeros (1, 362881);
a(1) = 1;
a(end) = -1;

## Divisor is this big composite polynomial
b = zeros (1, 279937);
b([1 1729 17281 19009 20737 36289 38017 60481 62209 77761 79489 81217 96769 98497 186625 188353 190081 210817 212545 214273 247105 248833 250561 271297 273025 274753]) = 1;
b([5185 6913 8641 29377 31105 32833 65665 67393 69121 89857 91585 93313 181441 183169 198721 200449 202177 217729 219457 241921 243649 259201 260929 262657 278209 279937]) = -1;

## Define this function to do polynomial division as we learned in middle school.
function [q, r] = polynomialdivision (a, b)
  na = numel (a);
  nb = numel (b);
  q = zeros (1, na-nb+1);
  r = a;

  for i = 1:na-nb+1
    if (r(i))
      q(i) = floor (r(i) / b(1));
      r(i-1 + (1:nb)) -= q(i) * b;
    end
  end
endfunction

## Benchmark
tic; c = deconv (a, b); toc
tic; d = polynomialdivision (a, b); toc

## Make sure they are the same result
assert (c, d)


Result:

Elapsed time is 7.92256 seconds.
Elapsed time is 0.051795 seconds.


That is some 150 times slower than interpreted code when the divisor has a lot of zero coefficients.

The problem seems to be that when the input divisor has many zeros, then deconv() wastes time doing divisions and subtractions that will not affect the result, essentially multiplying a long vector by zero and subtracting that zero result from the vector. The interpreted code above only does the division / multiplication / subtraction when the corresponding value is nonzero.

Should we detect numerically sparse inputs in deconv() and compute them differently?

Arun Giridhar <arungiridhar>
Group Member

 

Attached Files

Attached Files
file #57777:  filter.cc added by dasergatskov (22KiB - text/x-c++src)
file #57758:  filter_diff.txt added by arungiridhar (2.1KiB - text/plain)

(Note: upload size limit is set to 16MiB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

 

Dependencies

This item does not depend on any other items.

No items depend on this one.

 

Mail Notification Carbon-Copy List

Carbon-Copy List
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by arungiridhar (Submitted the item)
  •  

    Votes

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    History

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2025-11-04 dasergatskov Attached File- Added filter.cc, #57777
    2025-10-31 arungiridhar Attached File- Added filter_diff.txt, #57758

    Back to the top

    Powered by Savane 3.16.
    Corresponding source code