The Fugue

If you get errors like this:

$ autoreconf
configure.ac:110: error: possibly undefined macro: AC_TYPE_UINT8_T
If this token and others are legitimate, please use m4_pattern_allow.
See the Autoconf documentation.
configure.ac:111: error: possibly undefined macro: AC_TYPE_UINT16_T
configure.ac:112: error: possibly undefined macro: AC_TYPE_UINT32_T
configure.ac:113: error: possibly undefined macro: AC_TYPE_UINT64_T
configure.ac:115: error: possibly undefined macro: AC_TYPE_SSIZE_T
autoreconf: /usr/bin/autoconf failed with exit status: 1

It probably just means you have an old autoconf. These macros were introduced in autoconf 2.60. But it’s probably no big deal if you have a sensible stdint.h.

I’m seeing an EINVAL result when trying to do a sndmsg() call to a UNIX socket. The man page says that means that the sum of the iov_lens overflows an ssize_t, but an ssize_t is 8 bytes on this machine and there’s only one iov and its length is 671. Last I checked that doesn’t overflow anything but a char. What gives? Same code works fine in Linux and when using UDP or TCP.

So you fire up gdb and pepper your code with assert() calls. Then one of your assertions fails and you see this:

Assertion failed: (item_idx < si.slabclass[clsid].perslab), function ITEM, file slabs_items.h, line 78.
Program received signal SIGABRT, Aborted.
0x00007fff83efab16 in kevent ()
(gdb)

