Chameth.com - posts like apple-google-aligned-incentives, over-the-top-optimisations-in-nim

How tech companies failed to build the Star Trek computer

2025-07-16T00:00:00Z

A computer core room on the Enterprise-D

In most Star Trek series, the ship or station computer is ever-present in the background, waiting to be called on by the main characters¹. It nearly always does exactly the right thing, and there’s little limit to the functions it can perform. Take this mundane example from DS9:

KIRA: Computer, establish link with the Bajoran Medical Index for the Northwestern District.
COMPUTER: Link established.
KIRA: Access all information on Doctor Surmak Ren.
COMPUTER: There are no records matching that name.
KIRA: Try the Northeastern District, same search.
COMPUTER: Doctor Surmak Ren, currently serving as Chief Administrator of the Ilvian Medical Complex.
KIRA: Computer, open a channel to the Ilvian Medical Complex. Administrator’s office.

The computer is doing some kind of networking to a database only identified by name. It does a search and summarises the lack of results. It then repeats the process with another database, and succinctly announces the results. Finally, it opens a communication channel to a specific room in a facility, based only on its name.

This whole interaction is remarkably boring². Kira doesn’t have to know any URLs or API endpoints, or what protocol she wants to use. She doesn’t have to open a specific app and then login and then try the query again. She just says what she wants and the computer does it.

It seems like this should be one of the most easily obtainable bits of sci-fi wizardry with our current technology. We have multiple massive companies throwing lots of money at digital assistants, LLMs that are improving at an insane rate, but we’re somehow not even close to the usability or usefulness of the Trek computers. What gives?

Boring is, well, boring.

Larry Page once said something that might help explain it:

The Star Trek computer doesn’t seem that interesting. They ask it random questions, it thinks for a while. I think we can do better than that.

This is the same Larry Page that founded Google, whose mission statement is “to organize the world’s information and make it universally accessible and useful”. Of all people, surely he should find an omnipresent computer that can answer ‘random questions’ interesting?! It seems like it should be the epitome of Google’s mission!

Google’s “better than that” seems to have been to stuff LLMs into every product they can, even when you don’t want them there. Even when they’re worse than the normal content they displace. These things look exciting when they’re part of a scripted demo at Google I/O, but they fall flat and just get in the way when they’re exposed to the reality of day-to-day use.

The Star Trek computer is the opposite: it isn’t snazzy, but it is genuinely useful. That means it’s not an attractive target for the company execs who want marketing opportunities, and it’s not appealing for engineers who need to demonstrate “impact”. But even if Google did try to make the Trek computer, there are other problems…

Assistants need to be free

A significant amount of tech companies’ business models currently revolves around trapping users in walled gardens. They want you using their ecosystem; that way they get more data from you, and you’re more likely to spend more money on their other offerings that work together. There’s barely any incentive to allow any kind of interoperability with other platforms outside carefully contracted integrations.

I remember trying to help a family member move their photos from iCloud to Google Photos. At one point they turned around and said, exasperated, “why is this so hard? Aren’t they both in the cloud?!”. It’s easy to dismiss that as someone who hasn’t quite grasped the fundamental idea that “the cloud” is just someone else’s computers, but that’s not the whole story. There’s no reason why there shouldn’t be a quick and easy transfer: both services already allow uploading and downloading, there’s just no incentive for the companies involved to make it so³.

These kinds of misaligned incentives and walled garden business models cause even more problems when it comes to digital assistants. Siri is basically never going to be able to interact with, say, your Google Drive; ~~Bard~~ Gemini is never going to be able to send a message via iMessage. Even when there are appropriately blessed interactions, they’re so clunky. Can you imagine Captain Picard saying “Computer, ask the turbolift skill to take me to deck 5”?

Someone else’s computer

Software issues aside, there’s still a key difference between the Star Trek computers and our current batch of digital assistants: where they run. The Trek computers are all housed within the ship or station they serve; they can connect elsewhere to gather information, but they run entirely independently. If they go wrong, a local engineer can go in and fix things. While some of our assistants may have physical hardware in your home, they don’t work without a vast cloud apparatus behind them. If your Internet connection fails, they become paperweights. If the company running them decide to remove some functionality you depend on, you have no recourse.

