A real program: ctLame
On this page
- The C program
- 1. The activities
- 2. What each step needs
- 3. Needed order and written order
- State hides: the bit reservoir
- State hides: the psychoacoustic model
- Apparent state: the filterbank
- A buffer becomes a stream
- 4. The shapes
- What did not become a task
- The shared objects
- Assembling
- Testing
- The sequential program stays
- Every order, on one thread
- What measurement changed
- The way in short
- Reading the code
- See also
The examples of this chapter are small on purpose. This page applies Finding the tasks to a program that is not: LAME, the reference MP3 encoder, a C program with a single loop. The result is ctLame, which encodes one WAV file on all cores and writes exactly the bytes LAME writes.
Note
This page shows the way the chapter leads from LAME's loop to today's ctLame. The way ctLame really went was longer: it had a pool of worker tasks for two stages and file I/O with several requests in flight before it took this form. The ctLame showcase tells that history step by step, with the measurements of each step.
The code excerpts are copied from ctLame's source, which is in the Samples repository on GitHub. Unlike the other code in this documentation they are not compiled with it.
The C program
LAME's frontend has one loop (lame_encoder_loop in lame_main.c, shortened here: no error
handling, no progress output):
fwrite(id3v2tag, 1, n_bytes, outf); /* the ID3v2 tag */
do {
iread = get_audio(gf, Buffer); /* read: up to 1152 samples per channel */
imp3 = lame_encode_buffer_int(gf, buffer_l, buffer_r, iread,
mp3buffer, sizeof(mp3buffer)); /* encode: a frame, if one is complete */
fwrite(mp3buffer, 1, imp3, outf); /* write */
} while (iread > 0);
imp3 = lame_encode_flush(gf, mp3buffer, sizeof(mp3buffer)); /* the last frames */
fwrite(mp3buffer, 1, imp3, outf);
write_id3v1_tag(gf, outf);
write_xing_frame(gf, outf, id3v2_size); /* the LAME tag, over its placeholder */Read, encode, write, and at the end what is only known then. The LAME tag is such a thing: the encoder puts a placeholder for it at the start of the MP3 stream, and the last line writes the tag over the placeholder.
Two terms come back all through this page. A frame is 1152 samples per channel, coded as two halves of 576 samples, the granules. The window a frame is computed from is longer, 1904 samples: it reaches back into the samples of the frame before.
The encoding hides a second sequence. lame_encode_buffer converts the samples and appends them
to a buffer, runs the ReplayGain analysis over them and, once the buffer holds the window of a
frame, calls lame_encode_mp3_frame:
- the psychoacoustic model for the two granules of the frame, and the adjustment of the hearing threshold,
- the polyphase filterbank and the MDCT,
- the decision between mid/side and left/right stereo,
- the quantization,
- the bit stream.
Then the buffer is shifted by one frame, 1152 samples. All of this works on one structure that
holds the state of the whole encoder (gfc), and one core is busy.
1. The activities
The first step lists what could go on by itself if it had its data: loops with state, devices, work that repeats without state.
| Activity | State from round to round |
|---|---|
| read the WAV file, block by block | the position in the file |
| convert the PCM bytes into samples | the sample buffer: the window of a frame begins in the samples of the frame before |
| ReplayGain analysis, per channel | two filters that run over the whole channel, the sums of the window in progress |
| psychoacoustic model | energies and masking of earlier granules, the last block type, the adaptive hearing threshold |
| filterbank and MDCT | the subband samples of the previous granule |
| stereo decision | none |
| quantization | the bit reservoir |
| bit stream | main_data_begin, and what the LAME tag collects (music CRC, seek table) |
| write the MP3 file | the position in the file |
Two activities are devices, and almost everything between them carries state. Read like this, the program is a pipeline: one long-lived task per activity, each handing its frames to the next. That is a correct program, and it runs in parallel, but only one task works on each activity. When the stages were first timed, the psychoacoustic model took 38 % of a frame's time and the quantization 49 %; a pipeline leaves each of them on one core. Whether more is possible is decided by a closer look at the state.
2. What each step needs
For every step: which data does it read, which state does it continue, what does it use alone?
| Step | needs | because |
|---|---|---|
| read block i | read block i−1, a free block | the file is read front to back; the bytes need a place |
| convert block i | read block i, convert block i−1 | its bytes; the samples continue the stream |
| ReplayGain of piece i of a channel | the samples of the piece, piece i−1 of the same channel | the filters continue; nothing from the other channel before the end |
| psychoacoustic model of frame i | the window of frame i, the model of frame i−1 | its samples; attacks, block types and pre-echo control look back |
| filterbank and MDCT of frame i | the window of frame i, the filterbank of frame i−1, the block types of frame i | the subband samples of the previous granule; the block type chooses the MDCT window |
| stereo decision of frame i | the model of frame i | perceptual entropy and block types |
| quantization of frame i | MDCT, stereo decision and model of frame i, the bit stream of frame i−1 | its spectrum, and the thresholds from the model; the bits frame i−1 left in the reservoir |
| bit stream of frame i | quantization of frame i, bit stream of frame i−1 | the frames appear in order |
| write block i | the bytes of the stream, write block i−1 | the file is written front to back |
| the end: ID3v1 tag, LAME tag | the last frame, the end of the samples, the end of both ReplayGain analyses | padding, ReplayGain and CRC are only known then; the LAME tag goes over its placeholder |
The units differ from row to row. The files are read and written in blocks, the encoder works in frames, and the ReplayGain analysis in pieces: a piece is what one call of the analysis gets, the samples LAME has just added to its buffer.
3. Needed order and written order
LAME's loop does far more in order than this table asks for. Each "after" in it is needed or written.
Three rows of the table in step 2 turn out to hold for a small part of their step only: the psychoacoustic model, the filterbank and the quantization. The sections below the next table take them one at a time. They cut the model into a stage Prepare without state and a stage Resolve in order, and the quantization into Search without state and Encode in order. The table already uses these four names:
| "After" in LAME's loop | Needed? | What it becomes |
|---|---|---|
| read the next samples only after the last frame is written | written | Read, the encoder and Write run at the same time, with bounded pipes between them |
| ReplayGain before the frame of the same samples, left together with right | written | a task per channel beside the frames; needed only before the LAME tag |
| model of frame i+1 after the bit stream of frame i | written | several frames are in flight |
| model of frame i after the model of frame i−1 | needed for a small part: attack decision, block type, pre-echo control, perceptual entropy, hearing threshold. Written for the rest: FFTs, spreading, energies | Prepare without state, Resolve in order |
| filterbank of frame i after frame i−1 | it only seemed needed: the subband samples are a function of the input, and the input of every frame can be reached | the filterbank in Prepare; Resolve hands the result of the last granule on, a copy |
| MDCT after the block types | needed: its data | the MDCT in Search, after Resolve |
| quantization of frame i after the bit stream of frame i−1 | needed for the reservoir: the bits the frame may use, what to do when it does not fit, the bitrate. Written for the search: scalefactors, quantizing | Search without state, Encode in order |
| bit stream in frame order, the file front to back | needed | Encode and Write, one task each |
| the LAME tag after everything | needed | it travels with the end of the stream |
The rows that say "needed for a small part" are where this program is won. They come from looking into the state, one piece at a time.
State hides: the bit reservoir
An MP3 frame may use bits that earlier frames left unused. The bit stream of frame i records
how many are left (main_data_begin), and the quantization of frame i+1 spends them. In the C
code this is no parameter. The reservoir is a few fields of gfc, and the quantization just reads
them. It is the same kind of hidden state as the CRC of the
packer,
and it is the one dependency of the encoder that crosses both stages and frames. A lock around
the reservoir would not help: frame i+1 must come after frame i, not merely alone.
But the row of step 2, "the quantization of frame i needs the bit stream of frame i−1", says more than is true. What depends on the reservoir is how many bits the frame may use, what happens if it does not fit, and which bitrate it gets. The search for the scalefactors and the quantizing itself need only the frame, and they were about 95 % of the quantization's time when it was measured. So the activity is cut in two: a search without state, and a short commit that takes the frames in order. The search is the stage Search. The commit is the first half of the stage Encode, and the bit stream is the second.
State hides: the psychoacoustic model
The model looks back: an attack is a rise against the energy before it, the block type follows from the type of the last granule, pre-echo control compares with the thresholds of earlier granules, and the hearing threshold adapts to the loudness so far. The FFTs, the spreading and the energies look at nothing but the samples of the frame, and they were about 90 % of the model's time when it was measured. The cut is the same: a preparation without state, the stage Prepare, and a short resolution in order, the stage Resolve.
For work without state the rule of the method is to check everything the steps touch. ctLame has
the compiler do that: Encoder::Prepare and Encoder::Search are const member functions, and
the state of the stages is in members of the encoder that they cannot change.
Apparent state: the filterbank
mdct_sub48 keeps the subband samples of the last granule for the next frame. That looks like
the reservoir, but it is not. No decision of an earlier frame goes into these samples; they are
computed from the input alone. If a frame can reach its input, its filterbank needs nothing from
the frame before.
So the filterbank is work without state as well, and it runs in Prepare. What is left of the row "needs the filterbank of frame i−1" in step 2 is a hand-over: the MDCT of frame i wants the filtered last granule of frame i−1, which exists by then. Resolve takes the frames in order anyway, so it passes that granule on, a copy of a few kilobytes: the filterbank carry. The MDCT itself needs the block types and runs after Resolve, in Search.
A buffer becomes a stream
"If a frame can reach its input" names the last piece of state: LAME's sample buffer, which is shifted by a frame after each frame. The windows overlap: of the 1904 samples of a window, 1152 are new. In ctLame the samples of each channel are one stream in reserved virtual memory. The window of frame k begins at sample k × 1152, and a frame points to its window instead of copying it. Memory is committed as the stream grows and given back once the frames that used it are finished.
The state of one activity has become data with one writer and several readers: the tasks that
prepare frames read their windows, and the ReplayGain analysis reads the same samples at its own
pace. That analysis was the best hidden activity of all, a call in the middle of
lame_encode_buffer. It has a loop and a state of its own for each channel, and the channels need
nothing from each other before the end.
4. The shapes
With the cuts made, each part of the table has one of the shapes.
A pipeline. The activities with state are long-lived tasks, one each: Read, Dispatch (convert the samples and give each frame its window), Resolve, Encode, Write, and a Gain task per channel.
A stage with several tasks. Prepare and Search keep nothing from frame to frame. The frames keep coming and a fixed number of them is in flight, so each of the two is a stage with several tasks: one task per compute thread, each a loop over the frames of its stage.
An ordered join. After each parallel stage the order comes back: Resolve and Encode take the frames in frame order, however the tasks before them happen to finish.
One stream with several readers. Dispatch writes the sample stream, and each Gain task reads all of its channel.
The file in file order. Write is one task whose loop is the file, front to back.
A frame passes five stages, alternating between one task in order and several in any order:
| Stage | Frames | Task | Work |
|---|---|---|---|
| 1 Dispatch | in order | DispatchTask |
the PCM bytes into the sample stream; a slot and the window for each complete frame |
| 2 Prepare | any order, N tasks | PrepareTask |
psychoacoustic model without state, polyphase filterbank |
| 3 Resolve | in order | ResolveTask |
psychoacoustic model with state, filterbank carry |
| 4 Search | any order, N tasks | SearchTask |
MDCT, stereo decision, quantization search; the main data (scalefactors and Huffman codes) coded ahead |
| 5 Encode | in order | EncodeTask |
quantization with the reservoir, bit stream |
Read ─pcm─► Dispatch ─ring─► Prepare ─ring─► Resolve ─ring─► Search ─ring─► Encode ─mp3─► Write
in order any order in order any order in order
N tasks N tasks
└─stream─► Gain L, Gain R ───── the end of the stream ─────────►┘The diagram sketches who hands what to whom. It is not a timing.
The tasks of the two kinds of stage look the same. From
PrepareTask.h
and
ResolveTask.h:
void Run() noexcept override
{
const ProfiledRun run(profile_);
while (FrameData* const frame = ring_.AcquirePrepare()) {
encoder_.Prepare(frame->input, *frame);
ring_.CompletePrepare(*frame);
}
}void Run() noexcept override
{
const ProfiledRun run(profile_);
while (FrameData* const frame = ring_.AcquireResolve()) {
encoder_.Resolve(*frame);
ring_.CompleteResolve();
}
}Take the next frame, work on it, hand it on. That one stage gets any frame and the other the frame
whose turn it is does not show in the task. It is the business of the object they share.
(ProfiledRun measures the life time of the task for --stats; read past it.)
The task that writes the file reads like the file. From
Mp3WriterTask.cpp:
// the file, front to back
std::uint64_t position = 0;
Write(output, position, mp3_.Id3v2());
// the MP3 stream; it begins with the placeholder of the LAME tag
const std::uint64_t lameTagAt = position;
Mp3File::Bytes block;
while (mp3_.AcquireBlock(block)) {
Write(output, position, block);
mp3_.ReleaseBlock(); // also after an error (Write then does nothing), so Encode never waits for a full stream
}
Write(output, position, mp3_.Id3v1());
// only now known: the LAME tag, over its placeholder
position = lameTagAt;
Write(output, position, mp3_.LameTag());These are the fwrite calls of LAME's loop, in a task of their own. One write is under way at a
time, with AsyncFile and a local position; a write suspends the task and not its
thread.
What did not become a task
Not every activity is worth a task:
- The stereo decision has no state and is tiny. It is a few lines in Search.
- Converting and dispatching each have state, but a frame can only be dispatched once its samples are in the stream. The two never run at the same time, and the conversion is a small part of the work. They are one task.
- ReplayGain is the opposite case. It is a small filter too, but a serial chain over the whole file, and it needs nothing from the frames. Left inside the task that converts the samples, it would hold up every frame (what measurement changed).
The shared objects
The tasks do not know each other. They meet in four shared objects, the edges of the graph, and each is one of the forms of that page or two of them together:
| Object | Tasks that meet | Form |
|---|---|---|
BlockPipe, the PCM pipe |
Read and Dispatch | a stream between two tasks, in blocks |
SharedSampleStream |
Dispatch, the Gain tasks, Encode | blocks with several readers |
FrameRing |
the five frame stages | a ring that bounds the work, with an ordered join after each parallel stage |
Mp3File |
Encode and Write | a stream between two tasks, whose end carries the rest of the file |
The header of each class answers the three questions:
| Object | Who waits | Who wakes | How the end gets through |
|---|---|---|---|
BlockPipe |
Dispatch for the next block, Read for a free one | the other side | Read calls End on every path; Dispatch then gets the blocks that are left and no more |
SharedSampleStream |
a Gain task for the next piece of its channel, Encode for the end | Dispatch, the writer, wakes the Gain tasks as the stream grows; the writer's End and the last Gain task wake Encode |
End on every path of the writer; it reaches every reader after the last samples and carries the padding, the ReplayGain and whether samples were lost |
FrameRing |
Dispatch for a free slot; every other stage for a frame the stage before has completed, Resolve and Encode for the frame whose turn it is | the stage before, in its Complete…; Encode frees the slot and wakes Dispatch |
EndDispatch; the end passes through all stages after the last frame, and the tasks of a parallel stage hand it on to each other |
Mp3File |
Write for the next block of the stream, Encode for a free one | the other side | Encode calls End or EndAfterError on every path; the end carries the LAME tag and whether the ID3v1 tag follows |
The ring gives every stage a pair of calls. From
FrameRing.h,
without the comments:
// --- 1. Dispatch (one task) ---
FrameData& AcquireDispatch() noexcept;
void CompleteDispatch() noexcept;
void EndDispatch() noexcept;
// --- 2. Prepare (any number of tasks) ---
FrameData* AcquirePrepare() noexcept;
void CompletePrepare(const FrameData& frame) noexcept;
// --- 3. Resolve (one task) ---
FrameData* AcquireResolve() noexcept;
void CompleteResolve() noexcept;
// --- 4. Search (any number of tasks) ---
FrameData* AcquireSearch() noexcept;
void CompleteSearch(const FrameData& frame) noexcept;
// --- 5. Encode (one task) ---
FrameData* AcquireEncode() noexcept;
void CompleteEncode() noexcept;Acquire… may wait and hands out the next frame; it returns null once no more will come.
Complete… hands the frame on. Inside, a parallel stage claims the frames one after the other, so
each frame goes to exactly one task, and sets a mark on the slot when it is done. The ordered
stage after it waits for the mark of the frame whose turn it is. That is the ordered join.
The questions for an object of your own have answers here too:
- The state at the start. All slots of the ring are free, so Dispatch can take the first step. The sample stream counts its readers when it is initialized: the graph must start one Gain task for each, or Encode would wait for a reader that never ends.
- How many tasks wait at the same place. Dispatch, Resolve and Encode are one task each and wait on an AutoResetEvent_s. The tasks of Prepare share an AutoResetEvent, and those of Search another.
- The end carries data. What is only known at the end travels with it, so no task reads a
loose variable of another one. Encode shows both sides: it takes the end of the sample stream
as a reader, and it hands the end of the MP3 file on as the writer. From
EncodeTask.cpp:
frameEncoder_.Begin();
// after an error EncodeFrame does nothing; the frames are still taken and released, so the stages before and
// the Gain tasks run to their end
while (FrameData* const frame = ring_.AcquireEncode()) {
frameEncoder_.EncodeFrame(*frame);
stream_.Release(frame->frameNumber);
ring_.CompleteEncode();
}
// the end of the sample stream: the padding, the ReplayGain of the Gain tasks and whether samples were lost
const SharedSampleStream::StreamEnd end = stream_.WaitForEnd();
frameEncoder_.Finish(end.encoderPadding, end.radioGain, end.failed ? FrameEncoder::OutOfMemory : 0);WaitForEnd is the row "the end needs both ReplayGain analyses" of the table in step 2. Finish
flushes the encoder and, inside, calls Mp3File::End: the end of the MP3 file, which carries the
LAME tag to Write.
The comment in the loop is the rule of What can go wrong: a task keeps its promises on every path. After an error Encode still takes every frame, and Write still takes every block, so nobody waits for ever.
A Gain task reads the stream through a port of its own, which remembers where the task stands.
From
GainTask.cpp:
SharedSampleStream::GainReader reader = stream_.OpenGainReader(channel_);
ChannelGain& gain = reader.Analysis();
SharedSampleStream::Piece piece;
while (reader.NextPiece(piece))
gain.Analyze(piece.samples, piece.count);The pieces are those of LAME's calls, so the sums come out bit for bit as LAME's.
Two of the objects are close to what the library has ready-made and still classes of their own.
BlockPipe holds back the producer when all blocks are full, which
SpscVirtualMemoryPipe does not. The ring's stages need more than the
count of a Semaphore_s: they need to know which frame.
Assembling
The program is put together in one place, EncodeGraph. Its members are the edges and then the
nodes, in the order the data flows; the nodes are declared after the edges, so they are destroyed before
them. CreateNodes is a table: the task, the scheduler it runs on and its priority. From
EncodeGraph.cpp,
the nodes of the parallel graph between Read and Write:
dispatch_.emplace(pcm_, stream_, settings_.format, *ring_, ProfileOf(profile_, &Profile::dispatch));
Add(&*dispatch_, RunsOn::Compute, TaskPriority::Normal);
for (std::uint32_t i = 0; i < stageTasks_; ++i) {
prepares_[i].emplace(*ring_, encoder_, ProfileOf(profile_, &Profile::prepare));
Add(&*prepares_[i], RunsOn::Compute, TaskPriority::Normal);
}
resolve_.emplace(*ring_, encoder_, ProfileOf(profile_, &Profile::resolve));
Add(&*resolve_, RunsOn::Compute, TaskPriority::High);
for (std::uint32_t i = 0; i < stageTasks_; ++i) {
searches_[i].emplace(*ring_, encoder_, ProfileOf(profile_, &Profile::search));
Add(&*searches_[i], RunsOn::Compute, TaskPriority::High);
}
encode_.emplace(*ring_, stream_, *frameEncoder_, ProfileOf(profile_, &Profile::encode));
Add(&*encode_, RunsOn::Compute, TaskPriority::High);
for (std::int32_t ch = 0; ch < stream_.GainReaderCount(); ++ch) {
gains_[ch].emplace(stream_, ch, ProfileOf(profile_, &Profile::gain));
Add(&*gains_[ch], RunsOn::Compute, TaskPriority::Normal);
}Read and Write are added the same way with RunsOn::Io, Read with Normal and Write with High
priority. Run starts the table (shortened by the lines that take the time):
const Nodes nodes = CreateNodes();
// all nodes in one group, counted in before the first one starts
Synchronization::TaskGroup_s group; // one waiter: the caller
for (const Node& node : nodes)
group.AddTask(node.task);
for (const Node& node : nodes)
(node.runsOn == RunsOn::Io ? io : compute).AddTask(node.task, node.priority);
group.Wait();With 16 compute threads these are 37 tasks, 39 with ReplayGain. Read and Write run on the thread of the I/O scheduler. The other 35 or 37 share the 16 compute threads: at most 16 of them run at a time, and the rest wait in one of the four objects and hold no thread.
Where a node runs and how urgent it is was decided last, and it is a matter of speed only:
- Priorities. The stages after Prepare run with
Highpriority. Their frames are older and free their slots sooner, so the frames in the ring are finished before new ones come in. - Two schedulers. Read and Write have a scheduler of their own with one thread, so a completed request goes on at once and does not queue behind the compute tasks.
No task says any of this, and the output does not depend on it. The test below runs every node on one thread.
Testing
The method ends with two checks that come before any measurement.
The sequential program stays
ctLame has a second graph, --sequential: Read, one task that does all the encoding, Write. It
uses the same edges and the same encoder. From
SequentialEncodeTask.cpp:
const std::int64_t ready = stream_.FramesReady();
for (; next_ < ready && !Stopped(); ++next_) {
ChannelSamples input;
stream_.Window(next_, input);
frame_->frameNumber = next_;
encoder_.Prepare(input, *frame_);
encoder_.Resolve(*frame_);
encoder_.Search(*frame_);
frameEncoder_.EncodeFrame(*frame_);
stream_.Release(next_);
}These are the four calls of the stages 2 to 5 on one frame after the other: LAME's loop again. It is the reference inside the program. If the parallel graph ever writes another file than this one, the mistake is in the tasks and not in the port.
The reference outside is LAME itself. Every change was checked against the hashes of its output: 1372 encodings of 343 files, and about 1000 more with other settings and input formats.
Every order, on one thread
A task-based program is right if its result does not depend on the order in which its tasks run
(What can go wrong).
Because the graph hands out its nodes as a table, a test can start them itself: on one thread,
Read and Write included, in another order and with other priorities. From
EncodeGraphOrderTests.cpp:
Synchronization::TaskGroup group;
for (const EncodeGraph::Node& node : nodes)
group.AddTask(node.task);
std::uint32_t seed = (orderVariant + 1) * 2246822519u;
for (std::uint32_t i = 0; i < nodes.count; ++i) {
const EncodeGraph::Node& node = nodes.first[order[i]];
TaskPriority priority = node.priority;
if (priorities == Priorities::AllTheSame)
priority = TaskPriority::Normal;
else if (priorities == Priorities::AtRandom) {
seed = seed * 1664525u + 1013904223u;
priority = (seed >> 16 & 1) != 0 ? TaskPriority::High : TaskPriority::Normal;
}
oneThread.AddTask(node.task, priority);
}
group.Wait();The test encodes four seconds of a generated signal with three Prepare tasks, three Search tasks and both Gain tasks, in twelve start orders, three times: with the priorities of the graph, with all priorities the same and with priorities given at random. Every file must be the file of the sequential graph, byte for byte.
The random priorities are not decoration. To try the test, one dependency was removed on purpose: Encode did not wait for the Gain tasks. With the priorities of the graph and with all priorities the same the test stayed green in every start order, because on one thread the Gain tasks happened to be done in time. Only the random priorities found the mistake, in the first order. The start order decides who runs first; the priorities decide at every wait who goes on.
The test uses a default scheduler with one thread and not a LocalScheduler: its thread waits for the group while the tasks run, and the completions of the file I/O resume tasks from another thread.
What measurement changed
The tables give the tasks and their order. They do not give numbers: how many slots, how urgent a stage is, how thin a task in order has to be. Those came from measuring (the tutorial shows the method), and some of the answers were not the expected ones.
- The tasks cost nothing. When the encoder first ran as one task between Read and Write, a WAV file of 45 MB took 2.0 seconds, against about 1.9 seconds with LAME. (Today's sequential graph is faster than LAME, because the port has SIMD kernels since. The tasks have no part in that.)
- The form of this chapter costs nothing either. Before ctLame had one task type per stage, a pool of worker tasks served Prepare and Search. Against that version, cold, on a Core i9-11900K with 16 threads over 86 files, encoding takes 0.2 % longer without ReplayGain and 0.4 % less with it. Two builds of the same code already differ by about 0.3 %.
- Simple file I/O is enough. One request at a time with a local position is as fast as keeping several requests in flight and adjusting the priority to the fill level of the pipes, which ctLame did before. The simple form stayed.
- A yield that looked right was not. At first a Prepare task yielded to the later stages after every frame. It cost about 1 % with ReplayGain and gave nothing without, so it was removed. The priorities alone do the work.
- ReplayGain needs its own tasks. In the task that converts the samples, the analysis more than doubled the encoding time on 16 threads (+129 % on one test file), because it held up every frame. As one task per channel beside the frames, with its filters tuned, it costs about 29 %, which is its computing time on processors that are busy already.
- A task in order must be thin. Every microsecond Resolve or Encode needs per frame bounds all cores together. So the main data of a frame, its scalefactors and Huffman codes, is coded ahead in Search, and Encode only appends it: the serial bit stream went from 17 to 3.8 µs per frame.
- The size of the ring. Four slots per compute thread, at least 16 and at most 128. Fewer leave the parallel stages waiting for the tasks in order, more cost cache.
The way in short
- The program: one loop, and a second sequence hidden in
lame_encode_buffer. - Activities: two devices and seven activities between them, nearly all with state. A pipeline at first sight.
- The table: what each step needs, frame by frame.
- Needed or written: the bit reservoir and a part of the psychoacoustic model are state that must be taken in order. Most of the work around them is not. The filterbank only seemed to carry state, and the sample buffer became a stream.
- The shapes: long-lived tasks for the activities with state, a stage with several tasks for Prepare and Search, an ordered join after each, one stream with several readers, the file in file order.
- Shared objects: four, each with its answers to who waits, who wakes and how the end gets through.
- Assemble, compare, test on one thread: a node table, a sequential graph as the reference, every start order with random priorities.
- Then measure: priorities, schedulers, the size of the ring and the thickness of the tasks in order.
Reading the code
The task layer is small, and its files are named after what this page calls them. All are in
ctLame/src/Tasks:
EncodeGraph.h: the graph as a diagram, its edges and its nodes.- The shared objects:
BlockPipe.h,SharedSampleStream.h,FrameRing.h,Mp3File.h. - The tasks:
WavReaderTask,DispatchTask,PrepareTask,ResolveTask,SearchTask,EncodeTask,GainTask,Mp3WriterTaskandSequentialEncodeTask. - The encoder, which knows nothing about tasks:
Encoder.hhas the four callsPrepare,Resolve,SearchandEncode. - LAME's loop:
lame_main.c.
The README of ctLame has a reading order for the whole program, and How ctLame's task graph grew is the real history with its numbers.
See also
- Thinking in tasks, Finding the tasks, Shared objects, What can go wrong
- The ctLame showcase: how the task graph really grew, and what it gained
- The tutorial: the same way with a small program, with measurements
- Task graphs, Async file I/O, Priorities
- AsyncFile, AutoResetEvent_s, TaskGroup_s