0

I have a matrix of values that is anywhere from a few dozen to a few hundred rows and columns (always square). I have a series of tasks that need to be performed on the matrix. (I'm using the Hungarian Algorithm.) Because they may take a long time, I'm doing the work on different threads to keep the UI from getting locked up. But I'm finding that the asynchronicity of it makes the code harder to follow, and I'm wondering if there's a better way?

I'm doing this on macOS using dispatch_queues. It works something like this:

  1. For each row, find the minimum value in the row and subtract it from all elements in the row
  2. For each column, do the same
  3. For each row, if it has a single 0 value, mark it and cross out all the 0s in the corresponding column
  4. More stuff I haven't gotten to yet…

So for step 1, multiple rows can be worked on at the same time, so I use dispatch_async() to kick off the row processing. The problem is that since it happens asynchronously, I end up needing a finalizer which kicks off the processing of the columns. They too can be done concurrently, so I use another dispatch_queue and start it via dispatch_async(). Again, I need a finalizer since it's happening asynchronously.

So now, instead of having written a fairly straightforward function like this:

void processMatrix(Matrix m)
{
    processRows(m);
    processColumns(m);
    assignZeroes(m);
    // etc.
}

I have a chain of functions which aren't obviously related and have a bunch of extraneous housekeeping code:

void processMatrix(Matrix m)
{
    dispatch_queue_t rowQueue = dispatch_queue_create(...);
    dispatch_queue_setContext(rowQueue, contextData);
    dispatch_queue_setFinalizer(rowQueue, doneProcessingRows);
    dispatch_async(rowQueue, ^{ processRows(m); });
}

void doneProcessingRows(void* context)
{
    dispatch_queue_t colQueue = dispatch_queue_create(...);
    dispatch_queue_setContext(colQueue, contextData);
    dispatch_queue_setFinalizer(colQueue, doneProcessingColumns);
    dispatch_async(colQueue, ^{ processColumns(m); });
}

void doneProcessingColumns(void* context)
{
    dispatch_queue_t assignmentQueue = dispatch_queue_create(...);
    dispatch_queue_setContext(assignmentQueue, contextData);
    dispatch_queue_setFinalizer(assignmentQueue, doneAssigning);
    dispatch_async(assignmentQueue, ^{ processAssignments(m); });
}

What I'm wondering is if there is a better way to write this code so it's easier to read and understand and to see the flow of processing? I'd like to keep it as concurrent as possible for performance reasons.

1

(Disclaimer: I am not familiar with Objective C programming, so there may be mistakes in my answer. Some information is based on online links which might be out of date.)

In general, the coding style can be known as either Fork-Join or Bulk Synchronization.

Your code may be just a few steps of refactoring from the perfect state:

  1. Could you solve the code repetition problem by extracting the common part of it into a helper function, and specify the parts that change as function arguments? To do this, you will need to pass in blocks as arguments to that function.

  2. Could you rename the functions, so that instead of saying that each function is called when something else is done, you will name it with the task it will perform when it is called? For example: startProcessingRows, startProcessingColumns, and startProcessingAssignments. This will help one understand the function more naturally.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.