Full Width [alt+shift+f] Shortcuts [alt+shift+k]
Sign Up [alt+shift+s] Log In [alt+shift+l]
50

Getting $3300 from a casino promotion

from Evan Jones - Software Engineer | Computer Scientist [alt+shift+b] in programming

New York State legalized mobile sports gambling in January 2022. The casinos offered crazy promotions to get people signed up. The craziest offered $3300 of free money. I did the math, and there was a low risk way to claim this money. As long as you placed 11 or more bets, you had less than a 1% chance of losing the money you put in, but on average will walk away with an extra $3000. If you are interested in the probabilities of winning/losing, scroll down to "The Math". Unfortunately, this promotion ended on January 21st, 2022. I generally think gambling is a waste of money and time. However, working on the probabilities here was pretty interesting, and it worked out for me. I'm also not the only person who thinks this was basically free money. See What the fudge is happening with NY sports betting promos? for a second point of view. I'm pretty sure this promotion used to run until January 31st, so the casino eventually figured out that they did the math wrong on this one and cut it short. The Math The deal was open an account, deposit $3000, and you got $3300 of "bonus cash", which converts to real money after you bet it. This means you needed to bet the entire $6300, $3000 of our own money, and $3300 of the casino's money. We get to keep whatever winnings come out the other end. My goal was to get the casino's money, without losing my own. The strategy was to place a large number of bets that are highly likely to happen. This minimizes the chance of losing, and decreases the variability in outcomes. The downside is the most you could take home is limited to approximately 1.5x the initial bet ($9450). (An even safer strategy is to bet both sides of the event, but that is forbidden by the terms of the promotion, see below.) Each bet has "odds" that the casinos adjust to ensure they have a slight edge, but they try to stay "neutral". For my model, I assume that the casino's odds are an accurate assessment of the true probability of the event. This is not completely...
22nd Jan 2022

Stay updated

Get a weekly newsletter with the top 5 articles worth reading every week.

More from Evan Jones - Software Engineer | Computer Scientist

Setenv is not Thread Safe and C Doesn't Want to Fix It

