Motion - Labeling Speed Patch

Labeling Speed Improvement Patch

Introduction

This patch improves the speed of the alg_labeling function substantially. It also fixed a bug in said function.

Description of Patch

The patch does the following:

  • Fixes a bug that made iflood get called too many times.
  • Uses memset (fast) instead of a loop (slow) to zero-initialize labels.
  • Rearranges the two main loops to allow pixelpos to be incremented (fast) instead of calculated (slow).

Benchmarks

This is an excerpt from the flat execution profile, without the patch:
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 29.87     41.11    41.11      334   123.09   133.54  alg_labeling
...
  2.54    131.94     3.49   686242     0.01     0.01  iflood 
First in the list, i.e. most expensive, is alg_labeling. Note that iflood has been called 686242 times! That's around 2000 times per call to alg_labeling.

This is an excerpt from the profile with the patch:

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
...
 10.48     57.52     8.37      243    34.45    38.60  alg_labeling
...
  1.26     78.47     1.01     2648     0.38     0.38  iflood 

Now, alg_labeling is no longer first in the list. The performance gain is around 70%! Note also that iflood has been called a lot less.

Installation of Patch

The usual procedure:

  1. cd motion-3.1.18
  2. zcat ../motion-3.1.18_snap7-labeling.patch.gz | patch -p1

Discussion and Comments


Added to my sources and being testes

Great job smile

-- KennethLavrsen - 29 Nov 2004

Shame on me:-( How could I swap X and Y without ever noticing... Thank you, Per.

-- JoergWeber - 29 Nov 2004

Joerg, you shouldn't feel that way! The optimizations weren't obvious, and I was kind of surprised that the performance gain turned out to be that big.

-- PerJonsson - 30 Nov 2004
Topic revision: r7 - 30 Jan 2005, KennethLavrsen
Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Please do not email Kenneth for support questions (read why). Use the Support Requests page or join the Mailing List.
This website only use harmless session cookies. See Cookie Policy for details. By using this website you accept the use of these cookies.