That kind of helplessness isn’t limited to assistants, either. There’s a rapidly growing trend of being unable to modify or repair hardware you fully own and control. Part of this is just that they’re becoming more complex: it’s a lot harder to replace a microchip than a gear, but companies are also going out of their way to make it more difficult for users through draconian DRM regimes⁴ and aggressive intellectual property enforcement. If the US Navy can’t repair their own equipment because a corporation says so, what hope do consumers have?

We’re approaching a point where you don’t actually own anything. Software is cloud and subscription based, hardware is unrepairable. Even cars can be remotely updated and have features added or removed. The Federation wouldn’t allow a third party control over their ships⁵, so why are we so happy to put up with it in everything we consume?

A small ray of hope?

The most promising way of tackling all of these problems is through legislation. The EU’s Digital Market Act is an attempt to force ‘gatekeepers’ like Google, Apple and Meta, to allow third-party access to their services. It seems like a pretty reasonable approach, but the tech companies are unsurprisingly resisting it. Apple in particular have gone out of their way to refuse to comply, and when forced to do so have limited the functionality to people in Europe. Still, the DMA is a promising start, and if similar legislation is introduced (and robustly enforced) elsewhere it might start forcing companies to behave a bit better.

There are also smaller companies that actually do the right thing. Framework make laptops that are user-serviceable; Fairphone do the same for mobile phones. Smaller software companies provide useful, open APIs. The average person on the street will probably have never heard of these, unfortunately, but they do still exist. Maybe as the bigger tech companies tighten the screws more, people will turn to alternatives like this? Or maybe we’ll just keep accepting that our computers work for everyone but us?

Unless, of course, the computer is playing the role of the episode’s MacGuffin and has contracted space-computer-COVID or something, then it’s a lot less in-the-background. ↩︎
It’s almost like it only exists to move the plot along. ↩︎
You can generally export your data, thanks to a combination of legislation and efforts like Google’s “Data Liberation Front”, but I’ve never seen an export format that could then just be imported into an equivalent commercial product. ↩︎
Oh, you’ve changed the screen on your iPhone? Better hope it can do the secret handshake with the Apple hardware. ↩︎
I think there might actually have been an episode where that did in fact happen. We’ll just ignore that as a plot contrivance. ↩︎

Apple, Google and aligned incentives

2020-10-17T00:00:00Z

The HTC Dream, the first phone released running Android.

For the past decade I’ve exclusively used Android phones. I got the HTC Dream (aka the T-Mobile G1) shortly after it came out, and dutifully upgraded every 1-2 years. In that timespan I used Android as the basis for my Master’s Thesis, took a job on the Android team at Google, and eventually became a contractor specialising in Android app development. So when I switched to using an iPhone earlier this year a few people were surprised¹.

The good old days

When Android was announced in 2007 – alongside the formation of the Open Handset Alliance – it was positioned as a bastion of openness: it would be built on open standards and the operating system would be open source. At the time iPhones were strongly coupled to iTunes and Apple was exercising strict control over what app developers could do.

When the HTC Dream was released it lived up to expectations. You could write apps for it without shelling out for a Mac! You could get root access, and it was running Linux under the hood! A whole ecosystem of custom firmwares and bootloaders started to appear, thanks to the open source nature of the OS. It shipped with some Google apps, but they were just normal apps that served as examples of what could be done.

After the Dream came a line of Nexus devices. These were Android’s flagship devices, designed to show off what a good Android phone should look like. Both the hardware and software releases tended to feature interesting, useful upgrades. Some of the original open source apps were replaced with closed source, Google proprietary ones, but that was OK - the open source versions lived on in the open source project as examples of what you could do. The devices allowed flashing custom firmware, and the OS source was always released… eventually.

The downfall

The Pixel and Pixel XL

Over time, Android has got less and less free. The Nexus line of phones gave way to the Pixel range, which got rid of the clearly demarcated border where Android ended and Google began. The Android 11 highlights list is dotted with sections that say “On Pixel devices…”, and every single one is a software feature that could be implemented on any device, but Google have decided to keep it proprietary instead of releasing it as part of the open source platform.

At the same time more and more functionality has been added to Google Play Services. This was originally a shared location for Google specific services - in 2012 it merely handled some Google+ functionality and dealing with OAuth for Google accounts. These days it contains a huge swathe of Google services, as well as platform functionality such as push notifications, barcode scanning, geolocation, and so on. Google Play Services isn’t part of the Android Open Source Project, and is only available under license from Google. You can’t really have a device without these functions, so as a manufacturer you have the choice between agreeing to whatever terms Google requires² or spending an awful lot of development time creating an alternative.

