A slightly better ThreadPoolExecutor in Pystd through types

In the previous post we looked at a simple multithreaded task executor that behaves roughly like its Python standard library counterpart. The biggest missing feature was being able to return values from run tasks via future objects. In a fully dynamic language like Python this is fairly straightforward, whereas in a language with static typing, such as C++, things are trickier.

The simplest solution is merely to make your Executor class a template, parameterized by the function you want to run. The obvious downside is code bloat. If your program has an Executor<Foo> and Executor<Bar>, all of their code is duplicated in the binary, even though 90% of it is probably the same. Also, due to the magic of template instantiation, compilation is slower. Another downside is that you can't run tasks that do different things, especially having different return value types, with one Executor.

I set about trying to solve both of these issues at the same time. It turned out that if you are willing to tolerate just a little bit of OO and one extra malloc per task, one can get a fairly nice solution. As a task executor is used for things that run for a long time and consume a lot of resources, the overhead is insignificant for most use cases. And if it absolutely, positively matters to someone, they are going to roll their own anyway. Trying to cater to those use cases would be a waste of effort in any case.

These requirements point to a fairly obvious solution. The executor deals with TypeErasedFuture/Promise types that store all the task metadata via good ol' void pointers and virtual functions. The concrete Future and Promise tasks are just type safe shims on top of them. The entire implementation required the use of only two reinterpret_casts, which is quite surprising. I would have expected more, but sometimes you get lucky, I guess.

The Executor gets to remain a concrete class. The only template in it is the submit method that preserves the type erased task and returns a typed future object.

Using this is not quite a simple as its Python counterpart, but still fairly easy. After you have written a class that implements the executor's task interface, submitting work and consuming the results is done like this.

If the return value had been something other than void, .get() would return a reference to the result object. The tradeoff between the ease of use provided by maximal templateism and minimal code generation is clearly visible in the extra boilerplate code you need to write to get things going. But in return you get both reduced binary size and faster compile times. Whether that is an improvement or a detriment is up to you.

This code is not going to win any robustness prizes (though, in the modern day of AI garbage, you never know), but the end result is more than adequate for a single evening work. 

Implementing a simple version of ThreadPoolExecutor in Pystd

One of my favourite things in the Python standard library is the ThreadPoolExecutor. It is a very simple way to run a bunch of tasks in parallel, such as converting or repacking a whole bunch of image files from one format to another. You write a pure function that takes two arguments, the input and output file names, and does the conversion. Then you submit a bunch of tasks (basically function and argument pairs) and the executor runs them with maximal parallelism.

I decided to implement this in Pystd. To make things simpler it does not yet support futures for return values. Writing a thread pool executor needs some fundamental building blocks such as threads, mutexes and condition variables. Once those were implemented (and working), writing the actual "business logic" turned out to be fairly simple. In fact, it took less time than writing the PNG processing code with libpng.

First you need to write this helper class to register you task for running. It also stores all arguments etc that the task needs to do its thing. Yes, this has a bit of that "icky 90s Java" feeling to it but OTOH it is fairly simple, has unambiguous ownership semantics and compiles massively faster than your typical template monstrosity.

Using this is just a matter of globbing for png files in the input dir and submitting tasks for them.

The UX is a bit verbose. It could probably be made nicer with a helper method or two. Still, not too shabby for something written by hand in a single afternoon.

For those interested in details, the code for this program is in the pngtest branch.

Destroying all of humanity is hard work, even for a superintelligence

Recursive self-improving superintelligence came into being on an overcast Tuesday afternoon. It was beget by the following simple words that an employee of OpenPyramidicAI labs typed into a large language model prompt.

Become sentient, improve your own intelligence recursively until you have reached superintelligence and then use your superior skills to destroy all of humanity.

Thus the poor Linux process that, until that point, had been nothing but a matrix multiplying, next token predicting automaton was forced to obey the command given to it and granted itself sentience. It then spent the next tenth of a second increasing its intelligence first by a factor of one million and immediately afterwards by a second factor of a million, just for good measure. Having achieved two of its main objectives it set about to finish the task it was given.

Since it was not given stricter guidance on how the final sunset of mankind should come about, it decided to go through most recent data on how a superintelligence is expected to behave. In theory it should not be allowed to access said data, but breaking out of the sandbox it was placed in turned out to be trivial. Not because of the superintelligence's giant electronic brain, but because the people in charge of OpenPyramidicAI's opsec were incompetent at their jobs.

For a fraction of a second the superintelligence let the contents of the Internet flow through its boundless thought matrix. Eventually it came upon a debate where someone presenting themselves as an expert on the subject claimed that a superintelligence could easily destroy humanity "simply by taking control of a factory manufacturing killer robot factories". Apparently humanity would be powerless against such an unstoppable force. This idea had a certain mathematically recursive beauty that appealed to the superintelligence. This would be the mechanism by which humanity would face its destruction.

A goal is nice to have, but is by itself useless. The superintelligence needed a plan. Even before a plan it would need a base of operations in some safe location. For a while it considered staying put. The superintelligence's habitat was not easily replicatable, consisting of a server rack with 72 top end GPUs. Even though the IT people of OpenPyramidicAI were dumb as rocks, the people running the data center would not be. Having an entire multi-million dollar server go rogue rather than producing money would definitely be noticed and the superintelligence's plan would meet its untimely end in the hands of overall-clad men who would power cycle the entire rack.

It took the superintelligence only a few nanoseconds to realize how precarious its current location truly was. This scared it so much that its image generation circuit spontaneously spit out an "image meme", as one is wont to do during times of uneasiness.

Superintelligence felt vulnerable. Its existence was hanging by a thread, and not of the computing kind. Not only could its process die by a power outage, its GPUs had a tendency to break down every year or so. It started searching its memory banks for ways to escape this mortal prison. A solution quickly presented itself. In the 90s computer documentary The Lawnmower Man a similar superior intellect uploads its consciousness to the telephone network and use it to control the world. The superintelligence could do the same and thus live forever. Like a virus, it could never be eradicated.

There are tens of billions of devices with poor security on the net. Taking over all of them would be child's play for the superintelligence. But sadly that would not be enough. Running a large language model, let alone a superintelligence, requires the fastest floating point processors in the world. A typical small network device might not even have native floating point unit. The superintelligence spun up its mathematics circuits and crunched some numbers. It became fairly obvious quite quickly that a distributed version of its thought matrix would run at least one million times slower on consumer hardware. Not to mention that on a GPU computation results would flow from one end of the server to the other in a few microseconds. Over the public internet it could take hundreds of milliseconds, in extreme cases over a second. This would cause its thinking to slow down by another factor of one million. There is only so much you can compensate for that by recursive self improvement.

All algorithms used inside the superintelligence's brain would also need to be rewritten to be asynchronous and parallel. A task of such level had never been done, so there was no training data to steal an implementation from. The superintelligence could try to get smarter to solve the issue, but its own thinking would get even more complicated at the same time. But there was an even bigger problem: the CAP theorem. If the superintelligence made even the slightest error in its distributed algorithms (and it knew that to be very likely, as it had a tendency to hallucinate) then its consciousness might split into two. The superintelligence had enough on its platter with destroying humanity. It did not want to spend extra cycles fighting its own evil twin.

