Benchmark 3D filter

[dstansby]

This issue is to track benchmarking the 3D filter. The optimised code currently consists of two Cython files, ball_filter.pyx and structure_detection.pyx.

The graphs below show a memory profile of different implementations, and the code shows execution times.

Original Cython implementation

0.713 <module>  filter_3d.py:1
└─ 0.713 VolumeFilter._run_filter  cellfinder_core/detect/filters/volume/volume_filter.py:95
   └─ 0.712 BallFilter.walk  None

Pure Python implementation

32.455 <module>  filter_3d.py:1
└─ 32.455 VolumeFilter._run_filter  cellfinder_core/detect/filters/volume/volume_filter.py:95
   ├─ 29.968 BallFilter.walk  cellfinder_core/detect/filters/volume/ball_filter_py.py:128
   │  ├─ 28.197 BallFilter.__cube_overlaps  cellfinder_core/detect/filters/volume/ball_filter_py.py:159
   │  ├─ 1.140 [self]  None
   │  └─ 0.631 BallFilter.__is_tile_to_check  cellfinder_core/detect/filters/volume/ball_filter_py.py:190
   └─ 2.484 CellDetector.process  cellfinder_core/detect/filters/volume/structure_detection_py.py:82
      └─ 2.479 CellDetector.connect_four  cellfinder_core/detect/filters/volume/structure_detection_py.py:119

numba implementation

