Chameth.com - posts like debugging-beyond-the-debugger, over-the-top-optimisations-in-nim, travel-toolkit

Building a travel toolkit

2025-01-02T00:00:00Z

The container for my toolkit, a UGREEN “travel accessories” bag

For a while now, whenever I’ve traveled anywhere I’ve dumped a selection of tools into my backpack just in case I need them. Originally this was mostly focused around being able to open and fix my laptop if anything went wrong, but over time has slowly expanded to include other useful tools.

Repeatedly packing these tools and then returning them to where they belonged was tedious, though. I couldn’t just leave them in the backpack as I often needed them for non-travelling purposes, and I didn’t want to just buy duplicate tools that spent most of their life a few meters away from each other, so I ignored the problem and just dealt with the tedium.

Eventually I acquired enough tools that — while not quite duplicates — I wouldn’t miss often if they were kept in the backpack. Building on these I’ve created a little travel toolkit that contains everything I might want (and more) while away.

The base

The biggest challenge I had before was finding a screwdriver set. I have an iFixit Mako set that did the in-and-out-of-the-bag routine for several years. Nothing else covered the range of drivers I wanted for generic electronic tinkering and more chunky work. I finally found one in the form of a Wera Tool-Check PLUS TR-Edition. “TR” stands for “Tool Rebel” and is Wera’s “fan club” brand. Its signature features over the normal Tool-Check PLUS are a fancy fabric case and a 152mm bit extender; but it also comes with a much different set of bits, which is why I picked it up.

Here’s a comparison

Type	Standard version	Tool Rebel edition
Phillips	2x PH1 3x PH2 1x PH3	1x PH00 1x PH0 1x PH1 1x PH2 1x PH3
Pozidrive	None	1x PZ1 3x PZ2
Slotted	1x 5.5mm	1x 4mm 1x 4.5mm 2x 5.5mm 1x 6.5mm
Torx	1x T10 1x T15 1x T20 1x T25 1x T30 1x T40	1x T10 1x T15 1x T20 1x T25 1x T30 1x T40
Security Torx	1x T10 1x T15 1x T20 1x T25 1x T30	1x T25
Hex	1x H3 1x H4 1x H5 1x H6 1x H8	1x H1.5 1x H2 1x H2.5 1x H3 1x H4 1x H6 1x H8

There are only five bits present in the standard version that are missing in the TR edition: 5mm hex (pretty uncommon) and four sizes of security torx (rare). In exchange for those and the removal of a bunch of duplicates, you get two extra phillips sizes (0 and 00, both very useful for electronics and spectacles), some pozidrive bits (extremely common on random hardware/furniture/etc), smaller hex bits (for electronics, 3D printers, and so on), and a few other bits and pieces.

Overall it’s a vastly superior selection for my needs. And while it doesn’t have the full range of bits provided by the iFixit kit, it does cover almost everything I’m ever actually likely to need while travelling, and it’s probably around a third of the size.

The other core part of the toolkit is the bag. I had a UGREEN “travel accessory” bag hanging around unused, and noticed it was almost the exact right size for the Tool-Check. Now, how many other tools could I stuff in there?

All the tools

The array of tools that make up the travel toolkit

The kit can be broken down into a few sections:

Screwdriving

The aforementioned Wera Tool-Check
Its 152mm bit extender

I’ve talked enough about this already, I think, so I’ll spare you any additional commentary on screwdrivers and bits.

Splitting, gripping and cutting

Engineer tweezers
Engineer mini snips
Engineer mini screw removal pliers
Knipex mini waterpump pliers
Two iFixit spudgers (one metal, one plastic)
iFixit jimmy

I have bigger or slightly different versions of these that stay in my normal toolkit. The tweezers and snips are useful in a variety of situations, and the spudgers are handy for getting inside laptops and other devices. The pliers are less useful, but they’re one of those things where when you do need them there aren’t any good alternatives.

Sewing

Two needles
Some black thread
Set of mini clips

