bugGNU Octave - Bugs: bug #64264, reorganize tsearch for a 20%...

 
 

bug #64264: reorganize tsearch for a 20% performance gain

Submitter:  A.R. Burgers <arb>
Submitted:  Tue 30 May 2023 07:19:25 AM UTC
   
 
Category:  Performance 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

Add a New Comment Rich Markup
   

Wed 31 May 2023 08:21:22 AM UTC, comment #4: 

comment #1:

> Do you need the variable det_pos at all?  You could replace "if (det_pos != 0)" with "if (det > 0)" and remove the other lines where it shows up. Does that keep the speed the same?


Yes, I had a look at that too. No with (det > 0) instead of (det_pos != 0) I don't see a performance gain for the same platform.

There is scope for some improvement here, but it seems to be quite sensitive to the exact environment and compiler settings,

A.R. Burgers <arb>
Wed 31 May 2023 01:20:07 AM UTC, comment #3: 

Compiling with AVX seems to shave off few percent:

octave:1> cd ~/scratch/
octave:2> tsearch1
set 1: 0.646555 seconds
set 2: 0.498888 seconds
octave:3> tsearch1
set 1: 0.646822 seconds
set 2: 0.497757 seconds
octave:4> __octave_config_info__ ("CFLAGS")
ans = -ggdb3 -O2 -march=native -mtune=native -mavx -mavx2 -flto=auto


(unpatched).

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Wed 31 May 2023 01:08:16 AM UTC, comment #2: 

On my AMD Ryzen 9 3950X patched version runs slower:


octave:1> cd ~/scratch/
octave:2> tsearch1
set 1: 0.678004 seconds
set 2: 0.522955 seconds
octave:3> tsearch1
set 1: 0.67786 seconds
set 2: 0.522666 seconds
octave:4> version
ans = 9.0.0
octave:5> ver
----------------------------------------------------------------------
GNU Octave Version: 9.0.0 (hg id: 10daf5ce7f28)
GNU Octave License: GNU General Public License
Operating System: Linux 5.14.0-316.el9.x86_64 #1 SMP PREEMPT_DYNAMIC Fri May 19 11:26:13 UTC 2023 x86_64
----------------------------------------------------------------------
octave:5> __octave_config_info__ ("CFLAGS")
ans = -ggdb3 -O2 -march=x86-64-v2 -mtune=native -flto=auto


and patched:

octave:1> __octave_config_info__ ("CFLAGS")
ans = -ggdb3 -O2 -march=x86-64-v2 -mtune=native -flto=auto
octave:2> ver
----------------------------------------------------------------------
GNU Octave Version: 9.0.0 (hg id: 10daf5ce7f28+)
GNU Octave License: GNU General Public License
Operating System: Linux 5.14.0-316.el9.x86_64 #1 SMP PREEMPT_DYNAMIC Fri May 19 11:26:13 UTC 2023 x86_64
----------------------------------------------------------------------
octave:3> cd ~/scratch/
octave:4> tsearch1
set 1: 0.78682 seconds
set 2: 0.610473 seconds
octave:5> tsearch1
set 1: 0.785013 seconds
set 2: 0.607194 seconds


I have not tried Arun's <arungiridhar> suggestion.

Dmitri.
--


Dmitri A. Sergatskov <dasergatskov>
Tue 30 May 2023 05:58:05 PM UTC, comment #1: 

Do you need the variable det_pos at all?  You could replace "if (det_pos != 0)" with "if (det > 0)" and remove the other lines where it shows up. Does that keep the speed the same?

Arun Giridhar <arungiridhar>
Group Member
Tue 30 May 2023 07:19:25 AM UTC, original submission:  

a 20% performance gain is possible in tsearch (gcc 9.5.0, -O2, x86_64-pc-linux-gnu) by replacing divisions by det with multiplications, and by reducing the scope of some variables, allowing maybe better optimization by the compiler


stock octave 9.0.0
set 1: 1.21331 seconds
set 2: 0.666747 seconds
patched tsearch
set 1: 1.00543 seconds
set 2: 0.602174 seconds


m-file to create test input.

np = 30000;
npf = 20000;
pts = rand(np, 2);
tri = delaunay(pts(:,1), pts(:,2));
p_find1 = rand(npf, 2);
p_find2 = [rand(npf, 1), 0.5 * ones(npf, 1)];
save('inp.mat', '-v7', 'pts', 'tri', 'p_find1', 'p_find2');


m-code test script

load('inp.mat');

x = pts(:, 1);
y = pts(:, 2);

p_find1_x = p_find1(:, 1);
p_find1_y = p_find1(:, 2);

p_find2_x = p_find2(:, 1);
p_find2_y = p_find2(:, 2);

tic; tsearch(x, y, tri, p_find1_x, p_find1_y); t=toc;
fprintf('set 1: %g seconds\n', t);
tic; tsearch(x, y, tri, p_find2_x, p_find2_y); t=toc;
fprintf('set 2: %g seconds\n', t);


shell script to compare 2 octave executables

#! /bin/sh
echo "stock octave 9.0.0"
octave-9.0.0 tst.m
echo "patched tsearch"
run-octave tst.m


A.R. Burgers <arb>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #54795:  b64264.cset added by arb (3KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    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.

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2023-05-30 arb Attached File- Added b64264.cset, #54795

    Back to the top

    Powered by Savane 3.13-f762.
    Corresponding source code