Data Structures

There are primarily three ways of sorting slices in Go. Early on, we had the verbose but flexible method of implementing sort.Interface to sort the elements in a slice. Later, Go 1.8 introduced sort.Slice to reduce boilerplate with inline comparison functions. Most recently, Go 1.21 brought generic sorting via the slices package, which offers a concise syntax and compile-time type safety.

These days, I mostly use the generic sorting syntax, but I wanted to document all three approaches for posterity.

Comparing interface values in Go has caught me off guard a few times, especially with nils. Often, I’d expect a comparison to evaluate to true but got false instead.

Many moons ago, Russ Cox wrote a fantastic post on Go interface internals that clarified my confusion. This post is a distillation of my exploration of interfaces and nil comparisons.

Interface internals

Roughly speaking, an interface in Go has three components:

Just like any other dynamically growable container structure, Go slices come with a few gotchas. I don’t always remember all the rules I need to be aware of. So this is an attempt to list some of the most common mistakes I’ve made at least once.

Slices are views over arrays

In Go, a slice is a lightweight wrapper around an array. Instead of storing data itself, it keeps track of three things: a pointer to an underlying array where the data is stored, the number of elements it currently holds, and the total capacity before it needs more space. The Go runtime defines it like this:

I was fiddling with graphlib in the Python stdlib and found it quite nifty. It processes a Directed Acyclic Graph (DAG), where tasks (nodes) are connected by directed edges (dependencies), and returns the correct execution order. The “acyclic” part ensures no circular dependencies.

Topological sorting is useful for arranging tasks so that each one follows its dependencies. It’s widely used in scheduling, build systems, dependency resolution, and database migrations.

For example, consider these tasks:

Despite moonlighting as a gopher for a while, the syntax for type assertion and type switches still trips me up every time I need to go for one of them.

So, to avoid digging through the docs or crafting stodgy LLM prompts multiple times, I decided to jot this down in a Go by Example style for the next run.

Type assertion

Type assertion in Go allows you to access an interface variable’s underlying concrete type. After a successful assertion, the variable of interface type is converted to the concrete type to which it’s asserted.

One of my favorite pastimes these days is to set BingChat to creative mode, ask it to teach me a trick about topic X, and then write a short blog post about it to reinforce my understanding. Some of the things it comes up with are absolutely delightful. In the spirit of that, I asked it to teach me a Shell trick that I can use to mimic maps or dictionaries in a shell environment. I didn’t even know what I was expecting.

Python has a random.choice routine in the standard library that allows you to pick a random value from an iterable. It works like this:

# src.py
import random

# The seed ensures that you'll get the same random choice
# every time you run the script.
random.seed(90)

# This builds a list: ["choice_0", "choice_1", ..., "choice_9"]
lst = [f"choice_{i}" for i in range(10)]

print(random.choice(lst))
print(random.choice(lst))

This will print:

choice_3
choice_1

I was looking for a way to quickly hydrate a table with random data in an SQLite database. To be able to do so, I needed to extract unpremeditated values from an array of predefined elements. The issue is, that SQLite doesn’t support array types or have a built-in function to pick random values from an array. However, recently I came across this trick from Ricardo Ander-Egg’s tweet, where he exploits SQLite’s JSON support to parse an array. This idea can be further extended to pluck random values from an array.

In CPython, elements of a list are stored as pointers to the elements rather than the values of the elements themselves. This is evident from the list struct in CPython that represents a list in C:

// Fetched from CPython main branch. Removed comments for brevity.
typedef struct {

    PyObject_VAR_HEAD
    PyObject **ob_item; /* Pointer reference to the element. */
    Py_ssize_t allocated;

}PyListObject;

An empty list builds a PyObject and occupies some memory:

from sys import getsizeof

l = []

print(getsizeof(l))

This returns:

Imagine a custom set-like data structure that doesn’t perform hashing and trades performance for tighter memory footprint. Or imagine a dict-like data structure that automatically stores data in a PostgreSQL or Redis database the moment you initialize it; also it lets you get-set-delete key-value pairs using the usual retrieval-assignment-deletion syntax associated with built-in dictionaries. Custom data structures can give you the power of choice and writing them will make you understand how the built-in data structures in Python are constructed.