Chameth.com - posts like g15-ram-upgrade, over-the-top-optimisations-in-nim, why-you-should-be-using-https

Upgrading the RAM in a Dell G15 laptop

2023-07-29T00:00:00Z

The Dell G15

I currently use a Dell G15 laptop for work. It has served me well for a little over a year, but recently it has been struggling a little with my day-to-day workload. It came with 32GB of RAM — the highest possible specification at the time¹ — but that is apparently no longer enough for me.

For a recent project, I was working on a Rust library used in an Android app. That meant running the usual glut of Android tools (Android Studio, an emulator and at least one Gradle daemon) alongside a normal IDE (IntelliJ IDEA). Throw in a web browser and a couple of electron apps, and I often managed to use all 32GB.

When you start swapping memory out to an encrypted disk — even an SSD — it doesn’t make for great performance. At first, I tried to work around this by enabling the Linux out-of-memory (OOM) killer, but it turns out that it’s not too good with Electron apps: it will kill the large browser process, but then the small Electron wrapper will just respawn it.

Can it be upgraded or not?

The obvious solution to not having enough RAM is to add more RAM. A quick look in the manual showed this might not be possible, though. The manual includes the following “Memory specifications” table:

Description	Values
Memory slots	Two SODIMM slots
Memory type	DDR5
Memory speed	4800
Maximum memory configuration	32GB
Minimum memory configuration	8GB
Memory size per slot	8GB or 16GB
Memory configurations supported	8 GB, 1 x 8 GB, DDR5, 4800 MHz 16 GB, 1 x 16 GB, DDR5, 4800 MHz 16 GB, 2 x 8 GB, DDR5, 4800 MHz, dual-channel 32 GB, 2 x 16 GB, DDR5, 4800 MHz, dual-channel

That unambiguously says that an upgrade from 32GB is not possible. I gave up.

Later though, I was complaining about memory issues to a friend, and he pointed out a Dell forum thread where a couple of people claim to have successfully installed dual-channel 32GB modules. Since the alternative was getting an entire new PC after only a year, I decided to give it a go.

The upgrade attempt

I ordered a pair of Crucial 32GB DDR5-4800 SODIMMs, and after they turned up dismantled the laptop. The G15 comes apart pretty normally: there are uncovered screws on the bottom holding the lower part of the case on. With those removed and some gentle prying, it pops off, and you get access to the battery, GPU and motherboard.

The first thing I saw was this:

The G15 motherboard adamantly proclaiming that it doesn’t want 32GB SODIMMs

Not one but two labels that indicate it will only accept 8GB or 16GB modules. Oh well, what’s the worst that can happen?

Oops?

I dutifully installed the new modules, reconnected the battery and put the case back together. I pressed the power button, and… nothing. None of the usual garish lights that immediately come on, no screen output, just a dead laptop. After reading some more of the user manual, I found that there is a tiny status LED on the side next to the ethernet port. Forcing the laptop to power off and back on again, the status LED blinked a distress code at me: 2 amber blinks, 4 white blinks. The manual says that is — unsurprisingly — a memory fault.

I figured at this point that the manual and labels on the motherboard were probably right. I took the laptop apart again, reinstalled the original 2x16GB modules, reassembled it, and pressed the power button. It didn’t boot. I don’t spend a lot of time fiddling inside computers, but I’ve done it enough that I’m reasonably confident I can’t entirely break a computer while swapping some RAM modules. I took to Googling², and found an interesting article that said Dell laptops don’t like to boot after RAM changes unless you clear the CMOS by popping out the battery for 15 minutes.

I opened the laptop up, and looked around for the CMOS battery. There wasn’t one. Turns out they don’t exist any more. I left the main battery disconnected for a while to see if it would help, and it didn’t.

Unexpected success

I started to get worried: if I couldn’t fix this, I wouldn’t be able to work until I got a new PC, and that wasn’t really in my budget at the minute. I sat reading old forum threads and help guides³, none of which were actually useful. Out of nowhere, though, the laptop booted up.

Naturally, I immediately shut the laptop down again, opened it up, and switched back to the new RAM modules. Then I turned it on again and sat waiting. After about 15 minutes of it looking totally dead, it turned on and showed a BIOS warning about the hardware configuration being changed. It then booted perfectly normally, and all 64GB of RAM was visible and usable.

My theory is that the forum threads were right: Dell laptops are funny about RAM upgrades. But somehow in removing the physical CMOS battery, they’ve kept the same “you have to wait 15 minutes” behaviour just without any indication that’s what’s happening. Regardless, I now have enough RAM even for the greediest of IDEs and Electron apps.

Bizarrely, the maximum spec has decreased to 16GB since then. ↩︎
In the generic sense. I use Kagi these days. ↩︎
On my phone because, y’know, the laptop was busted. ↩︎

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