Well shucks, you think you're screwed because gdb doesn't seem to have left you in a useful state. So you investigate conditional breakpoints (that are a pain to set and don't seem want to work in inline functions), and generally beat yourself over the head for awhile.

Then you realize that gdb's throwing you out into a different thread, and your pretty backtrace is there for the exploring, you just have to switch to the right thread. Yeah, remember that. Then maybe you can set a breakpoint on the actual assert code (which you can find with the backtrace—it was __assert_rtn() in my case) so you're already in the right thread and just need to go up the backtrace one level to get to debugging goodness.

A very important tool in the toolbox of any collaborating developer is a merge conflict resolution tool. OS X has the fantastic FileMerge, there are various graphical tools for linux like kdiff3, but I have yet to hear of one for the terminal. There’s vimdiff, but it is really not up to the task of merge conflict resolution (doesn’t handle 3-way diffs). There’s probably something in emacs, just because there’s always something for emacs. Emacs users please enlighten me, I’m not above using emacs for merge-conflict resolution. Might even be the gateway drug.

It doesn’t seem overly hard (at least, no harder than writing kdiff3 or FileMerge) to make an ncurses tool that will take a 3-way merge and let you efficiently choose A, B, or edit for each diff section. Can it really be that nobody has done it yet?

May was a busy month, and not in a “fast-track-to-finish-dissertation” kind of way. I zoomed to Florida for a family reunion, then zoomed across the country to San Fransisco for an interview at Facebook, then the next week zoomed over to NYC for an interview at Google in their Manhattan office. Then, lest the last week in May should feel left out, I zoomed up to Utah for an interview with AST. As May drew to a close and June entered the scene, I found myself with four offers of employment, including Google and Facebook (Boeing just did a phone interview). Wow! I was feeling pretty pleased with myself.

Now dear casual reader from yonder internet, I know what you’re thinking. It’s exactly what I would have thought a few months ago. “No-brainer. Work for Google.” But I found myself perplexingly unable to decide between Google and Facebook. It didn’t help that Google was in New York and my wife wasn’t keen on New York, and that the Google position offered was a Site Reliability Engineer (SRE) which is, to grossly oversimplify, a glorified systems programmer. Not faced with an attractive competing offer like the one from Facebook, I’d have been headed to Manhattan to be an SRE in a heartbeat. But as it was I was torn.

I applied for the Facebook position on a whim. I had been on Facebook only a month or two and I noticed an ad on the side about how they were hiring. I clicked on it, looked at their careers page for awhile, liked what I saw, and decided to apply for a Machine Learning Engineer position. I came home and told my wife, who was instantly convinced I had lost my marbles. She is not a programmer, so how could she know that although I’m not a big social network guy and had only grudgingly signed up for Facebook a month or two before, I could be intensely interested in working on such a site.

Theoretically speaking, I love networks, and that includes graph theory, computer networks, and yes even social networks. I knew Facebook problems would be about networks and about scale. They would be hard problems. They would be fun problems. The perks page looked good, and I think it would be fun to be in Silicon Valley. So I applied.

Facebook called and had me do one of their pre-screening programming puzzles (you can enjoy them even if you’re not being considered for employment). I got a little obsessed and did 3 over the better part of a week. Then there was a phone screen, and then the invitation to interview on-site (This all happened over several weeks time, of course, and more or less in parallel with a similar process for Google, except that Google didn’t have a puzzle step).

I’ll skip to the end, lest I bore you. Facebook continually impressed me the more I interacted with them and the more I saw. I was similarily surprised at how enjoyable, useful, and private Facebook was as a user since I had signed up. Facebook skyrocketed from just another one of those pesky social networking sites to a daily habit and potential employer in a few short months.

Still, it can’t compare to Google right? Well, actually they try very hard to compare to Google. It’s quite obvious that most of the perks and benefits are directly inspired by Google’s, compensation was comparable, and I found that they have smart people working on hard problems just like Google. In addition, there are two things they have that Google doesn’t anymore: they’re still small and they’re pre-IPO. Of course, Google has more smart people and Facebook is more-or-less a one-trick pony. Publishing would probably be easier at Google. Here I go again… I was back and forth for a solid week. It drove me and my wife crazy. I talked to people at Facebook who had been at Google (at my request). I talked to people at Google. I talked to friends and family. I tried every decision making trick in the book. Both sides sweetened the deal a bit to make it easier for me to choose them (Google switched the offer to be in Mountain View as a Software Engineer, Facebook offered a bit more money). I just couldn’t make up my mind.

Well finally I did, and this is what it came down to: time off, impact, and stock.

Although both were generous with paid time off (PTO) compared to most US companies, Facebook offered more, especially in the area of paternity leave (my wife is expecting). As much as I anticipate enjoying either job, I enjoy being at home or on vacation with my family more.

Facebook is small—they’re hiring like crazy because they’re smaller than they want to be. Because of that, I feel that my wacky background in system administration, agileish pragmatic open-source programming, and high-brow CS theory and research would be more broadly brought to bear than in some team at Google responsible for some small part of one of the many wonderful Google products. I would have more impact—not on the world at large but on the thing that we are doing. Then there’s also the draw of quick seniority in a small and fast-growing company.

Finally, although both companies offered restricted stock units to vest over 4 years, Facebook’s offering has the potential to be worth several times what Google’s offering would. Or, Facebook’s offering could be worth about what Google’s would be. Or, in a really really bad scenario, worth less. I ran the numbers, pulled some probabilities out of the air, and decided at least as good as Google and possibly much better was the most likely scenario. Since they’re RSUs and not options, the only risk is in making less extra cash than I would have made at the other company. Google was the safer choice, Facebook the more potentially lucrative. I tried to leave this out of the decision making process as much as possible, because I didn’t want my decision to be about money. I wanted it to be about the work. But I have to admit there’s a draw here.

I believe more strongly now than I did before that Google is a fantastic place to work, and I would reapply there in a heartbeat down the road if my path takes me there. I wish I could just be in two places at once and work at both, at least long enough to know for sure where I really want to be. But life doesn’t work that way. I’ve decided to take the path that seems the most exciting and unsure out of a sheer sense of adventure. Google will be there in a few years if I want to reapply, and they may even want me then as they do now. The time to really make a difference at Facebook is now, while they’re small.

You may think I’m crazy to turn down Google. I think that sometimes too. One thing is certain: the next few years will be an amazing adventure that I never dared dream would come to me. Thanks to everyone who has helped me to this point in my life, especially my loving and supportive wife and kids, my parents who taught me to love learning, and my brothers who “let” me hog the computer when we were young (ha!).

Well, I think I have a dissertation lying around here that needs finishing.

Not literally, of course. This is programming talk, those of you who aren’t programmers can let your eyes glaze over.

I wanted a script to start a bunch of little servers, then wait around for them to finish or when the user interrupts with Ctrl-C, clean up the servers instead of orphaning them. I wanted to propagate the SIGINT to the child processes. I wanted to kill the kids.

The simple way, if you just want to make sure the kids are killed and you don’t care how:

sleep 300 &
# etc.
trap "kill $(echo $(jobs -p)) 2>/dev/null" EXIT
wait

If you only want to trap SIGINT and want to make sure you send SIGINT (not SIGKILL) to the children, then you want to do something like:

trap "kill -INT $(echo $(jobs -p)) 2>/dev/null" INT
wait

Update: I was asked by a shell scripting guru why I needed to do $(echo $(jobs -p)) and not just $(jobs -p). I intended to cover that but forgot. The reason is that $(jobs -p) has newlines and while that’s not usually a problem it is in a trap statement, because it’s evaluated at creation time not at run time. It also means that processes created after you create the trap wouldn’t be killed. Then, he suggested a function instead. Pure brilliance. Where does he come up with these things? Here’s the improved version:

function killkids() { kill $(jobs -p); }
trap "killkids" EXIT

You can still redirect stderr if you want to, but the reason I was directing stderr was because some of the kids may have already died (early evaluation remember) and then kill would needlessly complain. This way, it kills all the kids that are still alive, none more none less.

I often get confused about the scaling of magnitude and power spectra. I think I’ve worked it out so I’m puttin it here for my own benefit, and maybe the benefit of someone on the internet. If I’m wrong, please tell me.

Let’s take a unit-amplitude sinusoid at 100 Hz, and do a Fourier transform. If we look at the amplitude we’d get two components at 100 Hz and -100 Hz, each with amplitude 1/2. Something like this.

Now, if we do the same with a DFT we will get basically the same thing, except we’ll see the effects of discretization of course. But depending on which variation of the DFT you’re using, the magnitude of the components will be either about 1/2 or about N/2. The difference is, of course, the 1/N factor that you included or left out. In the case of the fft function in Octave (and I assume MATLAB), it’s without the 1/N factor.
max(abs(fft(x,1024)))
ans = 443.23

The power spectrum is the magnitude spectrum squared. abs(fft(x)).^2 or (abs(fft(x))/N).^2. Why would you want to square it? Well there are of course many reasons but the nature of audio signals makes most of the ones I know about moot. Furthermore the relative shape of the power spectrum and the magnitude spectrum is the same.

Try this. Take an audio signal (something more interesting than a single sinusoid) and plot the magnitude spectrum in dB, then plot the power spectrum also in dB, e.g.
plot(20*log10(abs(fft(x))))
figure
plot(20*log10(abs(fft(x)).^2))

They have a different scale, but they have the same shape. If you were doing something like peak-picking, it wouldn’t matter which you used if you’re working in dB.

I was walking home yesterday and walked past a girls soccer team practicing. The coach blew his whistle and they all started running around the circumference of the field. Naturally this brought up unpleasant memories of doing the same thing in basketball practice. But then I noticed something I hadn’t noticed in basketball practice. I wish I had my camera with me.

As they ran, they began to strew out—that annoying short girl with boundless energy in front, a pack of normal girls in the middle, and the tall and/or not-very-fit girls in the back (you can guess where I usually fell). What struck me is that even with a sample size of only about 15 girls, it was almost immediately very obviously a normal distribution. As they continued running, they got more strewn out, but the bell curve remained essentially intact. (It got a little bimodal for a bit, but give them a break—they’re only middle school girls.)

Is it sad that I think beauty in nature is noticing statistical truths everywhere?

I love it when someone else writes what I’ve been meaning to write, so I don’t have to write it.

This article covers the reasons why I switched from mercurial to git, about as well as he could possibly hope to without consulting me, reading my mind, or being me. It’s a bit creepy.

He explains it very well (probably better than I would) and has more insight into the technical details than I do.

While we’re on the subject, you should all go read git for computer scientists so you can think like a git. If you already have a CS background, it’s quite painless I assure you.

Tensai asked me how I made my graphs in my ringtones post. I’d like to blather on about the graphs and why they’re cool and how you can make them, because that’s the sort of thing I’m good at.

In the olden days, the spectrogram was invented.

Originally greyscale, they are now usually portrayed in color, with “hot” colors meaning higher amplitude and “cool” colors meaning lower amplitude.

While there are myriad ways to view and/or generate spectrograms, the most convenient for me right now is to do it in Octave. If you’re not familiar with Octave, it’s a MATLAB clone. Octave is libre, MATLAB is insanely expensive. Obviously, I use Octave. I have used MATLAB previously (I had a beta copy, until it left beta), and for the most part they are quite comparable. Octave is a bit slower for some things (less optimized) but I’ve seen Octave outperform MATLAB on some specific tasks. The biggest impedance mismatch is in user interface stuff (MATLAB has sophisticated dialog support) and graphing. Octave has most of the essential graphing functionality (it uses gnuplot to render graphs).

So how do we generate a spectrogram in Octave? First we need to read in the WAV file, then we generate the spectrogram.

[x,sr] = wavread('logchirp.wav');
specgram(x,8192,sr);

8192 is the size of the FFT. I find 8192 is a nice compromise between time and frequency resolution (and computation time), but other powers of 2 (especially 1024) are common as well. Here’s the chirp spectrogram:

Notice how the chirp is logarithmic. To our ears, this sounds like a steadily-rising tone. For this reason when dealing with music it’s often better to look at a log-frequency spectrogram. Otherwise all the low frequencies are scrunched together and the relationships between different pitches (and harmonics) aren’t constant. Here’s a log-frequency spectrogram of the same chirp:

This was generated by the Octave code

logfsgram(x,8192,sr); title('logchirp.wav');

Notice the bleed on the low frequencies, this is because we need a longer FFT in order to get more frequency resolution at low frequencies. This is a tradeoff in time resolution though, and processor time. Experiment with different FFT lengths for extra credit.

To use these functions you’ll need to put the specgram and logfsgram “m-files” in your octave search path (current directory or whatever else you specify in your ~/.octaverc).