You can't safely use the C setenv() or unsetenv() functions in a program that uses threads. Those functions modify global state, and can cause other threads calling getenv() to crash. This also causes crashes in other languages that use those C standard library functions, such as Go's os.Setenv (Go issue) and Rust's std::env::set_var() (Rust issue). I ran into this in a Go program, because Go's built-in DNS resolver can call C's getaddrinfo(), which uses environment variables. This cost me 2 days to track down and file the Go bug. Sadly, this problem has been known for decades. For example, an article from January 2017 said: "None of this is new, but we do re-discover it roughly every five years. See you in 2022." This was only one year off! (She wrote an update in October 2023 after I emailed her about my Go bug.) This is a flaw in the POSIX standard, which extends the C Standard to allow modifying environment varibles. The most infuriating part is that many people who could influence the standard or maintain the C libraries don't see this as a problem. The argument is that the specification clearly documents that setenv() cannot be used with threads. Therefore, if someone does this, the crashes are their fault. We should apparently read every function's specification carefully, not use software written by others, and not use threads. These are unrealistic assumptions in modern software. I think we should instead strive to create APIs that are hard to screw up, and evolve as the ecosystem changes. The C language and standard library continue to play an important role at the base of most software. We either need to figure out how to improve it, or we need to figure out how to abandon it. Why is setenv() not thread-safe? The biggest problem is that getenv() returns a char*, with no need for applications to free it later. One thread could be using this pointer when another thread changes the same environment variable using setenv() or unsetenv(). The getenv() function is perfect if environment variables never change. For example, for accessing a process's initial table of environment variables (see the System V ABI: AMD64 Section 3.4.1). It turns out the C Standard only includes getenv(), so according to C, that is exactly how this should work. However, most implementations also follow the POSIX standard (e.g. POSIX.1-2017), which extends C to include functions that modify the environment. This means the current getenv() API is problematic. Even worse, putenv() adds a char* to the set of environment variables. It is explicitly required that if the application modifies the memory after putenv() returns, it modifies the environment variables. This means applications can modify the value passed to putenv() at any time, without any synchronization. FreeBSD used to implement putenv() by copying the value, but it changed it with FreeBSD 7 in 2008, which suggests some programs really do depend on modifying the environment in this fashion (see FreeBSD putenv man page). As a final problem, environ is a NULL-terminated array of pointers (char**) that an application can read and assign to (see definition in POSIX.1-2017). This is how applications can iterate over all environment variables. Accesses to this array are not thread-safe. However, in my experience many fewer applications use this than getenv() and setenv(). However, this does cause some libraries to not maintain the set of environment variables in a thread-safe way, since they directly update this table. Environment variable implementations Implementations need to choose what do do when an application overwrites an existing variable. I looked at glibc, musl, Solaris/Illumos, and FreeBSD/Apple's C standard libraries, and they make the following choices: Never free environment variables (glibc, Solaris/Illumos): Calling setenv() repeatedly is effectively a memory leak. However, once a value is returned from getenv(), it is immutable and can be used by threads safely. Free the environment variables (musl, FreeBSD/Apple): Using the pointer returned by getenv() after another thread calls setenv() can crash. A second problem is ensuring the set of environment variables is updated in a thread-safe fashion. This is what causes crashes in glibc. glibc uses an array to hold pointers to the "NAME=value" strings. It holds a lock in setenv() when changing this array, but not in getenv(). If a thread calling setenv() needs to resize the array of pointers, it copies the values to a new array and frees the previous one. This can cause other threads executing getenv() to crash, since they are now iterating deallocated memory. This is particularly annoying since glibc already leaks environment variables, and holds a lock in setenv(). All it needs to do is hold the lock inside getenv(), and it would no longer crash. This would make getenv() slightly slower. However, getenv() already uses a linear search of the array, so performance does not appear to be a concern. More sophisticated implementations are possible if this is a problem, such as Solaris/Illumos's lock-free implementation. Why do programs use environment variables? Environment variables useful for configuring shared libraries or language runtimes that are included in other programs. This allows users to change the configuration, without program authors needing to explicitly pass the configuration in. One alternative is command line flags, which requires programs to parse them and pass them in to the libraries. Another alternative are configuration files, which then need some other way to disable or configure, to be able to test new configurations. Environment variables are a simple solution. AS a result, many libraries call getenv() (see a partial list below). Since many libraries are configured through environment variables, a program may need to change these variables to configure the libraries it uses. This is common at application startup. This causes programs to need to call setenv(). Given this issue, it seems like libraries should also provide a way to explicitly configure any settings, and avoid using environment variables. We should fix this problem, and we can In my opinion, it is rediculous that this has been a known problem for so long. It has wasted thousands of hours of people's time, either debugging the problems, or debating what to do about it. We know how to fix the problem. First, we can make a thread-safe implementation, like Illumos/Solaris. This has some limitations: it leaks memory in setenv(), and is still unsafe if a program uses putenv() or the environ variable. However, this is an improvement over the current Linux and Apple implementations. The second solution is to add new APIs to get one and get all environment variables that are thread-safe by design, like Microsoft's getenv_s() (see below for the controversy around C11's "Annex K"). My preferred solution would be to do both. This would reduce the chances of hitting this problem for existing programs and libraries, and also provide a path to avoid the problems entirely for new code or languages like Go and Rust. My rough idea would be the following: Add a function to copy one single environment variable to a user-specified buffer, similar to getenv_s(). Add a thread-safe API to iterate over all environment variables, or to copy all variables out. Mark getenv() as deprecated, recommending the new thread-safe getenv() function instead. Mark putenv() as deprecated, recommending setenv() instead. Mark environ as deprecated, recommending environment variable functions instead. Update the implementation of environment varibles to be thread-safe. This requires leaking memory if getenv() is used on a variable, but we can detect if the old functions are used, and only leak memory in that case. This means programs written in other languages will avoid these problems as soon as their runtimes are updated. Update the C and POSIX standards to require the above changes. This would be progress. The getenv_s / C Standard Annex K controversy Microsoft provides getenv_s(), which copies the environment variable into a caller-provided buffer. This is easy to make thread-safe by holding a read lock while copying the variable. After the function returns, future changes to the environment have no effect. This is included in the C11 Standard as Annex K "Bounds Checking Interfaces". The C standard Annexes are optional features. This Annex includes new functions intended to make it harder to make mistakes with buffers that are the wrong size. The first draft of this extension was published in 2003. This is when Microsoft was focusing on "Trustworthy Computing" after a January 2002 memo from Bill Gates. Basically, Windows wasn't designed to be connected to the Internet, and now that it was, people were finding many security problems. Lots of them were caused by buffer handling mistakes. Microsoft developed new versions of a number of problematic functions, and added checks to the Visual C++ compiler to warn about using the old ones. They then attempted to standardize these functions. My understanding is the people responsible for the Unix POSIX standards did not like the design of these functions, so they refused to implement them. For more details, see Field Experience With Annex K published in September 2015, Stack Overflow: Why didn't glibc implement _s functions? updated March 2023, and Rich Felker of musl on both technical and social reasons for not implementing Annex K from February 2019. I haven't looked at the rest of the functions, but having spent way too long looking at getenv(), the general idea of getenv_s() seems like a good idea to me. Standardizing this would help avoid this problem. Incomplete list of common environment variables This is a list of some uses of environment variables from fairly widely used libraries and services. This shows that environment variables are pretty widely used. Cloud Provider Credentials and Services AWS's SDKs for credentials (e.g. AWS_ACCESS_KEY_ID) Google Cloud Application Default Credentials (e.g. GOOGLE_APPLICATION_CREDENTIALS) Microsoft Azure Default Azure Credential (e.g. AZURE_CLIENT_ID) AWS's Lambda serverless product: sets a large number of variables like AWS_REGION, AWS_LAMBDA_FUNCTION_NAME, and credentials like AWS_SECRET_ACCESS_KEY Google Cloud Run serverless product: configuration like PORT, K_SERVICE, K_REVISION Kubernetes service discovery: Defines variables SERVICE_NAME_HOST and SERVICE_NAME_PORT. Third-party C/C++ Libraries OpenTelemetry: Metrics and tracing. Many environment variables like OTEL_SERVICE_NAME and OTEL_RESOURCE_ATTRIBUTES. OpenSSL: many configurable variables like HTTPS_PROXY, OPENSSL_CONF, OPENSSL_ENGINES. BoringSSL: Google's fork of OpenSSL used in Chrome and others. It reads SSLKEYLOGFILE just like OpenSSL for logging TLS keys for debugging. Libcurl: proxies, SSL/TLS configuration and debugging like HTTPS_PROXY, CURL_SSL_BACKEND, CURL_DEBUG. Libpq Postgres client library: connection parameters including credentials like PGHOSTADDR, PGDATABASE, and PGPASSWORD. Rust Standard Library std::thread RUST_MIN_STACK: Calls std::env::var() on the first call to spawn() a new thread. It is cached in a static atomic variable and never read again. See implementation in thread::min_stack(). std::backtrace RUST_LIB_BACKTRACE: Calls std::env::var() on the first call to capture a backtrace. It is cached in a static atomic variable and never read again. See implementation in Backtrace::enabled().

19th Nov 2023 • 69 votes
Random Load Balancing is Unevenly Distributed

This is a reminder that random load balancing is unevenly distributed. If we distribute a set of items randomly across a set of servers (e.g. by hashing, or by randomly selecting a server), the average number of items on each server is num_items / num_servers. It is easy to assume this means each server has close to the same number of items. However, since we are selecting servers at random, they will have different numbers of items, and the imbalance can be important. For load balancing, a reasonable model is that each server has fixed capacity (e.g. it can serve 3000 requests/second, or store 100 items, etc.). We need to divide the total workload over the servers, so that each server stays below its capacity. This means the number of servers is determined by the most loaded server, not the average. This is a classic balls in bins problem that has been well studied, and there are some interesting theoretical results. However, I wanted some specific numbers, so I wrote a small simulation. The summary is that the imbalance depends on the expected number of items per server (that is, num_items / num_servers). This means workload is more balanced with fewer servers, or with more items. This means that dividing a set of items over more servers makes the distribution more unfair, which is a reason we can get worse than linear scaling of a distributed system. Let's make this more concrete with an example. Let's assume we have a workload of 1000 items, and each server can hold a maximum of 100 items. If we place the exact same number of items on each server, we only need 10 servers, and each of them is completely busy. However, if we place the items randomly, then the median (p50) number of items is 100 items. This means half the servers will have more than 100 items, and will be overloaded. If we want less than a 1% chance of an overloaded server, we need to look at the 99th percentile (p99) server load. We need to use at least 13 servers, which has a p99 load of 97 items. For 14 servers, the average is 77 items, so our servers are on average 23% idle. This shows how the imbalance leads to wasted capacity. This is a bit of an extreme example, because the number of items is small. Let's assume we can make the items 10× smaller, say by dividing them into pieces. Our workload now consists of 10k items, and each server has the capacity to hold 1000 (1k) items. Our perfectly balanced workload still needs 10 servers. With random load balancing, to have a less than 1 in 1000 chance of exceeding our capacity, we only need 11 servers, which has a p99 load of 98 items and a p999 of 100 items. With 11 servers, the average number of items is 910 or 91%, so our servers are only 9% idle. This shows how splitting work into smaller pieces improves load balancing. Another way to look at this is to think about a scaling scenario. Let's go back to our workload of 1000 items, where each server can handle 100 items, and we have 13 servers to ensure we have less than a 1% chance of an overloaded server. Now let's assume the amount of work per item doubles, for example because the service has become more popular, so each item has become larger. Now, each server can hold a maximum of 50 items. If we have perfectly linear scaling, we can double the number of servers from 13 to 26 to handle this workload. However, 26 servers has a p99 of 53 items, so we again have a more than 1% chance of overload. We need to use 28 servers which has a p99 of 50 items. This means we doubled the workload, but had to increase the number of servers from 13 to 28, which is 2.15×. This is sub-linear scaling. As a way to visualize the imbalance, the chart below shows the p99 to average ratio, which is a measure of how imbalanced the system is. If everything is perfectly balanced, the value is 1.0. A value of 2.0 means 1% of servers will have double the number of items of the average server. This shows that the imbalance increases with the number of servers, and increases with fewer items. Power of Two Random Choices Another way to improve load balancing is to have smarter placement. Perfect placement can be hard, but it is often possible to use the "power of two random choices" technique: select two servers at random, and place the item on the least loaded of the two. This makes the distribution much more balanced. For 1000 items and 100 items/server, 11 servers has a p999 of 93 items, so much less than 0.1% chance of overload, compared to needing 14 servers with random load balancing. For the scaling scenario where each server can only handle 50 items, we only need 21 servers to have a p999 of 50 items, compared to 28 servers with random load balancing. The downside of the two choices technique is that each request is now more expensive, since it must query two servers instead of one. However, in many cases where the "item not found" requests are much less expensive than the "item found" requests, this can still be a substantial improvement. For another look at how this improves load balancing, with a nice simulation that includes information delays, see Marc Brooker's blog post. Raw simulation output I will share the code for this simulation later. simulating placing items on servers with random selection iterations=10000 (number of times num_items are placed on num_servers) measures the fraction of items on each server (server_items/num_items) and reports the percentile of all servers in the run P99_AVG_RATIO = p99 / average; approximately the worst server compared to average num_items=1000: num_servers=3 p50=0.33300 p95=0.35800 p99=0.36800 p999=0.37900 AVG=0.33333; P99_AVG_RATIO=1.10400; ITEMS_PER_NODE=333.3 num_servers=5 p50=0.20000 p95=0.22100 p99=0.23000 p999=0.24000 AVG=0.20000; P99_AVG_RATIO=1.15000; ITEMS_PER_NODE=200.0 num_servers=10 p50=0.10000 p95=0.11600 p99=0.12300 p999=0.13100 AVG=0.10000; P99_AVG_RATIO=1.23000; ITEMS_PER_NODE=100.0 num_servers=11 p50=0.09100 p95=0.10600 p99=0.11300 p999=0.12000 AVG=0.09091; P99_AVG_RATIO=1.24300; ITEMS_PER_NODE=90.9 num_servers=12 p50=0.08300 p95=0.09800 p99=0.10400 p999=0.11200 AVG=0.08333; P99_AVG_RATIO=1.24800; ITEMS_PER_NODE=83.3 num_servers=13 p50=0.07700 p95=0.09100 p99=0.09700 p999=0.10400 AVG=0.07692; P99_AVG_RATIO=1.26100; ITEMS_PER_NODE=76.9 num_servers=14 p50=0.07100 p95=0.08500 p99=0.09100 p999=0.09800 AVG=0.07143; P99_AVG_RATIO=1.27400; ITEMS_PER_NODE=71.4 num_servers=25 p50=0.04000 p95=0.05000 p99=0.05500 p999=0.06000 AVG=0.04000; P99_AVG_RATIO=1.37500; ITEMS_PER_NODE=40.0 num_servers=50 p50=0.02000 p95=0.02800 p99=0.03100 p999=0.03500 AVG=0.02000; P99_AVG_RATIO=1.55000; ITEMS_PER_NODE=20.0 num_servers=100 p50=0.01000 p95=0.01500 p99=0.01800 p999=0.02100 AVG=0.01000; P99_AVG_RATIO=1.80000; ITEMS_PER_NODE=10.0 num_servers=1000 p50=0.00100 p95=0.00300 p99=0.00400 p999=0.00500 AVG=0.00100; P99_AVG_RATIO=4.00000; ITEMS_PER_NODE=1.0 num_items=2000: num_servers=3 p50=0.33350 p95=0.35050 p99=0.35850 p999=0.36550 AVG=0.33333; P99_AVG_RATIO=1.07550; ITEMS_PER_NODE=666.7 num_servers=5 p50=0.20000 p95=0.21500 p99=0.22150 p999=0.22850 AVG=0.20000; P99_AVG_RATIO=1.10750; ITEMS_PER_NODE=400.0 num_servers=10 p50=0.10000 p95=0.11100 p99=0.11600 p999=0.12150 AVG=0.10000; P99_AVG_RATIO=1.16000; ITEMS_PER_NODE=200.0 num_servers=11 p50=0.09100 p95=0.10150 p99=0.10650 p999=0.11150 AVG=0.09091; P99_AVG_RATIO=1.17150; ITEMS_PER_NODE=181.8 num_servers=12 p50=0.08350 p95=0.09350 p99=0.09800 p999=0.10300 AVG=0.08333; P99_AVG_RATIO=1.17600; ITEMS_PER_NODE=166.7 num_servers=13 p50=0.07700 p95=0.08700 p99=0.09100 p999=0.09600 AVG=0.07692; P99_AVG_RATIO=1.18300; ITEMS_PER_NODE=153.8 num_servers=14 p50=0.07150 p95=0.08100 p99=0.08500 p999=0.09000 AVG=0.07143; P99_AVG_RATIO=1.19000; ITEMS_PER_NODE=142.9 num_servers=25 p50=0.04000 p95=0.04750 p99=0.05050 p999=0.05450 AVG=0.04000; P99_AVG_RATIO=1.26250; ITEMS_PER_NODE=80.0 num_servers=50 p50=0.02000 p95=0.02550 p99=0.02750 p999=0.03050 AVG=0.02000; P99_AVG_RATIO=1.37500; ITEMS_PER_NODE=40.0 num_servers=100 p50=0.01000 p95=0.01400 p99=0.01550 p999=0.01750 AVG=0.01000; P99_AVG_RATIO=1.55000; ITEMS_PER_NODE=20.0 num_servers=1000 p50=0.00100 p95=0.00250 p99=0.00300 p999=0.00400 AVG=0.00100; P99_AVG_RATIO=3.00000; ITEMS_PER_NODE=2.0 num_items=5000: num_servers=3 p50=0.33340 p95=0.34440 p99=0.34920 p999=0.35400 AVG=0.33333; P99_AVG_RATIO=1.04760; ITEMS_PER_NODE=1666.7 num_servers=5 p50=0.20000 p95=0.20920 p99=0.21320 p999=0.21740 AVG=0.20000; P99_AVG_RATIO=1.06600; ITEMS_PER_NODE=1000.0 num_servers=10 p50=0.10000 p95=0.10700 p99=0.11000 p999=0.11320 AVG=0.10000; P99_AVG_RATIO=1.10000; ITEMS_PER_NODE=500.0 num_servers=11 p50=0.09080 p95=0.09760 p99=0.10040 p999=0.10380 AVG=0.09091; P99_AVG_RATIO=1.10440; ITEMS_PER_NODE=454.5 num_servers=12 p50=0.08340 p95=0.08980 p99=0.09260 p999=0.09580 AVG=0.08333; P99_AVG_RATIO=1.11120; ITEMS_PER_NODE=416.7 num_servers=13 p50=0.07680 p95=0.08320 p99=0.08580 p999=0.08900 AVG=0.07692; P99_AVG_RATIO=1.11540; ITEMS_PER_NODE=384.6 num_servers=14 p50=0.07140 p95=0.07740 p99=0.08000 p999=0.08300 AVG=0.07143; P99_AVG_RATIO=1.12000; ITEMS_PER_NODE=357.1 num_servers=25 p50=0.04000 p95=0.04460 p99=0.04660 p999=0.04880 AVG=0.04000; P99_AVG_RATIO=1.16500; ITEMS_PER_NODE=200.0 num_servers=50 p50=0.02000 p95=0.02340 p99=0.02480 p999=0.02640 AVG=0.02000; P99_AVG_RATIO=1.24000; ITEMS_PER_NODE=100.0 num_servers=100 p50=0.01000 p95=0.01240 p99=0.01340 p999=0.01460 AVG=0.01000; P99_AVG_RATIO=1.34000; ITEMS_PER_NODE=50.0 num_servers=1000 p50=0.00100 p95=0.00180 p99=0.00220 p999=0.00260 AVG=0.00100; P99_AVG_RATIO=2.20000; ITEMS_PER_NODE=5.0 num_items=10000: num_servers=3 p50=0.33330 p95=0.34110 p99=0.34430 p999=0.34820 AVG=0.33333; P99_AVG_RATIO=1.03290; ITEMS_PER_NODE=3333.3 num_servers=5 p50=0.20000 p95=0.20670 p99=0.20950 p999=0.21260 AVG=0.20000; P99_AVG_RATIO=1.04750; ITEMS_PER_NODE=2000.0 num_servers=10 p50=0.10000 p95=0.10500 p99=0.10700 p999=0.10940 AVG=0.10000; P99_AVG_RATIO=1.07000; ITEMS_PER_NODE=1000.0 num_servers=11 p50=0.09090 p95=0.09570 p99=0.09770 p999=0.09990 AVG=0.09091; P99_AVG_RATIO=1.07470; ITEMS_PER_NODE=909.1 num_servers=12 p50=0.08330 p95=0.08790 p99=0.08980 p999=0.09210 AVG=0.08333; P99_AVG_RATIO=1.07760; ITEMS_PER_NODE=833.3 num_servers=13 p50=0.07690 p95=0.08130 p99=0.08320 p999=0.08530 AVG=0.07692; P99_AVG_RATIO=1.08160; ITEMS_PER_NODE=769.2 num_servers=14 p50=0.07140 p95=0.07570 p99=0.07740 p999=0.07950 AVG=0.07143; P99_AVG_RATIO=1.08360; ITEMS_PER_NODE=714.3 num_servers=25 p50=0.04000 p95=0.04330 p99=0.04460 p999=0.04620 AVG=0.04000; P99_AVG_RATIO=1.11500; ITEMS_PER_NODE=400.0 num_servers=50 p50=0.02000 p95=0.02230 p99=0.02330 p999=0.02440 AVG=0.02000; P99_AVG_RATIO=1.16500; ITEMS_PER_NODE=200.0 num_servers=100 p50=0.01000 p95=0.01170 p99=0.01240 p999=0.01320 AVG=0.01000; P99_AVG_RATIO=1.24000; ITEMS_PER_NODE=100.0 num_servers=1000 p50=0.00100 p95=0.00150 p99=0.00180 p999=0.00210 AVG=0.00100; P99_AVG_RATIO=1.80000; ITEMS_PER_NODE=10.0 num_items=100000: num_servers=3 p50=0.33333 p95=0.33579 p99=0.33681 p999=0.33797 AVG=0.33333; P99_AVG_RATIO=1.01043; ITEMS_PER_NODE=33333.3 num_servers=5 p50=0.20000 p95=0.20207 p99=0.20294 p999=0.20393 AVG=0.20000; P99_AVG_RATIO=1.01470; ITEMS_PER_NODE=20000.0 num_servers=10 p50=0.10000 p95=0.10157 p99=0.10222 p999=0.10298 AVG=0.10000; P99_AVG_RATIO=1.02220; ITEMS_PER_NODE=10000.0 num_servers=11 p50=0.09091 p95=0.09241 p99=0.09304 p999=0.09379 AVG=0.09091; P99_AVG_RATIO=1.02344; ITEMS_PER_NODE=9090.9 num_servers=12 p50=0.08334 p95=0.08477 p99=0.08537 p999=0.08602 AVG=0.08333; P99_AVG_RATIO=1.02444; ITEMS_PER_NODE=8333.3 num_servers=13 p50=0.07692 p95=0.07831 p99=0.07888 p999=0.07954 AVG=0.07692; P99_AVG_RATIO=1.02544; ITEMS_PER_NODE=7692.3 num_servers=14 p50=0.07143 p95=0.07277 p99=0.07332 p999=0.07396 AVG=0.07143; P99_AVG_RATIO=1.02648; ITEMS_PER_NODE=7142.9 num_servers=25 p50=0.04000 p95=0.04102 p99=0.04145 p999=0.04193 AVG=0.04000; P99_AVG_RATIO=1.03625; ITEMS_PER_NODE=4000.0 num_servers=50 p50=0.02000 p95=0.02073 p99=0.02103 p999=0.02138 AVG=0.02000; P99_AVG_RATIO=1.05150; ITEMS_PER_NODE=2000.0 num_servers=100 p50=0.01000 p95=0.01052 p99=0.01074 p999=0.01099 AVG=0.01000; P99_AVG_RATIO=1.07400; ITEMS_PER_NODE=1000.0 num_servers=1000 p50=0.00100 p95=0.00117 p99=0.00124 p999=0.00132 AVG=0.00100; P99_AVG_RATIO=1.24000; ITEMS_PER_NODE=100.0 power of two choices num_items=1000: num_servers=3 p50=0.33300 p95=0.33400 p99=0.33500 p999=0.33600 AVG=0.33333; P99_AVG_RATIO=1.00500; ITEMS_PER_NODE=333.3 num_servers=5 p50=0.20000 p95=0.20100 p99=0.20200 p999=0.20300 AVG=0.20000; P99_AVG_RATIO=1.01000; ITEMS_PER_NODE=200.0 num_servers=10 p50=0.10000 p95=0.10100 p99=0.10200 p999=0.10200 AVG=0.10000; P99_AVG_RATIO=1.02000; ITEMS_PER_NODE=100.0 num_servers=11 p50=0.09100 p95=0.09200 p99=0.09300 p999=0.09300 AVG=0.09091; P99_AVG_RATIO=1.02300; ITEMS_PER_NODE=90.9 num_servers=12 p50=0.08300 p95=0.08500 p99=0.08500 p999=0.08600 AVG=0.08333; P99_AVG_RATIO=1.02000; ITEMS_PER_NODE=83.3 num_servers=13 p50=0.07700 p95=0.07800 p99=0.07900 p999=0.07900 AVG=0.07692; P99_AVG_RATIO=1.02700; ITEMS_PER_NODE=76.9 num_servers=14 p50=0.07200 p95=0.07300 p99=0.07300 p999=0.07400 AVG=0.07143; P99_AVG_RATIO=1.02200; ITEMS_PER_NODE=71.4 num_servers=25 p50=0.04000 p95=0.04100 p99=0.04200 p999=0.04200 AVG=0.04000; P99_AVG_RATIO=1.05000; ITEMS_PER_NODE=40.0 num_servers=50 p50=0.02000 p95=0.02100 p99=0.02200 p999=0.02200 AVG=0.02000; P99_AVG_RATIO=1.10000; ITEMS_PER_NODE=20.0 num_servers=100 p50=0.01000 p95=0.01100 p99=0.01200 p999=0.01200 AVG=0.01000; P99_AVG_RATIO=1.20000; ITEMS_PER_NODE=10.0 num_servers=1000 p50=0.00100 p95=0.00200 p99=0.00200 p999=0.00300 AVG=0.00100; P99_AVG_RATIO=2.00000; ITEMS_PER_NODE=1.0 power of two choices num_items=2000: num_servers=3 p50=0.33350 p95=0.33400 p99=0.33400 p999=0.33450 AVG=0.33333; P99_AVG_RATIO=1.00200; ITEMS_PER_NODE=666.7 num_servers=5 p50=0.20000 p95=0.20050 p99=0.20100 p999=0.20150 AVG=0.20000; P99_AVG_RATIO=1.00500; ITEMS_PER_NODE=400.0 num_servers=10 p50=0.10000 p95=0.10050 p99=0.10100 p999=0.10100 AVG=0.10000; P99_AVG_RATIO=1.01000; ITEMS_PER_NODE=200.0 num_servers=11 p50=0.09100 p95=0.09150 p99=0.09200 p999=0.09200 AVG=0.09091; P99_AVG_RATIO=1.01200; ITEMS_PER_NODE=181.8 num_servers=12 p50=0.08350 p95=0.08400 p99=0.08400 p999=0.08450 AVG=0.08333; P99_AVG_RATIO=1.00800; ITEMS_PER_NODE=166.7 num_servers=13 p50=0.07700 p95=0.07750 p99=0.07800 p999=0.07800 AVG=0.07692; P99_AVG_RATIO=1.01400; ITEMS_PER_NODE=153.8 num_servers=14 p50=0.07150 p95=0.07200 p99=0.07250 p999=0.07250 AVG=0.07143; P99_AVG_RATIO=1.01500; ITEMS_PER_NODE=142.9 num_servers=25 p50=0.04000 p95=0.04050 p99=0.04100 p999=0.04100 AVG=0.04000; P99_AVG_RATIO=1.02500; ITEMS_PER_NODE=80.0 num_servers=50 p50=0.02000 p95=0.02050 p99=0.02100 p999=0.02100 AVG=0.02000; P99_AVG_RATIO=1.05000; ITEMS_PER_NODE=40.0 num_servers=100 p50=0.01000 p95=0.01050 p99=0.01100 p999=0.01100 AVG=0.01000; P99_AVG_RATIO=1.10000; ITEMS_PER_NODE=20.0 num_servers=1000 p50=0.00100 p95=0.00150 p99=0.00200 p999=0.00200 AVG=0.00100; P99_AVG_RATIO=2.00000; ITEMS_PER_NODE=2.0 power of two choices num_items=5000: num_servers=3 p50=0.33340 p95=0.33360 p99=0.33360 p999=0.33380 AVG=0.33333; P99_AVG_RATIO=1.00080; ITEMS_PER_NODE=1666.7 num_servers=5 p50=0.20000 p95=0.20020 p99=0.20040 p999=0.20060 AVG=0.20000; P99_AVG_RATIO=1.00200; ITEMS_PER_NODE=1000.0 num_servers=10 p50=0.10000 p95=0.10020 p99=0.10040 p999=0.10040 AVG=0.10000; P99_AVG_RATIO=1.00400; ITEMS_PER_NODE=500.0 num_servers=11 p50=0.09100 p95=0.09120 p99=0.09120 p999=0.09140 AVG=0.09091; P99_AVG_RATIO=1.00320; ITEMS_PER_NODE=454.5 num_servers=12 p50=0.08340 p95=0.08360 p99=0.08360 p999=0.08380 AVG=0.08333; P99_AVG_RATIO=1.00320; ITEMS_PER_NODE=416.7 num_servers=13 p50=0.07700 p95=0.07720 p99=0.07720 p999=0.07740 AVG=0.07692; P99_AVG_RATIO=1.00360; ITEMS_PER_NODE=384.6 num_servers=14 p50=0.07140 p95=0.07160 p99=0.07180 p999=0.07180 AVG=0.07143; P99_AVG_RATIO=1.00520; ITEMS_PER_NODE=357.1 num_servers=25 p50=0.04000 p95=0.04020 p99=0.04040 p999=0.04040 AVG=0.04000; P99_AVG_RATIO=1.01000; ITEMS_PER_NODE=200.0 num_servers=50 p50=0.02000 p95=0.02020 p99=0.02040 p999=0.02040 AVG=0.02000; P99_AVG_RATIO=1.02000; ITEMS_PER_NODE=100.0 num_servers=100 p50=0.01000 p95=0.01020 p99=0.01040 p999=0.01040 AVG=0.01000; P99_AVG_RATIO=1.04000; ITEMS_PER_NODE=50.0 num_servers=1000 p50=0.00100 p95=0.00120 p99=0.00140 p999=0.00140 AVG=0.00100; P99_AVG_RATIO=1.40000; ITEMS_PER_NODE=5.0 power of two choices num_items=10000: num_servers=3 p50=0.33330 p95=0.33340 p99=0.33350 p999=0.33360 AVG=0.33333; P99_AVG_RATIO=1.00050; ITEMS_PER_NODE=3333.3 num_servers=5 p50=0.20000 p95=0.20010 p99=0.20020 p999=0.20030 AVG=0.20000; P99_AVG_RATIO=1.00100; ITEMS_PER_NODE=2000.0 num_servers=10 p50=0.10000 p95=0.10010 p99=0.10020 p999=0.10020 AVG=0.10000; P99_AVG_RATIO=1.00200; ITEMS_PER_NODE=1000.0 num_servers=11 p50=0.09090 p95=0.09100 p99=0.09110 p999=0.09110 AVG=0.09091; P99_AVG_RATIO=1.00210; ITEMS_PER_NODE=909.1 num_servers=12 p50=0.08330 p95=0.08350 p99=0.08350 p999=0.08360 AVG=0.08333; P99_AVG_RATIO=1.00200; ITEMS_PER_NODE=833.3 num_servers=13 p50=0.07690 p95=0.07700 p99=0.07710 p999=0.07720 AVG=0.07692; P99_AVG_RATIO=1.00230; ITEMS_PER_NODE=769.2 num_servers=14 p50=0.07140 p95=0.07160 p99=0.07160 p999=0.07170 AVG=0.07143; P99_AVG_RATIO=1.00240; ITEMS_PER_NODE=714.3 num_servers=25 p50=0.04000 p95=0.04010 p99=0.04020 p999=0.04020 AVG=0.04000; P99_AVG_RATIO=1.00500; ITEMS_PER_NODE=400.0 num_servers=50 p50=0.02000 p95=0.02010 p99=0.02020 p999=0.02020 AVG=0.02000; P99_AVG_RATIO=1.01000; ITEMS_PER_NODE=200.0 num_servers=100 p50=0.01000 p95=0.01010 p99=0.01020 p999=0.01020 AVG=0.01000; P99_AVG_RATIO=1.02000; ITEMS_PER_NODE=100.0 num_servers=1000 p50=0.00100 p95=0.00110 p99=0.00120 p999=0.00120 AVG=0.00100; P99_AVG_RATIO=1.20000; ITEMS_PER_NODE=10.0 power of two choices num_items=100000: num_servers=3 p50=0.33333 p95=0.33334 p99=0.33335 p999=0.33336 AVG=0.33333; P99_AVG_RATIO=1.00005; ITEMS_PER_NODE=33333.3 num_servers=5 p50=0.20000 p95=0.20001 p99=0.20002 p999=0.20003 AVG=0.20000; P99_AVG_RATIO=1.00010; ITEMS_PER_NODE=20000.0 num_servers=10 p50=0.10000 p95=0.10001 p99=0.10002 p999=0.10002 AVG=0.10000; P99_AVG_RATIO=1.00020; ITEMS_PER_NODE=10000.0 num_servers=11 p50=0.09091 p95=0.09092 p99=0.09093 p999=0.09093 AVG=0.09091; P99_AVG_RATIO=1.00023; ITEMS_PER_NODE=9090.9 num_servers=12 p50=0.08333 p95=0.08335 p99=0.08335 p999=0.08336 AVG=0.08333; P99_AVG_RATIO=1.00020; ITEMS_PER_NODE=8333.3 num_servers=13 p50=0.07692 p95=0.07694 p99=0.07694 p999=0.07695 AVG=0.07692; P99_AVG_RATIO=1.00022; ITEMS_PER_NODE=7692.3 num_servers=14 p50=0.07143 p95=0.07144 p99=0.07145 p999=0.07145 AVG=0.07143; P99_AVG_RATIO=1.00030; ITEMS_PER_NODE=7142.9 num_servers=25 p50=0.04000 p95=0.04001 p99=0.04002 p999=0.04002 AVG=0.04000; P99_AVG_RATIO=1.00050; ITEMS_PER_NODE=4000.0 num_servers=50 p50=0.02000 p95=0.02001 p99=0.02002 p999=0.02002 AVG=0.02000; P99_AVG_RATIO=1.00100; ITEMS_PER_NODE=2000.0 num_servers=100 p50=0.01000 p95=0.01001 p99=0.01002 p999=0.01002 AVG=0.01000; P99_AVG_RATIO=1.00200; ITEMS_PER_NODE=1000.0 num_servers=1000 p50=0.00100 p95=0.00101 p99=0.00102 p999=0.00102 AVG=0.00100; P99_AVG_RATIO=1.02000; ITEMS_PER_NODE=100.0

29th Aug 2023 • 57 votes
How much does the read/write buffer size matter for socket throughput?

The read() and write() system calls take a variable-length byte array as an argument. As a simplified model, the time for the system call should be some constant "per-call" time, plus time directly proportional to the number of bytes in the array. That is, the time for each call should be time = (per_call_minimum_time) + (array_len) × (per_byte_time). With this model, using a larger buffer should increase throughput, asymptotically approaching 1/per_byte_time. I was curious: do real system calls behave this way? What are the ideal buffer sizes for read() and write() if we want to maximize throughput? I decided to do some experiments with blocking I/O. These are not rigorous, and I suspect the results will vary significantly if the hardware and software are different than one the system I tested. The really short answer is that a buffer of 32 KiB is a good starting point on today's systems, and I would want to measure the performance to go beyond that. However, for large writes, performance can increase. On Linux, the simple model holds for small buffers (≤ 4 KiB), but once the program approaches the maximum throughput, the throughput becomes highly variable and in many cases decreases as the buffers get larger. For blocking I/O, approximately 32 KiB is large enough to hit the maximum throughput for read(), but write() throughput improves with buffers up to around 256 KiB - 1 MiB. The reason for the asymmetry is that the Linux kernel will only write less than the entire buffer (a "short write") if there is an error (e.g. a signal causing EINTR). Thus, larger write buffers means the operating system needs to switch to the process less often. On the other head, "short reads", where a read() returns less than the maximum length, become increasingly common as the buffer size increases, which diminishes the benefit. There is a SO_RCVLOWAT socket option to change this that I did not test. The experiments were run on two 16 CPU Google Cloud T2D instances, which use AMD EPYC Milan processors (3rd generation, released in 2021). Each core is a real physical core. I used Ubuntu 23.04 running kernel 6.2.0-1005-gcp. My benchmark program is written in Rust and is available on Github. On localhost, Unix sockets were able to transfer data at approximately 9000 MiB/s. Localhost TCP sockets were a bit slower, around 7000 MiB/s. When using two separate cloud VMs with a networking throughput limit of 32 Gbps = 3800 MiB/s, I needed to use 6 TCP sockets to reliably reach that maximum throughput. A single TCP socket gets around 1400 MiB/s with 256 KiB buffers, with peaks as high as 2200 MiB/s. Experiment 1: /dev/zero and /dev/urandom My first experiment is reading from the /dev/zero and /dev/urandom devices. These are software devices implemented by the kernel, so they should have low overhead and low variability, since other tasks are not involved. Reading from /dev/urandom should be much slower than /dev/zero since the kernel must generate random bytes, rather than just zeros. The chart below shows the throughput for reading from /dev/zero as the buffer size is increased. The results show that the basic linear time per system call model holds until the system reaches maximum throughput (256 kiB buffer = 39000 MiB/s for /dev/zero, or 16 kiB = 410 MiB/s for /dev/urandom). As the buffer size increases further, the throughput decreases as the buffers get too big. This suggests that some other cost for larger buffers starts to outweigh the reduction in number of system calls. Perhaps CPU caches become less effective? The AMD EPYC Milan (3rd gen) CPU I tested on has 32 KiB of L1 data cache and 512 KiB of L2 data cache per core. The performance decreases don't exactly line up with these numbers, but it still seems plausible. The numbers for /dev/urandom are substantially lower, but otherwise similar. I did a linear least-squares fit on the average time per system call, shown in the following chart. If I use all the data, the fit is not good, because the trend changes for larger buffers. However, if I use the data up to the maximum throughput at 256 KiB, the fit is very good, as shown on the chart below. The linear fit models the minimum time per system call as 167 ns, with 0.0235 ns/byte additional time. If we want to use smaller buffers, using a 64 KiB buffer for reading from /dev/zero gets within 95% of the maximum throughput. Experiment 2: Unix and localhost TCP sockets Exchanging data with other processes is the thing I am actually interested in, so I tested Unix and TCP sockets on a single machine. In this case, I varied both the write buffer size and the read buffer size. Unfortunately, these results vary a lot. A more robust comparison would require running each experiment many times, and using some sort of statistical comparison. However, this "quick and dirty" experiment satisfied my curiousity, so I didn't do that. As a result, my conclusions here are vague. The simple model that increasing buffer size should decrease overhead is true, but only until the buffers are about 4 KiB. Above that point, the results start to be highly variable, and it is much harder to draw general conclusion. However, appears that increasing the write buffer size generally is quite helpful up to at least 256 KiB, and often needed as much as 1 MiB to get the highest localhost throughput. I suspect this is because on Linux with blocking sockets, write() will not return until it has written all the data in the buffer, unless there is an error (e.g. EINTR). As a result, passing a large buffer means the kernel can do a lot of the work without needing to switch back to user space. Unfortunately, the same is not true for read(), which often returns "short reads" with any data that is available in the buffer. This starts with buffer sizes around 2 KiB, with the percentage of short reads increasing as the buffer size gets larger. This means the simple model does not hold, because we aren't actually increasing the bytes per read call. I suspect this is a factor which means this microbenchmark is likely not representative of real programs. A real program will do something with the buffer, which will provide time for more data to be buffered in the kernel, and would probably decrease the number of short reads. This likely means larger buffers are in practice more useful than this microbenchmark suggests. As a result of this, the highest throughput often was achievable with small read buffers. I'm somewhat arbitrarily selecting 16 KiB at the best read buffer, and 256 KiB as the best write buffer, although a 1 MiB write buffer seems to be To give a sense of how variable the results are, the plot below shows the local Unix socket throughput for each read and write buffer throughput size. I apologize for the ugly plot. I did not want to spend the time to make it more beautiful. This plot is interactive so you can slice the data to the area of interest. I recommend zooming in to the left hand size with read buffers up to about 300 KiB. The first thing to note is at least on Linux with blocking sockets, the writer will almost never have a "short write", where the write system call returns before writing all the data in the buffer. Unless there is a signal (EINTR) or some other "error" condition, write() will not return until all the bytes are written. The same is not true for reads. The read() system call will often return a "short" read, starting around buffer sizes of 2 KiB. The percentage of short reads generally increases as buffer sizes get bigger, which is logical. Another note is that sockets have in-kernel send and receive buffers. I did not tune these at all. It is possible that better performance is possible by tuning these settings, but that was not my goal. I wanted to know what happens "out of the box" for general-purpose programs without any special tuning. Experiment 3: TCP between two hosts In this experiment, I used two separate hosts connected with 32 Gbps networking in Google Cloud. I first tested the TCP throughput using iperf, to independently verify the network performance. A single TCP connection with iperf is not enough to fully utilize the network. I tried fiddling with some command line options and with Kernel settings like net.ipv4.tcp_rmem and wasn't able to get much better than about 12 Gb/s = 1400 MiB/s. The throughput is also highly varible. Here is some example output with iperf reporting at 2 second intervals, where you can see the throughput ranging from 10 to 19 Gb/s, with an average over the entire interval of 12 Gb/s. To hit the maximum network throughput, I need to use 6 or more parallel TCP connections (iperf -c IP_ADDRESS --time 60 --interval 2 -l 262144 -P 6). Using 3 connections gets around 26 Gb/s, and using 4 or 5 will occasionally hit the maximum, but will also occasionally drop down. Using at least 6 seems to reliably stay at the maximum. Due to this variability, it is hard to draw any conclusions about buffer size. In particular: a single TCP connection is not limited by CPU. The system uses about 40% of a single CPU core, basically all in the kernel. This is more about how the buffer sizes may impact scheduling choices. That said, it is clear that you cannot hit the maximum throughput with a small write buffer. The experiments with 4 KiB write buffers reached approximately 300 MiB/s, while an 8 KiB write buffer was much faster, around 1400 MiB/s. Larger still generally seems better, up to around 256 KiB, which occasionally reached 2200 MiB/s = 17.6 Gb/s. The plot below shows the TCP socket throughput for each read and write buffer size. Again, I apologize for the ugly plot.

16th Jul 2023 • 103 votes
The C Standard Library Function isspace() Depends on Locale

This is a post for myself, because I wasted a lot of time understanding this bug, and I want to be able to remember it in the future. I expect close to zero others to be interested. The C standard library function isspace() returns a non-zero value (true) for the six "standard" ASCII white-space characters ('\t', '\n', '\v', '\f', '\r', ' '), and any locale-specific characters. By default, a program starts in the "C" locale, which will only return true for the six ASCII white-space characters. However, if the program changes locales, it can return true for other values. As a result, unless you really understand locales, you should use your own version of this function, or ICU4C's u_isspace() function. An implementation of isspace() for ASCII is one line: /* Returns true for the 6 ASCII white-space characters: \t \n \v \f \r ' '. */ int isspace_ascii(int c) { return c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r' || c == ' '; } I ran into this because On Mac OS X, Postgres switches to the system's default locale, which is something that uses UTF-8 (e.g. en_US.UTF-8, fr_CA.UTF-8, etc). In this case, isspace() returns true for Unicode white-space values, which includes 0x85 = NEL = Next Line, and 0xA0 = NBSP = No-Break Space. This caused a bug in parsing Postgres Hstore values that use Unicode. I have attempted to submit a patch to fix this (mailing list post, commitfest entry). For a program to demonstrate the behaviour on different systems, see isspace_locale on Github.