Why you should be using HTTPS

2016-06-17T00:00:00Z

The EFF’s HTTPS Everywhere logo

One of my favourite hobbyhorses recently has been the use of HTTPS, or lack thereof. HTTPS is the thing that makes the little padlock appear in your browser, and has existed for over 20 years. In the past, that little padlock was the exclusive preserve of banks and other ‘high security’ establishments; over time its use has gradually expanded to most (but not all) websites that handle user information, and the time is now right for it to become ubiquitous.

Why use HTTPS?

There are numerous advantages to using HTTPS, both for the users of a website and for the operator:

Privacy

The most obvious advantage is that HTTPS gives your users additional privacy. An insecure (HTTP) request can potentially be read by anyone on the same network, or the network operators, or anyone who happens to operate a network along the path between the user and the server.

Users on shared WiFi networks (such as those in coffee shops, hotels, or offices) are particularly vulnerable to passive sniffing by anyone else on that network. If the network is open (as is frequently the case) then anyone in radio range can see exactly what the user is up to.

Integrity

HTTPS also helps to maintain the integrity of your site. With a plain HTTP request, there’s nothing to stop anyone in between the server and the user from modifying the content of the request or the response. This is a frequent tactic used by annoying WiFi gateways (such as the ones you’d find in a hotel), dubious ISPs who want to serve you extra adverts, or just plain old nefarious attackers.

If you’re trying to convey some kind of information to users (and if you aren’t, why exactly are you running a website again?) it seems beneficial to both you and them if the information arrives as you intended, rather than in a modified form due to someone or something tampering with it.

Security

If your website has any kind of authentication, or session identifiers, it becomes extremely vulnerable to an attacker monitoring the traffic and stealing the credentials. This was starkly demonstrated in 2010 when Firesheep was released. This tool allowed anyone to quickly and automatically hijack social media accounts of anyone on the same network who was using HTTP to access them.

Even if your login pages are served over HTTPS, if you send a single session ID cookie over HTTP (such as a page you decided wasn’t particularly ‘important’) then an attacker can probably spoof the user’s session and gain full access to their account. Again, in the case of open WiFi networks that could be anyone in radio range.

Search engine rankings

Some search engines use HTTPS as a signal in their ranking algorithms. Google announced in 2004 that it was using the presence of HTTPS as a small positive signal, but that it may strengthen that signal over time as more and more websites switch to using a secure transport. It’s not unthinkable that at some point in the future there will be HTTPS-only search engines.

But… But… But…

There are lots of excuses for not implementing HTTPS. Most of them are either misguided or outdated.

It’s too expensive and/or complicated

In the past, getting HTTPS certificates was a pain. A number of free suppliers have existed for a while but the process for getting their certificates wasn’t particularly straight forward, and many imposed arbitrary restrictions on the certificate parameters. Even once you had the certificate, you had to fiddle about with your HTTP server configuration to make it work, remember to manually get a new certificate when the old one expired, and lots of other annoying busywork.

With the arrival of Let’s Encrypt, all that changed. You can retrieve and deploy a free HTTPS certificate with two or three commands. Renewal can be handled completely automatically with a single command executed by cron.

There’s no point; nothing on my site is sensitive

You might not think your content warrants privacy, but can you speak for everyone who accesses it? Even content that seems mundane to you — such as travel advice, or technical writing — could be used to build up a profile of a user. If an attacker is monitoring traffic in a coffee shop and sees a user looking at travel advice and weather forecasts for a foreign country, he could use that information to plan a burglary knowing that the user will be away. Similarly, some content which is perfectly mundane to you may actually be very sensitive in other countries with repressive governments. HTTPS makes it much harder for these people to snoop on traffic.

From another angle, if you’re offering any kind of information, instructions, or especially file downloads, there’s a severe risk to users if the content is modified on its way to them. An evil sysadmin could rewrite your travel advice to suggest visiting the local drug dealer’s hangout, or replace your download with a malware-infested version.

HTTPS is slower, uses more resources, etc

Back in 1995 this might have been a valid argument. Enabling HTTPS on a modern server will make an almost negligible difference to performance. If you also enable HTTP/2 (which most implementations only support over HTTPS), it’s likely to actually use fewer resources, and result in a faster, smoother experience for your users. HTTP/2 was designed to work with HTTPS, and designed with modern requirements and networking techniques in mind.

CloudFlare have an excellent demonstration of the benefits of HTTP/2, and it can show speed improvements of 2-3x in a typical environment. On top of being faster, HTTP/2 uses fewer connections which results in less resource overhead on both the server and the client.

So what are you waiting for?

If you run a website and aren’t using HTTPS, give it a try.