Staged Pipelines and what people think of them

scrut-hut wrote:

I must insist every one read the following reference.

Hmm. I'm quite good at parallel programming, i think. But trying to read this paper gives me the same experience i get from reading patents, Vulkan specifications, or articles about quantum physics. I would need to research every second term they use to figure out which concepts they mean, only to find in the end its all just obvious high level paradigms on how to connect the dots.
So i'll pass, since i never have problems with connecting the dots. I rather spend 99% of time on making the dots work, actually.

So, if you want to spread the word, feel free to describe your excitement about the mysterious topic in your own words, ideally accessible for self thought dummies equipped with only common sense. ;D

Looked at the paper, but I don't really see the point. It looks like a high level summary rather than something usable, especially in the game community.

Fractals are trivially parallel, so I can understand why you might want to use them. We left the era of the fractals used in the test case roughly 30 years ago. People were doing deep zoom infinite fractals in the 1990s before PCs had hardware floating point support, and shifted to 3D test cases before 3D specialized graphics hardware existed. If you are demonstrating something novel, please at least use a scene from the past quarter century.

A better, more typical test case for games would be a scene with mountains, forests with many types of trees dancing in the breeze, lakes, rivers, and grassy fields with wind waves, and some buildings all visible, maybe flags in the distance casting live-animated shadows affecting 2-6 pixels as the wind causes the flags to move, plus nearby flags for comparison, a sky with volumetric clouds and maybe light flares and bloom around the sun, a shiny vehicle, a human with detailed skin, hair, and eyes, plus their furry / feathery / fluffy animal companion. All with many lights and shadows.

Show me a 2M polygon dragon, view-dependent continuous detail levels, iridescent scales, face up close and body curling away to showcase both the high details nearby and the transition to the distance, in a high-poly cave filled with polished gold treasures, glittery gemstones, flickering torches, again with lighting and shadows.

The objective of this work is to provide the programmer and/or novice user with different multicore programming approaches so that without much effort they can develop their programs according to a sequential programming style, obtaining automatically, easily and the counterpart parallelization of your code with the help of a specific programming environment like the one proposed.

I'm not entirely sure you succeeded with the objective. The paper is aimed at grad students, but the skills discussed are extremely undergrad. Academically parallel programming is often introduced as a 3rd year topic, so you missed your mark by 2-3 years of schooling. In industry, because of the bugs it can introduce and the huge variability in consumer hardware it's almost always task-based parallelism when used in games.

There isn't really anything the paper for a programmer to implement, especially nothing for a "novice user". The handwaving topics you introduced were covered in undergrad, actually building them, and breaking down parallel processing constructively was my first semester of grad studies. I just don't see it, so maybe I missed the point of the article.

I think my favorite double-take in the paper was this: "The use of Threading Building Blocks or TBB, which was born more than 10 years ago as a solution for writing parallel programs..." A moment of "wait, what", then, ah, "more than". I encountered the commercial version in 2001 when it was tied to the Intel Compiler toolset, and the lab (my grad school years) had access to the tools. I think it was introduced in '99 or '00, and I loved the announcement in 2007 when they decided to move it to open source. "More than 10 years" indeed.

JoeJ wrote:

I would need to research every second term they use to figure out which concepts they mean, only to find in the end its all just obvious high level paradigms on how to connect the dots.

Indeed, I tapped out after 2 pages. While muttering things about P-completeness.

Parallel paradigm anything smacks of premature optimization. Who's using the rendering engine? Who's using the game engine on top of the rendering engine? What are the real bottlenecks of content production? Does the content actually have a problem being rendered? If something is to be parallelized, what bottleneck is there really? Pixels? Vertices? Object space models? Geometry amplification? User scripts? Loading from secondary storage? Loading from the internet?

@scrut-hut Pipelines aren't always applicable as a technique. They are immensely useful for when you have long tasks that can be split into a sequence of tasks, where if you were to just execute the tasks in parallel, you would have resource contention between threads for certain stages of the process. In the pipeline paradigm, you can completely eliminate intra-task contention by making it process one task at a time only. I'm doing that for my compiler:

• I have one thread that constantly loads files from disk, parses include statements at the top of the file, then passes the file on to the tokeniser and issues more work for itself based on the include statements (while also not processing files that are already loaded). This way, I can have one thread that is basically making full use of the disk's I/O capabilities. If I had the parallel workers model, then multiple workers would have to contend over a central file registry to prevent duplicate loads.
• The second stage is a pool of multiple threads that tokenise files (because the tokeniser is currently the slowest stage, and the slowest stage limits the overall throughput of the pipeline). The fully tokenised file then gets passed to a third stage:
• The identifier deduplicator. It takes all identifier tokens in the files it processes, and deduplicates them through a hashmap, assigning a running counter to each new distinct identifier it encounters. This leads to a global u16 ID for each distinct identifier, which later on speeds up scope lookups tremendously, since they can be reduced into normal array lookups instead of hashmap lookups. The ID is saved on the identifier tokens. This stage would be a nightmare on a naive worker pool setup, where I would need an atomic / threadsafe hashmap lookup for every identifier token. But since now only one thread executes this stage in a loop, I can use a single-threaded hashmap here and be super fast.
• Lastly, the tokenised & ID-deduplicated file gets passed into a pre-parser stage, which parses namespaces, classes, functions, etc., but does not yet parse function bodies. It skips over bodies by skipping over matching parenthese / brace / bracket pairs, making it very efficient compared to full parsing. And it also doesn't produce an AST, which I would later on have to traverse again.

When that pipeline is done executing (i.e., all source files have been loaded and processed), I do a post-processing step which pre-bakes lookup tables for scope lookups, so that I do not have to do a loop that first checks the innermost namespace, then the outer namespace, all the way to the root scope. Instead, it now has one fully baked lookup table for looking up identifiers from within any scope using a single array lookup. It also deduplicates names some more by only considering the set of identifiers that are used for global definitions (global classes, functions variables, namespaces), creating a much denser set of name IDs, leading to denser and much smaller lookup tables, and therefore better cache performance.

This compiler currently loads 68 files (11,366 lines, 315,646 bytes) in 1.39ms in the pipeline, and 0.14ms in the post-processing step. That is a processing speed of over 7M LOC/s or around 190 MiB/s. I only have one inter-thread operation per file per stage, as I pass on the output of one pipeline stage to the next pipeline stage's thread. Here are the numbers if you are interested (measurements only cover the actual time spent working, does not include stalls or synchronisation overheads):

info: Phase 1: 68F (11366L, 315646B) in 1.390+0.139ms. 1807|390 ids,   938µs load,   943+  847+  696µs tok,  1124µs dedup,  1127µs parse // 4.84ns/B, 7.425ML/s, 12.23%+1.23% of budget

There are 1807 distinct identifiers in my codebase, but only 390 are used for global declarations. Which means a namespace's scope lookup table would only require 390 entries instead of 1807, and since this is a sparse lookup table (not every namespace contains an entry for each name), this lets me massively cut down on the number of wasted entries.

However, the performance is quite unstable, even after manually managing CPU affinity, tying the threads to specific cores and hyperthreads. The kernel often schedules some work on ones of the cores I want to be on. I get this kind of performance only around 1% of the time, with the average being around 5–6 million LOC/s. Another thing to consider when using pipelines is that you cannot have arbitrarily many stages to your pipeline, and passing work on from one thread to the next means bus traffic. Bus traffic kills your performance because it is quite limited, and the more stages you have, the more bus traffic you get. So it might sometimes be better to bite the bullet and keep the workload on a single thread, and just have many of them, even if you end up with resource contention.

And finally, pipelines only work well if you have enough cores, and manage the thread affinity properly. Which means it does not scale as trivially as the naive worker thread pool, because on some devices, you might not have enough cores to dedicate a physical HW thread to each stage of the pipeline. And as I mentioned earlier, you want to roughly have all stages take equally long to process, or the slowest stage will stall all other stages.

So I don't think it's a sliver bullet, it's highly situational, but if used properly in the right kind of situation, can have massive benefits. And finally I would probably not recommend using pipelines like this in a game where you have real-time constraints and latency spikes are forbidden. If one thread of the pipeline gets swapped out for a few milliseconds, the entire pipeline hangs for that long. In a naive worker pool, swapping out one thread means the others can just steal more work and mitigate that spike pretty well, making it the much more robust choice for a game. However, if you have pathological workloads like my identifier deduplicator, then using a pipeline is still probably the most appropriate thing to do, but you must be aware of the brittleness. Also, the fewer threads the pipeline uses overall, the more robust it is against random OS scheduling shenanigans, I assume.

The goal for my compiler is >1M LOC/s compile speeds, and currently phase 1 consumes ~13% of that timing budget. But this leaves me in a position where I can now parse function bodies and already have a fully populated global scope tree, meaning I could theoretically immediately output code from the function body parser, without even creating an AST. Of course, template instantiations etc. complicate that process a little bit, but in general, the current design should be appropriate for reaching those final speeds easily. The goal is to have ~10–20K LOC programs compile within 30ms, or at 30FPS. Then, I don't even need executables anymore, and can directly distribute the source files. They can then launch within 1-2 FPS delay, meaning basically instantly. And then I also don't have the hassle of dealing with linking, machine-specific builds (the compiler can just do the equivalent of -mtune=native), and platform-specific builds that I would have to distribute. Without pipelining and squeezing out every last bit of performance out of the entire code, I would not have anywhere near that performance. Though, just as important is proper up-front management of data flows, cacheline migrations, cache working sets, etc..

Another reason why I chose the pipeline model early on for the compiler, before I even had the identifier deduplicator idea, was that since I only have one disk anyway, so I only have one data stream, that is my speed of light limitation. I cannot load files faster than I can load them from disk, and more threads won't help with that. So the most straightforward way to access as much source code as quickly as possible is to have a single thread that constantly loads new files in a tight loop, and does the minimum amount of work necessary to extract more includes from the file it just loaded. In my language, the includes can only appear at the top of the file, so I only have to parse until I encounter a line that is not an include statement. And then it goes straight back to loading files. I wish there was a syscall that let me load a bunch of files at once into pre-allocated buffers or something.

Another important observation is that you can put more work into a pipeline stage that is not bottlenecking the pipeline (i.e., it is not the slowest stage) for free. Although if the bottlenecking stage is memory bound, then adding more work to one stage can slow down the bottlenecking stage, too, because you get more cache evictions, etc.. Though this is just me using a cheap 500€ laptop, not a tower PC with huge L3 caches and beefy cores. My CPU has 16KiB L1 caches (or 32KiB shared between hyperthreads), 512KiB L2 caches per core, and one 4MiB L3 cache. On a 128MiB L3 cache, and with more than 8 cores, you would be looking at a completely different performance profile, though. Also, laptops have a different type of RAM that is not as fast as tower PCs, exacerbating the situation even more. Ideally, I would speed up my tokeniser by 3x and then I could nuke 2 of the threads. Then, my design would also run on old quadcore machines properly.

Charles, the paper you linked is interesting work, but it's about heterogeneous parallel computing — pipeline patterns implemented in SYCL/TBB across multi-GPU clusters for workloads like parallel fractal generation. That's a different universe from "should a solo dev ship a PC game in Java." The word "pipeline" is doing a lot of overloaded work between game engine architecture and HPC research.

The useful kernel of your advice — separate your engine into clear staged phases (input → update → physics → render).

I recorded some more fine-grained timings of my compiler's pipeline. Even with just 4 stages and 6 threads, I get lots of stalling from kernel context switches. Here are some diagrams: the timings are in microseconds, the vertical axis is the number of jobs processed. The “hook” timings are the logic executed after each workload, which usually amounts to just passing it along to the next stage.