While these are fairly abstract arguments about what a free platform should look like, during the same period there has been a marked restriction in how you can actually use Android devices – both as an end-user and as a developer. iOS has always had very stark restrictions on what apps can do in the background; Android started its life allowing pretty much anything, like any good general purpose computing device. This inevitably lead to lots of apps doing lots of things that ranged from stupid to mildly suboptimal, creating a tragedy of the commons amongst apps. The victim was the phone’s battery life, and Google’s solution was a progressive series of restrictions on what apps can do and when. This includes limits on when push notifications are delivered to a device, how frequently apps can wake up, and so forth. Some of these can be bypassed by the end-user, but not all, and the process is fairly cumbersome.

Aligned incentives

From my point of view, Android and iOS are now pretty much in a similar place. They’re not general purpose computers, but app consoles: much like games consoles they consist of hardware and software that the user lacks control over but accepts in order to access the library of apps/games.

Given there’s no clear winner between them in terms of hardware and software, my decision came down to a more holistic question: how aligned are their incentives to my own? Apple is a product company: they make their money by producing shiny things that people want to purchase; Google is an advertising company: they make their money by using my personal information to show me targeted adverts.

For Google, Android was originally a strategic move to ensure that Apple couldn’t dominate the mobile web, and by extension the revenue from ads. As a company, there’s nothing to really push them forward in any particular direction other than one that facilitates advertising. Of course, Google employs tonnes of good people who want to do good things which counterbalances this, but I’d still prefer to deal with a company that has an intrinsic motivation to do things I want them to do, rather than one forced to by regulation, custom, or the good intent of their employees.

So the decision became obvious: if I have no strong opinions about the software and hardware, Apple is the clear winner because their incentives are a lot better aligned to mine.

Image credits

Photo	Creator	Licence	Source
HTC Dream	Akela NDE	CC BY-SA 3.0	Wikimedia
Pixel and Pixel XL	Maurizio Pesce from Milan, Italia	CC BY 2.0	Wikimedia

Or, at least, politely feigned surprise. ↩︎
And Google’s terms were particularly onerous: as well as requiring Chrome and Google Search to be preinstalled, they prevented manufacturers from selling any devices powered by alternative versions of Android - e.g., Samsung wouldn’t be allowed to sell a refrigerator that ran Amazon’s FireOS. The European Union handed Google a $5,000,000,000 fine for this anti-competitive behaviour, which Google are still in the process of contesting. ↩︎

Over-the-top optimisations with Nim

2018-12-09T00:00:00Z

Christmas Tree from Advent of Code 2005

For the past few years I’ve been taking part in Eric Wastl’s Advent of Code, a coding challenge that provides a 2-part problem each day from the 1st of December through to Christmas Day. The puzzles are always interesting — especially as they get progressively harder — and there’s an awesome community of folks that share their solutions in a huge variety of languages.

To up the ante somewhat, Shane and I usually have a little informal competition to see who can write the most performant code. This year, though, Shane went massively overboard and wrote an entire benchmarking suite and webapp to measure our performance, which I took as an invitation and personal challenge to try to beat him every single day.

For the past three years I’d used Python exclusively, as its vast standard library and awesome syntax lead to quick and elegant solutions. Unfortunately it stands no chance, at least on the earlier puzzles, of beating the speed of Shane’s preferred language of PHP. For a while I consoled myself with the notion that once the challenges get more complicated I’d be in with a shot, but after the third or fourth time that Shane’s solution finished before the Python interpreter even started¹ I decided I’d have to jump ship. I started using Nim.

Introducing Nim

Nim, formerly Nimrod, is a compiled language that takes a lot of cues from Python. It has a very nice and familiar syntax, a reasonable standard library, and it’s fast. I’d thought about learning it before but didn’t really have anything suitable to use it on, until now. The code I used for my day one part one answer looks like this in Nim:

import math, sequtils, strutils

echo readFile("data/01.txt").strip.splitLines.map(parseInt).sum

It’s a one liner that Python would be proud of. The difference with Nim, though, is that this compiles down to C, and from there you get all the benefits of an optimising C compiler and linker. You end up with a blazingly fast stand-alone binary.

Losing my marbles

Day 9 of this year’s Advent of Code proved interesting to optimise, and I’m going to walk through some of the steps I took and their impact. I’m in no way a Nim expert and this is for a program that will be run once and then thrown away, so please don’t take this too much to heart.

Day 9 presents a marble game played by Santa’s elves, whereby marbles with increasing values are added to a circle according to certain rules; every 23rd marble is special and the elf playing it gets to keep that one and also pick up a marble a certain number of places away. The winner is the one with the highest marble value at the end. It doesn’t sound like a particularly thrilling game, but as far as I can tell there’s no way to easily predict the winner without simulating it step-by-step so it makes for an interesting problem.

Naive solution: over 10 minutes

My puzzle input called for a game with 72,104 marbles. My initial approach was to use a sequence (similar to a list) to store the values of the marbles as they’re added to the circle. This got an answer for part 1 in a about 10 seconds and put me at number 124 on the global leaderboard for fastest completion. Unfortunately, when part 2 was revealed it asked me to calculate the result if there were 7,210,400 marbles in play.

Obviously a puzzle 100x larger would take at least 100x longer to run, and almost certainly a lot more than that. There isn’t a way to calculate the advance stages more quickly, so the only thing to be done is to make it run a lot faster. Seven million iterations isn’t really that much of a burden for a modern CPU: for the code to be running this slowly the execution time of some of the operations must be scaling with the number of marbles. A quick look through the documentation reveals:

proc del[T](x: var seq[T]; i: Natural) {...}
deletes the item at index i by putting x[high(x)] into position i.
This is an O(1) operation.

proc delete[T](x: var seq[T]; i: Natural) {...}
deletes the item at index i by moving x[i+1..] by one position.
This is an O(n) operation.

Because we have to delete a marble at an arbitrary point and maintain the ordering of the others, I was using the delete() proc which has an O(n) runtime. The other potentially costly operation is inserting a new marble; the documentation doesn’t mention the runtime but all of the nim docs have a direct link to the source code, and we can see that inserting an element requires iterating over all the elements after it, so it’s also O(n) in the worse case.

DoublyLinkedLists: ~500ms

When you need performant inserts and deletes in a list, the go-to solution is a linked list. Because nodes store references to their neighbours (instead of being stored consecutively in an array or list), delete and insert operations are O(1): you simply need to change a few pointers. Nim’s lists package provides a convenient DoublyLinkedList that I went ahead and used.

Instead of using the old insert and delete methods I now had my own which simply manipulate the nodes’ previous and next pointers:

func insertAfter(node: DoublyLinkedNode[int], value: int) =
    var newNode = newDoublyLinkedNode(value)
    newNode.next = node.next
    newNode.prev = node
    newNode.next.prev = newNode
    newNode.prev.next = newNode

 func remove(node: DoublyLinkedNode[int]) =
    node.prev.next = node.next
    node.next.prev = node.prev

This implementation brought the runtime down to a respectable 500ms, which handily beat Shane’s PHP implementation. It was still an order of magnitude longer than any of my other solutions, though, so I wasn’t happy yet.

Reduced imports: ~470ms

One thing I was conscious of from trying to make Python performant was how the number of imports can pile on to startup time. I had a couple of unused imports that were easy to shed, and I also decided to implement my own linked list in favour of nim’s lists module. All this involved was defining a type and then replacing my usages of DoublyLinkedNode[int] with my new Marble.

type
    Marble = ref object
        next, prev: Marble
        value: int

These few changes didn’t have a huge impact, but I was clutching at straws and every 30ms was a small victory.

Inlining methods and small optimisations: ~420ms

Thinking the code was about as fast as I was going to get it, I made a final pass to see if there were any little tweaks I could make. First off, I added the inline pragma to my insert and remove methods, to hint to the C compiler that they should be inlined. I was concerned that the overhead of calling a function seven million times would add up, and inlining the fairly simple operation seems reasonable. It’s entirely possible the C compiler was already doing this (they’re pretty clever), but making the hint explicit in Nim is really easy so there’s nothing to lose:

func insertAfter(node: Marble, value: int) {.inline.} =
    var newNode = new(Marble)
    newNode.value = value
    newNode.next = node.next
    newNode.prev = node
    newNode.next.prev = newNode
    newNode.prev.next = newNode

func remove(node: Marble) {.inline.} =
    node.prev.next = node.next
    node.next.prev = node.prev

I also made some small algorithmic tweaks. These are usually the bread and butter of optimisations but for this problem there were only a couple I could see:

