Tutorial 1: The reference

Where we are

Nothing is parallel yet. Before you add a single task you need two things: a program whose output is correct by definition, and a measurement that tells you which part to parallelize first.

The problem

You cannot tell whether a parallel program is correct unless you have something to compare it with, and you cannot tell where parallelism pays off unless you know where the time goes. Guessing is expensive: splitting a stage that takes 5 % of the time gains at most 5 %.

The building block

None. This chapter uses only Windows and the C++ standard library. It is the reference that every later chapter has to match byte for byte.

The program

The program includes the common code of the tutorial:

#include "tutorial-common.h"

using namespace Tutorial;

Pack reads, encodes and writes one block after the other. It keeps a stopwatch around each stage and sums the times over all blocks:

// How long each stage took, summed over all blocks.
struct StageTimes {
    double read   = 0;
    double encode = 0;
    double write  = 0;
};

// Reads, encodes and writes one block after the other.
bool Pack(const Arguments& arguments, StageTimes& times)
{
    File input  = File::OpenRead(arguments.input);
    File output = File::Create(arguments.output);
    if (!input.IsOpen() || !output.IsOpen())
        return false;

    std::vector<std::byte> buffer(arguments.blockSize);
    EncodedBlock           block;
    std::uint32_t          crc = 0; // carried from block to block
    bool                   ok  = true;
    for (;;) {
        const Stopwatch   read;
        const std::size_t size = input.Read(buffer);
        times.read += read.Seconds();
        if (size == 0)
            break;

        const Stopwatch encode;
        EncodeBlock(std::span(buffer).first(size), block);
        times.encode += encode.Seconds();

        const Stopwatch write;
        crc = WriteBlock(output, block, crc, ok);
        times.write += write.Seconds();
    }
    return WriteFooter(output, crc) && ok;
}

• buffer holds one block of input, block the encoded block. Both are reused for every block, so the program needs the same memory for any file size.
• crc is carried from block to block: WriteBlock writes a block and returns the CRC continued over the bytes it wrote. Keep an eye on it – it is the one piece of state that ties each block to the one before. Chapter 7 comes back to it.

main reads the command line, packs the file, prints the times and compares the output when a reference is given:

int wmain(int argc, wchar_t* argv[])
{
    Arguments arguments;
    if (!ParseArguments(argc, argv, arguments))
        return arguments.exitCode;

    StageTimes      times;
    const Stopwatch total;
    const bool      packed = Pack(arguments, times);
    std::printf("time: %.2f s (read %.2f s, encode %.2f s, write %.2f s)\n",
                total.Seconds(), times.read, times.encode, times.write);
    if (!packed) {
        std::printf("cannot pack the file\n");
        return 1;
    }
    return CheckOutput(arguments) ? 0 : 1;
}

The result

Pack the test input once and keep the output; it is the reference for all later chapters:

blockpack input.bin reference.bpk
time: … s (read … s, encode … s, write … s)

The numbers depend on your machine, but the shape does not: encoding takes about 90 % of the time, reading and writing the rest. The file is in the file system cache after the first run, so reading costs little.

thread 1  │R│ encode │W│R│ encode │W│R│ encode │W│ …

What limits us now

Encoding is the largest stage, and its blocks do not depend on each other. That is where to start: spread the encoding over all cores. To do that, the program first needs a scheduler that runs tasks on those cores.

Learn more

• When it pays off

// Tutorial chapter 1: blockpack without ConcurrentTasks - the sequential
// reference that every later chapter has to match byte for byte.
#include "tutorial-common.h"

using namespace Tutorial;

// How long each stage took, summed over all blocks.
struct StageTimes {
    double read   = 0;
    double encode = 0;
    double write  = 0;
};

// Reads, encodes and writes one block after the other.
bool Pack(const Arguments& arguments, StageTimes& times)
{
    File input  = File::OpenRead(arguments.input);
    File output = File::Create(arguments.output);
    if (!input.IsOpen() || !output.IsOpen())
        return false;

    std::vector<std::byte> buffer(arguments.blockSize);
    EncodedBlock           block;
    std::uint32_t          crc = 0; // carried from block to block
    bool                   ok  = true;
    for (;;) {
        const Stopwatch   read;
        const std::size_t size = input.Read(buffer);
        times.read += read.Seconds();
        if (size == 0)
            break;

        const Stopwatch encode;
        EncodeBlock(std::span(buffer).first(size), block);
        times.encode += encode.Seconds();

        const Stopwatch write;
        crc = WriteBlock(output, block, crc, ok);
        times.write += write.Seconds();
    }
    return WriteFooter(output, crc) && ok;
}

int wmain(int argc, wchar_t* argv[])
{
    Arguments arguments;
    if (!ParseArguments(argc, argv, arguments))
        return arguments.exitCode;

    StageTimes      times;
    const Stopwatch total;
    const bool      packed = Pack(arguments, times);
    std::printf("time: %.2f s (read %.2f s, encode %.2f s, write %.2f s)\n",
                total.Seconds(), times.read, times.encode, times.write);
    if (!packed) {
        std::printf("cannot pack the file\n");
        return 1;
    }
    return CheckOutput(arguments) ? 0 : 1;
}

Next

• Tutorial 2: A scheduler and a task