Saturday, March 12, 2016

Multi thread parallelism and a dispatching table for finding a minimum

In my free time I enjoy by solving programming puzzles from Advent of Code website. Some of them are pretty simple, though others could be tricky, however, all of them are always witty. Of course, I do it in AX so that I could use as much its power as possible.

The day 4 Ideal Stocking Stuffer became a die-hard to me. And it is not because of its "business complexity" -- you simply need to find the lowest positive number producing an MD5 hash for a given secret code, so that such a hash, in hexadecimal, starts with at least five zeroes.

Honestly, I have a vague idea about MD5 hash math -- I just took a working example and injected it into my class.

The stumbling point here was calculation time. Even for the first part of the puzzle, which is always easier than than the second one, it took so much time that I started flirting with the idea to improve performance.

Wrapping the MD5 hash calculation method so that it could be run in CIL got it faster but not enough to be happy.

The next idea was batch task execution in parallel threads, like it is brilliantly explained by Ganas1 in four chapter blog series:

Batch Bundling

However, we need to find the lowest positive number; therefore, we do not know how many tasks must be created. (Let's assume that we are limited with the maximum of Int64)

My solution is the following.

I created a table, which is to centrally dispatch creating, executing, and stopping batch tasks based on a separate, sequentially assigned positive number ranges. So, for each batch task it keeps the assigned thread number, ranges, execution status and found results, if any.

The batch task generating class creates them for a given number of logical processors, four in my environment.

Each task checks the table for a found result. If it is already found in any range, it stops.
If not, it looks for the highest range from the table and than tries to add a new record. In case of success, it runs finding the lowest number in the given range.

If such a number is found in the current thread, this value becomes a new candidate only if there are no results found in the lower ranges and no any lower ranges still running.

Now blood runs faster: even the second part of the job did not give me a pause to get another beer from the fridge.

However, it is up to your judgement to set up the right range size and number of parallel tasks. The smaller a single step is, the more the transaction cost will be. And vice-versa, the larger the range is, the longer you need to wait the higher ranges tasks to finish: the total execution time is the longest task's.

This project comprises examples of the following techniques:

  • dynamic dialog creation on RunBaseBatch
  • wrapping for execution in CIL
  • execution time calc
  • multiple batch task creation
  • try-catch exception handling for concurrent table updating
  • InteropPermission assertion

Happy AX mining!

No comments: