The class used the Typesafe Scala IDE, which is built on Eclipse. I’ve been using JetBrains PyCharm for most of my python work and when they had IntelliJ 12 Ultimate Edition on sale at a 75% discount last week, I bought it. Last night, I spent a bit of time setting up IntelliJ to work with Scala on my Retina MBP. I’m posting this as a future reference.

To start with, we need to install scala and sbt using homebrew.

brew install scala --with-docs
brew install sbt

I also install drip, a JVM launcher which preloads and keeps a warm JVM instance to make things appear faster. This is optional, but highly recommended.

brew install drip

We also need to add the following lines to ~/.bash_profile.

export JAVA_HOME=$(/usr/libexec/java_home)

export SCALA_HOME=/usr/local/Cellar/scala/2.9.2/libexec

export JAVACMD=drip

export DRIP_SHUTDOWN=30

export SBT_OPTS="-XX:+UseConcMarkSweepGC -XX:+CMSClassUnloadingEnabled -XX:PermSize=128M -XX:MaxPermSize=512M"

Finally, get JDK docs and sources from Apple. Download and install “Java for OS X 2012-006 Developer Package” from here.

Now, to configure IDEA 12. Start by installing the Scala plugin from the plugin repository and restart IDEA.

Next, start a new project in IDEA and select “Scala Module”. Enter the project name, click on the New button for Project SDK. The $JAVA_HOME directory should already be selected in the dialog which appears, just click on Choose to proceed.

In Scala settings, select the “Set Scala Home” radio button and enter “/usr/local/Cellar/scala/2.9.2/libexec” in the text box below it. It’ll show a warning about not being able to find the /doc/scala-devel-docs/api directory. We’ll set it later. Click on “Finish” to create the new project.

Now to setup the documentation directories. Select “File -> Project Structure”. Select “Libraries” under “Project Settings” in the left most pane. Select “scala-library”. The JavaDocs path would be set to “/usr/local/Cellar/scala/2.9.2/libexec/doc/scala/devel-docs/api”, which is incorrect. Remove that entry and add a new JavaDoc entry pointing to “/usr/local/Cellar/scala/2.9.2/share/doc/scala”. This is where homebrew installs scala docs if scala is installed with the “–with-docs” option. Click on “Facets” under “Project Settings” and ensure that the “Language Level” is set to “Scala 2.9″.

It’s also a good idea to ensure that the locations for Java docs are set properly. Select “SDKs” under “Platform Settings”. On the “Sourcepath” tab, ensure that there’s an entry pointing to “/Library/Java/JavaVirtualMachines/1.6.0_37-b06-434.jdk/Contents/Home/src.jar!/src”. On the “Documentation Path” tab, ensure there are two entries pointing to “/Library/Java/JavaVirtualMachines/1.6.0_37-b06-434.jdk/Contents/Home/docs.jar!/docs/api” and “/Library/Java/JavaVirtualMachines/1.6.0_37-b06-434.jdk/Contents/Home/appledocs.jar!/appledoc/api”.

And that’s it. You could probably start by adding a Scala Worksheet to the project and try playing with the REPL. The default shortcut for inline documentation in IDEA is “Ctrl-J”.

The extension was making an HTTP POST request for every url I’d visited to http://74.201.117.232/getmeta.php?username=<my_user_id>.

The use case for this is to be to check if I’ve rated the url, and if so, what’s my rating. But then, why not cache the data instead of calling home every time I open a page (even in the same browsing session) ? I freaked out and uninstalled the toolbar the very moment, and that was pretty much it. Maybe mentioned it in passing to a couple of friends. Most of them didn’t really care about this since they don’t use StumbleUpon and those who did thought it was du jour with all the social bookmarking/news toolbars, which is true. Almost every other toolbar also does this.

I thought about this for a while, thought the toobars should hash the urls before sending it to the servers, and using bloom filters to reduce the number of time the client would have to call home to check if a user has rated a url. And that was pretty much it, until last week.

kamathln told me that someone wants to write a Jetpack extension for Tagz. That someone turned out to be Yathi, an old mutual friend of ours. He wanted to write a relatively simple Jetpack extension and wanted some server side support to get info on any url (comments, points, number of saves etc). I quickly added the requisite  server side support and he quickly hacked together a nice little jetpack script. It turned out to be one of the first few jetpack extensions on userscripts.org, a couple of people started using it and all was fine. Until I started looking at the server logs, when it felt like a deja vu all over again. Our script was leaking our users’ browsing history quite like I’d observed with the StumbleUpon toolbar 6 months ago.

Eventually, I decided that sending urls in plain text is a bad idea. Also, the lookups should be cached atleast for a short while. An extended form of the idea involved using bloom filters, but that’d have been too much work. So, we now normalize the url to a standard representation, then hash it with sha256 and then send the hash to the server. Although this is not quite a completely bullet proof solution, its certainly better than sending the url to the server every time.

Bloom filters are some of the simplest and yet the coolest of all probabilistic datastructures. Basically, are a set like datastructure, which you train on your dataset and then later use it to quickly check if it was trained on a certain value. The cool part is, unlike hashtables or trees, if you train a bloom filter on N elements (say 10,000) it doesn’t actually store any of those elements, so its like a compressed representation of your dataset, which can be used to do quick hit testing. But this comes at a price. Bloom filters might lie at times . But its still useful, nonetheless. Every time we query a bloom filter, its like asking it a question “Were you trained with the value X ?”, to which it replies with a yes or a no (a boolean result), so, there are 3 possibilites.

1. It tells the truth, which is the most likely case and all is fine.
2. It might say it was trained on X, while it really wasn’t. (A false positive)
3. It might say it wasn’t trained on X, while it actually was trained on it. (A false negative)

