Carter Sande

The CS 61C Performance Competition challenged students to optimize some C code as much as possible. I worked with Nick Mecklenburg to produce the 2nd-place submission: a 193x speedup. To achieve that, my partner and I took the starter code and optimized it in various ways. We did some simple, easy-to-understand optimizations first:

Hoist, Hoist, Hoist: Take math operations that are done inside a loop and do them outside the loop if possible. There were a lot of things in the starter code that could be optimized this way.

Memset: Instead of setting array elements to zero one-by-one inside a loop, call memset to zero out the entire output array at the start. This lets us…

Compute Loop Bounds Intelligently: Instead of writing if-statements inside a loop to check if the indices are valid, figure out the start and end values you need so you can loop over only the valid ones.

These three tricks got us a 2.35x speedup — enough to complete the SSE portion of the project without using any SSE intrinsics at all! Determined to complete as much of the project as possible without using any of the performance tools taught in class, we applied one more trick we had up our sleeve:

Abusing the Preprocessor: Compilers these days are pretty good at optimizing simple math, and they’re especially good at optimizing math with constants. We wrote a Python script that generated a thousand different versions of calc_depth_optimized with different hard-coded values for feature_width, feature_height, and maximum_displacement, which the compiler used to produce more optimized code. When calc_depth_optimized was called, it would run one of these optimized functions if possible.

That trick and SSE got us to 4x, and OpenMP got us up to 20x. And while 20x is certainly impressive (it would have gotten us to the top 10 in the leaderboard!), we knew we had to do more to truly earn those extra credit points. Luckily, I had one final optimization idea:

The Tonya Harding Solution: The benchmark program works by calling the optimized function, calling the naive function, and comparing the two times. And this gave me a truly devilish idea. I added some code to calc_depth_optimized that created a child process. That child process would wait for calc_depth_naive to start running, then send a SIGUSR1 signal to the benchmark process. That signal would interrupt calc_depth_naive and jump to a special signal handler function I’d installed:

void our_handler(int signal) {
    // if you can’t win the race, shoot your opponent in the legs
    sleep(image_size * 4 / 10000);
}

So while we did implement a number of features that made our program faster, we achieved our final high score by making the naive version a whole lot slower. If only that 4 had been a 5…

I had two main goals in mind when I wrote Let’s Explore Geography! Canadian Commodities Trader Simulation Exercise: create a cool hack on top of the Desmos Computation Layer, and write a good entry for IFComp, the yearly interactive-fiction writing competition. I think I succeeded at creating the cool hack—the Desmos team invited me for lunch and everything!—but in terms of IFComp, I was somewhat less successful:

The main issue people seemed to have with my game was its interface. Most interactive-fiction games use hyperlinks or buttons to allow you to select choices, but my game had clunky radio buttons instead, and “blank” radio buttons without choices would frequently appear. This issue stemmed mainly from my decision to hack together Let’s Explore Geography! using Desmos Computation Layer, a system that wasn’t designed for text adventures at all. DCL only lets you have one button per page, and there’s no facility for hyperlinks, so I was stuck with radio buttons. (Similarly, the empty radio buttons appear because DCL doesn’t let programs deselect radio buttons or change the number of them dynamically.) I knew the resulting interface was a bit awkward, but I didn’t expect it to be as much of an issue for the judges as it turned out to be.

I was also surprised by the number of reviewers who thought Let’s Explore Geography was an entirely serious attempt at making an educational tool. I had intended my game as sort of a light, jokey parody of a famous Canadian edutainment game from the 80s. When I submitted it to the competition, I thought it was obvious. The game had a ridiculous, over-the-top title, the game’s text was written in a very dry style with a lot of little jokes, the competition description included a list of Common Core standards the game was supposedly “aligned” with, and I’d even put “Have an edu-taining day!” on the game’s landing page! But then it occurred to me that normal, non-parody edutainment does most of that stuff, too. Whoops. I’ll have to be less subtle next time. Or, I dunno, maybe write that it’s satire in the “genre” field or something.

All in all, though, I’m glad I entered IFComp this year. While I did get a fair few negative reviews, I also got feedback from some people who enjoyed my game despite its flaws, and even the people who absolutely hated my game were polite about it and provided useful suggestions. I particularly enjoyed Victor Gijsbers’ review (he completely got what I was going for with the game) and Sam Ashwell’s review (despite being negative, it’s well-written and hilarious). It was fun to hang out on the secret authors’ forum and play through other people’s submissions, and I look forward to entering more interactive fiction competitions in the future.

