bugGNU Octave - Bugs: bug #63376, tsearchn quite slow (compared to...


bug #63376: tsearchn quite slow (compared to tsearch)

Submitter:  A.R. Burgers <arb>
Submitted:  Thu 17 Nov 2022 10:00:18 AM UTC
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  In Progress 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

Jump to the original submission

Fri 25 Nov 2022 06:13:25 PM UTC, comment #10: 

The value of -1e-12 is unchanged from before. It is the same threshold in tsearch.cc as well. I haven't found an error analysis for whether / why that value works best for this code.

Arun Giridhar <arungiridhar>
Group Member
Fri 25 Nov 2022 05:44:23 PM UTC, comment #9: 

I checked in an additional changeset to use more Octave coding conventions in tsearchn.m.  See http://hg.savannah.gnu.org/hgweb/octave/rev/c664627d601e.

One of the things I noticed was this line:

    inside = all (b >= -1e-12, 2);  # -1e-12 instead of 0 for rounding errors

Is the hard criteria of -1e-12 appropriate or should it scale in some way with the input?  Also, is it ever possible that the input are not double values, but single values, and this cut-off should change to reflect that?

Rik <rik5>
Group administrator
Fri 25 Nov 2022 05:01:01 PM UTC, comment #8: 

Thanks. Pushed here to default: https://hg.savannah.gnu.org/hgweb/octave/rev/72ef3d097059

Marking as Ready for Test.

Arun Giridhar <arungiridhar>
Group Member
Fri 25 Nov 2022 04:02:31 PM UTC, comment #7: 

Since this is a feature (performance improvement), rather than a bug fix, I think it should go on the development branch.  The stable branch is really in "feature freeze" mode right now as we are hopefully just a month away from a release.

Rik <rik5>
Group administrator
Thu 24 Nov 2022 11:36:37 PM UTC, comment #6: 

Does anyone have any thoughts on whether this patch should go to stable (Octave 8) or default (Octave 9)?

Arun Giridhar <arungiridhar>
Group Member
Wed 23 Nov 2022 07:24:39 PM UTC, comment #5: 

Yes, to me that patch looks good and makes perfect sense: in-lining cart2bary and falling back to tsearch when possible.

A.R. Burgers <arb>
Wed 23 Nov 2022 11:56:52 AM UTC, comment #4: 

I made an updated patch (attached). This one calls the faster tsearch.cc where possible. With it, your test becomes as fast in tsearchn as in tsearch, but that will change if you e.g. request the barycentric coords.

(file #53994)

Arun Giridhar <arungiridhar>
Group Member
Tue 22 Nov 2022 07:20:49 AM UTC, comment #3: 

OTOH octave's specialized 2D tsearch seems quite fast.
matlab's R2019B tsearchn needs about 4.2 seconds, a factor 4-5 slower for the same size search on the same platform.

Clearly not a trivial problem. Speeding up probably requires some geometric preprocessing, setting up data structures, which may be worth while or not depending on problem size or the number of searches in relation to the extra preprocessing work.

e.g. https://hal.inria.fr/inria-00166711

A.R. Burgers <arb>
Fri 18 Nov 2022 12:54:11 PM UTC, comment #2: 

Try the attached patch. It sped it up by maybe 20%, but not much more than that for me -- it reduced from some 20X as slow to some 16X as slow as tsearch.cc.

I tried using the bounding box method from tsearch.cc but that only slowed it down even more.

(file #53970)

Arun Giridhar <arungiridhar>
Group Member
Thu 17 Nov 2022 10:57:09 PM UTC, comment #1: 

Using the profiler, it looks like it is not just the for loop.  The conversion of Cartesian to barycentric coordinates (a subfunction in tsearchn.m) is what is taking most of the time.

  tsearchn: 1 calls, 102.605 total, 20.921 self
    1) tsearchn>cart2bary: 79968 calls, 75.149 total, 20.269 self
    2) binary >=: 79968 calls, 3.237 total, 3.237 self
    3) all: 79968 calls, 3.162 total, 3.162 self
    4) prefix -: 79968 calls, 0.136 total, 0.136 self
    5) NaN: 2 calls, 0.000 total, 0.000 self
    6) size: 1 calls, 0.000 total, 0.000 self
    7) rows: 2 calls, 0.000 total, 0.000 self
    8) postfix .': 1 calls, 0.000 total, 0.000 self
    9) binary +: 1 calls, 0.000 total, 0.000 self
    10) nargin: 1 calls, 0.000 total, 0.000 self
    11) binary !=: 1 calls, 0.000 total, 0.000 self

Rik <rik5>
Group administrator
Thu 17 Nov 2022 10:00:18 AM UTC, original submission:  

tsearchn seems to be quite slow, as illustrated by the code below with a triangulation of the unit square. In this example 30 times slower in the 2D case than tsearch.

tsearch is a compiled built-in function, tsearchn is m-code, with a non-vectorized for loop on the triangles, but vectorized over the points to be looked up.

np = 40000; np_lookup = 10000;
x = rand(np,1); y = rand(np,1);
tri = delaunay(x,y);
xi = rand(np_lookup,1); yi = rand(np_lookup,1);

fprintf('np=%d, nt=%d, np_lookup=%d \n', np, size(tri, 1), np_lookup);
tsearch(x, y, tri, xi, yi);
t1 = toc;
fprintf('tsearch time %g\n', t1);

tsearchn([x, y], tri, [xi, yi]);
t2 = toc;
fprintf('tsearchn time %g\n', t2);
fprintf('ratio: %g\n', t2/t1);

np=40000, nt=79973, np_lookup=10000
tsearch time 0.891463
tsearchn time 24.2793
ratio: 27.2354

A.R. Burgers <arb>


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

Attach Files:

Attached Files
file #53994:  tsearchn.patch added by arungiridhar (3KiB - text/x-patch)
file #53970:  tsearchn.patch added by arungiridhar (3KiB - text/x-patch)


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by arungiridhar (Updated the item)
  • -email is unavailable- added by rik5 (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.


    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-11-25 rik5 StatusReady For Test In Progress
    2022-11-25 arungiridhar StatusNone Ready For Test
    2022-11-23 arungiridhar Attached File- Added tsearchn.patch, #53994
    2022-11-18 arungiridhar Attached File- Added tsearchn.patch, #53970

    Back to the top

    Powered by Savane 3.13-4b48.
    Corresponding source code