Ok, so the property which makes bloom filters really useful is that it never gives false negatives, so #3 never happens. So, it mostly tells the truth, but in the unlikely event that it lies, it always errs on the conservative side. This, combined with the property that they don’t have to store the actual elements they were trained on, make bloom filters incredibly useful in a lot of of circumstances.

One place I used them in Tagz is to check if a user has voted on a particular link. If the filter replies afirmatively then we can go query the backend (DB, Memcached, whatever) to get the actual score for the vote. Assuming that the bloom filter lies 5% of the times, we still eliminate 95% of the backend queries in this case. And the best part is that the rate at which it lies can be tuned. Its really a compromise between the size of the filter and the rate at which it lies. Simply put, the bigger a bloom filter, the lesser it lies. So, the constructor for the SimpleBloomFilter class in my implementation takes 2 parameters, capacity and err.

Another application for bloom filters is to synchronize stuff. Lets say, you have to update a lot of items with a certain keys between two machines A & B over a slow connection, where each of them have quite a few items between them. So, A, instead of sending all the keys it has to B, can instead build a compact bloom filter out the keys it has and send it to B, B can test its item set against the bloom filter and send only the items it doesn’t find in it. The elaborate setup I just described is called a Bloom Join.

One more thing, this is a variant of a bloom filter called a counting bloom filter. Plain old bloom filters are add only structures. You can train it on an element, but you can’t untrain it on something which its already been trained on. Counting bloom filters gain the ability to be untrained on elements by consuming a little more space. Also, I noticed that the data in the filter tends to be pretty sparse, so I do some simple RLE compression on it before serializing it to JSON which makes it a lot more compact.

That concludes my watered down explanation of a counting bloom filter. The Wikipedia link i’d mentioned in the beginning has a much better explanation of bloom filters. As usual, the code can be found on bitbucket. All the code is MIT Licensed except for the 3rd party sha256.js javascript module from Christoph Bichlmeier.

PS: Whats next ? BK-Trees anyone ?

The utils.js file contains some utility functions like forEach, map, filter, partial. The only function from utils.js used in dombuilder.js is partial, so you might want to add it to dombuilder.js to remove the dependence on utils.js.

Here’s an obligatory trivial example (included in the repo).

Interestingly, some crude benchmarks indicate that the trie implementation is more efficient than the ternary search tree implementation in terms of both speed and space (Look for test.py in the repo), I also ported the trie module to javascript, and its included in the repo.

Here are two GraphViz graphs visualizing both the structures, generated using the excellent GvGen library.

In the Ternary Search Tree graph, Blue vertices = left, Green vertices = middle, Red vertices = right.

The code can be found here.

This happens whenever I end up storing large lists or dictionaries on memcached. Redis solves this problem effectively by providing list and set primitives besides storing plain old strings. This effectively solves the  aforementioned problem. Also, the list primitive supports atomic push/pop commands, which could be used to implement efficient queues. And this along with the on disk persistance feature solves another problem I have with beanstalkd, which is the lack of persistance.

Overall, this seems like a great solution to quite a few tiny little problems I have with performance on Tagz. I’m planning on playing with redis a little more tonight and if all goes well, I’ll shift from memcached to redis.

In retrospect, I feel Python and Postgres weren’t really the best choices I made for writing Tagz. I believe Tagz would be better written in PHP with MySQL as the DB. I’ve come to learn the hard way that Django with Postgresql can’t quite match the blazing speeds possible using raw PHP with MySQL (and MyISAM DBs).

Starting today, I’ve decided on stopping all development on the current code base of Tagz. I’ve begun a rewrite of Tagz in PHP. The current users may rest assured, since backwards compatibility is an important goal for this rewrite. I’m hoping to finish the rewrite in less than a month. I’m expecting the transition to be a smooth one.

Finally, Thanks to all the current users (no thanks to all the spammers) for all the encouragement and the feature requests, without which Tagz would’ve never have come close to what it is today.

But then, no fallacious argument is complete without a strawman or two. Start with more than a dozen sites (including two of his own) which don’t validate. Brilliant, capitalize on the bandwagon effect. Which is kinda like saying “Those big name sites made it big without having valid (x)html. Ipso facto, your site stands a better chance of making it big by not writing valid (x)html”. The second one’s a little better. With HTML 4.01 Strict, you can’t have a target attribute for an anchor tag. So, something like:

<a href="http://www.example.com/" target="_blank">foo</a>

Doesn’t validate. Now, I’m sure everybody these days uses some JS library (for those who don’t, there’s always getElementByClassName). Apparently, stackoverflow uses jQuery. So, here’s a solution. Start with

<a href="http://www.example.com/" class="external">foo</a>

Or something like it. Then do something like

$(a.external).attr("target","_blank");

Yeah, yeah, I know its a dirty hack, but heck it buys you compliance. For what price ? One extra line of Javascript. And the whole point in writing validators mostly is about making it easier to parse for all the programs and bots which crawl/fetch your pages and AFAIK, most of them, don’t grok Javascript. How hard is it to write

<td style="width:80px">

as opposed to

<td width=80>

Fortunately, you don’t have to compile html, so you don’t have a compiler which barks at you and also, the browsers are lax enough to consume almost any kludge that you throw at them.

The bottom line: hell yeah, its worth the effort, and how hard is it, really ? Just because your web site does’t validate, it doesn’t mean that you can brush it off. All I care about is that mine does and everyone’s should, atleast in theory

PS:

1: In all honestly, my blog isn’t w3c validator compliant, thanks to the wordpress plugin that I use for syntax hilighting source code.

2: Accesibility matters as well, we web devs keep bitching about having to support IE6 (I do it as well). How many of our web 2.0 apps work with Javascript and css disabled or on lynx or links ?