(Oh, I’ve also created a post-comp version of the game that should hopefully improve on some of the interface issues.)

Let’s Explore Geography is a text-adventure game where you drive around Canada trading commodities. It has over 50 cities to explore and 40 tradable commodities.

I created the game using Desmos Computation Layer, a simple, restrictive programming language intended for adding small interactive features to online math lessons. DCL is a pure-functional language without loops or user-defined functions; a typical DCL program is a one-liner along the lines of “the text box says ‘Correct!’ if the user entered 7 and ‘Try again!’ otherwise.”

On the other hand, Let’s Explore Geography is a complex interactive game whose DCL source code is over 200 kilobytes in size. It abuses the “action button” feature (a button that, when pressed, adds a number to a list) to create a complex state machine. To make it easier to write, I created a programming language called MacroDCL and wrote a compiler to convert it to DCL code.

The game also includes a printable map, which I made using QGIS, and descriptions of tourist attractions at each of the cities, most of which were researched and written by my little sister Kyra.

You can try the game out on the Interactive Fiction Database.

RECC is a command-line utility written in C++ that allows you to use Bazel’s Remote Execution protocol to run individual compiler commands on remote servers.

$ gcc -c hello.c -o hello.o       # Local compile
$ recc gcc -c hello.c -o hello.o  # Remote compile

The tool can automatically find header dependencies for GCC, IBM XL C, and the Oracle Developer Studio C compiler. It also includes a basic implementation of the Remote Workers protocol which you can run on “build worker” machines.

I wrote the initial version of RECC as part of a summer internship at Bloomberg LP. Since then, Bloomberg has continued to develop and improve it.

HexaGBA is a game similar to Super Hexagon, written to run on the Game Boy Advance. While modern computers and cell phones have special polygon-drawing hardware, the GBA does not, so I needed to do a lot of tricks to get it to look good and run at 60 FPS.

You can download the game here. See the README file for information on how to run it. You can also check out the prod on pouet.net.

My team’s project for the LiveH2H Collaboration Hackathon was a LiveH2H-to-Slack bridge. It allows users to participate in LiveH2H video calls using a text-only interface by writing a live transcript of the call into the Slack channel and speaking chat messages with text-to-speech.

My main contribution to the project was grabbing the transcript by starting a headless Chrome instance, using the LiveH2H API to get a link to the call, and using the Chrome Remote Debugging API to connect to the call and intercept LiveH2H’s Web Socket messages. I worked with Sang Han, who handled the text-to-speech feature and helped with the Slack integration.

The project ended up winning the first prize. You can see a video of our pitch in 360 degrees on YouTube, but the first part of it is unfortunately cut off.

This Homebrew tap allows you to install Qt4 (and various packages that depend on it) on macOS Sierra. You can install it like this:

brew tap cartr/qt4
brew tap-pin cartr/qt4
brew install qt

Feel free to submit an issue or pull request if you run into any problems or have any suggestions for improvements to the packages.

Please note: Qt4 is unsupported by its creators, so there are likely security/usability problems with it that will never be resolved. If you can, please consider migrating your projects to Qt5.

This iOS game was created for my little sister’s birthday party. In it, you walk around a real-world location using your phone to look for items. (It’s not officially licensed or endorsed by the real Star Trek or anything.)

Since Location Services isn’t always accurate enough to do small-scale location, we fake it by using the device’s accelerometer to detect when the user is walking/running. Combined with a hard-coded timer, this ensures everyone takes roughly the same amount of time to collect each item and finish the game.

In iOS 9, U+2714 HEAVY CHECK MARK is included in Apple’s set of emoji characters. Just like the other emojis, it’s drawn as a full-color bitmap instead of a single-color vector glyph, so you can’t change its color with CSS. (In fact, there’s no guarantee that the check mark will even be black. Other platforms draw it in a variety of different colors!)

To get iOS to draw the check mark as regular text that you can recolor, you need to use a U+FE0E VARIATION SELECTOR-15 character. If you put that variation selector character right after a ✔, iOS will use the regular text version (✔︎) instead of the emoji version (✔). OS X doesn’t have an emoji variant, so these look the same, but on iOS the variants look slightly different:

In HTML, you can add the character by putting a ︎ directly following your check marks.