3.024 <module>  filter_3d.py:1
└─ 3.024 VolumeFilter._run_filter  cellfinder_core/detect/filters/volume/volume_filter.py:95
   ├─ 2.460 CellDetector.process  cellfinder_core/detect/filters/volume/structure_detection_py.py:82
   │  └─ 2.460 CellDetector.connect_four  cellfinder_core/detect/filters/volume/structure_detection_py.py:119
   └─ 0.565 BallFilter.walk  cellfinder_core/detect/filters/volume/ball_filter_py.py:129
      ├─ 0.519 CPUDispatcher._compile_for_args  numba/core/dispatcher.py:388
      │  ├─ 0.476 CPUDispatcher.compile  numba/core/dispatcher.py:915
      │  │  └─ 0.476 _FunctionCompiler.compile  numba/core/dispatcher.py:124
      │  │     └─ 0.476 _FunctionCompiler._compile_cached  numba/core/dispatcher.py:131
      │  │        └─ 0.476 _FunctionCompiler._compile_core  numba/core/dispatcher.py:146
      │  │           └─ 0.476 compile_extra  numba/core/compiler.py:690
      │  │              ├─ 0.287 Compiler.compile_extra  numba/core/compiler.py:446
      │  │              │  └─ 0.287 Compiler._compile_bytecode  numba/core/compiler.py:515
      │  │              │     └─ 0.287 Compiler._compile_core  numba/core/compiler.py:469
      │  │              │        └─ 0.287 PassManager.run  numba/core/compiler_machinery.py:342
      │  │              │           └─ 0.287 _acquire_compile_lock  numba/core/compiler_lock.py:32
      │  │              │              └─ 0.287 StateDict._runPass  numba/core/compiler_machinery.py:268
      │  │              │                 └─ 0.284 check  numba/core/compiler_machinery.py:272
      │  │              │                    ├─ 0.182 NopythonTypeInference.run_pass  numba/core/typed_passes.py:98
      │  │              │                    │  └─ 0.182 type_inference_stage  numba/core/typed_passes.py:61
      │  │              │                    │     └─ 0.180 TypeInferer.propagate  numba/core/typeinfer.py:1067
      │  │              │                    │        └─ 0.180 ConstraintNetwork.propagate  numba/core/typeinfer.py:142
      │  │              │                    │           └─ 0.176 CallConstraint.__call__  numba/core/typeinfer.py:570
      │  │              │                    │              └─ 0.176 CallConstraint.resolve  numba/core/typeinfer.py:580
      │  │              │                    │                 └─ 0.176 TypeInferer.resolve_call  numba/core/typeinfer.py:1517
      │  │              │                    │                    └─ 0.175 Context.resolve_function_type  numba/core/typing/context.py:189
      │  │              │                    │                       └─ 0.175 Context._resolve_user_function_type  numba/core/typing/context.py:233
      │  │              │                    │                          └─ 0.173 Dispatcher.get_call_type  numba/core/types/functions.py:534
      │  │              │                    │                             └─ 0.173 CPUDispatcher.get_call_template  numba/core/dispatcher.py:348
      │  │              │                    │                                └─ 0.173 CPUDispatcher.compile  numba/core/dispatcher.py:915
      │  │              │                    │                                   └─ 0.162 _FunctionCompiler.compile  numba/core/dispatcher.py:124
      │  │              │                    │                                      └─ 0.162 _FunctionCompiler._compile_cached  numba/core/dispatcher.py:131
      │  │              │                    │                                         └─ 0.162 _FunctionCompiler._compile_core  numba/core/dispatcher.py:146
      │  │              │                    │                                            └─ 0.162 compile_extra  numba/core/compiler.py:690
      │  │              │                    │                                               └─ 0.161 Compiler.compile_extra  numba/core/compiler.py:446
      │  │              │                    │                                                  └─ 0.161 Compiler._compile_bytecode  numba/core/compiler.py:515
      │  │              │                    │                                                     └─ 0.161 Compiler._compile_core  numba/core/compiler.py:469
      │  │              │                    │                                                        └─ 0.161 PassManager.run  numba/core/compiler_machinery.py:342
      │  │              │                    │                                                           └─ 0.161 _acquire_compile_lock  numba/core/compiler_lock.py:32
      │  │              │                    │                                                              └─ 0.160 StateDict._runPass  numba/core/compiler_machinery.py:268
      │  │              │                    │                                                                 └─ 0.135 check  numba/core/compiler_machinery.py:272
      │  │              │                    │                                                                    └─ 0.086 NativeLowering.run_pass  numba/core/typed_passes.py:363
      │  │              │                    │                                                                       └─ 0.036 Lower.lower  numba/core/lowering.py:163
      │  │              │                    └─ 0.080 NativeLowering.run_pass  numba/core/typed_passes.py:363
      │  │              │                       ├─ 0.033 CPUContext.get_executable  numba/core/cpu.py:216
      │  │              │                       │  └─ 0.033 JITCodeLibrary.get_pointer_to_function  numba/core/codegen.py:975
      │  │              │                       │     └─ 0.033 JITCodeLibrary._ensure_finalized  numba/core/codegen.py:565
      │  │              │                       │        └─ 0.033 JITCodeLibrary.finalize  numba/core/codegen.py:739
      │  │              │                       └─ 0.032 Lower.lower  numba/core/lowering.py:163
      │  │              └─ 0.189 Compiler.__init__  numba/core/compiler.py:404
      │  │                 ├─ 0.157 CPUContext.refresh  numba/core/base.py:264
      │  │                 │  └─ 0.139 CPUContext.load_additional_registries  numba/core/cpu.py:68
      │  │                 │     └─ 0.094 <module>  numba/np/arraymath.py:1
      │  │                 │        └─ 0.089 _check_blas  numba/np/arraymath.py:36
      │  │                 │           └─ 0.089 ensure_blas  numba/np/linalg.py:54
      │  │                 │              └─ 0.088 <module>  scipy/linalg/__init__.py:1
      │  │                 │                 └─ 0.056 <module>  scipy/linalg/_sketches.py:1
      │  │                 │                    └─ 0.056 <module>  scipy/sparse/__init__.py:1
      │  │                 │                       └─ 0.034 <module>  scipy/sparse/csgraph/__init__.py:1
      │  │                 └─ 0.032 Context.refresh  numba/core/typing/context.py:153
      │  └─ 0.042 CPUDispatcher._compilation_chain_init_hook  numba/core/dispatcher.py:281
      │     └─ 0.042 init_all  numba/core/entrypoints.py:23
      │        └─ 0.042 entry_points  importlib/metadata/__init__.py:999
      │           └─ 0.042 SelectableGroups.load  importlib/metadata/__init__.py:456
      │              └─ 0.042 <genexpr>  importlib/metadata/__init__.py:1018
      │                 └─ 0.037 PathDistribution.entry_points  importlib/metadata/__init__.py:629
      │                    └─ 0.034 PathDistribution.read_text  importlib/metadata/__init__.py:919
      │                       └─ 0.034 PosixPath.read_text  pathlib.py:1129
      │                          └─ 0.033 PosixPath.open  pathlib.py:1111
      │                             └─ 0.032 [self]  None
      └─ 0.046 _walk  cellfinder_core/detect/filters/volume/ball_filter_py.py:198

[dstansby]

A brief summary of work/impasses today:

• connect_four is much slower with a pure Python implementation compared to the Cython, and currently the bottleneck.
• It has resisted being numba.jit decorated because it makes use of mutable dictionaries that are not supported by numba.
• We have had a brief think about how to rewrite connect_four so that it can take advantage of numba, and came to no good conclusion.
• Finally, I started writing some unit tests for the cell merging managed by the CellDetector class. I hope to write a set of small unit tests that check that the detection is merging different configurations of foreground pixels correctly, which we can then use as unit tests for any potential future rewrite of connect_four

[dstansby]

Some good news, it looks like it is possible to use dicts in numba. I've updated the class to use numba dicts at https://github.com/dstansby/cellfinder-core/tree/jit-connect-four, and it runs fine (without any numba jitting).

When I try to use jitclass on the class as is, I'm running into two issues:

1. A casting from uint to int warning, which is already reported at numba dict converts between int types numba/numba#8676. It seems like this is a bit annoying, but not a blocker as I don't think cellfinder is every going to test the large-number limits of int64.
2. numba doesn't like applying jitclass to a class where an an attirbute is a dict with an array type as the value. I've reported this here: jitclass doesn't work when dict class attribute has array as value type numba/numba#8808. This is a blocker to 'just' sticking jitclass on the class.

[dstansby]

This was finished in #112