Photo by crazybarefootpoet

I still remember my excitement when I discovered Google after years of struggling with awful search engines like Altavista, but every now and again it really doesn't find what I'm looking for.

I was just going to bed on Tuesday night when I remembered I had to start a job processing 500 GB of data, or it would never be done in time for a deadline. This process (merging adjacent lines of data into a single record) was painfully slow in the scripting languages I tried, so I'd written a tool in plain C to handle it. Unfortunately I'd never tried it on this size of data, and I quickly discovered an O(n^2) performance bug that ground progress to a halt. To fix it, I needed a hashmap of strings to speed up a lookup, so I googled 'c hashmap' to grab an implementation. I was surprised at the sparseness of the results, the top hit appeared to be a learning project by Eliot Back.

Before I go any further, if you need a good plain C hashmap that's been battle-tested and generally rocks, use libjudy. Don't do what I did, trying to build your own is a silly use of anyone's time! My only excuse is that I thought it would be quicker to grab something simpler than libjudy, and I'd had a martini…

I stayed up until 2am trying to get the hash map integrated, discovering some nasty performance bugs in the implementation as I did. For instance, the original code actually tried to completely fill the hash map before it reallocated, which means for a large map it often searches linearly through most of the entries if the key isn't present, since it only stopped when it found a gap. I also removed the thread primitives, and converted it over to use strings as keys, with a CRC32 hashing function.

I don't make any claims for the strength of the resulting code, but at least this version has a unit test and I've used it in anger. Thanks to Eliot for the original, here's my updated source:

http://github.com/petewarden/c_hashmap

Hopefully this will help out any other late-night coders like me searching for 'C hashmap'!

Photo by Joshua De Laughter

I recently finished The Big Rich, a history of Texas oil-men by the author of Barbarians at the Gate. It was striking how similar the early days of Texas oil felt to the current web startup world, full of skeptical old companies, a few new-born giants and a crowd of wild-catters convinced they were just one lucky strike away from riches.

One detail that really struck me was an innovation in financing that enabled the independent operators to build their businesses. Bankers in Houston began giving out loans with the collateral based on the estimated reserves underneath a wildcatter's oil wells. This was unheard of, but it made perfect commercial sense. As long as the banks could rely on a trustworthy geological report, the reserves represented a steady stream of cash to guarantee any loan. In return, the independents were able to re-invest in the gear and labor needed to sink new wells and expand.

This got me wondering if this is a better model than the current angel/VC equity standard for web financing? If you have a pretty reliable income stream from advertising on a site, are there banks comfortable enough scrutinizing audited visitor reports to lend you money against that? Nothing I'm working on fits that description, but I'm genuinely curious if we're at a stage of maturity in the industry where this sort of thing makes sense.

I see a lot of businesses out there that are never going to be the next Google but could be decent money spinners with some reasonable financing. The VC model relies on hitting for the fences, so most of the solid prospects I see end up either boot-strapping painfully slowly, getting angels and disappointing them with comparatively unexciting growth, or just hitting the end of the runway.

Photo by Pchweat

Building fanpageanalytics.com means analyzing with billions of pieces of information about hundreds of millions of users. At this sort of scale not only do traditional relational databases become impractical for my needs (even loading a few tens-of-millions of rows into a mysql table and then creating an index can take days), key-value stores also fail.

Why do they fail? Let's walk through a typical data-flow example for my application. I have an input text file containing new information about a user, so I want to update that user's record in the database. Even with a key-value store that means moving the disk head to the right location to write that new information, since user records are scattered arbitrarily across the drive. That typically takes around 10ms, giving an effective limit of around 100 users per second. Even a million users will take over two hours to process at that rate, with almost all the time spent tapping our toes waiting for the hard drive.

Stores like Mongo and Redis try to work around this by caching as much as they can in RAM, and using delayed writes of large sectors to disk so that updates don't block on disk seeks. This works well until the data set is too large to fit in RAM. Since my access locations are essentially random, the system ends up thrashing as it constantly swaps large chunks in and out of main memory, and we're back to being limited by disk seek speed.

So what's the solution? SSD drives don't have the massive seek bottleneck of traditional disks, but I'm still waiting for them to show up as an option on EC2. Instead, I've re-engineered my analysis pipeline to avoid seeks at all costs.

The solution I've built is surprisingly low-tech, based entirely on text files and the unix sort command-line tool. For the user record example I run through my source data files and output a text file with  line for each update, beginning each line with the user id, eg:

…
193839: { fanof:['cheese', 'beer'] }
…

I then run sort on these individual files, which since the command is very efficient and the individual files are only a couple of gigabytes in size, only takes a few seconds each. I can then take several hundred of these sorted sub-files and use the -m option on sort to very quickly merge them into an uber-file that's sorted, which avoids the thrashing you get when it tries to sort files larger than RAM.

What does this buy me? Within this uber-file, all the information related to a given user id is now in adjacent lines, eg:

…
193839: { fanof:['cheese', 'beer'] }
193839: { fanof:['hockey', 'ice fishing'] }
193839: { location:'Wisconsin' }
193839: { name:'Sven Hurgessoon' }
…

