Performance and code quality improvements needed

[SimplyNaOH]

I have come a long way in trying to optimize this implementation of Fortune's Algorithm, but the latest iteration 57cb02c still under-performs. What I did accomplish is both, eliminate space leaks, and achieve a reasonable running time dependence on the number of points (the data seems to fit O(n log n) ).

Improvement over iterations:

Performance of the latest iteration:

As a reference this javascript implementation includes some benchmarking information, and provides a basis to compare the performance of this code against.

Nº of Centers	This implementation	Reference	Performance ratio
10000	0.823 s	0.251 s	3.28
20000	1.67 s	0.451 s	3.70
200000	18.4 s	4.29 s *	4.289 *

* This is the result of a single run (no averaging), so it shouldn't be taken too seriously.

This goes to show that there is still room for improvement. At the same time, I'm looking forward to receiving criticism to my code, specially regarding what is idiomatic Haskell and what is not, as I'm learning along the way.

If you want to help me but are not familiar with fortune's algorithm, here is a great explanation.

[lpeterse]

I was curious and cloned your project. Unfortunately, I don't have time to further get into it, but I just wanted to share the profiling information I gathered.

Hint: Concentrate on the hot spots and try to avoid using lists (if possible).

    Tue Nov 15 19:17 2016 Time and Allocation Profiling Report  (Final)

       voronoi-exe +RTS -sstderr -s -p -hy -RTS -o test.svg -w 1000

    total time  =       15.58 secs   (15577 ticks @ 1000 us, 1 processor)
    total alloc = 5,931,295,080 bytes  (excludes profiling overheads)

COST CENTRE           MODULE                                          %time %alloc

polygonFrom.edges'    Main                                             47.8    0.1
formatRealFloat       Data.Text.Lazy.Builder.RealFloat                 13.2   37.4
polygonFrom.edges'.\  Main                                              5.5    0.0
render'.polygons.\    Main                                              2.8    0.0
renderAttr.\          Graphics.Rendering.SVG                            2.2    3.8
concat                Data.Text                                         1.9    4.8
getAttr.ty            Diagrams.Core.Style                               1.2    1.7
buildAttr             Graphics.Svg.Core                                 1.1    4.8
transferFunction      Data.Colour.SRGB                                  1.0    2.0
centers.(...)         Main                                              1.0    1.8
intersection          BreakpointTree                                    0.9    1.0
getAttr               Diagrams.Core.Style                               0.8    1.1
fromHtmlEscapedString Blaze.ByteString.Builder.Html.Utf8                0.6    2.3
toLazyTextWith        Data.Text.Internal.Builder                        0.6    2.8
roundTo               Data.Text.Internal.Builder.RealFloat.Functions    0.5    2.2
fromHtmlEscapedText   Blaze.ByteString.Builder.Html.Utf8                0.4    5.4

[SimplyNaOH]

Hi there, thanks for your time!

I hadn't profiled with the image output yet, so that's some interesting data. But Main.hs is really a mess right now so I think a rewrite would be necessary before going too deep into optimizing it. However, it's interesting to see how the list allocation increases towards the end of the algorithm (10 seconds mark). I will definitely concentrate on eliminating that list next.

Thanks again!