6th Jun 2023 • 110 votes
Huge Pages are a Good Idea

Nearly all programs are written to access virtual memory addresses, which the CPU must translate to physical addresses. These translations are usually fast because the mappings are cached in the CPU's Translation Lookaside Buffer (TLB). Unfortunately, virtual memory on x86 has used a 4 kiB page size since the 386 was released in 1985, when computers had a bit less memory than they do today. Also unfortunately, TLBs are pretty small because they need to be fast. For example, AMD's Zen 4 Microarchitecture, which first shipped in September 2022, has a first level data TLB with 72 entries, and a second level TLB with 3072 entries. This means when an application's working set is larger than approximately 4 kiB × 3072 = 12 MiB, some memory accesses will require page table lookups, multiplying the number of memory accesses required. This is a brand-new CPU, with one of the biggest TLBs on the market, so most systems will be worse. Using larger virtual memory page sizes (aka huge pages) can reduce page mapping overhead substantially. Since RAM is so much larger than it was in 1985, a larger page size seems like obviously a good idea to me. In 2021, Google published a paper about making their malloc implementation (TCMalloc) huge page aware (called Temeraire). They report this improved average requests-per-second throughput across their fleet by 7%, by increasing the amount of memory that is backed by huge pages. This made me curious about the "best case" performance benefits. I wrote a small program that allocates 4 GiB, then randomly reads uint64 values from it. On my Intel 11th generation Core i5-1135G7 (Tiger Lake) from 2020, using 2 MiB huge pages is 2.9× faster. I also tried 1 GiB pages, which is 3.1× faster than 4 kiB pages, but only 8% faster than 2 MiB pages. My conclusion: Using madvise() to get the kernel to use huge pages seems like a relatively easy performance win for applications that use a large amount of RAM. Unfortunately, using larger pages is not without its disadvantages. Notably, when the Linux kernel's transparent huge page implementation was first introduced, it was enabled by default, which caused many performance problems. See the section below for more details. Today's default to use huge pages only for applications that opt-in (aka madvise) should improve this. The kernel's policies for managing huge pages have also changed since then, and are hopefully better now. At the very least, the fact that Google uses transparent huge pages for all their applications is some evidence that this can work for a wide variety of workloads. The second problem with larger page sizes is software incompatibility, since so much software is only tested on x86 with 4 kiB pages. Linux on ARM64 used to default to 64 kiB pages. However, this caused many problems (e.g. dotnet, Go, Chrome, jemalloc, Asahi Linux list of broken software). It appears that around 2020 most distributions switched to 4 kiB pages to avoid these problems (e.g. RedHat RHEL9 change in 2021, Ubuntu note about the page size change). Page size historical details Other CPU architectures have made different page size choices. Notably, iOS and Mac OS X on ARM64 uses 16 kiB pages (ARM64 aka aarch64 supports 4, 16, and 64 kiB pages, although specific CPUs will only support some of them). Alpha and Sparc used 8 kiB pages. PowerPC on Linux uses 64 kiB pages, although Redhat/Fedora are considering switching to 4 kiB due to the same compatibility issues. See page sizes used by Windows on various processors. Latency and throughput problems with transparent huge pages The Linux kernel's implementation of transparent huge pages has been the source of performance problems. When introduced, it was initially enabled for all processes and memory regions by default. This caused a large number of problems, which eventually caused the kernel's default to change to madvise, where programs have to opt-in to use huge pages (see Nelson Elhage's summary (2017), and Ubuntu bug that changed the default (2017/released 2019). The performance problems are rare high latency (e.g. operations being substantially slower than normal), throughput issues due to excess CPU consumption of the kernel background tasks, or substantial increases in memory usage. Some examples are Hadoop (2012), TokuDB/MySQL (2014), Redis/jemalloc (2015), TiKV/TiDB (2020). The problems seem to fall into the following categories: Increasing memory usage by making fragmentation worse: using transparent huge pages rounds allocations up to 2 MiB. If an application allocates many separate memory regions, this can cause lots of memory to be wasted. Most of the problems have been where an application uses a large amount of memory, then frees a lot of it, leaving "holes" in the large pages. Sometimes the kernel's transparent page policy can decide to turn these back into huge pages, which causes the memory usage to increase. For example, see a Go bug (2015) and the corresponding kernel bug report (2015). The fix for Go was to only return memory on huge page granularity. This also happened to Redis with jemalloc (2015) malloc implementations that are not huge page aware may add more kernel CPU overhead: When returning memory to the operating system, if the memory allocator is not aware of huge pages, it may return part of a huge page. This causes the kernel to split the huge page back into separate 4 kib pages. This adds overhead, and also fragments memory, making fewer huge pages available, causing the kernel to do more work the next time it tries to allocate a huge page. This article about TokuDB from 2014 suggests that it ran into this problem with jemalloc. The good news is that it now seems like all major malloc implementations (jemalloc, tcmalloc, mimalloc, and glibc malloc) all have some huge page support, which should make this less bad. slow memory allocations due to fragmentation (latency): When trying to allocate a huge page, the kernel may spend time moving memory around to free up a page. See a detailed thread about impacts on the JVM (2017). The kernel's current default is to only do this for regions that have opted in with madvise. This should mean that other processes won't be penalized too much by this, but it does mean the process that called madvise could be stalled briefly when allocating new pages. One way to avoid this is to immediately touch every huge page in an allocation, to cause the cost to happen up front. This would work well for allocations that are made at program startup, such as caches. fork() e.g. Redis: Calling fork marks all of the process's pages as copy-on-write. Then when a single byte on a page is modified, the page must be copied. Redis uses fork to create a read-only "snapshot" of memory, when writing a checkpoint to disk. Since huge pages are 512X larger than "normal" pages, the time to copy a page increases by 512X. It also means the memory usage is higher, since modifying a single byte causes 2 MiB to be copied, instead of only 4 kiB. Using fork() in this way with huge pages seems like a bad idea. See details about a workload that causes this behavior (2014). References Huge Page Demo Evan Jones 2022-01-18: My huge page demonstration program. Larger Pages: Richard Sites 2022-05-06: Argues we should increase the minimum page size to 64 kiB, and maintain compatibility by using access flags on 4 kiB sub-pages. Stack Overflow: Why is the page size 4 KB? Answer by Hadi Brais 2018-04-26: a great look at the history of why 4 kiB pages were chosen. Using huge pages on Linux: Erik Rigtorp 2020-10-08: A hash table benchmark in C++ with results for both transparent and explicit huge pages. Reliably allocating huge pages in Linux: Francesco Mazzoli 2021-11-22: Includes C code describing how to verify if an address is a huge page. Intel Coffee Lake Microarchitecture (2017 aka Core 9th gen): L1 Data TLB: 64 entries for 4 kiB pages / 32 entries for 2 MiB pages / 4 entries for 1 GiB pages ; L2 unified TLB: 1536 for 4 kiB/2 MiB pages; 16 entries for 1 GiB pages.

16th Jan 2023 • 62 votes

More in programming

Writing a Demoscene Intro for the ZX Spectrum

Download Now View on pouet.net Intro In the late 80s, I spent an embarrassing number of hours hunched over my ZX Spectrum, typing in Sinclair BASIC programs and rudimentary assembler routines copied from magazines, trying to re-create the Amiga crack intros I’d seen round at a friend’s house. Obviously, they never came even slightly close - but now, many decades later, I’ve finally managed it! I’m now the proud author of a hand-rolled retro demoscene intro that runs on a stock 128Kb Spectrum. It features all those late 80s tropes: A smooth scrolltext (with ‘leet custom fonts!), a three-channel AY soundtrack, bouncing VU meters and the essential parallax starfield. It’s currently 10287 bytes of code, or 19552 bytes as a complete tape image - which, given I’ve been working on this since December 13th last year, means my average rate of code-production is a paltry ~ 455 bytes per week! This blog post is a technical overview of how I got there, some cool tricks I picked up, and everything I had to learn (and re-learn) about the Speccy and Z80 assembly along the way. It simultaneously rates as one of my favourite side-projects ever, and also the one that most often nearly triggered a foot put through my monitor in frustration. I’ll reflect on all that at the end, but for now if you just want to see the finished product, the download button is at the top of the article and the included .tap cassette tape image should load into any emulator. There’s also a YouTube capture, links to the production on pouet.net, and you can run it from within a web browser by visiting my TNFS site portal - check option 4 for recent uploads. Be Kind, Rewind But let’s skip back briefly to the late 80s. Coming from the world of an 8-bit, cassette tape loading computer, seeing an Amiga for the first time was like encountering something from outer space. Like everyone who saw one back in the day, I was blown away by the amazing graphics and sound on display, not to mention the library of ground-breaking games. But I found myself even more captivated by the mysterious (and totally badass) “intros” displayed at the beginning of pirated games. Created by the software piracy groups that had cracked the copy protection and distributed the floppy-disk based games, they were mini works of art in their own right - music, graphics and usually some cool-looking effect to show off the group’s prowess. There’s a great collection of these intros (or “cracktros”) archived on YouTube. Watch a few of those videos and you’ll quickly notice the “design” tropes that almost every cracktro shares: a cool, edgy logo at the top of the screen (bonus points if it’s dripping blood or in any way “metal”), some boastful text displayed on top of an effect of some sort - usually a scrolling parallax starfield, or rotating 3d object - and a further scroll-text full of shout outs, greetings to fellow pseudonymous crackers and adverts for illegal BBS systems galore. Needless to say, to a kid in the 80s/early 90s this was possibly the coolest thing ever. I thought this one was the absolute bomb when I first saw it. Sine-scroller, pirate BBS adverts, cool logo with a sword - and of course, a starfield. There’s something for everyone here. The music from this is burned into my brain. I think pretty much everyone of my classmates knew this intro given the popularity of Lemmings in the early 90s. Skid Row as a group are still active to this day and this is probably the quintessential Amiga cracktro of the period. Endless Piracy. Edgy. Another cool logo, sine-wave scroller, starfield and boasting text. The classics never go out of style. Another great combination of all the essential ingredients. Cool logo, even cooler text font, scrolling starfield and a scroll-text running along the bottom. Vintage stuff. Logo. Text. Scroller. But no starfield - otherwise a solid effort from Anthrox here :) The demoscene grew out of these intros. The cracking eventually faded into the background, and coders, “graphicians” and musicians all contributed to feature-length productions that showcased their abilities, competed with other groups and pushed the machine to its limits. In amazing feats of ingenuity and pure “code as an art form”, the scene lives on today, with groups producing breathtaking productions like this and this - bear in mind, both of those are running on a 7Mhz home computer equipped with a floppy disk, 1Mb of memory and a sound chip from 1985. But much as I admire the sheer skill and dedication that takes, it’s the early “single screen” scrolly-text-and-starfield cracktros I’ve always found captivating. They took on a sort of mystical quality for me, hinting at a scene and a culture I could only ever experience from the outside - which is exactly why I spent all those hours in Sinclair BASIC, trying in vain to re-create them, and dreaming of the day I’d eventually have an Amiga of my own. The Jump Back I eventually did trade up to a range of Amiga systems, joined a few “scene” groups myself and threw myself into a variety of activities until exams and the end of my teenage years beckoned. I dabbled with Z80 code back then, and at one point knew enough 68k assembly to bluff my way through - partly from the Amiga’s heyday, partly from a few “embedded systems” modules at University where I had to program a set of traffic lights or lift-controllers. Given there’s not much call for that sort of thing at my $DAYJOB, though, it had all pretty much faded from my memory. I have kept working on a bunch of projects in my spare time, and one of my favourites is my TNFS site - sort of an old-school BBS system or interactive “website” for the Spectrum, which grew out of a fun experiment to see how far I could push Sinclair BASIC. It relies on a modern network card fitted to the Spectrum, which is how I came to be chatting to “Desertkun”, another TNFS-protocol enthusiast. He’s now producing a great new WiFi network card for the Speccy, and was kind enough to send me a few of the prototypes to test out for him. I was massively inspired by his hardware and low-level coding chops, and during one of our video calls where we’d been comparing our development setups, he asked why I didn’t write any Z80 assembly myself. A throw-away comment, but the challenge was set! Now, I couldn’t face re-writing the whole site in asm, but I figured I could produce a self-contained intro to promote it in the style of the early “BBStros”, and finally be one of the cool kids with a scene production of my own :) I mean, how hard could it be ? (ooooh - foreshadowing!) Dev Environment My development environment through this was pretty straightforward, and is the same stack I use for developing my TNFS site. I just used a Makefile-driven build system which ran my code through the Pasmo assembler, my fork of zmakebas to build BASIC files, and the FUSE emulator for testing. For final testing on the real hardware, I uploaded my .tap files to my local TNFS server where I could run them on my +3. A few additional tools I have to call out because they ended up making a big difference - one is the amazing web-based “asm-editor” I discovered while looking up Z80 instructions. Not only does this site have a great reference of all the Z80 instructions, but it also has an editor where you can run example code and see how the memory and/or various registers change state. Take for example, the djnz instruction - you can build it and step through the example loop construct one instruction at a time. Or try my example of an add instruction in the screenshot to see how the carry flag works when a bit gets shifted out of a register. Although it uses a slightly different syntax to Pasmo (so I couldn’t drop my code directly in it), it massively helped when manually stepping through things. And lastly, probably the most significant debugging tools I used on this project - a notepad and pen, and my two dogs (say “Hi!” to Biscuit & Pebble…) I’ll write some more about this in the wrap-up, but this really was a highly unusual project for me, coming from decades of much higher-level languages and constructs. Most of my z80 code I only ever really understood after drawing out the bytes and bitmasks, keeping a table of register flags and drawing chunks of screen memory out by hand. And I found my evening walks with the two dogs provided ideal rubber duck exercises, although I’m not sure what they both made of my protracted mutterings about the hl register pair. Either way, debugging-by-dog is highly recommended! The Starting Point So, let’s get started. I followed a great “Hello, world!” example from futurice.com to validate my build environment. Beyond that, the first thing I wanted to do was load in my logo and background image I’d use as a “stage” for the remainder of the planned intro. I wasn’t really sure what I was going to do at this point, just that I wanted my logo at the top, and a scrolltext along the bottom row of the screen. As my TNFS site header already looked kinda demoscene-y, I made a quick edit putting in place two blue guide-bars inside which I’d put further content. Memory map courtesy of breakintoprogram.co.uk A Spectrum SCREEN$ file (usually displayed as loading screens) is just a dump of screen memory, starting from byte 16384, and running for 6912 bytes. The weird layout of this is very relevant later, but in order to display it all you need to do is load your file into that memory location. After a few hour’s work of reviewing Speccy internals and following various guides, I had a very simple starting point for my demo that served as the basis for everything else that came after. org $8000 screen EQU $4000 ; address of the first byte of screen memory, 16384 in dec scrlen EQU 6912 ; total length of the screen memory inc. attributes ula EQU $FE ; I/O port for the ULA to control the border black EQU 0 ; Spectrum colour number, the exact same ones BASIC uses start: ld a,black ; Set the border colour to black using the ULA out (ula),a ; Copy my logo header picture to screen memory ld hl,header ; HL = location of my screen file in this code ld de,screen ; DE = start of screen memory ld bc,scrlen ; BC = 6912 bytes to copy ldir ; block copy, see https://jnz.dk/z80/ldir.html ; busy loop - rest of intro goes here :P hold: halt ; sleep until the next interrupt (1/50 second) jr hold ; then jump back and sleep again, for ever header: incbin "assets/header.scr" ; my logo header/background end start Not much to look at now, but this simple starting point introduced me to important concepts like interfacing with the Spectrum’s hardware (ULA chip to start with, and AY sound chip later) via the out instruction, how to pull in binary files using Pasmo’s INCBIN directive, using the Z80’s block copy ldir instruction, the use of register pairs for 16-bit addressing, and simple branching to labels. Hello World The next step was to print something on the screen and explore some of the Speccy’s built-in ROM routines, which are somewhat analagous to syscalls on modern operating systems. There are plenty of disassemblies and guides to the Spectrum ROM available on the internet, one of the best commented and linked one is at https://skoolkid.github.io/rom/. Using this as a reference alongside the various “Hello, world!” tutorials showed me how this sort of thing is built up: at EQU 22 ; "at" control character used to position the cursor row EQU 11 ; coordinates where to print the message col EQU 9 prstring EQU $203C ; where the pr_string routine lives in ROM ld de,msg ; DE = address of the first character ld bc,msglen ; BC = how many characters to print call prstring ; print the lot ; busy loop is the same... msg: db at,row,col ; equivalent of "PRINT AT 11,9" in BASIC db "Hello, world!" msglen EQU $-msg ; 16 bytes in all, pasmo shortcut, $=program counter I ended up mostly not using the ROM routines in my code as they dragged in all sorts of things I didn’t need, but it was massively useful to understand how they worked as they introduced me to yet more commonly-used constructs. For example, the PR_STRING routine defined here shows how you can build a loop over each character. If you’re just starting out, I highly recommend going over the 8 lines in that routine with a notepad and pen, working out the contents of the registers and following the loop constructs. I also made a version of it in asm-editor you can try. If you click that link, you’ll see a version of the code loaded into the web editor. Click “Build”, and then step through the code using the “Step” button - although no text will be actually displayed (I skipped over the call to the Spectrum ROM “restart” vector that does this), you’ll see the various states of the registers and for example the BC register counting down as each byte of the string is processed. Adding Some Style Problem is, the Speccy’s built-in font is not exactly dripping with demoscene credibility. I wanted to use some stylish fonts and this turned out to be super easy - a quick search turned up Jim Blimey’s awesome font collection, which included a ready-to-use set of assembler files and some instructions which soon led me to these additions in my code: ; CHARS is the address the ROM's printing routine reads to find the font. ; Picking our own font is simply a matter of over-writing this chars EQU $5C36 ; from Jim's docs - POKE 23607=5C36 in hex ld hl,myfont-256 ; HL = font address - 256 as per docs ld (chars),hl ; from now on the ROM draws with it! ; rest of code is the same myfont: include "textfont.asm" ; "Cartoon" font from jimblimey.com There we go! Now that’s looking a little more elite. Sorry, I mean 31337. Strap in folks, we’re leaving lamer city… So at this point, a month or so in to my dabblings and I’d started to get a reasonable understanding of common idioms and was starting to feel like this was a project that might actually go somewhere. The problem started when I moved on to trying to implement actual demo effects: It became very apparent, very quickly, just how much I didn’t know about how this all worked. Not to mention the fact that at this level, you’re really closely exposed to the physical hardware intricacies, including the design decisions and trade-offs that the hardware designers had to make when working with the extremely limited specs of the early 1980s. Cursed Screen Layout The first such problem - and the cause of probably 90% of my pain - is the Speccy’s extremely weird screen layout. Rather than standard bitmapped display you might expect on more modern hardware, it is instead split into 3 sections, each with a set of interleaved rows (so if you keep adding 1 to a screen address, eventually instead of reaching the next row, you’ll instead end up 8 rows down, and so on until you hit the bottom of the section and then loop back to the row underneath where you started!) followed by a block of “attribute” bytes which determine the colours of each 8x8 block. The attribute blocks are the reason why each 8x8 character cell can only have two colours (a PAPER and INK attribute) which led to the garish “colour-clash” of spectrum games and distinctive style where artists try to keep inside 8x8 blocks as much as possible. But it was the layout of the bitmap portion that is such a mind twister. Download the video You can see this illustrated whenever a game reads in a loading screen from tape. You can see each section built up with the interleaved rows one at a time, and then finally the colour and other attributes (like flashing ). There’s a lot of detail at the fantastic Break Into Program site. In the defense of the designers, they were working with extremely limited hardware and I don’t think the Speccy was ever imagined as a games machine. When you start shuffling bytes around, you realise that this approach is really optimised for displaying text which is neatly arranged into 8x8 character boundaries. For example, using this “scrambled” bit order, if you have a screen address in the hl register pair, you can quickly get to the next pixel line of a given address by simply incrementing the “high” byte. There’s a bunch of other “cheap moves” you can make by simply shifting bits around: Move Instruction Right 8 pixels inc l Left 8 pixels dec l Down 1 pixel line inc h Up 1 pixel line dec h Down 1 character row add 32 to l It was a reasonable choice for a machine that would probably spend a lot of it’s time displaying BASIC program listings - it’s only when you start trying to write demo or sprite routines that it starts to feel really weird. This also means you’ll pretty quickly need a routine to convert X,Y addresses to the relevant memory addresses. Again, L Break Into Program has a useful routine and if you disassemble more or less any spectrum game or demo, you’ll find a version of this procedure somewhere. And yes, this all became horribly relevant later on… The Scroller Download the video Admittedly, not the most interesting demonstration - but this was the first time I had made something move on the Spectrum’s screen with assembly! I watched this with pride more times than I care to admit :) I had a snazzy logo and “Hello World” text, but that doesn’t make for a very interesting intro! The first effect I wanted was the scrolltext - without that, it’s not really an intro. Now, the Amiga had all kinds of hardware sprites, blitter operations, custom chips but the Spectrum had none of that. I was going to have to work out how to do things the hard way - “banging on the metal”, literally by shifting bits around the screen memory by hand and having the CPU do all the work. This is where understanding the Speccy’s weird screen and character cell layout is so important. It turns out there’s a neat trick as long as I stay inside one character row - there’s a RL instruction, which takes a byte and “rotates” it left. It inserts whatever is in the carry flag into the rightmost bit, and whatever gets shifted out ends up in the carry bit again. That means if you string a bunch of them together, you can move a set of pixels across the screen - the moment they “fall off” one character cell, they end up in the carry flag and then the next rl instruction inserts them at the beginning of the next character cell to the left. Repeat 32 times, and you’ve just moved a pixel (or set of pixels) across a line of the screen: linestart EQU $4880 ; leftmost byte of the line 12 rows down lineend EQU linestart+31 ; rightmost byte column ($489F) linelen EQU 32 ; one whole line is 32 bytes (character cells) across dot EQU %00000001 ; the dot "shape", just one pixel lit at the far right end newdot: ld a,dot ; load the dot shape (only rightmost pixel lit) into a ld (lineend),a ; store it in the rightmost byte of the line, pixel is now lit frame: halt ; wait for the next frame, otherwise it whizzes across too fast to see ld hl,lineend ; hl = last (rightmost) byte of the line ld b,linelen ; loop counter, 32 bytes to work through or a ; trick to clear the carry flag, or against itself leaves a register ; unchanged but clears various bits including the carry flag ; see https://jnz.dk/z80/or_r.html shift: rl (hl) ; rotate this byte left (00000001 -> 00000010) dec hl ; point hl at the next byte to the left djnz shift ; loop construct: b=b-1 and then jump back to shift label until b=0 jr c,newdot ; now we've shifted the whole line, so if the carry flag is set now it means ; the dot has just left the screen, so we jump back to the start jr frame ; otherwise it is still somewhere on the screen, so keep shifting! Download the video Hell yeah. It’s almost a proper scrolltext now! Wrapping this in another loop that increments h each time (remember - that gets us moving down a scanline) gets us moving an entire character cell. Here you can see it moving an entire row of my “Hello world” message. There was however a lot more work needed to make a proper scrolltext, with each letter appearing smoothly. I started off by just printing an entire character at a time on the right-hand edge of the screen - it worked, but was pretty ugly as you saw each new character appear at once in the right-hand side of the screen, scrolling 8 pixels over and then the next character flashed up. Instead, I wanted to make each character appear pixel by pixel and that required a bit more bit juggling. The routine I ended up with effectively streams each character in, line by line, pixel by pixel using the font data directly instead of calling the ROM print character routine. It does this by looking up the ASCII code for a character, and then fetching the corresponding font representation into a 8-byte buffer, one byte for each line of data. The font data starts with the space character (character code 32), so a lookup is simply font code base address + (ascii code - 32) * 8 to get to the bits for that letter. Arranged into an 8x8 grid, the bits for the letter H in the font data look like this. For each row of bits, I shift the line left using a neat trick. The byte is loaded into the a register, and then by adding itself to itself - add a,a we shift the value left (in binary, multiplying by 2 moves everything over one bit) so that the pixel I want to draw ends up dropping into the carry flag. This is an idiomatic way of doing it in Z80 code as it’s faster and smaller than the sla instruction. And every cycle quickly adds up when you’re re-drawing 256 bytes every frame! The character buffer then looks like this, with the top line shifted. Now, with the hl register pair pointing at the correct location on the screen, I can then use the rl trick discussed above. This shifts a scanline from the bottom character row of the screen left by one pixel and draws my pixel in the rightmost position by moving it in from the carry flag. Looping 32 times over this moves the entire row by 1 pixel with my new pixel inserted at the right. I then repeat this step again using inc h to move down one scan line until the entire character column has been drawn. At this point, the character buffer looks like this, and all 8 lines of the bottom screen row have all been shifted left by one bit by looping over all 32 character columns. The whole thing then repeats another 7 times until the entire character has been smoothly scrolled onto the screen. So just to re-state this because I think it’s worth the emphasis - just to scroll a message across the bottom of the screen, we’re having to loop over and re-draw 256 pixels every frame! It shows how much faster assembly is than the BASIC interpreter built into the spectrum’s ROM. I found it amazing to see my code finally working and imagining all the bits flying around and registers flapping away. It really makes me appreciate just how much effort went into creating the games I played back then. Music The original Amiga module I converted. A proper 1980s ear-worm! Of course, any good intro needs some music. On the Amiga, the standard was the “tracker” module format, which has a long and involved history of different forks, versions and tweaks. A song is built up from a series of patterns, each made up of rows of instructions. Each instruction usually includes note or pitch information, which sample to play and various parameters such as volume, effects - or in the case of some instructions, which position in the song to jump to. In many ways, it’s almost like a programming language for music. Using ProTracker as an example, a typical note cell is 4 bytes, shown on-screen as something like C-2 01 C20. That breaks down into three fields: the note and octave (C-2), the sample number (01), and the effect and its parameter (C20 - in this case, “set the volume to $20”, which is half of the maximum $40). A close-up of Protracker playing a tune. Note the VUmeters - another classic demo effect I would pinch later on! For an impressive demonstration of what’s possible with a tracker and to see what the note data looks like on-screen, check out the work of h0ffman, and in particular his winning “Professional Tracker” entry from the Revision 2014 competition. He’s an undisputed master of the science (or art!) of tracking, and his “Secrets of Protracker” talk gives a great overview of what’s possible. The Amiga’s sound hardware far eclipsed anything else on the market at the time, and the ZX Spectrum is paltry by comparison. The original 48K models only offered a rudimentary “beeper”, but the later 128K models included a 3-channel AY-3-8912 sound chip. This was very popular in 8-bit micros of the time, and a more-or-less identical variant was also used in the Atari ST. While it only offers basic waveforms and sound processing, it does enable multi-channel “chip music”, and so it became the mainstay of the ZX Spectrum demoscene. It also spawned a variety of SoundTracker clones on the Spectrum itself, although most musicians these days prefer to work in modern tools like Vortex Tracker II, which runs natively under Windows. The Conversion Pex looking back on his demos - this starts at the point where he features my letter and plays a bit of my cover version! For my intro, I wanted to port an Amiga module - and I had the perfect one in mind. One of my favourite Amiga music disks was “Sounds Of Gnome”, released in 1989 by the Swedish duo “Mahoney & Kaktus”. Mahoney also wrote NoiseTracker, one of the first really widely used trackers on the Amiga, and the program that served as my teenage introduction to making computer music of my own. Back in 2018 I made a rock cover of one of the other tunes on that disk, and wrote to Mahoney (real name “Pex”) about it. He ended up showing my “music video” at a demo conference, which I am eternally grateful for! So it seemed only fitting that I mangle another song from that collection with a Spectrum conversion… Sorry, guys! I picked the track “Milkman” which was written by “Glue Master”, an associate of Mahoney’s who had a few of his tracks featured on the compilation. It’s an ideal track for converting: It’s short (only 7 patterns in total), most of those patterns share the same chord sequence, and it looked fairly easy to squeeze the original 4 channels down into the Spectrum’s 3. Plus, it’s an incredibly catchy tune and I knew it well - I’ve been listening to it for 35+ years and often jam along to it on guitar or bass. The conversion started off pretty easily: all I really had to do was copy the patterns note-for-note from the Amiga mod, which I had open in OpenMPT as my Windows tracker. Below is a session with both trackers open on the same pattern - the original Amiga mod on the left, and my 3-channel Spectrum conversion on the right. Note the 11.7 in the 3rd channel of the Spectrum version. This is a “pitch slide down” effect in Vortex Tracker syntax, which drops the pitch by about a quarter-tone. It’s repeated on the next line, so the overall effect is a slide down from the A# that leads in to the next bass note. The original Amiga mod does the same thing using its own syntax - those are the 202s you can see on the same notes, at the bottom of the 4th track. Using just a single “beep” sound for everything was enough to check everything was working, and after a few weeks of hacking on it and re-arranging things in the evenings, I had a basic version which sounded surprisingly good for a first draft: Download the MP3 instead. I have to give a special mention to this forum post which was a massive help getting me started. It’s probably the best introduction to Vortex Tracker I’ve found - many, many thanks to the original author for taking the time to write it all up! The real challenge was making it sound as close to the original as possible. That meant building up a library of better-sounding samples for the different parts, and making extensive use of Vortex Tracker’s “ornaments”. Vortex Tracker comes with a great selection of sounds, and fortunately I’m also a weirdo who likes to listen to chiptunes in the background while I work! So whenever I found something particularly enticing, I filed it away for later pilfering inspiration. A Vortex Tracker sample isn’t really a “sample” in the Amiga sense of a recorded sound - it’s a definition of how a note sounds, one line per frame. Each line can mix in a tone or the white noise generator (useful for snare effects and suchlike), along with various other parameters. Ornaments, on the other hand, give you extra control over what pitch a note plays - and this enables really useful tricks like “arpeggio chords”. For example, an ornament of 0,4 makes the channel switch rapidly (25 times a second) between the note being played and the one 4 semitones above it. It happens so quickly that it sounds much like two notes played at the same time, which means you can build up full-sounding triad chords using only two channels. Take the opening chord in my fully converted version, Cm: It plays C in the first channel and the minor 3rd (D#) in the second, then I apply an ornament to the second channel to bring it up 4 semitones to the 5th (G). That gives all three notes of the chord, while keeping the 3rd channel free for other parts. As well as making much more efficient use of the limited 3 channels, this also gives Spectrum music that characteristic “warbling” sound, which I find really appealing in a retro kind of way! Between tricks like this and samples that mix tones with white noise (to make a combined “bass-snare” sound, for example), I managed to condense the full track down to 3 channels. Many months later, I have to say I’m really pleased with the final result. Playback The original site that was home to Vortex Tracker, documentation and other resources appears to be offline at the moment. I managed to grab a copy of everything I needed from archive.org - you’ll want the PTxTools.7z file for the playback routines discussed here. The playback was simple in theory: As this overview notes, you basically just pull in the player routine, include your module file and call the playback routine once per frame in your main loop. The catch is, none of the source code versions supplied in the archive worked with my Pasmo assembler. Fortunately, there is a pre-compiled binary object shipped alongside the source (VTII10bG in the PTxTools/PT3Play directory). This just has to be loaded in at address $C000 - this cannot be changed, as it has lots of absolute addresses baked in. My code to handle module playback now looks something like this, with the binary module loaded in place: ; Define the start address of the player routine and functions we need player EQU $C000 ; hard-coded org address of binary player plinit EQU player+3 ; init function in docs, module address in hl plplay EQU player+5 ; play and move on one frame ; from the docs - this "analyzes PT3 module header and prepares ; corresponding note and volume tables" ld hl,moduleimg call plinit ; main loop hold: halt call plplay call scroll ; other effects / routines go here... jr hold moduleimg: incbin "assets/music.pt3" Starfield Download the video Well, that didn’t work as hoped. TNFStro - tortoise edition. This brings me to the main event. No self-respecting cracktro is complete without a starfield! My first, naive approach to the classic starfield effect was to scatter random stars across the screen, then move down each scan-line applying the same rl trick I’d used for the scroll-text. I figured I could get parallax by shifting each row a different amount: One pixel for the first row, two for the second, three for the third, then back to one again, all the way down the screen to give the impression of several “fields” of stars moving at different speeds. It turned out there were two major problems with that approach. Firstly, shifting an entire row smeared whatever else was on it along with the stars - which I’d expected, and had filed away as a problem for future me. The bigger issue was speed: by the time I’d finished the first three rows I’d already performed hundreds of shift operations, and it was nowhere near fast enough to fit inside a single frame. Everything crawled across the screen, and the music playback slowed down so much that you could actually hear the arpeggio ornaments warbling away as separate notes. Clearly I was going to have to keep track of the individual stars instead. I found this routine, which was more-or-less what I had in mind and started me off with the idea of a structure to hold the state of each star. It also uses a screen address lookup much like the one from “Break Into Program”. Download the video Dammit. Back with another funeral dirge rendition :( That got things moving, but the co-ordinate lookup and tracking proved expensive to do (it has to run for every star, every frame as well as keep track of the old position for erasing) and I’d been ignoring the bigger question how to display stuff on top of the starfield. My original idea was simply to draw the stars and then paint text over them each frame, which blew the frame budget just as comprehensively as my first attempt. If I wanted something more interesting than an empty starfield, I’d have to keep track of which cells were occupied by text and avoid drawing stars in them in the first place, rather than over-painting them every time. After lots of scribbling in my notepad and visualising rows of bits, I eventually solved both challenges by “cheating” fairly liberally. So now, I don’t generate a random starfield at all. Instead, I built a table of pre-calculated Y and X position pairs: stdata: defb 109, 25, 88,182, 42, 96, 155,226 defb 59,254, 137,169, 160, 84, 125,193 ; ... and so on, for 32 stars ... This saves faffing about with an RNG, and once I have a layout that looks good I know it’ll always look good. I can also “fudge” things and ensure no two stars share the same y co-ordinate which sidesteps a whole class of problems like stars sharing a scanline, and having to deal with them overtaking each other. The “random” layout is generated by a simple Ruby script: #!/usr/bin/env ruby PAIRS = 32 PER_LINE = 4 # pairs per line Y_RANGE = 40..175 # exclude rows taken up by my logo & bars X_RANGE = 0..255 raise "y range too small" if Y_RANGE.size < PAIRS # no duplicate y values ys = Y_RANGE.to_a.sample(PAIRS) pairs = ys.map { |y| [y, rand(X_RANGE)] } pairs.each_slice(PER_LINE) do |row| body = row.map { |y, x| format('%3d,%3d,', y, x) }.join(' ') puts "defb #{body.chomp(',')}" end When the routine initialises, I convert those co-ordinate pairs into a table that tracks the state of each star. So rather than storing a position and translating it to a screen address every frame, each of my star records now looks like this (offsets from the base address): STSCR EQU 0 ; screen address of the byte the star is in, e.g. $4123 STOCC EQU 2 ; a pointer to the "occupancy check" table cell STMASK EQU 4 ; the star's bit pattern, e.g. %00010000 STSTEP EQU 5 ; "speed" - num. of pixels this star travels per frame The key thing is that there are no X/Y co-ordinates at all. For each star I store the screen byte it sits in and the bit mask within that byte, so it’s already in the form the screen writes need. That means no address conversion per frame, just simple bit shifting and rotation. Moving a star is then dead simple. I rotate its mask left with rlca, and when the bit rotates out of bit 7, it lands back in bit 0 with the carry flag set. That’s the signal I need to move the star one character cell to the left, which is one of the “cheap moves” from earlier. Because I’m tracking which cell each star is in, the collision check comes almost for free. That’s what the second pointer is for: STOCC (Star Occupancy) moves in step with STSCR through a table holding one byte per character cell. The “typewriter” routine sets a byte to 1 for every cell containing a text character or the cursor, so checking whether a star is hidden behind text is a single or instruction. If the cell is occupied, I skip drawing the star but carry on rotating and stepping it along until it reaches a cell where it can be displayed: ld l,(ix+STOCC) ld h,(ix+STOCC+1) ld a,(hl) ; A = the occupancy check for this cell or a ; test A against zero jr nz,stmove ; it's occupied, so leave the screen alone Parallax is still handled by moving each star a different number of pixels per frame, but the cost is a lot lower this time as I’m only touching the cells the stars actually occupy, rather than every byte of every row. Download the video That’s looking more like it! The typewriter routine is a simple copy of the font data from memory, and is very cheap as we can use the “cheap moves” to quickly fetch the 8x8 block. I also skip drawing any space character so it leaves the “occupancy cell” unmarked. This means the stars keep drifting through the gaps in the text - you can see here the odd star passing in between the words. I switched to ALL CAPS writing for the final version which helps the effect even more as the font is quite blocky, so you don’t really notice stars skipping the spaces inside a glyph at all. Misc Notes A few odds and ends that didn’t warrant a section of their own… VU Meters Some sort of graphic display bouncing along with the audio playback was another common early demo trope. I did originally consider a real-time graphic equaliser, but that would have been far too complex, probably in terms of spare cycles per frame, and definitely in terms of my limited mental capacity at this point! So I settled for a simple set of bouncing meter bars instead. It’s worth a mention mostly because it gives me an excuse to link to the awesome chibiakumas website! I just love the late 90s web design on display - one can argue that readability and accessibility take a hit, but it’s just so much fun to encounter a site that still looks like this. It’s a clear labour of love and there’s a wealth of content there as well, if your eyeballs are up to it. Their guide on Making Sound with the AY-3-8910 was what showed me how to get the data I needed to draw the meter bars. The examples write a register number to $FFFD to select a register, and I realised that once a register is selected, I could use the in instruction to read its value back out instead of writing a new one. As the page says, R8, R9 and R10 hold the channel amplitudes, so they feed nicely into the height parameter for drawing a bar. Getting the amplitude for channel A is then as simple as: ld a,8 ; Channel A register call ayread ; ... rest of code here ... ayread: ld bc,$FFFD ; Register select port out (c),a in a,(c) ret Twinkle, Twinkle, Little Star This is a simple effect that makes the header logo a little more interesting. I’m not sure where I originally got the idea - I’ve definitely seen something like it on a few late 80s/early 90s demos, though. All I wanted was to pick random star dots in the logo background and animate them. Here’s the header image loaded in ZXPaintbrush with the character cell grid showing. By happy chance, there are four stars which each sit neatly inside a single character cell with enough surrounding space, so they can be used to give an animated “twinkle” effect by drawing a cross out from the centre point and back in again. These dots map to the following co-ordinates, which target the top scanline of each fully-grown star (two pixels up from the centre): twkdata: defb 1,5 ; char row 0, col 5, centre y=3 ink 5 defb 1,20 ; char row 0, col 20, centre y=3 ink 1 bright defb 26,7 ; char row 3, col 7, centre y=4 ink 4 defb 25,22 ; char row 3, col 22, centre y=3 ink 6 bright The “twinkle” routine itself is simple enough: it adds a pixel on either axis to grow the star, waits a few frames, then shrinks it back down again. The interesting bit was how I made the twinkle order pseudo-random. Remember that my starfield was entirely pre-calculated from a data table generated by a Ruby script, which meant I’d never actually needed a random number generator in assembly. From Jonathan Cauldwell’s “How To Write Spectrum Games” e-book, I found another great “hack” which simply walks through the start of the Spectrum’s ROM, picking out random-looking bytes as it goes. As he says, he uses it in most of his games, and it does the job in a really simple way - as long as you stay below the block of structured, repeating data that sits 8Kb into the ROM. twkrand: push hl ld hl,(twkseed) ld a,h and 31 ; keep it within the first 8k of ROM ld h,a ld a,(hl) ; the "random" byte inc hl ld (twkseed),hl pop hl ret Out Of Space About halfway through writing the intro, I hit a fairly predictable problem: I had run out of memory. In an attempt to keep everything self-contained in one block of code, I was pulling all of the assets (the screen background, the player binary, the music file etc.) into the program itself, and then using the ldir block copy instruction to move each one into its correct location. Since that meant effectively storing every block twice, and the player routine had a hard-coded start address of $C000, I quickly ran out of room and my code started crashing into the playback routine. The simplest option was to split things out into separate code blocks, load each one directly to the address it needed to live at, and wrap the lot in a multi-stage BASIC tape loader: 10 CLEAR 32767 20 BORDER 0: PAPER 0: INK 0: CLS 30 LOAD "" CODE 40 LOAD "" CODE 50 LOAD "" CODE 60 RANDOMIZE USR 32768 This loads the main program, then the player routine directly into $C000, and finally the background screen straight into screen memory. It does mean the background starts appearing before the demo has fully loaded, but as I imagine most people will be seeing this running in an emulator or on my TNFS site, it doesn’t really matter. Plus, at this point I was in danger of disappearing down yet more rabbit holes (I still really want to work out how to do multi-colour border effects!) and I’d never have got this thing released. The Zen Of Z80 This whole project is a really weird one to look back at. On the one hand, I’ve fulfilled a childhood ambition and have something I’m very proud of. It’s also pretty unusual these days to end up with a binary where you can say pretty much what every single byte is doing and the story of how it got there. But on the other hand - I now have an answer for why I don’t code in assembly: It’s because I value (what’s left) of my sanity! The thing is, in order to write code like this you have to start thinking like the machine itself. You have to visualise the registers and the status flags flapping away, graphics as lines of bits slotted into strange orders, loops and conditionals as binary logic and so on. Getting this close to the hardware definitely brought about a greater sense of attachment to the hardware of my childhood, and it’s easy to see why assembly coders and sceners get so passionate about it. That said, I’m in no hurry to start re-writing my body of work in assembly! The projects I really enjoy are those that give me an excuse to learn something for the sheer hell of it, and to slow down a little from the ever-increasing velocity and demands of the modern work world. Going back to Z80 code is probably about the furthest I could have taken this, short of going into hardware hacking. I found it at times an intriguing puzzle, often a frustrating exercise that nearly had me throwing in the towel at several stages. This project has certainly taken the longest to go from the “idea” stage of any given feature to any kind of meaningful output. True, I didn’t spend every day of the last year working on it - my actual coding time was probably only a few hours over a couple of evenings a week. But I’ve certainly been thinking about it and pondering it most days (as my dogs will attest). The biggest breakthroughs and “aha!” moments usually didn’t come from behind the keyboard; they came from scribbles in my notebook and thinking about processor states while doing something unrelated. It has however given me massive appreciation and respect for the coders who pull this stuff off and make it look easy. And that goes double for those kids and bedroom coding superstars who managed all of this back in the 80s, and had to work it all out by experiment themselves. I only managed to get this far because of numerous books, online tutorials, GitHub repositories with sample code, YouTube videos… I can’t imagine how much longer this would have all taken me if the only resources I had were my Spectrum, a cassette tape recorder and a notepad. So, as I draw a line under this project - for now! - I raise a glass, and in the words of h0ffman: “Shout out to the hackers, graphicians and protrackers.”