You never know when you’re going to rip a seam in something. I find the clips a lot less fiddly than using pins for keeping material in place when I’m trying to sew.

Computering

Retractable ethernet cable
RJ45 coupler
USB-C to RJ45 adapter
Dual USB-A and USB-C thumb drive, with an Arch ISO on it

Sometimes Wi-Fi just doesn’t cut it, or you need to fiddle with a router that doesn’t expose its admin UI over Wi-Fi. The USB-C adapter is for use with my phone, as it’s often easier to move that get the laptop where it needs to be.

I can boot from the thumb drive into an Arch environment, and from there reinstall my laptop from scratch if needed. There’s enough space left over so it can be used to transfer files as well.

Miscellaneousing

Fabric tape measure
Spirit level
Sharpie
Superglue
Spare batteries: 2 CR2032s, 2 AA, 2 AAA

I’m almost certain I won’t use the spirit level, but it’s tiny and I had a spare so it went in. Everything else is just in the “generally handy to have” category.

Putting it all together

The nicely-organised side of the toolkit

The Tool-Check PLUS fits almost perfectly into one side of the UGREEN bag, leaving a little wiggle room along the side for the longer parts like spudgers. The middle pockets can’t fit much in, but keep the batteries and sewing bits out of the way. Everything else is in a big zip-up compartment in the other side, which is slightly messy but still easy enough to dig through to find whatever I need.

The complete kit weighs in at around 1.2KG, so it’s not exactly lightweight, but it goes in a bag with a heavy laptop and all of its peripherals so it’s not as noticeable as it might otherwise be.

It remains to be seen how much use I’ll actually get out of any of this. Maybe I’ll put a bit of paper in so that I can track how often I use each tool…

Debugging beyond the debugger

2019-05-08T00:00:00Z

Real-life debugging tools

Most programming — and sysadmin — problems can be debugged in a fairly straight forward manner using logs, print statements, educated guesses, or an actual debugger. Sometimes, though, the problem is more elusive. There’s a wider box of tricks that can be employed in these cases but I’ve not managed to find a nice overview of them, so here’s mine. I’m mainly focusing on Linux and similar systems, but there tend to be alternatives available for other Operating Systems or VMs if you seek them out.

Networking

tcpdump

tcpdump prints out descriptions of packets on a network interface. You can apply filters to limit which packets are displayed, chose to dump the entire content of the packet, and so forth.

Typical usage might look something like:

# tcpdump -nSi eth0 port 80
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on eth0, link-type EN10MB (Ethernet), capture size 262144 bytes
16:03:35.577781 IP6 2001:db8::1.54742 > 2001:db8::2.80: Flags [S], seq 2815779044, win 64800, options [mss 1440,sackOK,TS val 2378811665 ecr 0,nop,wscale 7], length 0
16:03:35.586853 IP6 2001:db8::2.80 > 2001:db8::1.54742: Flags [S.], seq 1522609102, ack 2815779045, win 28560, options [mss 1440,sackOK,TS val 3063610173 ecr 2378811665,nop,wscale 7], length 0
16:03:35.586877 IP6 2001:db8::1.54742 > 2001:db8::2.80: Flags [.], ack 1522609103, win 507, options [nop,nop,TS val 2378811674 ecr 3063610173], length 0
16:03:35.620678 IP6 2001:db8::1.54742 > 2001:db8::2.80: Flags [P.], seq 2815779045:2815779399, ack 1522609103, win 507, options [nop,nop,TS val 2378811708 ecr 3063610173], length 354: HTTP: GET / HTTP/1.1

Here you can see the start of a plaintext HTTP request: the three-way handshake as the TCP connection is established followed by a GET request. Even if the data is encrypted as it will be in most cases, it’s often useful to see the “shape” of the transmissions: did the client start sending data when it connected, did the server ever respond, etc.

Daniel Miessler has a good tutorial on tcpdump if you’re not familiar with it and don’t want to jump straight into the man page.

… with Docker

Docker sets up separate network namespaces for each container. To see the traffic across the interfaces of a single container you can nsenter the container’s network namespace:

# nsenter -t $(docker inspect --format '{{.State.Pid}}' my_container) -n tcpdump -nS port 80

This retrieves the PID for the container, and tells nsenter to enter the network (-n) namespace from the given target (-t) PID, and then run the given command (in this case tcpdump ...).

openssl s_client / s_server

When a connection is using TLS it’s often useful to try connecting to the server and see what certificate it presents, algorithms it negotiates, and so forth. OpenSSL offers two useful subcommands which can help with this: s_client for connecting as a client, and s_server for listening to connections.

For example, using s_client to connect to google.com on the standard HTTPS port shows us details about the server cert and its verification status:

$ openssl s_client -connect google.com:443
CONNECTED(00000003)
depth=2 OU = GlobalSign Root CA - R2, O = GlobalSign, CN = GlobalSign
verify return:1
depth=1 C = US, O = Google Trust Services, CN = Google Internet Authority G3
verify return:1
depth=0 C = US, ST = California, L = Mountain View, O = Google LLC, CN = *.google.com
verify return:1
---
Certificate chain
 0 s:C = US, ST = California, L = Mountain View, O = Google LLC, CN = *.google.com
   i:C = US, O = Google Trust Services, CN = Google Internet Authority G3
 1 s:C = US, O = Google Trust Services, CN = Google Internet Authority G3
   i:OU = GlobalSign Root CA - R2, O = GlobalSign, CN = GlobalSign
---
# ...

Whereas connecting to my webserver and providing an unknown host in the SNI field results in an SSL alert 112 (“The server name sent was not recognized”) and no server certificate is sent:

$ openssl s_client -connect chameth.com:443 -servername example.com
CONNECTED(00000003)
140384831313024:error:14094458:SSL routines:ssl3_read_bytes:tlsv1 unrecognized name:../ssl/record/rec_layer_s3.c:1536:SSL alert number 112
---
no peer certificate available
---
# ...

Often if you hit this kind of alert in an application the exact error will be lost somewhere in the many layers between the SSL library and the logs, so being able to directly connect and test can help diagnose a lot of issues.

Once a connection is established you can read and write plain text and it will be encrypted and decrypted automatically.

Java apps

If a Java app is involved in the connection, you can enable a lot of built-in debugging with a simple JVM property: javax.net.debug. You can tweak what exactly gets logged, but the easiest thing to do is just set the property to all and you’ll see information about certificate chains, verification, and packet dumps:

$ java -Djavax.net.debug=all -jar ....
# ...
found key for : duke
chain [0] = [
[
  Version: V1
  Subject: CN=Duke, OU=Java Software, O="Sun Microsystems, Inc.",
  L=Cupertino, ST=CA, C=US
# ...

More information about Java’s debugging options is available on docs.oracle.com.

Thread and core dumps

Higher-level languages frequently provide an interactive way to dump the current execution state of all of their threads (a “thread dump”). This is useful to spot deadlocks, some types of race conditions, and as a quick and dirty method of investigating hangs or excessive CPU usage.

With both Java and Go applications you can send a QUIT signal to have a thread dump printed out; Go applications will quit after doing so, Java ones will carry on running. At most terminals you can hit Ctrl and \ to send a QUIT signal.

For Java you can also use the jstack tool from the JDK to dump threads by PID; this can be useful if the application is running in the background or has redirected sysout:

$ jstack 8321
Attaching to process ID 8321, please wait...
Debugger attached successfully.
Client compiler detected.

Thread t@5: (state = BLOCKED)
 - java.lang.Object.wait(long) @bci=-1107318896 (Interpreted frame)
 - java.lang.Object.wait(long) @bci=0 (Interpreted frame)
 - java.lang.ref.ReferenceQueue.remove(long) @bci=44, line=116 (Interpreted frame)
 - java.lang.ref.ReferenceQueue.remove() @bci=2, line=132 (Interpreted frame)
 - java.lang.ref.Finalizer$FinalizerThread.run() @bci=3, line=159 (Interpreted frame)

# ...

A core dump provides more complete information about the state of a process, but is often more complex to interpret. The gcore utility from GDB will create a core dump of a process with a given PID. You can then generally load the core file using your normal debugger, depending on the language in question.

System calls

strace is the swiss army knife for seeing what a process is doing. It details each system call made by a program (you can filter them down, of course). For example:

$ strace -e read curl https://google.com/
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0 \236\0\0\0\0\0\0"..., 832) = 832
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0P!\0\0\0\0\0\0"..., 832) = 832
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\200l\2\0\0\0\0\0"..., 832) = 832
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\20Q\0\0\0\0\0\0"..., 832) = 832
# ...
read(3, "\0\0\0\0\0\0\0\4\25\345\366\302\273sE6\365wI\225\321|\3435Z\362\216\372\215\251aO"..., 253) = 253
<HTML><HEAD><meta http-equiv="content-type" content="text/html;charset=utf-8">
<TITLE>301 Moved</TITLE></HEAD><BODY>
<H1>301 Moved</H1>
The document has moved
<A HREF="https://www.google.com/">here</A>.
</BODY></HTML>
read(3, "\27\3\3\0!", 5)                = 5
# ...

Brendan Gregg has a nice guide on strace and alternatives.

… with docker

When the application is running in docker you can usually just strace it from the host with the correct PID (from e.g. docker inspect --format '{{.State.Pid}}' my_container). Sometimes you may need to trace the startup of an application though, which is a bit trickier. Instead you can run a new container using the same PID namespace as your target, and the permissions needed to strace:

$ docker run --rm -it --pid=container:my_container \
  --net=container:my_container \
  --cap-add sys_admin \
  --cap-add sys_ptrace \
  alpine

From within the new container you can install strace, and trace any running program within the target container using strace -p as normal. To start a new program you need access to the target container’s filesystem, which you can get to via /proc/1/root (PID 1 being the main process that docker started in the target container).

Files

Sometimes the problem might relate to file access. There are a couple of straight forward — but nonetheless useful — tools which might help here. inotifywait uses the Linux inotify subsystem to watch files or directories for operations. For example:

$ inotifywait -mr site/content
Setting up watches.  Beware: since -r was given, this may take a while!
Watches established.
site/content/post/ MODIFY 2019-05-08-debugging-beyond-the-debugger.md
site/content/post/ OPEN 2019-05-08-debugging-beyond-the-debugger.md
site/content/post/ MODIFY 2019-05-08-debugging-beyond-the-debugger.md
site/content/post/ MODIFY 2019-05-08-debugging-beyond-the-debugger.md
site/content/post/ CLOSE_WRITE,CLOSE 2019-05-08-debugging-beyond-the-debugger.md
# ...

Here the -m switch makes inotifywait monitor the files forever (instead of exiting on the first modification, which is the normal behaviour) and r makes it recurse into the directory and monitor each file and subdirectory in there.

If you want to see what processes currently have a file open, fuser is the go-to tool. For example:

$ fuser -v /
                     USER PID ACCESS COMMAND
/:                   root     kernel mount /
                     chris      2961 .rc.. systemd
                     chris      2986 .r... gdm-x-session
                     chris      2994 .r... dbus-daemon
                     chris      3001 .r... gnome-session-b
# ...

Honourable mentions

These aren’t really debugging tools, but I feel it’s worth mentioning as they often feature somewhere along the debugging-of-weird-problems journey.

I’ve seen some weird and wonderful problems happen because a disk is full, so a quick df early on in the debugging process never hurts. Some apps may hang, some may corrupt their config, some may fall over and die; sometimes the manner in which they fail doesn’t obviously point to a disk space issue.

Another issue that comes up now and then — especially inside VMs or other environment that don’t have a decent amount of “noise” happening — is entropy exhaustion. A quick look at /proc/sys/kernel/random/entropy_avail should be enough to confirm that everything is ticking along nicely. If it’s exceedingly low then you may find that anything involving random number generation stalls (TLS connections for example).

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 ↩︎