Preliminary. ThinkMeta ConcurrentTasks and this documentation are preliminary; everything is subject to change.

Finding the tasks

On this page

Thinking in tasks took one small program apart. This page is the method behind it, for a sequential program of your own: four steps that lead from a loop to tasks. The example is a second program with a different result. It packs a file block by block, and it is the program of the 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;
}

1. List the activities

An activity is a part of the program that could go on by itself if it had its data. In sequential code, look for three things:

  • A loop with state that lives from one round to the next: a file position, a running checksum, a parser that is in the middle of something.
  • A device or a connection. Whatever talks to a file, a socket or a window has a rhythm of its own and usually a state of its own.
  • Work that repeats without state. The same computation on one item after the other, where no round needs anything from the round before.

The packer has one of each:

Activity State from round to round
read the input, block by block the position in the input file
encode a block none
write the output, block by block the position in the output file, the CRC of everything written

The difference between the first and the second kind decides what the tasks will look like. An activity with state becomes one task that lives as long as the activity, like the reader and the hash tasks of the hashing program. Work without state becomes one task per item: a short task that does one thing and ends.

2. Write down what each step needs

Go through the steps and ask of each one: which data does it read, which state does it continue, and what does it use that nobody else may use meanwhile?

Step needs because
read block i read block i−1 the file is read front to back; a buffer to read into
encode block i read block i its input; nothing from any other block
write block i encode block i, write block i−1 the blocks must appear in order; the CRC continues

This table is the design. Everything that follows only writes it down in code.

3. Tell the needed order from the written order

The sequential program does more in order than the table asks for. Here it encodes block i after block i−1, and it reads block i+1 only after block i is written. Neither is in the table. Each "after" in the code is one of two things:

  • Needed, for one of three reasons: the data must exist before it is used; a state continues from one step to the next; or a resource serves one user at a time.
  • Written, because statements have to stand in some order.

Only the needed order goes into the task-based program. Everything else is freedom the scheduler can use.

State hides

The hard part of this step is state that does not look like a dependency. In the packer it is the CRC: WriteBlock takes the CRC so far and returns the new one, so block i cannot be finished before block i−1. Move the CRC into the encode tasks without noticing that, and the program is wrong. A lock does not help:

// The first attempt: one CRC for the whole output, shared by all encode tasks
// and guarded by a critical section.
struct SharedCrc {
    TC::Synchronization::CriticalSection lock;
    std::uint32_t                        crc = 0;
};
class EncodeTask : public TC::Tasks::Task
{
public:
    void Run() noexcept override
    {
        EncodeBlock(input, encoded);
        if (shared != nullptr) {
            // Wrong: continues the CRC in the order in which the blocks finish.
            TC::Synchronization::CriticalSectionLock lock(shared->lock);
            shared->crc = ContinueCrc(shared->crc, encoded);
        } else
            crc = BlockCrc(encoded); // this block's own CRC, in parallel
    }

    std::span<const std::byte> input;
    EncodedBlock               encoded;
    std::uint32_t              crc    = 0;
    SharedCrc*                 shared = nullptr; // set for -v lock
};

A lock makes sure that one task at a time changes the CRC. It does not say which one comes first. Exclusion is not order. State that continues from item to item belongs to one task that sees the items in order, or it has to be reformulated so that the parts can be combined later (Tutorial 7: State that flows).

So before an activity is split into one task per item, check everything its steps touch: counters, caches, a random number generator, an output stream, the allocator of a library. Whatever carries over from item to item is a row in the table.

4. Choose the shape

The table of a program usually has one of three shapes, and each has its own way of becoming tasks.

A pipeline

Every step continues the state of the step before it in the same activity, and activities hand data to each other. The hashing program is this shape: reading, MD5 and SHA-1 each continue their own state from block to block.

The tasks are few and live long. They meet in an object that hands the data from one to the next: the SharedMemory of Thinking in tasks, or a pipe.

Fork-join

The steps of an activity need nothing from each other. The packer's encoding is this shape. There is one task per block:

// Encodes one block. Blocks are independent, so these tasks can run in any
// order and on any thread.
class EncodeTask : public TC::Tasks::WaitableTask
{
public:
    void Run() noexcept override { EncodeBlock(input, encoded); }

    std::span<const std::byte> input;
    EncodedBlock               encoded;
};

Whoever starts the tasks also collects the results, and here the collecting is where the needed order lives. The write loop waits for task i and only then for task i+1, however the tasks happen to finish:

// Holds the file and the tasks. It must outlive every task it started, so main
// destroys it only after the scheduler has stopped.
class Packer
{
public:
    bool Pack(TC::ITaskScheduler& scheduler, const Arguments& arguments)
    {
        File input  = File::OpenRead(arguments.input);
        File output = File::Create(arguments.output);
        if (!input.IsOpen() || !output.IsOpen() || !input.ReadAll(data_))
            return false;

        // Fork: one task per block.
        const std::size_t blockSize = arguments.blockSize;
        const std::size_t count     = (data_.size() + blockSize - 1) / blockSize;
        tasks_ = std::make_unique<EncodeTask[]>(count); // fixed addresses
        for (std::size_t i = 0; i < count; ++i) {
            const std::size_t offset = i * blockSize;
            tasks_[i].input          = std::span(data_).subspan(
                offset, std::min(blockSize, data_.size() - offset));
            scheduler.AddTask(&tasks_[i]);
        }

        // Join in order: block i is written as soon as it is ready, while the
        // blocks after it are still being encoded.
        std::uint32_t crc = 0;
        bool          ok  = true;
        for (std::size_t i = 0; i < count; ++i) {
            tasks_[i].Wait();
            crc = WriteBlock(output, tasks_[i].encoded, crc, ok);
        }
        return WriteFooter(output, crc) && ok;
    }

private:
    std::vector<std::byte>        data_;
    std::unique_ptr<EncodeTask[]> tasks_;
};

Two rows of the table are visible in this code. "Encode needs only its own block" is the fork: the tasks are added and nothing connects them. "Write block i needs write block i−1" is the join in order, in one loop with the CRC as a local variable.

This version reads the whole file before it starts, so that every task has its input. Reading on while blocks are encoded, with a fixed number of blocks in flight, is the pipeline shape again, now around the fork-join: Tutorial 5 and Tutorial 6.

One task per request

The items do not come from a loop of the program. They arrive from outside, at times nobody knows, and each one starts a conversation of its own: a connection, a job, a window. The table of such a program has two parts. Inside a conversation, the steps follow each other strictly. Between conversations there is no row at all.

So every conversation is one task, written as if it were alone:

// One connection: receive, send back, until the client shuts down its side (a
// receive of 0 bytes).
class EchoTask : public TC::Tasks::Task
{
public:
    // moved in by the accept task before the task is started
    AsyncTcpSocket4 socket;
    std::size_t     echoed = 0;

    void Run() noexcept override
    {
        std::byte buffer[4096];
        for (;;) {
            ByteCount received = 0;
            if (SocketError::Failed(socket.Recv(buffer, sizeof(buffer), &received))
                || received == 0)
                break;
            if (SocketError::Failed(SendAll(socket, buffer, received)))
                break;
            echoed += received;
        }
        socket.Close(); // nothing is pending: Recv and Send have returned
    }
};

One more task waits for the next arrival and starts a task for it:

// Accepts a known number of connections and starts one EchoTask for each. The echo
// tasks are owned by main and counted into the group before they are started.
class AcceptTask : public TC::Tasks::Task
{
public:
    AcceptTask(AsyncTcpSocket4& listener, EchoTask* echoTasks,
               TC::Synchronization::TaskGroup_s& group) noexcept
        : listener_(listener),
          echoTasks_(echoTasks),
          group_(group)
    {}

    SocketErrorCode error = SocketError::Success;

    void Run() noexcept override
    {
        for (std::size_t i = 0; i < Clients; ++i) {
            AsyncTcpSocket4 connection; // Accept creates it
            error = listener_.Accept(connection);
            if (SocketError::Failed(error))
                return;
            echoTasks_[i].socket = std::move(connection);
            group_.AddTask(&echoTasks_[i]);
            echoTasks_[i].Schedule(); // on the scheduler of the calling task
        }
    }

private:
    AsyncTcpSocket4&                  listener_;
    EchoTask*                         echoTasks_;
    TC::Synchronization::TaskGroup_s& group_;
};

A sequential server has to interleave its conversations by hand, with a state per connection and a loop that asks every connection what happened. With tasks, the state of a conversation is the local variables of its task, and the place where it waits is the place where the code stands (TCP echo server).

Programs mix the shapes

Real programs are seldom one shape. The finished packer of the tutorial is a pipeline of a reader and a writer with a fork-join between them, and a server may answer each request with a small pipeline. Find the shape for each part of the table, and let the parts meet in shared objects.

Then assemble and test

With the tasks and their objects written, the program is put together in one place, as in Thinking in tasks. Two checks come before any measurement:

  • Compare with the sequential program. Keep it. It is the reference: same input, same output, byte for byte. The tutorial's programs all write the file of the first one.
  • Run on one thread, in different orders. A row that is missing from the table shows as a wrong result in some order (What can go wrong).

When a task is not worth it

Not every activity should become a task, and not every item a task of its own.

  • The step is tiny. Starting a task and waiting for it costs something, little but not nothing. Work that is small compared with that belongs into one task per batch of items (Tutorial 4: Sizing the work).
  • Everything needs everything. If each step needs the complete result of the step before it, the table is one chain, and tasks add nothing but the freedom to do something else meanwhile. That can still be worth it: for a user interface that stays alive, or for I/O that waits without holding a thread.
  • The state cannot be separated. Steps that all change one large structure in fine grains do not come apart by adding locks. Change the structure first, so that each task owns a part.

The steps in short

  1. Activities: loops with state, devices and connections, work that repeats without state.
  2. The table: for each step, the data it reads, the state it continues, what it uses alone.
  3. Needed or written: keep the rows of the table, drop every other order. Look for hidden state.
  4. The shape: long-lived tasks for activities with state, one task per item for work without, one task per conversation for what arrives from outside.
  5. Assemble, compare, test on one thread. Then measure.

See also