Using black magic to make a fast circular buffer.

Yesterday, I took a glance at the Wikipedia page for the circular buffer and was intrigued by an alleged optimization technique that I was not familiar with:

A circular-buffer implementation may be optimized by mapping the underlying buffer to two contiguous regions of virtual memory. (Naturally, the underlying buffer‘s length must then equal some multiple of the system’s page size.) Reading from and writing to the circular buffer may then be carried out with greater efficiency by means of direct memory access; those accesses which fall beyond the end of the first virtual-memory region will automatically wrap around to the beginning of the underlying buffer. When the read offset is advanced into the second virtual-memory region, both offsets—read and write—are decremented by the length of the underlying buffer

When implementing a circular buffer, we need to handle the case where a message spans the “discontinuity” in the queue and wraps around. The naive circular buffer’s write routine might employ a byte-by-byte write and look something like this:

void put(queue_t *q, uint8_t *data, size_t size) {
    for(size_t i = 0; i < size; i++){
        q->buffer[(q->tail + i) % q->buffer_size] = data[i];
    q->tail = (q->tail + size) % q->buffer_size;

The fact that a modulo operation is necessary to index into the array makes this function hard (if not impossible) to vectorize, and thus unnecessarily slow. Though there are other optimizations we can make, the technique offered in the above Wikipedia surpasses hardware-agnostic approaches by virtue of the fact that the memory management unit can handle most of the wrap-around logic on our behalf. I was so excited by this idea that I did no further research whatsoever, and implemented it based only on the brief description above.

Continue reading Using black magic to make a fast circular buffer.

Integrating GitLab and Google Calendar.

Zeall, like many other software startups, uses GitLab for version control and issue management. We also use the ever-popular Google Calendar to handle meetings, reminders, and deadlines. For several months, we’ve been looking for a way to automatically push GitLab issue deadlines into Google Calendar, and until now it seemed impossible. Only after a recent migration from our own private mailserver to G Suite did we find a solution — or rather, figure out how to feasibly build one.

Continue reading Integrating GitLab and Google Calendar.

Fun with integer division optimizations.

I recently stumbled across a post about some crazy optimization that clang does to divisions by a constant. If you aren’t interested in reading it yourself, the summary is as follows:

  • Arbitrary integer division is slow.
  • Division by powers of 2 is fast.
  • Given a divisor n, the compiler finds some a, b such that a/2b approximates 1/n.
  • This approximation gives exact results for any 32-bit integer.

I was interested in seeing just how much faster this seemingly-magic optimization was than the regular div instruction, so I set up a simple test framework:

Continue reading Fun with integer division optimizations.

The problem with Python’s datetime class.

This might sound like a strong opinion, but I’m just going to put it out there: Python should make tzinfo mandatory on all datetime objects.

To be fair, that’s just an overzealous suggestion prompted by my frustration after spending two full days debugging timestamp misbehaviors. There are plenty of practical reasons to keep timezone-agnostic datetimes around. Some projects will never need timestamp localization, and requiring them to use tzinfo everywhere will only needlessly complicate things. However, if you think you might ever need to deal with timezones in your application, then you must plan to deal with them from the start. My real proposition is that a team should assess its needs and set internal standards regarding the use of timestamps before beginning a project. That’s more reasonable, I think.

Continue reading The problem with Python’s datetime class.

Parallelizing single-threaded batch jobs using Python’s multiprocessing library.

Suppose you have to run some program with 100 different sets of parameters. You might automate this job using a bash script like this:

ARGS=("-foo 123" "-bar 456" "-baz 789")
for a in "${ARGS[@]}"; do
  my-program $a

The problem with this type of construction in bash is that only one process will run at a time. If your program isn’t already parallel, you can speed up execution by running multiple jobs at a time. This isn’t easy in bash, but fortunately Python’s multiprocessing library makes it quite simple.

Continue reading Parallelizing single-threaded batch jobs using Python’s multiprocessing library.

A simple recommender system in Python.

Inspired by this post I found about clustering analysis over a dataset of Scotch tasting notes, I decided to try my hand at writing a recommender that works with the same dataset. The dataset conveniently rates each whisky on a scale from 0 to 4 in each of 12 flavor categories.

Continue reading A simple recommender system in Python.

Why are tuples greater than lists?

I pose this question in quite a literal sense. Why does Python 2.7 have this behavior?

>>> (1,) > [2]

No matter what the tuple, and no matter what the list, the tuple will always be considered greater. On the other hand, Python 3 gives us an error, which actually makes a bit more sense:

>>> (1,) > [2]
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
TypeError: unorderable types: tuple() > list()

The following post is a journey into some CPython internals, with a goal of finding out why 2.7 gives us such a weird comparison result.

Continue reading Why are tuples greater than lists?

An easy way to visualize git activity

Today, I wrote gitply — a fairly simple Python script for visualizing the weekly activity of each contributor to a git repository.

It started out as a run-once script to get some statistics for one of my projects, but I ended up improving it incrementally until it turned into something friendly enough for other people to use.

Continue reading An easy way to visualize git activity

Demonstrating the double-DES meet-in-the-middle attack


DES (Data Encryption Standard) is an old-school block cipher which has been around since the 1970s. It only uses a 56-bit key, which is undeniably too short for use in the modern day. Between the realization that DES is weak in the late 90s and the invention of AES in the early 2000’s, Triple-DES had a brief time to shine.

Triple-DES is just what it sounds like: you run the DES algorithm three times. You use two 56-bit keys, K1 and K2, and apply them in the order K1K2K1. The result is a cipher with 112 bits of key strength.

Students often ask me, why not just encrypt twice: K1, K2, done? The reason is that this construction is vulnerable to a particular chosen-plaintext attack, which we call the meet-in-the-middle attack. That is, if the attacker knows your plaintext in addition to your ciphertext, he doesn’t have to try all 2^112 keys. The maximum amount of work he has to perform is actually only 2^56 — not much more than to break single DES.

Continue reading Demonstrating the double-DES meet-in-the-middle attack

A fun experiment with Twilio

I first heard about Twilio a long, long time ago. As Google Voice faded out of relevance, it took the lead in the mobile-communication-as-a-service market. However, I had never had the chance (or inclination) to play around with its API until today.

About 12 hours after we landed back in the US from our holiday in Mexico, Lynsey departed once again — this time to the Plant and Animal Genome conference (PAG) in San Diego. She asked me to supply her with pictures of our cats for the duration of her trip. I told her I would send her a cat pic every hour, on the hour.

I didn’t realize what I had gotten myself into until I had already deposited $20 into a new Twilio account and spent 2 hours coding away… Though my goal was just to send some photos of cats, I had developed a pretty general application that lets you build a queue of MMSes to be disseminated at a constant rate.

Continue reading A fun experiment with Twilio