It's now pretty simple to write a script that runs through the uber-file and can output complete records containing all of a user's information from multiple source files without having to do any seeking, since you're just outputting each user to a new row or file, and all the source data is also local.

This same technique can be applied to any attribute you want to index in your source data. You can use the fan page name as the key in the first part of each line instead, which is how I'm assembling the data on each topic.

So in summary, I'm using sort to pre-order my data before processing to avoid seeks. I'm sure I'm not the only person to discover this, but it's not something that I've run across before, and it's enabled me to cope with orders-of-magnitude larger data sets than my pipeline could handle before.

Photo by Davezilla

If you've got someone's first name, it's possible to make a pretty accurate guess what their gender is. Obviously there's plenty of exceptions, Sean and Francis spring to mind, but for lots of applications you don't need 100% accuracy or coverage. In my case I want a better understanding the demographics of my users, so a figure that's within a few percent is fine.

There's a great Perl module called Text::GenderFromName that implements this idea, with accumulated wisdom dating all the way back to a 1991 awk script! I haven't found anything that fits well into my PHP projects though, so I finally bit the bullet and ported that Perl script to PHP. The result is up at

http://web.mailana.com/labs/genderfromname/

and you can get the source at

http://github.com/petewarden/genderfromname

Thanks to Eamon Daly and Jon Orwant for the original code, and apologies for the mechanical translation of Perl code to PHP. It's now painfully non-idiomatic, but it does work!

For best results you should also install the doublemetaphone PHP module, though it will function without it.

Fan Page Analytics is a new project I've just launched to help answer questions about Facebook pages. Here's some examples:

Which parts of the world have the most fans of God? In the US the map pretty clears shows the traditional Bible Belt, but looking worldwide the Phillipines is pretty god-fearing too.

How does ReadWriteWeb's fan base compare to TechCrunch's? From the map, RWW is much more broadly based, whereas TC's readership is heavily concentrated in the traditional US tech centers of California, Washington and Massachusetts. I only see one venture capital fan page in RWW's top 20 most related pages, but I count 8 in TC. On the other hand there's a couple of HR related pages for RWW, and none for TC, which suggests a less geeky audience.

That's all fascinating, but what problem does it solve? Suppose I'm planning the next DEMO conference. Glancing at the related pages shows that Charlene Li and Fred Wilson are people my audience care about, so they should be top of my list to attend and spread the word. ReadWriteWeb and GigaOm fans are more likely to be fans of DEMO than Techcrunch readers, so I might get more bang for my buck buying ad space on those sites. Looking at the locations, CA, WA and MA are way ahead, so I can craft some Facebook ads targeted only at those areas and tied in to some of the other related interests. I can even look at some examples of users in particular locations or with shared interests to understand if they're really my target market. These appear in the right side-bar when you click on an area or a location.

This is an initial release, so expect a few bugs, and it's not yet got complete coverage of fan pages, so apologies if yours isn't there yet. Hopefully you can still have some fun uncovering things like Glenn Beck's fan base in Outer Mongolia.

Photo by HerzogBR

One of the least-understood developments of the last few years is the growth of databases of personal information linked to email addresses. Rapleaf is probably the leader in this field, but even Flickr lets companies search their API for users based on an email address. I wrote a service that queries all the data sources I could find to demonstrate how much is out there:

http://web.mailana.com/labs/findbyemail/

Give it a try for yourself, you might be surprised by how much companies can discover about you once they know your email address! Many services give out at least your full name and a location, which is often enough to get your address and a phone number from a service like whitepages.com.

Google’s Intensity Map charts are a really easy and clean way to show heat maps of geographic data. Unfortunately, there’s no way to take the next step in the user experience, and let people mouse over and click on the maps to see additional information about a particular area.

To solve that problem, I’ve written a PHP script that extracts the country and state boundaries from the maps and constructs a Javascript function to return the state code for any point on the maps. You can see an example of this in practice at http://web.mailana.com/labs/mapclicker/ or you can download the complete source, including the boundary extractor.

The example page will show the state or country code for any point you move the mouse over on either of the maps, and if you click, will display an alert showing the name. It assumes your image has the maximum 440×220 dimensions, but you can apply scaling to the coordinates if you are using something smaller.

I've been using Google's simple map visualizer to picture some of the geographic data I'm gathering, but I've been looking for something more customizable and interactive. After a lot of searching, I finally found Mercator, an open-source flash library for creating maps. I've only been using it for a few hours, but already I'm very excited! It's not only very slick, with built-in animation and a clean look, it's also got a lot of depth, with data and graphics for an astonishing array of countries, states and cities.

The only down-side was getting started. The beginner's guide is aimed at someone with a deeper knowledge of Flash application building than me, and there was no 'hello world' example I could download, though there are several more advanced projects available. So, for anyone else out there who struggles with Flex basics here's a complete project for Flex Builder 3 that just creates and displays a Mercator map. You can see it running at the head of this post, or over at http://web.mailana.com/labs/mapview/