The file loader does not have any idle time, because it produces the data ingress. We can see that the very first file takes unnaturally long to load, almost 10% of the entire runtime. Yet that file is not particularly large (around 2% of the total code size, in bytes). So it is probably due to cold instruction or data caches, some page faults, and maybe also problems caused by the scheduler.

Next up, we got the tokenisers:

These run in parallel, and get work assigned to them in round-robin style. Two tokenisers were too few, but 3 are too much, resulting in a lot of idle time. And we can see wheere the kernel swapped out a thread when some job takes extremely long. The tokenisers then feed their results on to the next stage as they finish processing a file (so, without adhering to round-robin ordering).

This stage is the identifier deduplicator. We also can see some unfortunate stalls here, either waiting for work, or being swapped out while working.

And finally, we got the timings of the last stage of the initial phase: the parser. In this specific run, we did not have any idle time on the parser, because it got swapped out during processing of the very first file (at least I think that's what happened), so it was constantly behind on work.

For context, this was an above-average run, I'd say within the top 5–10% of my overall timings. We can see just how brittle the pipeline model is, and how any delays that are incurred will propagate. One of my takeaways from all of this is that you would want to have a warmup procedure that runs during the idle time where no work is available yet, to get some page faults out of the way and to try to prefetch some code into cache already. Ideally, there would be some dummy workload that you can run the real logic on, followed by some fixup logic that undoes the dummy workload's effects. We got an initial propagation delay of ~15% of the overall runtime here, despite the first file being only around 2% of the total code size, and us having 70 files in total. So we would expect something around 1/70th of the total runtime to be the overall initial delay. And the first job also takes around 10% of the total time to execute on each stage. So we waste around 26% of the total wallcklock time until we finish just the first workload, which should be something like 4·2% instead (number of stages · relative size of the workload). So we should take around 20% less total time even just in the startup phase.

For timing measurements, I used the rdtscp CPU counter instruction, and the threads are locked to specific cores, so there are no drifts or jumps in the readings, and a measurement does not involve a syscall or anything like that. The recorded timings are written into a pre-allocated container, so they also do not involve any memory allocations that would grossly impact the timings. Since the timings are on unsynchronised clocks, I defined the first workload as starting at the time when the previous stage's first workload finishes.

Aren't dummy workloads just hogging the available computing resources so that your own application can look better? In some benchmarking contexts it could even be considered a form of cheating. It depends on whether the computer and OS are deemed to be doing something else important, or just sitting around idle with the user staring at the screen. Like if the computer is under load, how is you thrashing the cache actually helping anyone?

A pipeline needs a warmup phase (marked in red here). The worker threads for the stages are already running, but they don't have work yet that they could be performing. So you can insert a dummy workload in the red zone, and that can warm up caches, trigger necessary page faults, etc.. And I could also start up the first stage thread right at the start of main(), and then insert a dummy operation there, too, before I even start to parse command line arguments etc..

If you got hundreds of workloads, then the startup time gets amortised and becomes negligible, as throughput starts to dominate over latency. But currently even at 70 workloads and 4 stages, the startup time takes ¼ of the execution time. That's because the first job a thread tries to process takes 10x longer or something, and the latencies of processing the first job get added up. In my setup, it's not really feasible to pass on partial work to the next stage before the current stage fully completes handling the workload. Inserting a dummy workload in timeslot 0 would still incur the 10x cost, but that's before any useful work actually arrives, so I'm idle anyway. And then the first actually intended workload would not incur that staggered 10x cost. Instead I pay that cost once in parallel instead of in series, and (at least partially) during a time during which I would be idle anyway.

And my compiler only runs that pipeline once per invocation. It is not like a game that repeats the pipeline every frame, where you would only have the warmup phase on the first workload of the first frame, and then never again. The goal for my compiler is to compile a 10–20k LOC program from scratch within a 16ms (60FPS) budget. Which means even 0.3 wasted milliseconds are a big deal. Especially since I will be launching multiple pipelines in different phases of the compiler, and they all have a serial dependency. The pipeline of phase 1 of the compiler has to fully complete processing all files before the phase 2 pipeline (type checking, etc.) can start doing anything. So any latencies I waste will add up and make it infinitely harder to meet my performance goal.

If I have 3 major compiler stages, and each incurs a 0.3ms delay on even starting to process work, then that's already roughly 1ms, or 1/16th (6.25%) of the budget, stalling. And I'm already optimising my actual workload code as much as I can already, and the data models, data flow, allocation strategy, etc., just so that I can even get close to that performance goal. Any tiny mistake in my workload code easily costs me 5-10% performance, sometimes more. And I really mean tiny mistakes.

I seem to recall the IBM Cell chips had a DMA scheme that could help greatly with the synchronicity of caches. I also thought there were some low level x64 caching commands, doing so-called scatter-gather DMA. But I never used them, and I don't recall whether I had the OS privilege level to use them. It was a device driver sort of thing to worry about.

There are cacheline prefetch instructions, which are user-mode. Then there are manual cacheline eviction instructions. There are also a few instructions for gather-scatter on more recent x64 processors (SIMD gather scatter), but they are not really about cache management. When you first access a page that was never accessed before, you get a page fault, and that page gets allocated by the OS. If it's a .bss section page, or allocated via mmap(), then the page does not trigger a page fault if you read it, and instead is mapped to one global 0-initialised page. But the first write to it will then page fault and allocate a new page, zero it out, and return it. That involves a context switch into the kernel, which due to spectre/meltdown mitigations flushes caches or something. So you can get a huge cost for accessing an unallocated page, and then get a follow-up speed penalty because your caches got flushed or something. That's why “touching” pages you intend to write to up-front with a dummy write can lead to overall performance gains, as the code writing to it doesn't forcibly switch into the kernel once for every 4KiB that you access, and doesn't evict cache all the time.

There are also a few privileged cache management instructions, or those that are only available on very recent CPUs, so I can't really use them for my baseline performance. I only want to opt into new HW features when the baseline performance is already good enough. And some simply don't exist even on modern laptop CPUs for example (like AVX512).

RmbRT wrote:

A pipeline needs a warmup phase (marked in red here).

A proposal on how to solve this:

Instead of optimizing the shit out of your compiler to save a nanosecond each time you'll compile in the future,
write actual code you want to compile. Lots of code, so the idle cores at the beginning and at the end do no longer matter. \:D/

Alternatively you can find some other work to keep cores busy all the time, e.g. some Intellisense system constantly compiling edited code in the background, to annoy you with warnings on potential bugs and proposals to fix them.

Or a similar thing analyzing scopes so you can collapse / hide code you currently don't want to see. Very useful feature.
But this may be very, very hard it seems. Even after decades Microsoft has not yet figured out how to make this actually work.

Though, maybe having some idle cores here and there isn't that bad at all. I keeps the CPU alive and the room cold. : )

JoeJ said:
write actual code you want to compile. Lots of code, so the idle cores at the beginning and at the end do no longer matter. \:D/

The code I want to compile the most right now is my self-hosted compiler. After all, I am currently stuck with the bootstrap compiler which just does a syntactical transformation to C++, and takes a minute to compile my 12K LOC codebase (because it generates like 100K LOC of heavily templatised C++, lol).

JoeJ said:
Alternatively you can find some other work to keep cores busy all the time, e.g. some Intellisense system constantly compiling edited code in the background, to annoy you with warnings on potential bugs and proposals to fix them.

I was thinking about something like that, as well. But that would come once I start writing my own IDE for my language. But I still want to be able to compile stuff even without having an IDE open. For example I want to port my compiler to WASM later on, and then I can compile my programs just in time in the browser, like scripts. And, I also have the long-term vision of building a linux distro where everything except for the kernel, drivers, and the compiler is just a source .tar or something instead of an executable. And then when you want to launch a program, you install launch the compiler and compile it, and then it gets launched. This means basically the entire user space of the OS would consist of source code that gets compiled on your machine, meaning you get -mtune=native style compilation for all software you run. Once a program has been compiled, its executable gets cached in /tmp/ somewhere or something.

Having all software in source format and a fast compiler means you can also generate debug builds at any time, and you have infinite time for optimisation, because you can run an optimising build on the user machine, and can even use profile-guided optimisations. Basically like modern JIT runtimes do it: you get a super quick startup, and then it progressively optimises itself at runtime with techniques that you rarely get on precompiled binaries. And it could try to optimise itself some more every time you launch the program. And the debugger could be much more powerful, since it has full introspection into the language, it can access inlined functions, can instantiate templates, query the type system, etc.. You could even edit the code at debug time and stuff like that, like you got in some interpreted languages.

JoeJ said:
Though, maybe having some idle cores here and there isn't that bad at all. I keeps the CPU alive and the room cold. : )

Ideally, I'd only use 4 threads at a time, so that I can keep a few hyperthreads available for OS scheduling without any need to swap out my threads. But that's the same for video games, actually. You don't want to max out all the cores and then drop frames because the OS scheduled some other stuff. You always want to leave some buffer for the kernel like that.

RmbRT wrote:

This means basically the entire user space of the OS would consist of source code that gets compiled on your machine, meaning you get -mtune=native style compilation for all software you run. Once a program has been compiled, its executable gets cached in /tmp/ somewhere or something.

Now you only need a way to encrypt the source code so there is still a software business possible on your OS.
Spir-V would be an example. At least it was an initial argument from Khronos.
Later they released tool to generate readable shader code from spirv as a debugging tool, afaik. ?:

RmbRT wrote:

you can also generate debug builds at any time, and you have infinite...

Lives, in game dollars, and XP points to finally beat your multiplayer buddies which were always better than you before. \:D/
And you can extend your Adobe subscription to infinity without a need to pay. >:)

