More from alexwlchan
I listen to a lot of podcasts, and I like how they fit around other tasks. I press play, lock my phone, and put it down. I’m free to wash the dishes, fold the laundry, or shop for groceries. Unfortunately, more and more information is only published as a video. Technical talks, conference sessions, video essays – they don’t work in an audio-only podcast app. I could convert these videos to MP3 files, but that breaks down the moment a video isn’t pure spoken word. If a speaker says, “Look at this slide” or holds up a diagram, an audio-only file leaves me stranded. I don’t want to give up the podcast player I like, nor stare at a screen for an hour – but I do want the information in these videos. To solve this, I’m abusing my podcast player’s chapter support. This gives me the best of both worlds: I can listen to a video as audio-first, and glance at my lock screen if I need a moment of visual context. The idea: Chapters every few seconds MP3 files can have ID3 metadata, and ID3 metadata can include chapters. A chapter covers a particular time range, and it can have an associated title, description, and cover art. My podcast app of choice is Overcast, which can’t play videos, but it does have robust chapter support. I can jump between chapters, navigate a table of contents, and see per-chapter cover art. To get videos into Overcast, I’m creating MP3 files with a new chapter every few seconds, and the per-chapter cover art is a corresponding frame from the video. As I play the file, I get a slow, stop-motion-like rendition of the original video. If my phone is locked, I can glance at my lock screen and see the current frame in the Now Playing screen. Overcast is developed by Marco Arment, and I got this idea from Forecast, his app for adding chapters to podcasts. In particular, I was struck by its ability to create chapters that don’t display in the chapter list – ideal if I don’t want a table of contents with hundreds of entries. As I was developing my script, I compared my output to the output from Forecast to ensure I was creating the chapters correctly. The code: FFmpeg and Mutagen There are three steps in this process: Convert a video file to an MP3 Extract images from the video at a fixed interval Insert the images as hidden chapters in the MP3 file Let’s go through each in turn. 1. Convert a video file to an MP3 Converting a video file to an MP3 is a single FFmpeg command: ffmpeg -i video.mp4 audio.mp3 This is consistently the slowest step of the process, and I do wonder if I could use different settings or an alternative encoder to make it go faster – but it’s not slow enough to be worth further investigation. 2. Extract images from the video at a fixed interval Extracting images from a video needs a more complicated FFmpeg command: ffmpeg -i video.mp4 \ -vf 'fps=1/5,scale=iw*sar:ih,scale=min(iw\,945):min(ih\,945):force_original_aspect_ratio=decrease' \ thumbnail_%04d.jpg This extracts an image every 5 seconds, downscales any image larger than 945 pixels square (while preserving the original aspect ratio), and saves the results as sequentially numbered JPEG images (thumbnail_0001.png, thumbnail_0002.png, and so on). The key is the -vf flag, which defines two FFmpeg filters: The fps filter selects one frame every 5 seconds (fps=1/5). The first scale filter scales the width based on the sample aspect ratio (scale=iw*sar:ih). Without this filter, frames can be stretched and distorted. The second scale filter scales the input video, preserving the original aspect ratio (force_original_aspect_ratio=decrease), and ensuring the output images fit within 945×945px or the size of the input video, whichever is smaller. My limit is 945 pixels because that’s the largest size that cover art is shown on my iPhone. This filter still isn’t completely correct – it sometimes creates images from portrait videos that are smaller than I’m expecting – but it’s good enough. These are only thumbnails for glancing at, and if I want to change it later, I can always do the image resizing outside FFmpeg. 3. Insert the images as hidden chapters in the MP3 file Inserting the chapters into the MP3 file is more complicated. Although FFmpeg has basic support for ID3 metadata, as far as I know, it can’t insert chapters with per-chapter artwork. Instead, I’m going to reach for Python and the Mutagen library. Here’s the code to add a chapter to an MP3 file: from mutagen.id3 import APIC, CHAP, ID3, PictureType audio = ID3("audio.mp3") with open("thumbnail_0001.jpg", "rb") as f: img_data = f.read() image_frame = APIC(mime="image/jpeg", type=PictureType.OTHER, data=img_data) chapter_frame = CHAP( element_id="chp1", start_time=0, end_time=5 * 1000, sub_frames=[image_frame] ) audio.add(chapter_frame) audio.save() This creates a single chapter that lasts the first 5 seconds (0 to 5000 milliseconds), and the per-chapter cover art is thumbnail_0001.jpg. If we ran this in a loop, we could add images for every 5 second slice of the original video. This code is inserting two frames into the ID3 metadata: The CHAP (chapter) frame contains the timing information, and it can have subframes for metadata like title, chapter art, or associated URL. The APIC (attached picture) subframe contains information about a picture, which can either be a blob of image data or a URL to an image on the web. Normally, you’d also insert a CTOC frame which defines a table of contents, but I don’t want a TOC with hundreds of 5-second chapters, so I’m deliberately not doing this here. This is allowed by the ID3 spec – you’re not required to insert a CTOC frame if you’re using chapters, and you can have chapters that aren’t listed in your table of contents. To work out which frames I needed, I used Forecast to create some chapters by hand, and I inspected their frames. In particular, loading an MP3 and calling Mutagen’s pprint() method shows a human-readable list of frames, and then I could drill into the individual fields: from mutagen.id3 import ID3 audio = ID3("audio.mp3") print(audio.pprint()) I wrapped all this code in a project called glancecast, which allows you to convert a video file with a single command, with optional flags to set the frame length and chapter art size: $ python3 glancecast.py interesting_talk.mp4 interesting_talk.mp3 The process takes a minute or so to complete, most of which is spent transcoding the video file to MP3. The resulting MP3s are usually 40 to 50 MB in size, which is very reasonable. The outcome: How it looks in practice Here’s what one of these “glanceable” podcasts looks like in Overcast and on my lock screen: Maggie Appleton presented this talk over two years ago and it’s been on my “talks to watch” list ever since. Once I put it in Overcast? I listened to it in less than a day. It’s not a lot of extra information, but enough that I can quickly glance down and get the gist of what a speaker is saying. Both views update with a new frame every few seconds, or I can put my phone in my pocket and ignore the screen. I’ve used this approach for half a dozen videos so far, and I’m happy with the results. I expect to keep using it, because I have a long queue of videos I’ve been meaning to watch. If you’d like to try this, check out glancecast for the full code and instructions. [If the formatting of this post looks odd in your feed reader, visit the original article]
I wrote a post for the Tailscale blog about a long-running series of corruption incidents, and how they eventually led us to find an SQLite bug that predates my entire programming career. I’m incredibly proud of this, both the work and the blog post. Before Tailscale, I was coming from smaller teams where I didn’t get to tackle problems of this scale or complexity. This was exactly the sort of tricky, deep technical challenge I wanted to be part of (though I’d rather it hadn’t been quite so stressful)! I’m glad I got to play a small part in these incidents, and I learnt so much from the more experienced engineers I worked with. I never want to hear the words “SQLite corruption” again, but if I do, I’d want to have Tailscalars at my side. Writing the blog post has a blast, too. The piece transformed from a rough draft into a solid, engaging piece of writing, thanks to thoughtful feedback from many people at Tailscale. Most of my writing is self-edited, and it’s always a pleasure to work with a dedicated editor. Please check out the blog post if you haven’t read it already – I think it’s a fascinating technical story, and one readers of this site are bound to enjoy. [If the formatting of this post looks odd in your feed reader, visit the original article]
Yesterday at work, a customer spotted a typo in our UI: “you can use the use the Tailscale CLI”. After the typo was fixed, I wanted to find other cases of accidentally repeated words or phrases. I used two regular expressions to search every codebase for unnecessary repetition. The first regex finds repeated words: \b([A-Za-z]+) \1\b Backfill product data from from Stripe Learn more about about inviting users Argument must be be one of host name, IP set name, IP prefix, or IP There’s a capturing group for a single word made up of letters ([A-Za-z]+), a space, then a backreference to the group. That expression is surrounded by word boundary assertions \b, which check that I’m at the start/end of a word – this avoids finding repeated character sequyences that within longer words, like “with the reason”. The second regex finds repeated phrases: \b([A-Za-z]+ [A-Za-z]+) \1\b Follow the steps in the in the "How to" section Log in to in to your account To configure federated identities federated identities using the Go SDK I’ve changed the capturing group, so now it looks for two words separated by a space. Sometimes repetition is useful, like when I really really went to emphasise a point, but often it’s just a typo. Cleaning up these mistakes has been a fun Friday cleanup task. [If the formatting of this post looks odd in your feed reader, visit the original article]
A month ago, I wrote about my Playwright fixture for testing static websites in a browser. I’ve been copying that fixture from project-to-project, but recently I decided to add it to chives, the utility library I use for all my static websites (or tiny archives). One of my rules for chives is that everything in it has to be tested – but how do you test a pytest fixture? Test code is just code, and it isn’t immune to bugs. Who tests the tests? Enter Pytester, a tool designed for testing pytest plugins. Pytester allows you to run isolated test suites, make assertions about the outcomes, and verify the behaviour of custom fixtures. In your top-level test suite, you always want everything to be passing, but with Pytester you can write a mixture of passing and failing tests, and check the results are what you expect. Pytester is disabled by default, so you first enable it in your top-level conftest.py file (the pytest configuration file where you configure plugins and fixtures): # conftest.py pytest_plugins = ["pytester"] Here’s an example of using Pytester where we create a test suite with two tests and check that one passes, one fails: from pytest import Pytester def test_with_pytester(pytester: Pytester): """ Run an isolated test suite with pytester. """ # Make a temporary pytest test file pytester.makepyfile( """ def test_arithmetic(): assert 2 + 2 == 4 def test_list_inclusion(): assert "yellow" in ["red", "green", "blue"] """ ) # Run the isolated test suite with pytest result = pytester.runpytest() # Check that one test passed, one failed result.assert_outcomes(passed=1, failed=1) I can imagine creating something similar with some complicated collection of nested functions, exec() and pytest.raises, but using Pytester is a cleaner interface than what I’d build. Under the hood, Pytester creates a temporary directory, writes specified files into it, then runs a fresh pytest subprocess against it. It has helper functions for writing files, including Python files (makepyfile), a conftest.py file (makeconftest), and plain text files (maketxtfile). When we’re testing a fixture, we can create a conftest.py file that imports that fixture, then reference it in the tests. Here’s a more complicated example, where we import one of my Playwright fixtures in my conftest.py, write an HTML file into the temporary directory, then use them both in the test: from pytest import Pytester def test_browser_fixture(pytester: Pytester): """ Try testing the browser fixture with pytester. """ # Make a conftest.py file pytester.makeconftest(""" from chives.browser_fixtures import browser """) # Make an HTML file (pytester.path / "greeting.html").write_text(""" <p>Hello world!</p> """) # Make a temporary pytest test file pytester.makepyfile( """ from chives.browser_fixtures import file_uri from playwright.sync_api import Browser, expect def test_browser_fixture(browser: Browser) -> None: uri = file_uri("greeting.html") p = browser.new_page() p.goto(uri) expect(p.get_by_text("Hello world!")).to_be_visible() """ ) # Run the isolated test suite with pytest result = pytester.runpytest() # Check that one test passed result.assert_outcomes(passed=1) This pattern is sufficient for many fixtures, but it doesn’t work for Playwright – if you run this test, the isolated test suite gives an error rather than a passing test. Playwright needs you to install a web browser to work (for example, playwright install webkit), and Pytester runs in a sufficiently isolated environment that Playwright can’t find the browsers you already have installed. We could run the install command inside the temporary directory, but that would be slow and inefficient – it would be better if we could tell Playwright to look for the already-installed browsers elsewhere. If we set the PLAYWRIGHT_BROWSERS_PATH environment variable inside our isolated test suite, Playwright will look there for browsers. First, we need to work out where browsers are installed – we could hard-code the location, or we could inspect the executable_path property property on a browser: from pathlib import Path from playwright.sync_api import sync_playwright import pytest @pytest.fixture(scope="session") def playwright_browsers_path() -> str: """ Return the cache directory where Playwright browsers are installed. """ with sync_playwright() as p: # In my local builds, this returns a path like: # # ~/Library/Caches/ms-playwright/webkit-2272/pw_run.sh # # Unwrap two levels to get to the `ms-playwright` folder. return str(Path(p.webkit.executable_path).parent.parent) Then we need to set this as an environment variable inside the Pytester test suite. I couldn’t find an easy way to set an environment variable; the best approach I came up with was to modify os.environ inside the conftest.py file. (Perhaps we could access the MonkeyPatch object and set more environment variables, but using private attributes is icky.) Here’s how the new test starts: def test_browser_fixture(pytester: Pytester, playwright_browsers_path: str): """ Test the browser fixture with pytester. """ # Make a conftest.py file pytester.makeconftest(f""" from chives.browser_fixtures import browser import os os.environ["PLAYWRIGHT_BROWSERS_PATH"] = {playwright_browsers_path!r} """) ... and now the overall test passes. Here’s the complete code for the new test: test_browser_fixture.py from pathlib import Path from playwright.sync_api import sync_playwright import pytest from pytest import Pytester @pytest.fixture(scope="session") def playwright_browsers_path() -> str: """ Return the cache directory where Playwright browsers are installed. """ with sync_playwright() as p: # In my local builds, this returns a path like: # # ~/Library/Caches/ms-playwright/webkit-2272/pw_run.sh # # Unwrap two levels to get to the `ms-playwright` folder. return str(Path(p.webkit.executable_path).parent.parent) def test_browser_fixture(pytester: Pytester, playwright_browsers_path: str): """ Test the browser fixture with pytester. """ # Make a conftest.py file pytester.makeconftest(f""" from chives.browser_fixtures import browser import os os.environ["PLAYWRIGHT_BROWSERS_PATH"] = {playwright_browsers_path!r} """) # Make an HTML file (pytester.path / "greeting.html").write_text(""" <p>Hello world!</p> """) # Make a temporary pytest test file pytester.makepyfile( """ from chives.browser_fixtures import file_uri from playwright.sync_api import Browser, expect def test_browser_fixture(browser: Browser) -> None: uri = file_uri("greeting.html") p = browser.new_page() p.goto(uri) expect(p.get_by_text("Hello world!")).to_be_visible() """ ) # Run the isolated test suite with pytest result = pytester.runpytest() # Check that one test passed result.assert_outcomes(passed=1) The full test suite is more extensive, and checks that certain scenarios fail or error – will the fixtures spot the mistakes I expect them to? For example, my Page fixture is meant to load a page and fail the test if there are any console warnings or errors; does it actually fail the test correctly? I don’t expect to use Pytester very often, because it’s rare for me to write fixtures complex enough to need their own test suite – but sometimes I do, and it’s good to know how to create another layer of safety net. [If the formatting of this post looks odd in your feed reader, visit the original article]
More in programming
A clip of me singing a funny song from Gilbert and Sullivan’s Ruddigore back in 2013
In this video, we look at why fork() needs copy-on-write, how it works inside the kernel, and a memory usage problem that Instagram encountered with Python.
Comments require commitment, but they’re worth it.
An aggregation is some kind of summary of a set of data. This can be the sum, length, minimum, etc. It is quite common to want to calculate such a summary repeatedly, e.g. “the maximum noise level in dB for the past 30 seconds” for a nuisance detector. In such a case we say there is a sliding window over our data, and we want to aggregate over our window. If our aggregation is a binary operator with an inverse, like integer sums, there is a very easy solution using a double-ended queue: from collections import deque class SlidingWindowSum: def __init__(self): self.sum = 0 self.elems = deque() def push(self, x): self.sum += x self.elems.append(x) def pop(self): self.sum -= self.elems.popleft() def eval(self): return self.sum But what if our operator has no inverse? This is actually the case for most interesting summaries such as minimum, quantile, approximate unique count (for example using HyperLogLog), etc. In fact, even something as simple as a floating-point sum suffers from the fact that floating-point addition is not invertible. For example, if you ever have a NaN in your input data with the above naive algorithm your sum will forever remain NaN, even long after the bad value has left your window. Six years ago I came up with an algorithm for maintaining just the minimum/maximum in a sliding window and posted it to cs.stackexchange. I now consider this algorithm pointless, because it turns out there is a simple and efficient algorithm that solves this problem for a very wide class of aggregations. I’m writing this blog post to spread the word, because I feel it should be more widely known. Folklore I came across this algorithm while reading a far more advanced paper, Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time by Tangwongsan et al. Why is this paper titled low-latency? Because it does the same as what I’m about to describe, but in O(1) time for each step. However, in it they also described a “two-stack” algorithm, which does it in amortized O(1), and is far, far simpler. Amortized O(1) means that across many operations the total amount of work per element is constant, but an individual operation can take much longer. This is almost always fine, unless you absolutely need a low upper bound on latency. Funnily enough that paper attributes this algorithm to “adamax” from a 2011 Stack Overflow post. They in turn credit a 2001 lecture note by D. Sleator for the inspiration. However, this lecture note does not describe a sliding window aggregate, it describes the classical two-stack algorithm for implementing a FIFO queue and does amortized analysis on it. Ultimately I would not be surprised to find that this algorithm was already described in an obscure paper from the 1970s, seeing how simple and brilliant it is. Two stacks Like the authors of the paper, I will generalize the two-stack algorithm to arbitrary associative aggregation functions. By abstracting the aggregation as a set of functions, empty(), unit(x), combine(x, y) and finalize(x), you can describe many possible aggregations, for example a mean: empty = lambda: (0, 0) unit = lambda x: (x, 1) combine = lambda x, y: (x[0] + y[0], x[1] + y[1]) finalize = lambda x: x[0] / x[1] if x[1] else None I’d like to note here that these functions have the following signatures: fn empty() -> Agg; fn unit(x: Value) -> Agg; fn combine(x: Agg, y: Agg) -> Agg; fn finalize(x: Agg) -> Out; I’m making a distinction here between Value, Agg and Out because while they seem superficially similar for something like an integer sum, for an approximate unique count on strings you would have (Value, Agg, Out) = (String, HyperLogLogSketch, u64), three wildly different types. Without further ado, the algorithm: class TwoStackAgg: def __init__(self): self.values = [] self.values_agg = empty() self.cum_aggs = [] def push(self, x): self.values.append(x) self.values_agg = combine(self.values_agg, unit(x)) def pop(self): if not self.cum_aggs: cum_agg = empty() while self.values: cum_agg = combine(unit(self.values.pop()), cum_agg) self.cum_aggs.append(cum_agg) self.values_agg = empty() self.cum_aggs.pop() def eval(self): return finalize( combine(self.cum_aggs[-1], self.values_agg) if self.cum_aggs else self.values_agg ) That’s it, the entire algorithm. There’s two stacks (values and cum_aggs) and one more aggregate, values_agg. At any point in time values_agg holds the aggregate of values, and cum_aggs contains the cumulative aggregates of all values in our window that aren’t in values, in reverse order. From this we can get the aggregate over our entire window in constant time by by combining the last value of cum_aggs with values_agg. The neat part is that (assuming w is our window size) every wth operation we drain all of values and maintain a running aggregate while pushing the partial cumulative aggregates onto cum_aggs. This is what makes it amortized O(1), doing O(w) internal operations every wth pop bounds the total amount of work per element to O(1), even though a singular operation might not be constant time. I think this is best visualized. Suppose we sum [1, 2, ..., 10] with a fixed-size sliding window of four elements, then the state on each eval() call would look like this (values_agg not shown as it is simply the aggregate of the values): cum_aggs values out [] [] = 0 [] [1] = 1 [] [1, 2] = 1 + 2 [] [1, 2, 3] = 1 + 2 + 3 [] [1, 2, 3, 4] = 1 + 2 + 3 + 4 [4, 3 + 4, 2 + 3 + 4] [5] = 2 + 3 + 4 + 5 [4, 3 + 4] [5, 6] = 3 + 4 + 5 + 6 [4] [5, 6, 7] = 4 + 5 + 6 + 7 [] [5, 6, 7, 8] = 5 + 6 + 7 + 8 [8, 7 + 8, 6 + 7 + 8] [9] = 6 + 7 + 8 + 9 [8, 7 + 8] [9, 10] = 7 + 8 + 9 + 10 [8] [9, 10] = 8 + 9 + 10 [] [9, 10] = 9 + 10 [10] [] = 10 [] [] = 0 In total the memory usage is O(w), where w is your maximum window size. Note that for simplicity of analysis and the example I assumed a fixed-size window w, but there is nothing about the two-stack algorithm that requires this. You can call push(x) and pop() as many times as you’d like between each eval(), growing and shrinking the window size as needed. Floating-point non-associativity Note that we required above that our aggregate combine is associative, meaning: combine(combine(x, y), z) = combine(x, combine(y, z)) Technically speaking, floating-point addition doesn’t respect this. Nevertheless, the above algorithm is still very useful because the results closely match the expected outcome, even more so if you use a compensated summation algorithm like Kahan summation. Another neat thing about the two-stack algorithm is that it doesn’t require commutativity, if you follow the above implementation precisely. The order of operands is maintained, which can matter for things like string concatenation. However, there is a second very useful property of the above algorithm. Each aggregate is strictly a combination of the elements in the window, and none outside the window. This means if your window contains a NaN or infinity (or some other outlier), that value only poisons the windows that contain it rather than the rest of your computation. But even without NaN or infinity it is useful, due to not propagating errors endlessly. E.g. if your sliding window starts with [1e20, 1], this is what would happen with a naive rolling sum: >>> 1e20 + 1 - 1e20 - 1 -1.0 Compensated summation will reduce these effects, but not making your result depend on values outside of the window will eliminate long-term error accumulation entirely.