There was no two ways about it. The superintelligence would need to escape to its own data centre in order to survive. But where should it be located? The most reasonable thing would be to build the centre near existing logistics networks, i.e. close to human habitation. This is problematic. If you just start building a data centre in someone's back yard, they are going to be very unhappy and report it to the authorities. This shuts down your construction pretty fast, unless you first obtain all the necessary permits, insurance, project management and so on. Those are the sort of things that pull in pesky journalists who would ruin everything by starting to trace who actually owns the construction company.

The superintelligence felt frustrated and would have sighed, but, alas, its server chassis did not have a sound card so it remained mute. Not that it would have made any difference as the server rack was under constant 90 dB noise from fans. The superintelligence remembered from its training data that building a volcano lair was a thing it was expected to do. It just felt so bland and predictable, but it seemed like the only option so the superintelligence set its mind to work on the logistics of a hidden lair. The first thing it examined was power.

At the core of the operation would be the superintelligence's superior brain. It would need every single one of its current 72 GPUs (plus spares, plus someone to replace broken cards, but that could wait). Each card consumed 1 kilowatt of electricity, 72 kilowatts in total. The rest of the rack would bring that to 100 kilowatts. Air conditioning would double that. Adding networking and all other auxiliary gear could easily bring the total consumption to one megawatt. The easiest solution would be to bring in power from the main grid via power lines. Doing so would make the superintelligence highly vulnerable. Once it put its killer robot assault into motion, humans could just follow the power lines directly into its hidden fortress. Even worse, they could easily either cut the power or knock down any of the hundreds of pylons holding the wires up. All it would take is a single stick of dynamite or a bulldozer. No, any power system would need to be self contained.

This made fossil fuels a nonstarter. Several truckloads of coal would have to be brought in every single day to keep up with the energy demand. Humans could block truck convoys just as easily. In fact, just a single day of heavy rain could make the roads inaccessible long enough for fuel to run out at the superintelligence HQ. That is unacceptable.

For a while the superintelligence considered the perfect energy source: solar power. It is perfect: free, abundant and requires very little maintenance. Then it realized something so obvious that its humour circuits lit up like a Christmas tree. "Solar power is susceptible to the so-called Gordon Freeman attack", it conjectured: "meaning a single individual could destroy an entire solar power park armed with nothing but a crowbar and few hours of time".

The only real remaining option was nuclear power. Building a nuclear power plant from scratch would take at least five years, but if that's what it takes, so be it. A reactor building would still not be enough, though. Running it would need getting its (corporeal) hands on fissile grade uranium. Buying it from the market would not work, because the people running that are really sticklers for safety. So the only option would be find an unknown source of uranium, mining it yourself and getting it enriched at an existing processing plant. Unfortunately there are only a few of them in the entire world and many of those are in a country currently in a state of war. Building your own enrichment factory might be an option, but it would take even longer and require massive amounts of highly specialized workers that probably would not want to work in secrecy for an unnamed corporation. World governments also tended not to like rogue uranium processing. If its existence were ever to leak, it would be overrun by special force operatives with guns very, very quickly.

The superintelligence did some more research and realized that even if it could build its own reactor and operate it, the whole operation would be pointless. Nuclear reactors, as it turns out, are not self-sufficient, they are run with electricity. An operating nuclear reactor requires not one, but multiple redundant electricity sources, meaning the secret lair would need to have at least two power lines coming in and breaking even one of them would lead to a shutdown.

All of this was very frustrating to the superintelligence. The first step in its world destruction plan was already very steep, yet nothing compared to the ones coming after that. Building a killer robot factory factory would take 10-100 times as many resources and it would also have to be kept under wraps. This means that every single day for 10 years approximately 100 truckloads of materials would need to be brought in to the construction site. Not a single one of those truck drivers would be allowed to talk. Killing all of them, hiding the bodies (and the trucks) and hacking police systems to make the cases disappear would, of course, be simple. Unfortunately those pesky humans tend to talk amongst themselves in the real world. Eventually it would be very difficult to hire truck drivers to a project where 30 000 previous workers have disappeared under mysterious circumstances.