But... why not? They say software is dead anyway.

RmbRT wrote:

You don't want to max out all the cores and then drop frames because the OS scheduled some other stuff. You always want to leave some buffer for the kernel like that.

No. I don't want that.

Imo, if PS4 reserves one core out of 8 for OS, it should cost 349 instead 499. Simple math.

I want an OS which does nothing while i play. It can't be that hard. : )

JoeJ said:
Now you only need a way to encrypt the source code so there is still a software business possible on your OS. Spir-V would be an example. At least it was an initial argument from Khronos. Later they released tool to generate readable shader code from spirv as a debugging tool, afaik. ?:

LOL. Machine code obfuscation is for jerks, but it's the only way to really keep your trade secrets. But my OS won't be like that, so it's fine. People already paid enough money for the hardware, so the software should be free, and financed through donations or self-sacrifice. At least tools and productivity software should be like that. Games can still cost something, though. But not 80€ or whatever they want nowadays, and also not subscription-based costs.

JoeJ said:
No. I don't want that. Imo, if PS4 reserves one core out of 8 for OS, it should cost 349 instead 499. Simple math. I want an OS which does nothing while i play. It can't be that hard. : )

TempleOS. You own the machine, you own all the cores. Though I guess playstation etc. is also specifically designed for being as unintrusive as possible. But windows and linux aren't designed for that. Though if you are superuser, you can get real-time scheduling on linux. But you can't expect that the compiler only runs well if you give it root access, that's dumb.

