[Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm

[Nicholas Jankowski]

Update of bug #60818 (project octave):

                  Status:             In Progress => Patch Submitted        

    _______________________________________________________

Follow-up Comment #53:

ok, never figured out how to get around the high nD memory issue, so uploading
a new patch. Hoping this might be sufficient to push for now (maybe for 7?),
tabling some of the performance improvement until a later task. 

1 - fixes all codepaths so they use the same volume comparison for trivial
simplex removal. (main bug topic needing to be fixed)

2 - in the process, simplifies the n-D for loop by pulling as much of the
calculation outside of the loop as possible. (the actual det function is the
only thing left inside.)  speeds up for loop about 2-4x for 3D and 4D cases
over the current delaunayn

3 - pulled just the 3D case out into its own explicit path like 2D.  Figured
2D and 3D are likely most used (eg by interpolant and grid functions) and
would benefit the most, and there had been no question on which det approach
made sense for 3D. pulling it out is about 10-20x faster than leaving it in
the loop, 20-40x faster than the old loop.

I also added a couple BISTS for 3D and 4D, including a simple 3D that requires
trivial simplex removal, and added more explanatory comments to the code.

This makes a decent improvement over current version. Dealing with the memory
impact of vectorizing the nD part can be a separete performance improvement
task.  

(file #52303)
    _______________________________________________________

Additional Item Attachment:

File name: bug60818-delaunayn-v8.patch    Size:6 KB
   
<https://file.savannah.gnu.org/file/bug60818-delaunayn-v8.patch?file_id=52303>



    _______________________________________________________

Reply to this item at:

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

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