We only care about the current player every 23rd marble, so instead of tracking the player each turn we can just calculate a 23 player jump when needed
Instead of testing whether the current marble is divisible by 23, which is potentially non-trivial for large numbers, we can use a separate variable that just counts down from 23 and gets reset
Instead of calculating the boundary condition (100 * marbles) whenever it’s used, we can put this in a variable and calculate it once up-front. (The C compiler probably handled this for us anyway)

These combination of tweaks saved another 50ms, and it seemed like there wasn’t a whole lot left that could possibly change.

Non-reference counted objects: ~180ms

While I was pondering further improvements, Shane mentioned that he managed to make PHP’s garbage collector segfault with his solution. That got me thinking: what would happen if Nim didn’t have to worry about garbage collecting our marbles? We have a fixed amount of them and don’t need to worry about memory leaks as the program runs for half a second and then quits. Changing the Marble type and manually allocating memory for it — something that is virtually impossible in languages like PHP or Python — was trivial in Nim:

type
    Marble = object
        next, prev: ptr Marble
        value: int32

proc insertAfter(node: ptr Marble, value: int) {.inline.} =
    var newNode = cast[ptr Marble](alloc0(sizeof(Marble)))

Taking the garbage collector out of the equation over doubled the performance! Still, it was my only solution that took more than 100ms and that bothered me…

No looking back: ~120ms

Thinking about memory allocations made me take a hard look at the structure of the Marble type. Each of the seven million marbles has a previous pointer that we only use to backtrack by a fixed amount every 23rd play, which seems wasteful. If we reduce the amount of memory we have to allocate, we’ll logically reduce the time taken allocating it.

As the game is simulated we keep track of the “current” marble, so why not keep track of the marble eight behind that? That would allow us to turn the doubly-linked list into a singly-linked list and save a whole bunch of memory. This ends up being slightly complicated as initially there aren’t eight marbles, and every 23rd play we jump the current position backwards (and without previous pointers, we can’t jump the “current minus eight” pointer backwards).

To work around these issues, I added a “trailing” pointer that gradually drifts backwards to eight behind the current pointer as moves are played. There are 22 normal moves that each advance the current pointer by two, so there’s plenty of time for this to happen.

var
    currentTrail = current
    currentTrailDrift = 0

# When a standard move occurs:
current.next.insertAfter(i)
current = current.next.next
if currentTrailDrift == 8:
    # Keep the trail eight marbles behind the current one
    currentTrail = currentTrail.next.next
else:
    # Don't move the trail so it drifts away by two marbles
    currentTrailDrift += 2

This is one of those optimisations that makes the code a bit harder to follow, but it sliced a third of the runtime off and takes us tantalisingly close to that 100ms threshold.

One bulk order of memory, please: ~50ms

Thinking about memory allocations, I realised we were doing seven million small allocations over the lifetime of the program. We know upfront how many marbles there are going to be and will need to allocate memory for them all at some point, so why not just do it in one big bang?

Fortunately, again, Nim lets you dive from the high-level Python-like world down to the nitty-gritty of memory management and pointers without blinking. Now after reading the puzzle input, I allocate a big chunk of memory (for my input with seven million marbles this equates to around 86MB of RAM) and keep a pointer to it:

let
    hundredMarbles = marbles * 100
    memory = alloc(MarbleSize * hundredMarbles)

Then when it comes to creating a “new” Marble, we simply calculate the position in our memory block and use it as a pointer:

proc addressOf(memory: pointer, marbleNumber: int): Marble {.inline.} =
    cast[Marble](cast[uint](memory) + cast[uint](marbleNumber * MarbleSize))

proc insertAfter(node: Marble, memory: pointer, value: int): Marble {.inline.} =
    var newNode = memory.addressOf(value)

Changing to this one-time allocation more than halved the runtime of the program, placing it firmly under the 100ms target I was aiming at. It’s particularly pleasing how little effort was required for optimisations like this, and how you can switch from high-level Python-style code to low-level C-style pointer manipulation.

You can find the full code to my solution in my aoc-2018 repository. If you’re not taking part in Advent of Code I highly recommend it, and if you’ve not used Nim it’s definitely worth a look.

PHP has always been fast to start, due to its primary use in a CGI environment, and the last few major versions of PHP have made its unbelievably blazingly fast as well, while Python unfortunately has issues with startup time ↩︎