JoeJ said:
Lives, in game dollars, and XP points to finally beat your multiplayer buddies which were always better than you before. \:D/ And you can extend your Adobe subscription to infinity without a need to pay. >:) But... why not? They say software is dead anyway.

If all that's required to cheat in a multiplayer game is a modified client, then the game developer is a dumbass. Always validate your inputs you receive over the network…

Well, my OS won't be POSIX compliant. Or rather, my language won't be. Basically, you boot straight into a runtime that only allows you to run my language, and my language provides its own hardware access layer. So you can't talk directly to the kernel without going through my language. So you also won't get the C runtime, etc.. The goal is to have the software written in my language to run anywhere I want, as long as the platform provides a runtime that provides the API of the hardware access layer. So the exact same code will run on web or on linux or in my custom linux distro, or on windows, or on a completely custom kernel, or on that FPGA ISA I want to build some day. As long as the hardware access layer is designed well, you won't even miss any OS features anyway.

Anyway, so in my planned OS, you won't even compile and run C code anyway. It won't even ship with a C compiler. And you also won't be able to launch .exe files. You'd request to run a .tar file or something, and that would then check whether it's already been compiled or whether it has to call my compiler. So you are sandboxed into only running my language on that OS. Of course the runtime layer has full access to the underlying kernel, etc., but user code won't. But it won't need it, anyway, because I want everything you'd want to do to already be offered in a platform-independent way by the language runtime.

