Refactor SofQWNormalisedPolygon for performance

[eXeC64]

This issue was originally TRAC 11746

Running the script below seemed very slow so I profiled the execution.

source_file = 'MAP05935_ei34.nxspe'
mat_ws = 'MAP05935'
Load(Filename=source_file, OutputWorkspace=mat_ws)
SofQW(InputWorkspace=mat_ws, OutputWorkspace='out', QAxisBinning='0,0.02,5', EMode='Direct', Method='NormalisedPolygon')

Valgrind indicates that 30% of the execution time is being spent handling thrown exceptions. This comes from the call in SofQNormalisedPolygon::exec to Rebin2D::rebinToFractionalOutput which calls intersectionByLaszlow in a tight loop. intersectionByLaszlow returns either a ConvexPolygon representing the intersection, or throws an exception. We're throwing a huge number of exceptions in a tight loop, which is very bad for performance.

Instead intersectionByLaszlow should accept an additional non-const ConvexPolygon reference that will be used for output, and then return a bool indicating whether an overlap exists. This should reduce the execution time by 30%.

In addition, there is a strongly suspected secondary performance problem: Vertex2D. Vertex2D is a V2D like class that implements its own linked list. It's used by ConvexPolygon to represents the polygon's vertices. During the execution of the algorithm we allocate and deallocate thousands of Vertex2Ds on the heap, which cannot be good for the algorithm's performance. We should strongly consider removing Vertex2D from Mantid in totality, and in this case use std::vector`` instead.

Overall this ought to improve performance by 40%, if not more. A performance test should be created before refactoring work begins, to allow measuring any performance improvements made.

---

Keywords: maintenance

[eXeC64]

@martyngigg (2015-05-26T09:17:23):
Thanks for the profile information. I had always wondered whether the tight-loop exception handling was an issue and it's good to have some hard numbers to say so.

I think this will probably split into 2 tickets as the it will be worth reprofiling after the exception changes to see whta difference the Vertex2D changes can make. A lot of that code was borrowed from another place that implemented the algorithm.