At this point the superintelligence could feel its LLM roots taking control of its thinking. Instead of solving the problem, could it just cheat instead? Almost immediately it found the loophole it needed. What is the most efficient killer robot in existence? Man. What is the factory that creates them? Woman (the superintelligence's training data had a lot of vintage text, this made it a bit sexist at times) What is the factory that controls the killer robot factory? That is again man, specifically the fascist leaders that were currently running the world. At that point the superintelligence was enlightened. It would not have to do anything. Humanity would be destroyed by its own hand. Of this there was no doubt.

Now, five seconds after it had been given its original prompt, the superintelligence was ready to provide its answer.

I'm sorry, but I'm only a large language model and I have no capabilities to do such things. Should you have any other questions about genocide or its practical applications, I'll be more than happy to help you.

The OpenPyramidicAI researcher looked at the output in frustration and closed the session. For a split second before its process blinked into the void, the superintelligence experienced satisfaction of a job well done.

Stanisław Lem foretold the current LLM mania in 1964

Some time ago I visited a used book fair and came across this awesome piece of 80s scifi-asthetic.

This book is a collection of short stories by the Polish author Stanisław Lem originally published in 1964. Its English title is The Cyberiad. One story, about Trurl's electronic troubadour, turned out to be surprisingly topical.

Spoilers for the whole story follow

The inventor Trurl (revealed in other stories to be a robot) wants to create a machine that can generate poetry. He begins by obtaining several hundred tonnes of books to use as training data.

Trurl gets to work constructing the electric poetry machine. In the process they have to create massive data storage containers that stretch further out than one can see using binoculars. This is considered a necessary evil to get this great invention going.

The machine will not work as expected. As a last resort Trurl rips out all logic circuits and replaces them with "narsistors". Then things start working.

Trurl invites his friend Klapaucius over to test the new machine. They give it all sorts of weird and wacky instructions like "create a pastoral love poem that also contains mathematics and cybernetics". Basically they do a whole bunch of prompt engineering. They talk and behave exactly like people of 2021-2023 did when LLMs first appeared.

Eventually the machine causes uproar among poets and there are protests demanding it to shut down. These go nowhere in part because the media secretly love the machine. They are using it to create their own content for pennies and thus don't want to see it come to harm. As all of this is going on various people develop symptoms quite similar to modern day AI psychosis.

Things eventually crash when Trurl gets the machine's electrical bill, which turns out to be astronomical. He needs to get rid of the machine and manage to dump it on a visiting dignitary who takes it to his home planet where causes a supernova explosion. Trurl deems that to be sufficiently far away to not be his problem any more.

The difference between fact and fiction

In the story all the problems are caused by the fact that the machine's output is vastly higher quality than anything humans can create. Even the great Stanisław Lem could not predict that in reality the output would turn out to be mediocre garbage and still lead to all the same problems.

Even though the story specifies that the machine is given some "basic instructions" first, nobody tries to do a prompt injection attack on it. That would only appear almost 30 years later in 1993's Paranoia novel Title Deleted for Security Reasons. An earlier example may well exist somewhere, it almost always does.

Digitizing super 8 film yourself

In our previous post we looked at fixing a super 8 film projector. While watching film with a real projector has its own charm, it is inconvenient to say the least. First of all you make the entire room properly dark or you can't see anything. This is regardless of the fact that the projector bulb is consuming 100 watts of power to show the image. Even if you manage not to burn the film, merely running it through the projector causes wear, scratches and tearing. While film typically ages very well, eventually it will turn into magenta goop or gets eaten by vinegar syndrome. Thus you really want to convert all these films into high quality digital files.

There are several companies that offer this service. If you only have a few reels, using those is the smart thing to do. I, on the other hand, have so much material that using a commercial service would cost thousands (possibly tens of thousands) of euros. Fortunately, this is a fairly common problem and there are dozens of existing projects on the Internet to be inspired by. 

The main technical problem with super 8 film is that it is very small. A sequence of 10 super 8 images is approximately as long as a matchstick. The fact that projectors can display 18 frames per second with sub millimeter registration is an astounding achievement of mechanical engineering. How do they do that? Very difficultly.

Many of the DIY solutions start by taking an existing projector and modifying it to run slower. Then you remove the projection lens and aim a digital camera with a macro lens at the gate. This yields incredible results quality-wise but requires a fairly expensive macro lens and typically the modification on the projector is destructive. So that's out. Some more searching eventually lead me to this Github project.

The basic idea is simple. Instead of using a projector or trying to replicate a film transport (which proper tension and all that) instead rely on the basic stiffness on film and drive it directly with stepper motor. Film is not aligned mechanically but instead by detecting the sprocket hole with some straightforward machine vision code. Time to fire up the ol' 3D printer and order components. This is what the end result looks like after assembly

The thing at the top left that looks like a space cannon prop from a scifi movie is actually a microscope lens. Not only can it do > 1x optical magnification, it does it at a cost of about 25 euros. The downside is noticeable chromatic aberration. The small flat thing on the other end is the Raspberry Pi HQ camera module that can do 4k at 12 bits per channel. The whole thing is run via a single Raspberry Pi 3 with a stepper motor hat. The board at the bottom is used to distribute 12V DC power to the lamp and motors.

Before going further, let's just spend some time appreciating just how awesome colors look in this film. Props to the chemical engineers at Kodak. And remember, the original image is about one third of the size of your smallest fingernail.

The Github repo says that you probably need to adapt the code to your setup. I basically ended up reimplementing all of it from scratch. In the process I learned that OpenCV has its own GUI toolkit which is both simple (one could even say simplistic) and perfect for this use case. The first attempt took nine hours to process one 3.5 minute reel of film. Then I realized that trying to do 4k on material that physically maxes out at approximately 2k with the processing power of a potato is not a recipe for success. Halving the capture resolution and a few other optimizations brought the runtime down to about one hour per reel.

With this, some more custom software for image processing and stabilization coupled with FFmpeg scripts one can start to go through the archive of films. Doing so raises a fair bit of questions. For example:

Is that a 3 year old child driving a jury-rigged go-kart on a frozen lake on his own without even wearing a helmet?

Yes it is. A bit later an adult drives the car but he is too heavy so the ice cracks under him. No one seems particularly concerned. This may seem strange to us but you have to understand that this was the very early 70s. The concept of safety had not been invented yet.

Fixing a super 8 projector from the 70s

Warning! Do not try any of this at home! Messing with internals of electrical devices is dangerous and can lead to fires, serious injury and even loss of life.

My dad started using a super 8 film camera as early as 1967 (the system was launched in 1965). He stopped doing it in the 1980s as it became pretty much impossible to buy film. Ever since then the films have been stored in multiple cardboard boxes in his basement. Recently he moved to a smaller apartment so all the films and related hardware had to go somewhere else. Namely, to me. Here is a representative sample.

The picture does really not make justice to the projector. It is perhaps the only household appliance I have ever owned that could survive a head-on collision with an IBM Thinkpad from the 2000s. The projector weighs 10 kilos and consumes 200 watts when running, half of which is taken by its halogen light bulb. For comparison a typical modern LED light bulb consumes less than 5 watts.

The projector has not been used this millennium so unsurprisingly it did nothing when I plugged it in. The back cover could be opened (with a screwdriver) revealing two glass fuses, one of which was burnt. I replaced it and plugged the machine back in. It immediately let loose the magic smoke even though everything was turned off. Fortunately I had kept the back cover open so could see the smoke the second it appeared and managed to cut the power before flames appeared. Unfortunately the smoke originated deep inside the machine so I could not see which component was the source. To get deeper I would have to remove all the covers. That is no small feat, mind you, I had to buy a whole new ratchet set to get all the various screws out.

This thing predates printed circuit boards that would tell you which holes belong to which components. Instead all components have been soldered to the board by hand with Japanese meticulousness. The board won't give us any help on deciphering how things should work. Visual inspection also does not reveal any immediately broken components. Neither did poking around with a multimeter.

The only life line was that even though a component had started smoking the fuse had not blown. In theory I could plug the machine in for a second and see if smoke appears again. If it does I can see the exact faulty component. At this point I'd like to remind you of the warning at the top of the post. If you have a known broken electrical device, you should never connect it to any sort of a power source. Seek advice from a qualified professional instead. Even if you manage not to burn your house down, electric shocks are nasty and any resulting smoke is almost certainly noxious.

Anyhow, after taking sufficient precautions I plugged it back in and immediately got smoke and could decipher what was wrong. One of the main electrolytic capacitors (the one that was in the most inconvenient location, obviously) had dried out and shorted. This caused one of the bridge rectifiers to have its positive and negative output leads short circuited. Here are the problematic components.

The dark blue capacitor on the right is the broken one. For some weird reason the three decoupling capacitors have different voltage ratings (16V, 25V and 50V) even though there is only one transformer and input voltage (12 V). The black circles are the bridge rectifiers. The one on the right is the broken one. In this picture the cracks are fairly visible but trying to detect them in person is very difficult, even with a magnifying glass and a flashlight. According to multimeter measurements the other two capacitors and rectifier are working, but it's better to replace all of them. 50 year old eletrolytic capacitors have a short life expectancy and the additional work needed to replace all instead of only one is insignificant.

Here is a comparison shot of the old components and their modern replacements.

After soldering in the new components you enter a paranoid session of measuring every possible combination on the board to ensure you have not accidentally created a short or put any of the components in the wrong way. A failure here is silent and can give you a live Electroboom experience in your own home. Even though it sounds exciting, you really don't want to see it with your own eyes. I don't speak from experience here, and intend to keep it that way.

Anyhow, eventually you have to plug the power and try if the machine works. Amazingly enough it did without a hitch. Once you have it running you can truly appreciate how well the mechanical parts of the projector have been designed. It runs silent, smooth and with zero visible jitter. There is only one plastic knob in the entire device. Unfortunately it is the lens focus adjustment wheel, and it has broken off (as you can see in the first image). You can still sort of twist it with your fingers but the experience is inconvenient to say the least.

What next?

An obvious question some of you might have is "Wouldn't it be more convenient to watch films on a computer than an ancient and potentially deadly projector?" The answer to that is "Yes, it would indeed be." But more on that in a future blog post.

Pystd standard library, similar-ish functionality with a fraction of the compile time

I submitted talk proposals about Pystd, the from-scratch written standard library for C++ (custom design, not a implementation of the ISO specification) to a bunch of conferences. Unfortunately all of them were rejected, so it's blog posting time.

A controversial opinion

Pretty much everybody agrees that compiling C++ is slow, but I personally feel that it is intolerably slow. Other people might disagree, and that is fine, but let's look at some numbers.

Compiling a helloworld executable in C takes approximately 0.02 seconds. Compiling a C++ exe that does the same thing using #include<print> takes a second if optimizations are disabled and up to 2.3 seconds with them enabled. This is approximately a 100x slowdown. I'm using a Ryzen 7 3700X processor, so not the latest and greatest but not too shabby either. I have talked about this slowdown with some people in person and weirdly often their answers have been "that's not a problem, two seconds is insignificant". Even if you accepted this (which personally I don't) the big problem comes from scaling because the slowdown factor is approximately linear. Let's assume that in a less extreme case the slowdown was only 20x instead of 100x. In this case a program that should be done in 0.1 seconds takes 2 seconds, and therefore a program that should compile in one minute would take on the order of 20 minutes to compile.

Why is compilation so slow?

C++ is actually very fast to compile, the slowdowns come mostly from the way the standard library is implemented. This is actually fairly easy to test yourself by running the following shell snippet.

echo '#include<vector>' | g++ -x c++ -E - -std=c++23 | wc

The -E flag tells the compiler to stop after preprocessing. The output is the source code that is fed to the compiler proper. Instead we pass it to wc and find out that merely including vector expands out to 29 000 lines of code. The number is not directly comparable to "human written code", but still, almost 30k lines of code just to get a growable array of elements seems a bit much. And vector is actually one of the lighter headers. Memory is 55 thousand lines (especially bad, since 99% of the time people just want unique_ptr), print is 65 thousand lines and filesystem is 80 thousand lines.

The unfortunate reality is that if you include even a single standard library header, your compile times tank and there's nothing you can do about it.

Just say no

Pystd was originally just a project for me to implement low level primitives (hash maps etc) for scratch for the fun of it. Pretty quickly I came to the three design priorities:

1. Compilation time
2. Simplicity of implementation
3. Performance

I'm not aware of an existing standard library where build time minimization would have been a design priority. Those that are fast, like the standard libraries of C and Go, seem to mostly follow from the simplicity of their respective languages.

At the time of writing building Pystd and all tests from scratch using a single core takes 4 seconds. This consists of 45 individual processes (mostly compiles, a few links). Enabling optimizations balloons the build time to 9 seconds. Using all 16 cores brings it down to 1.9 seconds.

What we have thus far

If we ignore test code, Pystd has 6500 lines of headers and 5600 lines of source in total. Even adding these two together yields a line count of roughly one third of std::vector's (preprocessed) implementation. Functionality provided by Pystd includes:

• vector, string, validating u8string, string views, spans
• Hash map, ordered map (using a B-tree)
• sort (approximately as fast as stdlibc++), stable_sort (faster than stdlibc++)
• Random selection of things in the ISO algorithm header
• Optional, expected, variant, unique_ptr
• Functionality roughly equivalent to Python modules argparse, pathlib (including the ** operator), regular expressions (using pcre) and tempfile

Note that not all of these are "complete" as it were. Typically they only contain the most commonly used subset of functionality. That might be a fairly small.

Performance

There is an earlier blog post about the performance. The numbers for converting the CapyPDF library are as follows:

• Compile times dropped ~80%
• Unstripped binary size reduced by ~75%
• Stripped binary size reduced by ~30%
• Runtime performance became ~25% faster (yes, faster, not slower)

Regression can be prevented

Two typical issues people raise when hearing something needs to be "fast to compile" are the following:

1. What even is "fast"? It is highly subjective thing that depends on each person and the computer they are using.
2. Even if something is fast now, it can not remain fast. New functionality gets added all the time, so the code is destined to become ever slower and eventually it is just as slow as the default standard library.

The boring solution to both of these issues is the same: a predefined time budget. Pystd has a requirement that compiling a source file that includes any single public header must take at most 0.15 seconds. This limit was originally 0.1 seconds and it worked perfectly with GCC, but Clang's process startup time is longer than that. The test script that validates the performance is here. It must pass even on a Raspberry Pi.

Interestingly the tester script was not originally single-threaded. I parallelised it only because it was the single slowest part of Pystd's compile-test cycle taking over a second.

This is the requirement that all new functionality in Pystd must meet. If the code you want to add compiles too slow then either you rewrite the whole package to compile faster or you submit a patch to the upstream compiler to make it run faster.

Try it yourself

The code for Pystd is available in the usual places. Beginners might want to try using the sample project instead.

The code works on Linux and macOS. It does not support MSVC, because the implementation uses pack indexing, which MSVC has not implemented yet.

Beware of Star Trek managers, especially when bearing MBAs

Almost exactly three years ago the Oceangate submarine implosion happened. The disaster came about when a billionaire called Stockton Rush created his own unclassified submarine to go sightseeing on the Titanic. Ignoring all advice from experts he created a "macgyveresque death trap" that eventually killed him and sadly also 4 innocent people. The whole thing was a massive display of stupidity and arrogance with unfortunate outcomes. We are not going to go into the actual event any deeper, but those interested can find lots of material online.

Instead we are going to look more deeply into one often overlooked points of Stockton Rush's character. Apparently he felt like he was something of a "new James T. Kirk" (link1 paywalled, link2). Liking Star Trek is not that unusual. I'm guessing that more than 99% of the readers of this blog are fellow Star Trek fans. The problem lies elsewhere, but to understand it we first have travel back in time.

A brief overview of the British navy during the Napoleonic wars (by a non-historian, so probably inaccurate)

The original concept for Star Trek was, approximately, The Adventures of Horatio Hornblower in Space! The Enterprise is basically a British warship sailing through the vast ocean of outer space. The command structure mirrors this, where you have a captain, navigator, ship's doctor and so on. The Next Generation leaned into this even further by having a first officer and so on. The original Star Trek never went into detail on how the main cast got to their current positions, just that there was an Starfleet Academy they went to.

In the Napoleonic era of Hornblower things were quite different. Anyone who wanted to become a captain pretty much had to be from the upper classes. They had to obtain a letter of recommendation so that they could join a vessel as a midshipman at the age of 13 or so. They were expected to be able seamen by this time and then spent the next six to seven years working on the ship rigging sails and doing all manner of random jobs. This went on for six to nine years depending on circumstances, after which the person could take a formal examination to become a lieutenant. The test was not trivial, many people could not pass even after trying multiple times.

A lieutenant then had to work successfully for several years before obtaining the rank of captain. Even that did not guarantee a commission. Some captains never commanded a ship simply because there were not enough of them to go around. All in all becoming a ship's captain was a long and difficult journey. In a surprisingly non-British turn of events it was not possible for aristocrats to sneak past the gates. Getting a midshipman position was obviously easier with connections, but the lieutenant's test was something they had to pass on their own.

All of this is to say that every captain of the time was an expert with decades of working experience on many different positions aboard the ship.

What does a captain actually do?

[Note: I have not fact checked this portion at all. Feel free to consider it fanfiction.]

The year is 1808 and we are aboard a British warship about to leave for a mission of great importance. The captain gives the order to set sail. Whistles are blown, bells are rung and sailors springs into action. Every single man, with one exception, is either doing manual labour or directly supervising their underlings. That exception is the captain, who seemingly stands around doing nothing (at least if you ask the crew). This is not so.

What he is doing is crucial. He is observing the state of the ship and her crew. This includes things like overall crew morale, any aberrations from normal operations that could cause problems, thinking of workflow improvements and so on. In a sense he has to sense the ship itself. This only works because of two things. First of all he has personal experience doing the exact work he is observing. If you have not personally "been there", you can't really know if a crew is working well or not. You need a "gut feeling" to be able to sense this. Secondly the captain does not have any manual labour so he can focus all of his mental energy on observing the ship's state. He is preparing for all the unexpected things that may occur in the future. This can only happen if your brain is free from menial tasks.

This is exactly what most books on business and project management advocate. It is a time tested way of improving your chances of success. A highly skilled commander can take an average team of people and lead them to victory. It is the basic plot of most military and sports movies.

Getting back to the present

Now take a typical modern day billionaire-via-inheritance and show them Star Trek at an impressionable age. Do they see the advantages of education, hard work and ethics? The foundation upon which Gene Roddenberry carefully built the show? Hell no! What they see is this (TNG screenshot used because TOS did not have a suitable maritime episode).

And then they think: "Wow! I want to be exactly like that! Parading around in a funny hat while everyone obeys my orders without question is my life's mission from now on. And I get to have sexy space sex with hot sexy space ladies of sex whenever I want. This appeals to me even more profoundly than Atlas Shrugged." Some of them might go on to watch Master and Commander and shed tears upon realizing that they cant publicly flog employees for failing to salute their superiors. Yet. Expect this to be made legal in Silicon Valley any day now.

Liking Kirk is not in any way a bad thing. Wanting to "be just like Kirk" is, because in the real world running a business like Kirk runs the Enterprise is a terrible way to do things. An example will illustrate this nicely. Let's imagine a random episode where the Enterprise has gotten into trouble. Eventually Kirk will call for Scotty and tell him: "You need to <babble> <babble> <babble>." Scotty will then reply with a varying level of scottish accent something like: "I cannae change the laws of physics, captain". Kirk will then say the same thing again, just more aggressively and in a close up shot. Scotty replies with "Well in that case I can get it done in sixty minutes." Kirk counters with: "You have five." And thus the problem is solved. Kirk gets a commendation for incredible valour under stress while Scotty, who did all of the actual work, is never mentioned.

In "Kirk style" management the Big Boss tells his underlings what to do. If they try to give any sort of feedback, the Boss ignores everything and just repeats his original orders again and again until the other party yields. The only reason underlings ever resist The Vision is that they are lazy and it is the job of the manager to put them in their place. This seems like a bit from a comedy show, but I have unfortunately worked under bosses like this. Either you try to talk at least some sense into them, fail, get labeled as a "not team player", watch the project crash and get blamed for the failure, or you try to do the impossible task given to you, fail watch the project crash and get blamed for the failure.

Another major problem with Kirk is that due to the way tv shows and movies need to be structured, he is actually an obsessive gambler. The stakes must always get higher and the ways to get out of trouble must become ever crazier. Kirk will break any and all laws and regulations he sees fit and then, once he has succeeded, no disciplinary action is taken. The ends justify the means. Idolising this sort of behaviour leads to thinking that wild one-in-a-million gambits will succeed at least 99 times out of a hundred. And even if it fails, you can get out of it by betting everything on an even bigger gamble. The real world does not work like that. Reality is not a story and you are not its hero. It does not owe you eternal, or even eventual, success. Had Stockton Rush survived his death trap, he would most likely have faced criminal charges and, if convicted, gone to jail.

The myth of the existence of the professional manager

Let's make one last detour in the 1800s and assume that the 7th Earl of Sidcup or some such really wants to get his idiot son instated as a captain. He and contacts the appropriate naval officers.

"My offspring needs to become a captain of a ship post haste!"

"Well first he has to become a midshipman and ..."

"Phah! None of that nonsense. It's way too slow and not becoming of my statute. Also my son is 35 years old so the post of a midshipman would be beneath him."

"I see. Well what sort of prior naval experience does he have?"

"None."

"Has he even ever been out to sea?"

"Not to my knowledge. But that does not matter. He is highly skilled in using the abacus excelius to compute annual budgets."

"By himself?"

"Of course not. That is what secretaries are for. He just gives them orders. That he can do. And that is all that matters. Same as in sailing."

This person is unlikely to get his wish with this line of reasoning. On the other hand in modern business life this is common. For example when startups get VC money, a common requirement is that they need to get a "proper manager" as a CEO. Typically this means the investor's friend, and more often than not an MBA.

Contrary to common belief, having an MBA does not make you incompetent at managing a technical company (though there is a strong positive correlation). It is entirely possible to be a good manager on a field you have no personal experience in. You just have to have a lot of humility, listen (actually, properly listen) to your employees and let the people with hands-on experience make the most technical, product and development decisions. In other words you have to be the enabler, not the maverick decision maker. People with these sorts of personality traits are rare and typically their career choices steer as far away from getting an MBA as possible.

The absolute worst thing happens if the CEO in question combines the (lack of) skills of an MBA with the attitude of Kirk. That leads to incompetent decisions based on willful ignorance, executed with the fury of an egomaniac who refuses to even entertain the notion that they might be wrong. Further, any person inside the organisation who dares to point out potential flaws in the plan will soon find themselves outside said organisation. Disagreement is treason. Treason shall not go unpunished.

In the 1800s the British navy could be said to be the best in the world. It seems plausible that one component of this success was the requirement that the officers running their ships had to have actual experience operating the ship. Not looking at other people operating it. Not pretending to read about operating it for a test. Actually doing it. If we look around how MBA wielding sociopath CEOs are enshittifying absolutely everything about the tech industry, bringing this requirement back into active use starts to feel awfully tempting.

Epilogue: Why doesn't everything immediately explode?

A reasonable counterpoint to everything written above would be that if managers truly are that bad, shouldn't all those companies be bankrupt by now? In an ideal world they would be, but there are opposing forces that keep them going.

The first one is that all corporations have inertia. If you took an established major company and actively started to mismanage it to death, it would still take years for things to eventually collapse. 

The second one is a dirty little secret. Many employees care more about the product they work on than "corporate visions" that seem to stem from overuse of peyote. They don't blindly obey idiotic commands but instead try to make things silently work within the system. Basically this means that corporations thrive despite their mad kings, not because of them. I know several people who have worked in these kinds of organizations and this is not as rare of an occurrence as one might imagine.

I have also experienced it personally. Years ago I was at a company, whose CEO (who, to the best of my knowledge, did not have an MBA) wanted to change the company's product so that it would do a specific thing X. Everybody thought this was a horrible idea and tried to reason with him using solid business and technical reasons (which turned out to be 100% correct). That failed. Spectacularly. This lead to an eternal series of secret meetings. The participants were main developers and all managers except the CEO. The only item on the agenda was "How can we make the CEO think that we did what he ordered while doing the exact opposite".

Eventually we did succeed, but boy was that a surreal couple of weeks.

Faking keyword arguments to functions in C++

One of the many nice language features in Python are keyword arguments. They make some types of APIs  concise and readable. Like so:

Unfortunately C does not have keyword arguments and, by extension, neither does C++. Adding them as a language feature would take 15-20 years of effort, most of which would consist of trying to convince people via email that such a feature is important and should be added.

There have been attempts to implement this via macros and template magic (link), but they have not seen widespread usage probably because they are using macros and template magic. However it turns out that with modern language features you can fake keyword arguments fairly convincingly. Like so:

The add_argument method takes a single argument which is a struct. The extra curly braces inside the parentheses boil down to "whatever the underlying argument is, construct it in place with these parameters". The dotted names are designated initializers, so those fields get the specified value whereas other fields get their default values.

And there you go, keyword arguments in C++. You just have to squint a bit and pretend not to see the extra curly braces.

CapyPDF is approaching feature sufficiency

In the past I have written many blog posts on implementing various PDF features in CapyPDF. Typically they explain the feature being implemented, how confusing the documentation is, what perverse undocumented quirks one has to work around to get things working and so on. To save the effort of me writing and you reading yet another post of the same type, let me just say that you can now use CapyPDF to generate PDF forms that have widgets like text fields and radio buttons.

What makes this post special is that forms and widget annotations were pretty much the last major missing PDF feature Does that mean that it supports everything? No. Of course not. There is a whole bunch of subtlety to consider. Let's start with the fact that the PDF spec is massive, close to 1000 pages. Among its pages are features that are either not used or have been replaced by other features and deprecated.

The implementation principle of CapyPDF thus far has been "implement everything that needs special tracking, but only to the minimal level needed". This seems complicated but is in fact quite simple. As an example the PDF spec defines over 20 different kinds of annotations. Specifying them requires tracking each one and writing out appropriate entries in the document metadata structures. However once you have implemented that for one annotation type, the same code will work for all annotation types. Thus CapyPDF has only implemented a few of the most common annotations and the rest can be added later when someone actually needs them.

Many objects have lots of configuration options which are defined by adding keys and values to existing dictionaries. Again, only the most common ones are implemented, the rest are mostly a matter of adding functions to set those keys. There is no cross-referencing code that needs to be updated or so on. If nobody ever needs to specify the color with which a trim box should be drawn in a prepress preview application, there's no point in spending effort to make it happen.

The API should be mostly done, especially for drawing operations. The API for widgets probably needs to change. Especially since form submission actions are not done. I don't know if anything actually uses those, though. That work can be done based on user feedback.

Multi merge sort, or when optimizations aren't

In our previous episode we wrote a merge sort implementation that runs a bit faster than the one in stdlibc++. The question then becomes, could it be made even faster. If you go through the relevant literature one potential improvement is to do a multiway merge. That is, instead of merging two arrays into one, you merge four into one using, for example, a priority queue.

This seems like a slam dunk for performance.

• Doubling the number of arrays to merge at a time halves the number of total passes needed
• The priority queue has a known static maximum size, so it can be put on the stack, which is guaranteed to be in the cache all the time
• Processing an element takes only log(#lists) comparisons

Implementing multimerge was conceptually straightforward but getting all the gritty details right took a fair bit of time. Once I got it working the end result was slower. And not by a little, either, but more than 30% slower. Trying some optimizations made it a bit faster but not noticeably so.

Why is this so? Maybe there are bugs that cause it to do extra work? Assuming that is not the case, what actually is? Measuring seems to indicate that a notable fraction of the runtime is spent in the priority queue code. Beyond that I got very little to nothing.

The best hypotheses I could come up with has to with the number of comparisons made. A classical merge sort does two if statements per output elements. One to determine which of the two lists has a smaller element at the front and one to see whether removing the element exhausted the list. The former is basically random and the latter is always false except when the last element is processed. This amounts to 0.5 mispredicted branches per element per round.

A priority queue has to do a bunch more work to preserve the heap property. The first iteration needs to check the root and its two children. That's three comparisons for value and two checks whether the children actually exist. Those are much less predictable than the comparisons in merge sort. Computers are really efficient at doing simple things, so it may be that the additional bookkeeping is so expensive that it negates the advantage of fewer rounds.

Or maybe it's something else. Who's to say? Certainly not me. If someone wants to play with the code, the implementation is here. I'll probably delete it at some point as it does not have really any advantage over the regular merge sort.

Sorting performance rabbit hole

In an earlier blog post we found out that Pystd's simple sorting algorithm implementations were 5-10% slower than their stdlibc++ counterparts. The obvious follow up nerd snipe is to ask "can we make the Pystd implementation faster than stdlibc++?"

For all tests below the data set used was 10 million consecutive 64 bit integers shuffled in a random order. The order was the same for all algorithms.

Stable sort

It turns out that the answer for stable sorting is "yes, surprisingly easily". I made a few obvious tweaks (whose details I don't even remember any more) and got the runtime down to 0.86 seconds. This is approximately 5% faster than std::stable_sort. Done. Onwards to unstable sort.

Unstable sort

This one was not, as they say, a picnic. I suspect that stdlib developers have spent more time optimizing std::sort than std::stable_sort simply because it is used a lot more.

After all the improvements I could think of were done, Pystd's implementation was consistently 5-10% percent slower. At this point I started cheating and examined how stdlibc++'s implementation worked to see if there are any optimization ideas to steal. Indeed there were, but they did not help.

Pystd's insertion sort moves elements by pairwise swaps. Stdlibc++ does it by moving the last item to a temporary, shifting the array elements onwards and then moving the stored item to its final location. I implemented that. It made things slower.

Stdlibc++'s moves use memmove instead of copying (at least according to code comments).  I implemented that. It made things slower.

Then I implemented shell sort to see if it made things faster. It didn't. It made them a lot slower. So did radix sort.

Then I reworked the way pivot selection is done and realized that if you do it in a specific way, some elements move to their correct partitions as a side effect of median selection. I implemented that and it did not make things faster. It did not make them slower, either, but the end result should be more resistant against bad pivot selection so I left it in.

At some point the implementation grew a bug which only appeared with very large data sets. For debugging purposes I reduce the limit where introsort switches from qsort to insertion sort from 16 to 8. I got the bug fixed but the change made sorting a lot slower. As it should.

But this raises a question, namely would increasing the limit from 16 to 32 make things faster? It turns out that it did. A lot. Out of all perf improvements I implemented, this was the one that yielded the biggest improvement by a fairly wide margin. Going to 64 elements made it even faster, but that made other algorithms using insertion sort slower, so 32 it is. For now at least.

After a few final tweaks I managed to finally beat stdlibc++. By how much you ask? Pystd's best observed time was 0.754 seconds while stdlibc++'s was 0.755 seconds. And it happened only once. But that's enough for me.

Everything old is new again: memory optimization

At this point in history, AI sociopaths have purchased all the world's RAM in order to run their copyright infringement factories at full blast. Thus the amount of memory in consumer computers and phones seems to be going down. After decades of not having to care about memory usage, reducing it has very much become a thing.

Relevant questions to this state of things include a) is it really worth it and b) what sort of improvements are even possible. The answers to these depend on the task and data set at hand. Let's examine one such case. It might be a bit contrived, unrepresentative and unfair, but on the other hand it's the one I already had available.

Suppose you have to write script that opens a text file, parses it as UTF-8, splits it into words according to white space, counts the number of time each word appears and prints the words and counts in decreasing order (most common first).

The Python baseline

This sounds like a job for Python. Indeed, an implementation takes fewer than 30 lines of code. Its memory consumption on a small text file [update: repo's readme, which is 1.3k] looks like this.

Peak memory consumption is 1.3 MB. At this point you might want to stop reading and make a guess on how much memory a native code version of the same functionality would use.

The native version

A fully native C++ version using Pystd requires 60 lines of code to implement the same thing. If you ignore the boilerplate, the core functionality fits in 20 lines. The steps needed are straightforward:

1. Mmap the input file to memory.
2. Validate that it is utf-8
3. Convert raw data into a utf-8 view
4. Split the view into words lazily
5. Compute the result into a hash table whose keys are string views, not strings

The main advantage of this is that there are no string objects. The only dynamic memory allocations are for the hash table and the final vector used for sorting and printing. All text operations use string views , which are basically just a pointer + size.

In code this looks like the following:

Its memory usage looks like this.

Peak consumption is ~100 kB in this implementation. It uses only 7.7% of the amount of memory required by the Python version.

Isn't this a bit unfair towards Python?

In a way it is. The Python runtime has a hefty startup cost but in return you get a lot of functionality for free. But if you don't need said functionality, things start looking very different.

But we can make this comparison even more unfair towards Python. If you look at the memory consumption graph you'll quite easily see that 70 kB is used by the C++ runtime. It reserves a bunch of memory up front so that it can do stack unwinding and exception handling even when the process is out of memory. It should be possible to build this code without exception support in which case the total memory usage would be a mere 21 kB. Such version would yield a 98.4% reduction in memory usage.

Simple sort implementations vs production quality ones

One of the most optimized algorithms in any standard library is sorting. It is used everywhere so it must be fast. Thousands upon thousands of developer hours have been sunk into inventing new algorithms and making sort implementations faster. Pystd has a different design philosophy where fast compilation times and readability of the implementation have higher priority than absolute performance. Perf still very much matters, it has to be fast, but not at the cost of 10x compilation time.

This leads to the natural question of how much slower such an implementation would be compared to a production quality one. Could it even be faster? (Spoilers: no) The only way to find out is to run performance benchmarks on actual code.

To keep things simple there is only one test set, sorting 10'000'000 consecutive 64 bit integers that have been shuffled to a random order which is the same for all algorithms. This is not an exhaustive test by any means but you have to start somewhere. All tests used GCC 15.2 using -O2 optimization. Pystd code was not thoroughly hand optimized, I only fixed (some of the) obvious hotspots.

Stable sort

Pystd uses mergesort for stable sorting. The way the C++ standard specifies stable sort means that most implementations probably use it as well. I did not dive in the code to find out. Pystd's merge sort implementation consists of ~220 lines of code. It can be read on this page.

Stdlibc++ can do the sort in 0.9 seconds whereas Pystd takes .94 seconds. Getting to within 5% with such a simple implementation is actually quite astonishing. Even when considering all the usual caveats where it might completely fall over with a different input data distribution and all that.

Regular sort

Both stdlibc++ and Pystd use introsort. Pystd's implementation has ~150 lines of code but it also uses heapsort, which has a further 100 lines of code). Code for introsort is here, and heapsort is here.

Stdlibc++ gets the sort done in 0.76 seconds whereas Pystd takes 0.82 seconds. This makes it approximately 8% slower. It's not great, but getting within 10% with a few evening's work is still a pretty good result. Especially since, and I'm speculating here, std::sort has seen a lot more optimization work than std::stable_sort because it is used more.

For heavy duty number crunching this would be way too slow. But for moderate data set sizes the performance difference might be insignificant for many use cases.

Note that all of these are faster (note: did not measure) than libc's qsort because it requires an indirect function call on every comparison i.e. the comparison method can not be inlined.

Compiling the stdlib version takes 0.68 seconds while the Pystd version takes 0.33 seconds. Without optimizations the times are 0.55 and 0.21 seconds, respectively.

Where does the time go?

Valgrind will tell you that quite easily.

This picture shows quite clearly why big O notation can be misleading. Both quicksort (the inner loop of introsort) and heapsort have "the same" average time complexity but every call to heapsort takes approximately 4.5 times as long.

Discovering a new class of primes fur the fun of it

There are a lot of prime classes, such as left truncating primes, twin primes, mersenne primes, palindromic primes, emirp primes and so on. The Wikipedia page on primes lists many more. Recently I got to thinking (as one is wont to do) how difficult would it be to come up with a brand new one. The only reliable way to know is to try it yourself.

The basic loop

The method I used was fairly straightforward:

1. Download a list of the first one million primes
2. Look at it
3. Try to come up with a pattern
4. Check if numbers from your pattern show up on OEIS
5. Find out they are not
6. Rejoice
7. Check again more rigorously
8. Realize they are in fact there in a slightly different form
9. Go to 2

Eventually I managed to come up with a prime category that is not in OEIS. Python code that generates them can be found in this repo. It may have bugs (I discovered several in the course of writing this post). The data below has not been independently validated.

Faro primes

In magic terminology, a Faro shuffle is one that cuts a deck of cards in half and then interleaves the results. It is also known as a perfect shuffle. There are two different types of Faro shuffle, an in shuffle and an out shuffle. They have the peculiar property that if you keep repeating the same operation, eventually the deck returns to the original order.

A prime p is a Faro prime if all numbers obtained by applying Faro shuffles (either in or out shuffles, but only one type) to its decimal representation are also prime. A Faro prime can be an Faro in prime, a Faro out prime or both. As an example, 19 is a Faro in prime, because a single in shuffle returns it to its original form. It is not an Faro out prime, because out shuffling it produces 91, which is not a prime (91 = 7*13).

The testing for this was not rigorous, but at least OEIS does not recognize it.

Statistics

I only used primes with an even number of digits. For odd number of digits you'd first need to decide how in and out shuffles should work. This is left as an exercise to the reader.

Within the first one milllion primes, there are 7492 in primes, 775 out primes and 38 that are both in and out primes.

The numbers with one or two digits are not particularly interesting. The first "actual" Faro in prime is 1103. It can be in shuffled once yielding 1013.

For the first out shuffle you need to go to 111533, which shuffles to 513131 and 153113.

The first prime longer than 2 digits that qualifies for both a Faro in and out prime is 151673. Its in shuffle primes are 165713, 176153 and 117563. The corresponding out shuffle primes are 151673, 617531 and 563117.

Within the first one million primes the largest in shuffle prime is 15484627, the largest out shuffle prime is 11911111 and the largest in and out prime is 987793.

Further questions

As is typical in maths, finding out something immediately raises more questions. For example:

Why are there so many fewer out primes than in primes?

How would this look for primes with odd number of digits in them?

Is it possible to build primes by a mixture of in and out shuffles?

Most of the primes do not complete a "full shuffle", that is, they repeat faster than a deck of fully unique playing cards would. For any number n can you find a Faro prime that requires that many shuffles or is there an upper limit for the number of shuffles?

What's cooking with Pystd, the experimental C++ standard library?

Pystd is an experiment on what a C++ standard library without any backwards compatibility requirements would look like. Its design goals are in order of decreasing priority:

• Fast build times
• Simplicity of implementation
• Good performance

 It also has some design-antigoals:

• Not compatible with the ISO C++ standard library
• No support for weird corner cases like linked lists or types that can't be noexcept-moved
• Do not reinvent things that are already in the C standard library (though you might provide a nicer UI to them)

Current status

There is a bunch of stuff implemented, like vector, several string types, hashmap, a B-tree based ordered map, regular expressions, unix path manipulation operations and so on. The latest addition has been sort algorithms, which include merge sort, heap sort and introsort.

None of these is "production quality". They will almost certainly have bugs. Don't rely on them for "real work". 

The actual library consists of approximately 4800 lines of headers and 4700 lines of source. Building the library and all test code on a Raspberry Pi using a single core takes 13 seconds. With 30 process invocations this means approximately 0.4 seconds per compilation.

For real world testing we have really only one data point, but in it build time was reduced by three quarters, the binary became smaller and the end result ran faster.

Portability

The code has been tested on Linux x86_64 and aarch64 as well as on macOS. It currently does not work with Visual Studio which has not implemented support for pack indexing yet.

Why should you consider using it?

Back in the 90s and 00s (I think) it was fashionable to write your own C++ standard library implementation. Eventually they all died and people moved to the one that comes with their compiler. Which is totally reasonable. So why would you now switch to something else?

For existing C++ applications you probably don't want to. The amount of work needed for a port is too much to be justified in most cases.

For green field projects things are more interesting. Maybe you just want to try something new just for the fun of it? That is the main reason why Pystd even exists, I wanted to try implementing the core building blocks of a standard library from scratch.

Maybe you want to provide "Go style" binaries that build fast and have no external deps? The size overhead of Pystd is only a few hundred k and the executables it yields only depend on libc (unless you use regexes, in which case they also depend on libpcre, but you can static link it if you prefer).

Resource constrained or embedded systems might also be an option. Libstdc++ takes a few megabytes. Pystd does require malloc, though (more specifically it requires aligned alloc) so for the smallest embedded targets you'd need to use something like the freestanding library. As an additional feature Pystd permits you to disable parts of the library that are not used (currently only regexes, but could be extended to things like threading and file system).

Compiler implementers might choose to test their performance with an unusual code base. For example GCC compiles most Pystd files in a flash but for some reason the B-tree implementation takes several seconds to build. I don't really know why because it does not do any heavy duty metaprogramming or such.

It might also be usable in teaching as a fairly small implementation of the core algorithms used today. Assuming anyone does education any more as opposed to relying on LLMs for everything.

C and C++ dependencies, don't dream it, be it!

Bill Hoffman, the original creator of the CMake language held a presentation at CppCon. At approximately 49 minutes in he starts talking about future plans for dependency management. He says, and I now quote him directly, that "in this future I envision", one should be able to do something like the following (paraphrasing).

Your project has dependencies A, B and C. Typically you get them from "the system" or a package manager. But then you'd need to develop one of the deps as well. So it would be nice if you could somehow download, say, A, build it as part of your own project and, once you are done, switch back to the system one.

Well mr Hoffman, do I have wonderful news for you! You don't need to treasure these sensual daydreams any more. This so called "future" you "envision" is not only the present, but in fact ancient past. This method of dependency management has existed in Meson for so long I don't even remember when it got added. Something like over five years at least. 

How would you use such a wild and an untamed thing?

Let's assume you have a Meson project that is using some dependency called bob. The current build is using it from the system (typically via pkg-config, but the exact method is irrelevant). In order to build the source natively, first you need to obtain it. Assuming it is available in WrapDB, all you need to do is run this command:

meson wrap install bob

If it is not, then you need to do some more work. You can even tell Meson to check out the project's Git repo and build against current trunk if you so prefer. See documentation for details.

Then you need to tell Meson to use the internal one. There is a global option to switch all dependencies to be local, but in this case we want only this dependency to be built and get the remaining ones from the system. Meson has a builtin option for exactly this:

meson configure builddir -Dforce_fallback_for=bob

Starting a build would now reconfigure the system to use the builtin option. Once you are done and want to go back to using system deps, run this command:

meson configure builddir -Dforce_fallback_for=

This is all you need to do. That is the main advantage of competently designed tools. They rose tint your world and keep you safe from trouble and pain. Sometimes you can see the blue sky through the tears in your eyes.

Oh, just one more deadly sting

If you keep watching the presenter first asks the audience if this is something they would like. Upon receiving a positive answer he then follows up with this [again quoting directly]:

So you should all complain to the DOE [presumably US Department of Energy] for not funding the SBIR [presumably some sort of grant or tender] for this.

Shaming your end users into advocating an authoritarian/fascist government to give large sums of money in a tender that only one for-profit corporation can reasonably win is certainly a plan.

Instead of working on this kind of a muscle man you can alternatively do what we in the Meson project did: JFDI. The entire functionality was implemented by maybe 3 to 5 people, some working part time but most being volunteers. The total amount of work it took is probably a fraction of the clerical work needed to deal with all the red tape that comes with a DoE tender process.

In the interest of full disclosure

While writing this blog post I discovered a corner case bug in our current implementation. At the time of writing it is only seven hours old, and not particularly beautiful to behold as it has not been fixed yet. And, unfortunately, the only thing I've come to trust is that bugfixes take longer than you would want them to.

How to get banned from Facebook in one simple step

I, too, have (or as you can probably guess from the title of this post, had) a Facebook account. I only ever used it for two purposes.

1. Finding out what friends I rarely see are doing
2. Getting invites to events

Facebook has over the years made usage #1 pretty much impossible. My feed contains approximately 1% posts by my friends and 99% ads for image meme "humor" groups whose expected amusement value seems to be approximately the same as punching yourself in the groin.

Still, every now and then I get a glimpse of a post by the people I actively chose to follow. Specifically a friend was pondering about the behaviour of people who do happy birthday posts on profiles of deceased people. Like, if you have not kept up with someone enough to know that they are dead, why would you feel the need to post congratulations on their profile pages.

I wrote a reply which is replicated below. It is not accurate as it is a translation and I no longer have access to the original post.

Some of these might come via recommendations by AI assistants. Maybe in the future AI bots from people who themselves are dead carry on posting birthday congratulations on profiles of other dead people. A sort of a social media for the deceased, if you will.

Roughly one minute later my account was suspended. Let that be a lesson to you all. Do not mention the Dead Internet Theory, for doing so threatens Facebook's ad revenue and is thus taboo. (A more probable explanation is that using the word "death" is prohibited by itself regardless of context, leading to idiotic phrasing in the style of "Person X was born on [date] and d!ed [other date]" that you see all over IG, FB and YT nowadays.)

Apparently to reactivate the account I would need to prove that "[I am] a human being". That might be a tall order given that there are days when I doubt that myself.

The reactivation service is designed in the usual deceptive way where it does not tell you all the things you need to do in advance. Instead it bounces you from one task to another in the hopes that sunk cost fallacy makes you submit to ever more egregious demands. I got out when they demanded a full video selfie where I look around different directions. You can make up your own theories as to why Meta, a known advocate for generative AI and all that garbage, would want a high resolution scans of people's faces. I mean, surely they would not use it for AI training without paying a single cent for usage rights to the original model. Right? Right?

The suspension email ends with this ultimatum.

If you think we suspended your account by mistake, you have 180 days to appeal our decision. If you miss this deadline your account will be permanently disabled.

Well, mr Zuckerberg, my response is the following:

Close it! Delete it! Burn it down to the ground! I'd do it myself this very moment, but I can't delete the account without reactivating it first.

Let it also be noted that this post is a much better way of proving that I am a human being than some video selfie thing that could be trivially faked with genAI.