Update on adding a dummy job at the start of the pipeline: I added a dummy job to the first tokeniser (it does not appear in the records), so that while the first file gets loaded by the file loader stage, the tokeniser stage is already tokenising a short dummy file. This then gets passed through to the identifier deduplicator and eventually the parser.

Since I cannot give a dummy job to the parser stage, I made a dummy fopen()/fread() call in a separate thread that I spawn right at the start of main(), before I even do global state initialisation of the compiler. This removes the initial cost of dynamically resolving the C runtime library, and this happens simultaneously with the global state initialisation (touching some pages to allocate them, pre-allocating global dynamic buffers, etc.).

It drastically improved my performance, and I now get 7% better peak performance than before (7.444M LOC/s now vs. 6.950M LOC/s previously, being the peak measurements out of thousands of runs). Here are the new timings (taken from a 7.182M LOC/s run):

As you can see, we are faster by a lot here, in part because I was able to get a luckier recording here (percentile-wise) than the previous recording. But what's important in this data is the first file being processed.

The latency until the first file in the tokeniser slightly less, because we do not incur the cost of dynamically loading the C runtime (each time we call a C runtime function for the first time, it gets dynamically loaded).

The first tokeniser is now much faster in processing the first file, while the other tokenisers remain largely unchanged (incidentally, they did not receive a dummy workload).

The identifier deduplicator receives the first workload much sooner and also finishes processing it so quickly that it stalls afterwards, waiting for the second file to come in.

The tokeniser now finishes the file much quicker and even fully processes the second file before it would have even received the first file in the naive pipeline implementation that did not issue a dummy workload. This headstart compared to before now makes the parser stall while waiting for new work to arrive when the deduplicator is busy on a particularly large file.

This perfectly illustrates the problems that non-uniform workload sizes can cause. And also, the file that stalled us for so long isn't even that expensive to process in the parser, while the identifier deduplicator is having a particularly hard time with it, as is the tokeniser. So one very large job that is particularly challenging for one stage of the pipeline can have a disproportionate impact on the entire pipeline. And I cannot get around that by introducing another identifier deduplicator thread, because then, both would be slower because they would constantly contend over a complex, shared container.

In conclusion: Pipelines can be extremely fast, but they are very hard to use correctly, because there are so many pitfalls and it's hard to get the friction out of them. Identifying anomalies like this “cold first workload” problem can make a big difference if you aren't dealing with hundreds or thousands of workloads. It is important to identify which stage is bottlenecking your pipeline, and ideally, you can make all stages equally fast on average. If there is one stage that is inherently faster, and sitting idle a lot, this gives you the opportunity to do more work for free on that thread, without impacting the overall runtime. So you can always try to make the slowest stage faster until it meets the other stages in average throughput, or, if you can no longer squeeze any performance out of it anymore, you can then bloat the other stages instead and make them perform more useful work on the side.

