ctLame writes exactly the same MP3 files as LAME, byte for byte, and is
14 times as fast on an 8-core CPU. LAME is sequential by design: every frame depends on
the state the one before it left behind. These nine pictures show how, step by step, a
single encoder became a task graph on ThinkMeta ConcurrentTasks that keeps every core busy – and why
each step was needed.
Picture 1 of 9
The reference: LAME
LAME reads a block, encodes it and writes it – all on one thread,
one after another. Every stage carries state from frame to frame: the
psychoacoustic model, the filterbank, the bit reservoir. One core works,
the others wait.
These bits are the yardstick: every following picture has
to write exactly the same MP3 file, byte for byte.
Bit reservoir
An MP3 frame may use bits that earlier frames left unused. How a
frame is coded therefore depends on every frame before it –
the main reason why MP3 encoders work sequentially.
The reference
LAME 4.0, reduced to what ctLame implements: MPEG-1 Layer III
with LAME’s “new” VBR routine from WAV files.
For these settings it writes the same bytes as the unmodified
LAME.
Run time · test file, 4 minutes of music
1.9 s
Picture 2 of 9
Reading and writing run alongside
fread and fwrite become tasks of their own with
asynchronous I/O on an I/O scheduler; the whole encoder is one task on
the compute scheduler. Reading and writing now happen while the
encoder works, with up to four requests in flight.
The I/O chain manages about 600 MB/s – some 27 times what the
encoder processes on one core. It will not become the bottleneck later
either. Still only one core computes: as fast as LAME, bit-identical.
Pipes and priority
The pipes between the tasks are bounded. Their fill level sets the
priority of the I/O tasks: when the input pipe runs low, the reader
switches to high priority, so the encoder never waits for data and
memory stays small.
The LAME tag
The LAME tag with checksum and table of contents is only known
after the last frame. Write puts it at the start of the file at
the very end.
Still in use today
This graph is still in the code: ctLame --sequential
runs the finished encoder in it on one thread – the
reference path for comparisons.
Run time · test file, 4 minutes of music
2.0 s
Picture 3 of 9
Untangling the state
The graph stays the same, but the encoder is rebuilt from the inside: six
stages, and everything that belongs to one frame lives in a record of its
own. What is carried from frame to frame stays in the state of its stage
(the loops): psychoacoustics, filterbank, bit reservoir.
Only one dependency crosses both stages and frames (dashed): the bitstream
of frame N decides how many bits the quantization of frame N+1 may use.
You can only parallelize what you can take apart.
The map
A frame takes about 200 µs. Of that, psychoacoustics need 38 %,
the MDCT 8 %, quantization 49 % and the bitstream 5 %.
This profile guided every following step.
False alarms
Two values in LAME looked as if a frame depended on a later one.
Both turned out to be resolvable forward.
Run time · test file, 4 minutes of music
2.0 s
Picture 4 of 9
Two tasks, one ring
The encoder is cut into two tasks between analysis and quantization. Both
halves are about the same size; as a pipeline, frame N is quantized while
frame N+1 is analysed. Between them sits a ring of frames: a slot is free
again as soon as its frame is done.
Handing a frame to another thread costs about 0.4 µs, against some
200 µs of work – so every frame is handed over on its own, no
batching. The bottleneck now: Encode.
Sample stream
Each channel is a stream of samples in reserved virtual memory. A
frame points to its window instead of copying it; only what is in
the ring right now takes up memory.
Why Encode has a bold border
The bold border marks a task with high priority. Encode, the later
stage, runs before the analysis: the pipeline drains first, before
the analysis computes further ahead. Later, Resolve gets high
priority for the same reason.
Pipeline time · the same test file
2.12 → 1.27 s (1.68×)
Picture 5 of 9
The search goes frame-parallel
The profile showed: about 95 % of the quantization does not depend
on the bit reservoir at all. The search for scalefactors therefore runs
for many frames at once, one task per compute thread. Only the commit
– bit budget, bitrate choice – stays serial, and it takes a
few microseconds.
The heaviest stage is spread over all cores. The bottleneck now: the analysis, serial with its state.
The scheduler learns, too
On the way, ctLame showed that the scheduler woke all sleeping
threads for every new task. It now wakes at most one – and
the run time no longer depends on the number of threads. Every
encoder also makes ThinkMeta ConcurrentTasks itself better.
Pipeline time · the same test file
1.27 → 1.05 s
Picture 6 of 9
The graph takes shape
About 90 % of the psychoacoustics need no state: FFTs, spreading,
energies. They now run as Prepare for many frames at
once. Only Resolve stays serial: attack detection, block
type, pre-echo control. The MDCT turns out to be stateless as well.
Every frame passes five stages: serial, parallel, serial, parallel,
serial. Only three short links remain serial: Dispatch, Resolve and
Encode.
One worker pool
Prepare and Search are the same worker tasks, one per thread. They
take the search first: it belongs to older frames and frees slots
in the ring sooner.
Pipeline time · the same test file
1.05 → 0.29 s · about 8× LAME
Picture 7 of 9
The serial links get thin
Every microsecond a serial link needs per frame limits all cores
together. So work moves out of the serial nodes into the parallel ones:
Huffman coding now runs in the search, the serial bitstream only appends
it (17 → 3.8 µs per frame). The filterbank is computed in Prepare;
Resolve only passes its carry on, in order.
From here on the result is measured over whole program runs on a corpus of music files.
Tried and dropped
Splitting Resolve further was bit-identical and shrank the serial
chain from 13.7 to 4.9 µs per frame – on 8 cores it
gained nothing, because the workers were already busy. It is ready
for CPUs with more cores. Look-ahead, other priorities, a larger
ring: within the noise.
Speed-up over LAME · whole run
7.76× → 8.33×
Picture 8 of 9
Less work per node
The graph has reached its optimum on this machine; from now on gains
come from less work per frame. SIMD kernels (SSE4.1, AVX2) in the parallel
nodes compute the same operations in the same order as the scalar code
– and so give the same bits.
The ring grows with the number of threads: 4 slots per thread, 16 to 128.
On one thread ctLame is now 1.7 times as fast as LAME.
Why the ring grew
With 16 threads the stages were only 60 to 70 % busy: the fixed
ring of 32 slots allowed too few frames in flight. Growing it with
the thread count took the corpus from 12.75× to 14.08×.
Speed-up over LAME · whole run
8.33× → 14.08×
Picture 9 of 9
The complete graph
Seven kinds of nodes; with 16 threads that is 21 tasks on two schedulers.
A frame is finished about every 13 µs. On 45 hours of music, ctLame
needs 83 seconds instead of 19½ minutes – every file
bit-identical to LAME.
Why fibers make the difference
The serial nodes wait in the middle of their work: Dispatch for a
free slot, Resolve for the state of the frame before, Encode for the
bits it left over. On ThinkMeta ConcurrentTasks such a wait suspends only the task; its
thread meanwhile computes other frames, and every node stays a
simple loop over the frames in order.
Other CPUs
Intel Core i9-11900K, 8 cores: 14.08×
Intel Xeon E3-1275 v6, 4 cores: 8.14×
Intel Core Ultra 7 155H, notebook: 7.54×
Bit-identical to LAME on every machine.
Speed-up over LAME · 45 h of music
14.08×
Try it yourself
The reference build of LAME and the benchmark are on
GitHub.
Have a workload that should use every core?
Get in touch.