14 hours ago • 1 votes
CalVer 26.0: 10th Anniversary Edition

A decade ago, a little bit of history was made. I didn't realize it, but a colleague made a great point, one of those real mind-changing points that seem too obvious to admit same-day. But, the next day, calver.org was born. At the time my team maintained the Python infrastructure for eBay and PayPal, and we were stuck deciding whether we were really ready for a "major" 1.0 release. Semantic Versioning was the only game in town and "major" means "big", right?! Thankfully, a wiser colleague mentioned: Ubuntu and Twisted don't struggle with version number debates. They slap a date on it and keep shipping. In fact, their date-based versions were even better because you always knew where it stood, in terms of updatedness and support. The only problem is that no one really knew about it. Somehow, this problem solving versioning alternative, arguably as old as history itself, had gone nameless for millenia, conspiring to make me feel foolish in an office meeting. Never again! Ten years of adoption Fast forward 10 years, we've seen CalVer adopted by Apple, Nvidia, JetBrains, and countless others. (We have a timeline!) The site may have more inbound links than any other project of mine. Apple made the biggest jump, at WWDC 2025: iOS went from 18 to 26 macOS from 15 to 26 watchOS from 11 to 26 and visionOS from 2 to 26 All landing on one, consistent number like a car's model year. I still remember the texts from the Venn diagram fanbase of my friends who love Apple and reasonable versioning. No such texts from when NVIDIA announced calendar versions across the GPU Operator, RAPIDS, and its monthly NGC containers, but still very cool. Open source, too: Home Assistant, pip, CockroachDB, and yt-dlp all ship on dates, with plenty more on the users page. The conversation even reached the language core; PEP 2026 proposed versioning CPython as 3.YY, and it almost happened, too. And it's never too late, time marches on! Fixing the notation But I don't think I got every detail right from day 1. That's the main motivator for CalVer 26. It's high time to start righting a couple idiosyncratic token design choices, starting with some additions: Meaning Before 26.0 26.0 Full year YYYY YYYY Short year (6, 16) YY YY Zero-padded year (06, 16) 0Y 0Y Short month (1 ... 12) MM M Zero-padded month (01 ... 12) 0M 0M Short week (1 ... 52) WW W Zero-padded week (01 ... 52) 0W 0W Short day (1 ... 31) DD D Zero-padded day (01 ... 31) 0D 0D Seeing double First, the doubled letters. From the first version (16.6), MM and DD meant the unpadded month and day, which reads backwards to anyone who knows date formats (ISO 8601's YYYY-MM-DD, Java, moment.js, day.js), as some community members correctly pointed out. I was ready to flip them, until I checked what people actually use: most projects with a YY.MM.MICRO badge (conda, Twisted, Ansible's tooling) don't pad, and more than a dozen other version management tools (like bumpver and bump-my-version) implement the old meaning. So, it's too late to flip MM's meaning. Instead, 26.0 deprecates it and offers a more explicit and hopefully clearer option: M is the short month, 0M the padded one, and MM is a technically-retired synonym for M. In case you're wondering, the explicit 0M was me being overinspired by Ubuntu's approach, perhaps: 6.06 pads its month but not its year, and YY.0M says exactly that. To pad or not to pad I think it's worth a detour into why padding is even a thing anyways. It's become important now that new ecosystems have emerged that enforced SemVer formatting semantics, and I wanted clear guidance about on the spec site. SemVer forbids leading zeros outright, so Cargo rejects 26.04.0 and Go modules reject v26.04.0. Even Python's packaging spec normalizes leading zeros away, so you can tag 2026.08.19 if you want, but PyPI will still show 2026.8.19. NVIDIA's GPU Operator docs put it this way: "Zero padding is omitted for month to be still compatible with semantic versioning." CalVer was always intended to drop in where SemVer was used. So 26.0 recommends unpadded (YYYY.M.D) as a sane "pure" default for software libraries. But libraries are not the only objects of versioning schemes. The exception is a version that becomes a filename, an image tag, or an object-store key that gets listed lexically. There, padding keeps 26.10 sorted after 26.09, which is why Ubuntu, NixOS, and NVIDIA's own NGC containers pad. More evidence of teams designing their versions. We love to see it. Our FAQ has a longer discussion of the padding issue, as well. Optional segments There was never any rule against them, but 26.0 makes optional trailing segments more explicit with square brackets. Now, yt-dlp's scheme can finally be written down: YYYY.0M.0D[.MICRO]. For the CalVer badges I could find on GitHub, they all stay valid for now. I've got a note on the deprecated spellings and a new copy-paste badge section for new ones. What else is new? It's always a great time to add more citations to the site. A spec changelog; the spec now versions itself: 16.6, 19.7, 26.0. A FAQ: breaking changes, same-day releases, and padding. The users page, rebuilt by category, with past users of note (schemes change; that's fine) and tooling. Case studies: Apple and NVIDIA in, yt-dlp replacing youtube-dl. Much of the thinking behind these changes happened in the GitHub issue tracker over the years, and 19 or so issues close with this release. That's where ideas for CalVer should go, so by all means, open an issue, and we'll get it sorted! In due time, of course. In closing, I can't believe I still love belaboring these numbers so much. Thanks to all (but especially Mark, Glyph, Hugo, issue reporters, translators, and maintainers) for the discussion, and ultimately making the most timely versioning system a timeless classic. See also 2016 announcement Designing a version My Yap on Why CalVer beats Semver

yesterday • 1 votes
"You didn't do it right"

Four sincere attempts at OKRs, four failures, and every time: "you didn't do it right." Maybe the framework doesn't fit you -- so how do you find one that does?

yesterday • 1 votes
We solved SQLite's single-writer limitation

Multiple concurrent writers. Multiple processes. Same SQLite. No modifications.

3 days ago • 1 votes
If your team is happy, are you doing a good job?

Brilliant jerks, ZIRP-era managers, and how psychological safety lost the plot. Part 3 of my conversation with Dr. Cat Hicks.

4 days ago • 1 votes
📚 BoredReading

You seem to be enjoying this.

Join free to unlock everything.

Create free account

Already have an account? Sign in