For this particular project, it means I will have a look at the tokeniser and identifier deduplicator implementations, and try to make them faster. If I can't achieve that, I might end up reworking the pipeline structure to allow passing partially completed workloads along while I am still processing them, like the paper recommends (see below). This could for example mean that I process at most 1024 tokens before I pass that chunk on to the next stage, reducing the stalls caused by large files. This would come at the cost of having to introduce checks to the subsequent stage which stall when we need to wait for more partial data from the previous stage.

RmbRT wrote:

People already paid enough money for the hardware, so the software should be free, and financed through donations or self-sacrifice.

Shouldn't we be making our own hardware out of melted down aluminum cans? You don't really own and control the means of production if you can't make the electronics.

bvanevery said:
Shouldn't we be making our own hardware out of melted down aluminum cans? You don't really own and control the means of production if you can't make the electronics.

That's much harder than you think. To make anything even remotely passable at home, you would still need lots of (sometimes restricted) chemicals, you would need your own wafers, and you might even need stuff like an electron scanning microscope or something else you can use to etch highly intricate structures into a silicon wafer. You can check out Sam Zeloof's youtube channel, that guy is basically doing the best you could possibly do in a garage setting. And unlike us, he received some machinery that doesn't even have a public market price on it, as a donation or something. He has a sputterer, an electron gun, and some other stuff like that. No normal individual can afford those things.

The closest you can get to making your own hardware, realistically, is if you buy an FPGA and design your own circuitry that you load onto it. And then, if you want to get really fancy, you can maybe design your own PCB and assemble it from custom parts instead of buying a preconfigured FPGA board. At least for that you only have to buy a few chips, custom-order a PCB design, and then buy soldering equipment.

That would still put you far ahead of what Zeloof was able to produce even with his electron beam & sputterer setup, in terms of cost, density, and effort required.

“Owning the means of production” is a pipe dream for something as sophisticated as microchips and integrated circuits. Or do you also plan to own an iron smelting facility for producing your own steel, and a forge to make your own knives? And then your own excavation site & tools for excavating ore & fuel?

For what it's worth, the multithreading in my game engine is written using what's described in this paper as FGI. Messages are being sent through endpoints, which are the communicating channels between agents. Agents can represent a dedicated thread or task based multithreading. My resource cache is single threaded and thread safe for example, while the actual asset loading follows a fan-out pattern where each stage can be processed independently.
The whole graph is wired at compile time using the builder pattern and lets user write their own agents (by subclassing) which they can plug where they want in the graph.
I wrote this system quite a while ago, and so far it has proven the test of time in terms of refactors and new engine needs.

Update: just added proper dummy workloads to the other two tokeniser threads as well (they throw away the output instead of propagating it through the pipeline, while the first tokeniser does pass it on). This got me a new record measurement of 7.635M LOC/s over the previous record of 7.444M LOC/s, or a 2.57% total program speedup (for a 12K LOC / 70 files compilation). So in total, I sped up my program's peak performance from 6.95M to 7.635M since yesterday, or a 9.9% total speedup. This matters less for large inputs, but becomes more dominant for small programs. And we can expect the same kind of performance gains for later compiler stages that are also using the pipeline pattern. Next, I will make it so that the tokeniser can pass batches of ~1024 tokens to the deduplicator, instead of having to fully process a file first. Both of these stages have the nice property that they work independently on single tokens, and they do not actually care about whether they have a complete file or not. The parser stage has to receive whole files, though, so some delay will still be there when encountering large files, but it should be halved, roughly.

antoine4 said:
The whole graph is wired at compile time using the builder pattern and lets user write their own agents (by subclassing) which they can plug where they want in the graph.

Does that mean you have a huge template construct that represents the whole graph? Or is it an in-memory data structure with virtual function calls?

antoine4 said:
I wrote this system quite a while ago, and so far it has proven the test of time in terms of refactors and new engine needs.

Sounds like a suitable design for something like an engine, where you have a host application that wants to own and customise everything. That's actually pretty cool, to make the entire threading behaviour customisable, because you don't want to impose any arbitrary design decision upon the host application.