Manfred's done an excellent job on Mercator, it's a poster child for the quality of open-source projects, and I'm looking forward to creating some rich visualizations on top of it.

Photo by Christina Matheson

I've been working a lot with MongoDB lately, including some tinkering to add domain socket support. Unfortunately those modifications mean that I can't just use a binary download when I need to install it on a new machine, I have to build from source instead. There's general instructions on building for Fedora 8, but I found that yum had either versions that were too old for some packages like scons, or as with PCRE it ended up complaining about other programs requiring older versions than Mongo asked for.

As a result, I ended up creating a shell script to handle all the building steps required. This is pretty specific to my own environment and very hackish, but if you're running into the same sort of issues trying to use RPMs for all the dependencies, hopefully this will give you some hints on building from source.

Download Makemongo

#!/bin/sh
# Builds MongoDB and its needed dependencies for Fedora 8
# By Pete Warden

# First, make sure we have git
yum install git

# Now grab the Mongo source from github
git clone git://github.com/mongodb/mongo.git

# Get an up-to-date version of Scons, yum installs a 0.97 version that doesn't work!
curl -L "http://downloads.sourceforge.net/project/scons/scons/1.2.0.d20090919/scons-1.2.0.d20090919.tar.gz?use_mirror=cdnetworks-us-1" > scons-1.2.0.tar.gz
tar -xf scons-1.2.0.tar.gz
cd scons-1.2.0.d20090919/
# Scons relies on Python, so make sure that's present
yum install -y python-devel
python setup.py install
cd ..

# Now grab boost sources - I do see some warnings in Mongo's config about this being out of date
yum install -y boost
yum install -y boost-devel

# Spidermonkey is needed for Javascript support, and there's no RPM
curl -O ftp://ftp.mozilla.org/pub/mozilla.org/js/js-1.7.0.tar.gz
tar zxvf js-1.7.0.tar.gz
cd js/src
make -f Makefile.ref
JS_DIST=/usr gmake -f Makefile.ref export
cd ../..

# You need an up-to-date version of PCRE, more recent than the one installed by yum
curl -O "ftp://ftp.csx.cam.ac.uk/pub/software/programming/pcre/pcre-8.00.zip"
unzip pcre-8.00.zip
cd pcre-8.00
./configure --prefix=/usr
make
make install
cd ../mongo
scons all

# On my AMIs there's old versions of PCRE libraries left lying around, so move them
mv /usr/lib64/libpcrecpp.so.0 /usr/lib64/libpcrecpp.so.0.original
ln -s /usr/lib/libpcrecpp.so.0 /usr/lib64/libpcrecpp.so.0

# Create the database location and run Mongo
mkdir /mnt/data
mkdir /mnt/data/db
./mongod --dbpath=/mnt/data/db --bind_ip=/tmp/mongo.sock --port=0 &

# Now build the PHP drivers and add them to the php.ini
cd ..
git clone git://github.com/mongodb/mongo-php-driver.git
cd mongo-php-driver/
phpize
./configure
make
make install
echo "" >> /etc/php.ini
echo "extension=mongo.so" >> /etc/php.ini
/etc/init.d/httpd restart

We had my parents to stay over Thanksgiving. They'd never been to Colorado before, so there was plenty to do around Boulder, but I also wanted a long weekend somewhere in the mountains. After digging around on the great Vacation Rentals by Owner site, I found a little two bedroom condo near Idaho Springs, about an hour from Denver.

We drove up the I70, then about 9 miles up a twisty mountain road to get to the little community of St Mary's Glacier. I have to admit my heart sank when I saw the building we were staying in, it looked like an apartment block from East Germany in the 1970's. That impression wasn't helped by the two abandoned cars across the street, next to a boarded-up cabin with broken windows, along with multiple for-sale signs in our building. Climbing upstairs to the condo, the door across the hall had been forced open, splintering the frame. We were pretty sure it was being used by squatters, since the door was permanently open, but towards the end of our stay we spoke to the building manager and they'd apparently just lost their keys!

I felt a flood of relief once we stepped inside, the place was beautiful. You can see a full tour on Randy's website, but he's done a fantastic job decorating. There was a dining nook with windows on three sides, giving a view of the lake and mountains, and the living room was great in the evening thanks to the roaring fireplace.

The real point of the trip was outside the condo. Even though there hadn't been much snow, we were up at 10,400 feet so there was some pretty wild terrain. We had new snow-shoes to try out, so we trekked up the glacier itself, to 11,700 feet. We're fairly certain that Thor is the only Chihuahua to make it up to the top of the glacier, and we were all stunned by the views from the plateau. The only off-note was a couple of jack-asses on quad bikes who decided to ride them up the glacier despite all the sign-posts, only to be driven off by irate hikers.

If you're looking for an authentic slice of old Colorado, St Mary's Glacier is pretty fascinating, with no pretensions, lots of history and more ghost towns nearby than I could count. It's somewhere with character – if you're looking for an adventurous mountain vacation off the beaten track I'd highly recommend it. It's definitely not Aspen, but that's it's charm!