JuliaGeometry / Contour.jl

Calculating contour curves for 2D scalar fields in Julia
Other
43 stars 13 forks source link

Use arrays rather than Dicts for Contour Chasing #51

Open sjkelly opened 4 years ago

sjkelly commented 4 years ago

This builds on #50. Inspired by: https://www.researchgate.net/publication/282975362_Flying_Edges_A_High-Performance_Scalable_Isocontouring_Algorithm

This could serve as a basis for that implementation, which should yield even better performance once fully implemented.

The basic idea is to store each case in a 2D Matrix and loop through this matrix (once). Since the matrix is all UInt8, it ends up very compact in memory. We also avoid hashing overhead and do not need to store keys. Since we track the number of non-zero elements for large arrays, sparse contours (such as one closed loop) should still perform better than the dictionary approach, though they may require more memory allocations.

For reference: v0.5.1:

contour
1-element BenchmarkTools.BenchmarkGroup:
  tags: []
  "testdata" => BenchmarkTools.Trial: 
      memory estimate:  3.14 MiB
      allocs estimate:  31197
      --------------
      minimum time:     2.951 ms (0.00% GC)
      median time:      3.283 ms (0.00% GC)
      mean time:        3.464 ms (3.25% GC)
      maximum time:     7.878 ms (0.00% GC)
      --------------
      samples:          1438
      evals/sample:     1

This PR:

contour
1-element BenchmarkTools.BenchmarkGroup:
  tags: []
  "testdata" => BenchmarkTools.Trial: 
      memory estimate:  569.73 KiB
      allocs estimate:  370
      --------------
      minimum time:     911.743 μs (0.00% GC)
      median time:      1.029 ms (0.00% GC)
      mean time:        1.068 ms (1.40% GC)
      maximum time:     2.901 ms (58.94% GC)
      --------------
      samples:          4662
      evals/sample:     1
sjkelly commented 4 years ago

Here is a case where allocations are greater but performance is better:

using Contour
using BenchmarkTools

x = -1:0.0001:1
y = -1:0.0001:1
c(x,y) = sqrt(x^2+y^2) - 1

z = [c(xi,yi) for xi in x, yi in y];

@benchmark contours(collect(x), collect(y), z)

Master:

BenchmarkTools.Trial: 
  memory estimate:  103.07 MiB
  allocs estimate:  795684
  --------------
  minimum time:     37.911 s (0.03% GC)
  median time:      37.911 s (0.03% GC)
  mean time:        37.911 s (0.03% GC)
  maximum time:     37.911 s (0.03% GC)
  --------------
  samples:          1
  evals/sample:     1

PR:

BenchmarkTools.Trial: 
  memory estimate:  396.66 MiB
  allocs estimate:  291
  --------------
  minimum time:     12.295 s (0.00% GC)
  median time:      12.295 s (0.00% GC)
  mean time:        12.295 s (0.00% GC)
  maximum time:     12.295 s (0.00% GC)
  --------------
  samples:          1
  evals/sample:     1

https://github.com/JuliaGeometry/Contour.jl/pull/50 :

BenchmarkTools.Trial: 
  memory estimate:  48.22 MiB
  allocs estimate:  634
  --------------
  minimum time:     37.249 s (0.00% GC)
  median time:      37.249 s (0.00% GC)
  mean time:        37.249 s (0.00% GC)
  maximum time:     37.249 s (0.00% GC)
  --------------
  samples:          1
  evals/sample:     1