Implementing runtime-constant persistent "LUT"s in MATLAB functions

Question

I am implementing (for class, so no built-ins!) a variant of the Hough Transform to detect circles in an image. I have a working product, and I get correct results. In other words, I'm done with the assignment! However, I'd like to take it one step further and try to improve the performance a little bit. Also, to forestall any inevitable responses, I know MATLAB isn't exactly the most performance-based language, and I know that the Hough transform isn't exactly performance-based either, but hear me out.

When generating the Hough accumulation space, I end up needing to draw a LOT of circles (approximately 75 for every edge pixel in the image; one for each search radius). I wrote a nifty function to do this, and it's already fairly optimized. However, I end up recalculating lots of circles of the same radius (expensive) at different locations (cheap).

An easy way for me to optimize this was precalculate a circle of each radius centered at zero once, and just select the proper circle and shift it into the correct position. This was easy, and it works great!

The trouble comes when trying to access this lookup table of circles.

I initially made it a persistent variable, as follows:

[x_subs, y_subs] = get_circle_indices(circ_radius, circ_x_center, circ_y_center)

    persistent circle_lookup_table;

    % Make sure the table's already been generated; if not, generate it.
    if (isempty(circle_lookup_table))
        circle_lookup_table = generate_circles(100); %upper bound circ size
    end

    % Get the right circle from the struct, and center it at the requested center
    x_subs = circle_lookup_table(circ_radius).x_coords + circ_x_center;
    y_subs = circle_lookup_table(circ_radius).y_coords + circ_y_center;

end

However, it turns out this is SLOW! Over 200,000 function calls, MATLAB spent on average 9 microseconds each call just to establish that the persistent variable exists! (Not the isEmpty() call, but the actual variable declaration). This is according to MATLAB's built-in profiler.

This added back most of the time gained from implementing the lookup table.

I also tried implementing it as a global variable (similar time to check if the variable is declared) or passing it in as a variable (made the function call much more expensive).

So, my question is this:

How do I provide fast access inside a function to runtime-constant data?

I look forward to some suggestions.

Bentoy13 Bentoy13 · Accepted Answer · 2014-01-10T14:08:11

It is NOT runtime-constant data, since your function has the ability of generating the table. So your main problem is to discard this instruction from the function. Before all the calls of this critical function, make sure that this array is generated elsewhere outside the function.

However, there is a nice trick I've read from Matlab's files, and more specifically bwmorph. For each functionality of this particuliar function which requires a LUTs, they have created a function which returns the LUT itself (the LUT is written explicitely in the file). They also add an instruction coder.inline('always') to ensure that this function will be inlined. It seems to be quite efficient!

Implementing runtime-constant persistent "LUT"s in MATLAB functions

1 Answers