jon jensen's blog

Are you with us?

It really pays to digg — coding deathmatch 2.0

The good news: The coding deathmatch is back, this time with twice the prize money and a guarantee that every finalist will win something.

The bad news: Employees can't compete (obviously), and previous finalists can't win prize money, so that makes me doubly ineligible.

Ok, so it's not really bad news at all. Making previous finalists ineligible helps level the playing field and lets us share the love with everybody else. And as tempting as that $10K+ first prize is, to me it really isn't worth that whole unemployment thing.

So if you are a Utah programmer with nothing better to do this Saturday — let's be honest here, you're a programmer and you live in Utah — you owe it to yourself to sign up. It could be the easiest $10K you ever make in your life (Derek, it might be the easiest $10K you ever make in your life legitimately). Who knows, you might even find yourself doubly ineligible for the next one. Trust me, that's a good thing.

Sign up

Thwarting comment spam

There are a variety of approaches to combatting blog spam. Each has its pros and cons, and none of them is perfect. Three common approaches that I've seen:

1. CAPTCHA's can be effective, but spammers are getting better at finding ways around them. Generally speaking, the better the CAPTCHA is at keeping out spammers, the harder it is for your user to decipher.

2. Bayesian algorithms, keyword filters, and other types of content analysis are good, but spammers are getting smarter. Blog spam is becoming increasingly on-topic, making it harder to filter it out and requiring more manual work.

3. Requiring a login or subscription to a service is a good approach in theory, but in practice spammers have no problem setting up bogus accounts. Then there's the fact that most people don't like creating accounts just to post comments.

Recently I decided to test out a new approach to dealing with comment spam. It occurred to me that most spammers don't necessarily crawl my blog at the same moment they spam it. It seems more likely that they have bots that crawl the web to find comment forms (or even subscribe to services that do this) and then systematically spam it some time later.

So I set up a simple PHP script that ties into Apache's mod_rewrite to manage the URL's for my blog. Basically every day, the URL for the comment form changes. The new URL comtains an effectively random 32 character string, making it impossible to guess the correct URL without actually going to the blog. The end result has been an 80% reduction in comment spam. Combined with MT's junk filters, it has proven to be extremely effective.

The next step will be to adjust the frequency of the URL changes to see how that affects the remaining 20% — if it ends up making a big enough dent, I'll make the source public to give people an additional weapon in the war on spam.

Horizontal CSS bar graphs

Even though I've been doing CSS for years, I still think it's the coolest thing since sliced bread—the novelty hasn't worn off and probably won't until something better comes along.

Last night I gave my CV a much needed update. One neato feature I included in the online version is a horizontal chronology of my work experience. Looking at the source code reveals it's all done in CSS.

CSS bar graphs are nothing new, but my approach is a little unique. By using em's for all measurements, it makes it especially easy to specify the bounds of the various items; a job that lasted 12 months is simply 12 ems wide. This also makes the whole thing scale very nicely as you adjust text size.

Another cool thing is the toggle between outline and timeline views—just changing a class on the body completely restructures the whole thing.

It pays to digg — the deathmatch that wasn't

Whereas spam is the leading cause of lost productivity for many people, digg is my Achilles' heel. I spend more time on digg (and slashdot and fark) than I'd like to admit, so it's nice to see it finally paying off.

Last Friday I found this gem—a local programming contest with a $10K grand prize. This was the first I'd heard of it, even though it had received quite a bit of local media coverage. So I went to mozy.com and registered for the competition, and the next morning my $10K quest began.

Round 1 took place online and began at 10 AM, with six 10-minute programming challenges. Nothing overly complex, but the time limit left little room for error. Fortunately I got all of my solutions in, and shortly after was informed that I made the cut for Round 2.

Round 2 was also online, with 4 questions spread across an hour. Here's where things got a little more complicated and the technical difficulties began. One of the tasks required you to open a socket to the mozy.com server and read some data. Seems like everyone tried connecting at once, and a mini-DDOS ensued. In the end, I was able to connect, read the data and produce the correct output, but others weren't so lucky. At this point, I thought I had done pretty well, but I wasn't sure if I had made the final cut. Much to my surprise, I got an email shortly thereafter informing me I was one of 8 finalists.

We gathered at the mozy.com offices at 4:00 PM for the Ultimate Showdown of Ultimate Destiny. I was nervous—being a lapsed undergrad, I was going up against college faculty and professionals with far more experience and knowledge than me.

I should also point out that I had done all of the exercises in PHP, even the one with the O(2^n) algorithm (shudder). Everyone seemed a bit surprised that a PHP programmer had made it this far, and I can't say I blame them. PHP is looked down upon by many—it lacks the elegance of Java and the speed of C, and the language itself looks something like the mutant spawn of C++, Perl and Retarded. You might call it the short bus of programming languages, in large part due to the caliber of the average PHP programmer. Nevertheless, good programmers are rarely constrained by languages, and PHP is no exception. It kicks ass if you know how to use it.

Our final task was to write a server that would accept 10,000 connections. Each connection would send 9K of data - over 2000 4-byte integers. We would have to then sort the 20+ million integers and return the 100th, (n-100)th, and (n/2)th ones from the list. Whoever could do this the fastest would win the $10,000 prize.

And so it began. Sockets are easy, and there is only so much optimization you can do there, so I saved that for last. My main concern was making the sort as fast as possible. Rather than try to sort all 20 million numbers, I stored them in a 4-level tree—one level for each byte, meaning each node had at most 256 children. Memory was not a concern, only speed—I didn't actually sort anything unless I had to. That means I sorted at most 1024 (4*256) elements for the first lookup and 784 elements for subsequent lookups. Each node cached how many numbers it contained, making it easy to find a number in the tree once the relevant nodes had been reordered. The sorting itself incurred no real cost—the only consideration was the time to receive the numbers and populate the tree, which was constant relative to n. O(n) is nothing compared to O(n log n).

Once I had that squared away, I set up my simple server to handle the requests. I had overheard other people running into difficulties, and I soon discovered why. Windows doesn't like too many simultanous connections, and everyone hit a wall right around 300. Even with a 20 minute time extension, nobody was able to get it 100% working. Things were not looking good.

We had a quick powwow to figure out what to do. Several of us wanted to try running our programs on a Linux machine to see if they would fare any better. That helped a bit, but none of us were able to get much past a couple thousand connections—nowhere near the 10K target.

So after a brief debate, we decided there was no clear winner and the best thing to do would be to split the prize money 8 ways. Thus died the deathmatch, but everyone got something out of it in the end ($1,250 to be precise).

True, it was a bit of a letdown, but I really can't complain. The whole experience definitely piqued my interest in learning more about how TCP/IP connections are managed by the OS. It was especially interesting to see the working low-level prototype written by a mozy employee. It handled all 10K connections effortlessly, something none of our C++/Java/PHP/Ruby servers could do, due to shortcomings in our implementations and/or limitations of the OS.

I really would have liked to see how my sorting algorithm stacked up to everyone else's. I suppose there's always next year's competition. Guess I'll keep digging in the meantime.