C++ High Performance

Divide and conquer

In order to get a good general purpose implementation of the parallel transformation, we divide the range recursively into smaller ranges, sometimes referred to as "divide and conquer".

It works as follows:

1. The input range is divided into two ranges; if the input range is smaller than a specified threshold, the range is processed, or else the range is split into two parts:
   • One part is branched to another task recursively processed at that task
   • One part is recursively processed at the calling thread

The following illustration shows how it would recursively transform a range with the following properties:

• Range size: 16
• Chunk size: 4
• Transformation function: [](const auto& v){ return v*v; }

A range is divided recursively ...