/devel/talk

Implementing bloom filter with a murmur hash function

Recently I read a blog post by Jonathan Ellis about bloom filters. Jonathan works on Cassandra and though had lots of empirical recommendations on its implementation. Cassandra uses bloom filter extensively for performance optimization. Bloom filter is a space-efficient probabilistic data structure used to test whether an element belongs to a set. It's similar to a standard hashtable, except that its space efficient and doesn't store the actual value, rather it hashes the keys in a bit array. The reason it's a probabilistic data structure, is that it allows false positives, but not false negatives. This means, that to answer the question whether A is a subset of B (A ⊆ B), a bloom filter returns true or false. A false (doesn't exist) is guaranteed to be accurate, but true (exists), has a probability of being false positive.

So why would one use such an algorithm? Say you store records on disk. Someone requests a particular record and you proceed to seek this record. This is usually an expensive operation for high throughput or systems with limited resources, though before invoking such an expensive operation you can find out if the record exists. If record does exist, you can then proceed to retrieve it through the more intensive operation. Because there is a small probability of this being a false positive, you might still find (through the resource intensive operation) that it doesn't exist. So in an environment where you're servicing many requests which might not exist, you can reduce the amount of expensive operations and answer such request in constant time O(1).

Jonathan's blog post provides some great information about how to implement a very effective bloom filter. One of the most important considerations is the hash function. To lower the probability of false positives, one must use a hash function which effectively distributes the hashes across the hash-space. Jonathan recommends the use of murmur hash algorithm, which is one of the most efficient and effective hash functions, which has great performance and low collisions rate.

Another thing done to reduce hash collisions and in turn false positives, is the fact that you don't just turn on the bits of a single hash function result, rather, you do so numerous times. (5 times is referred to a lot in literature and seems like a sweet spot). This means, that you take a key, calculate 5 hashes (using 5 different hash algorithms or a single hash algorithm strategy I'll discuss below) and set the bit for each one of these hashes in the bit array. Answering the question of whether the key exists, does the reverse. Calculate 5 hashes and check to make sure they are all set in the bit array. If any of the 5 aren't set, then you can be assured it doesn't exist.

So let's look at some code. Below is the implementation of bloom filter in Scala. It relies on a murmur hash implementation which I won't list, but you can view/download it here.

The code above should be pretty self explanatory, but let's just take a look at the hashing strategy. We calculate 5 hashes (default) on the key being stored, although we only ever invoke the murmur algorithm twice. Look at the highlighted lines above. Adam Kirsch and Michael Mitzenmacher wrote a paper titled, Less Hashing, Same Performance..., which shows that using a particular hashing technique which simulates additional hash functions beyond two, can increase performance of bloom filters without any significant loss in the false positive probability. To summarize the math in the paper, this is the formula: g_i(x) = h₁(x) + ih₂(x) mod m, where m is the number of buckets in the bloom filter, h₁ and h₂ are the two calculated hashes respectively, and i will range from 0 up to k - 1 where k is the number of hashes we want to generate.

Here is how you'd use the above bloom filter...

NOSQL Databases for web CRUD (CouchDB) - Shows/Views

There are many applications that easily land themselves to CRUD paradigm. Even if only 80% of the application's functionality is pure CRUD, one can benefit from a simpler storage model. For so many years many (including myself) thought that storing application state which needs to be used in an enterprise-grade applications, meant we had one option, an RDBMS. Not that other models weren't available, but their prevalence was not as high which made one question the quality/stability and long term health of such software. So we've gotten accustomed to approaching state persistence by sticking everything into one hole. If it didn't fit, we trimmed it, cut it, squeezed it, stumped on it, but we made it fit. Then when it was time to pull out, ah, we repeated the procedure. ORMs are one of the most popular remedies for such procedures. But if one has ever developed a complex data model and actually took the time to think about the data access strategy, on both ends, application and RDBMS, you'd quickly run into many limitations of the ORM model. I guess you can abstract away the impedance mismatch only so much, but watch out for these leaky abstractions. So if you're still rusty on your SQL and the relational theory because the great Gods promised that you'll never have to worry about it if you use ORM, you better get to learning, unless you're planning maintaining a ToDo List application for the rest of your life.

So, with this out of the way, let's talk about real data persistence. So there are many applications (especially web applications), that don't lend themselves very well into the relational persistence model. There are many reasons for this, but those who have ever had to beat their heads against the wall to bend the relational model to persist data know what I mean. By the time you're done, you're using and RDBMS to store non-relational data and all the benefits of the relational model are moot. You might as well store your data in an excel spreadsheet. So what are some of these reasons?

1. Highly dynamic structure (relational schemas are rather static, if you're doing it the relational way (no tall/skinny tables))
2. Data model is not very relational. That speaks for itself, but many don't really know when and how to identify this, as we've spend so much time identifying relations that don't exist or are irrelevant to the application.
3. Your relational schema is denormalized to the point where you're no longer benefiting from relational database features like enforcing consistency and reducing redundancy in the data.
4. Your relational database is bending backwards to accommodate your read/write throughput even after you denormalized (which itself is a reason to look elsewhere) and optimized, forcing you to continuously have to scale up to allow for increased load.
5. You continuously marshall/unmarshall data (ORM???) to persist it and then to transform it to another data format.

Touching a bit more on bullet #5; Lots of software is written using good OO principles of encapsulation. Encapsulation is the heart of software abstractions and is probably the most important principle. But people tend to abuse it. Abstractions are good when they add value, but marshalling and unmarshalling one data structure into another without a good apparent reason, other than you don't have to learn how to deal with a particular data structure, I'm not sure is such a good reason. So many software projects use ORM for the sake of not learning SQL, but how far can you actually get? ORM is a perfect example of a leaky abstraction. So many projects retrieve data from a web view in JSON or url-encoded format and marshall that into objects, only to validate the data and persist it using an ORM. So now you've unmarshalled the data from JSON to an object graph to just then marshall it again into a SQL query to send to the database. Do we really need these superfluous steps?

I'm sure there are other reasons I haven't mentioned here. These reasons I personally faced when making my decisions.

A rational way of deciding on data persistence is not to automatically start writing a DDL script or grab your ER diagram tool, but rather look at what data you have, how would this data persist in a "natural" way, how does the client software need to access this data, what are the performance/scalability considerations and then go out and look at different persistence models to find the best match.

In my latest project, I had to think about a way to persist hierarchical data. This data will be accessed through some web medium (browser, mobile client, etc...) majority of the time. One of the web interfaces will be an ajax enabled web app, another will be an iphone and/or adroid app. JSON is communication protocol lingua franca of the web. Some will argue it's XML, but I'll keep my XML opinions to myself at this point.

CouchDB is a document database which one would call key/value store. It allows for storage of JSON documents that are uniquely identified by keys. Sounds interesting, not really. There are tens of other databases that have same capabilities, so why CouchDB? Well in one short sentence: CouchDB is build one the web and for the web. So what does that really mean? Well, besides the JSON storage structure and its innate ability to scale horizontally, they've build some pretty awesome features that makes it very appealing for a particular type of an application. The task is to decide whether the application you're building is that application. So not to make this post any longer than it already is with my rant, let me describe and demonstrate some of the features that I've used over the last few days and why they are relevant.

Please make sure you have couchdb 0.10.* version installed as well as curl command line utility. For installation instructions see http://wiki.apache.org/couchdb/Installation

Once couchdb is installed, you can start it using the couchdb command. Depending on your setup, you can do...

sudo couchdb

A little bit of a background though before we get any further...

We're going to store hierarchical data, which JSON is a natural fit for. One of the issues we have, is that in our industry, there are numerous data standards and they are all defined either in XML or in some delimited rectangular format. One major use case involves performing CRUD operations on the data from variety of sources (web app, mobile app, etc...) as well as being able to emit this data in one of the industry standard formats for integration purposes.

CouchDB exposes a RESTful API, so it's rather easy to use it from any language which supports HTTP. Most popular languages have abstraction libraries on top of that, to abstract away the HTTP abstraction. Here is a list of available clients: http://wiki.apache.org/couchdb/Basics. For our purposes we're going to use curl, a command line utility which allows us to make HTTP requests. So let's see how we can easily accomplish this with CouchDB.

Now that CouchDB is successfully running, let's create a database and insert some sample data...

curl -X PUT "http://localhost:5984/sample_db"

Above line create a database called sample_db. If the command is successfule, you will see the following output: {"ok":true}. Now lets add three files to this database. The JSON data files which we're sending below are found in code snippets below labeled accordingly, so make sure they are in the directory from which you're running the below commands.

curl -X PUT -d @rec1.json "http://localhost:5984/sample_db/record1" curl -X PUT -d @rec2.json "http://localhost:5984/sample_db/record2" curl -X PUT -d @rec3.json "http://localhost:5984/sample_db/record3"

Again, each command should yield a JSON response with "ok" set to true if the add succeeded. Here is what one would expect from the first command: {"ok":true,"id":"record1","rev":"1-7c15e9df17499c994439b5e3ab1951d2"}. Again, ok is set to true making this a success response. The id field is set to the name of the record which we created. You can see that names are set through the URL as they are just resources in the world of REST. The rev field displays the revision of this document. CouchDB's concurrency model is based on MVCC, though it versions the documents as it updates them, so each document modification gets it's unique revision id. You can read more about this in CouchDB's architecture and API documentation.

rec1.json

rec2.json

rec3.json

Now that we have the data persisted, let's talk about some strategies for getting the data out.

CouchDB supports views. They are used to query and report on the data stored in the database. Views can be permanent, meaning they are stored in CouchDB as named queries and are accessed through their name. Views can also be temporary, meaning they are executed and discarded. CouchDB computes and stores view indexes, so view operations are very efficient and can theoretically (and I believe practically) span across remote nodes. Views are written as map/reduce operations, though they land themselves well for distribution. Here is an example of a map function in a view. (Reduce functions are optional if your query requires aggregating result sets)

There are other two really cool features, which allow more effective data filtering and transformation. These features are shows and lists. The purpose of shows and lists is to render a JSON document in a different format. Shows allow to transform a single document into another format. A show is similar to a view function, but it takes two parameters function(doc, req), doc is the document instance being iterated and request is an abstraction over CouchDB request object. Here is a simple show function...

The xml function and inlines you see here is the e4x which adds native support as a part of ECMAScript and is implemented in the embedded javascript engine Spidermonkey, which CouchDB uses.

This show function, takes a particular JSON record and turns it into XML. Creating a show is pretty simple, you just encapsulate the function above into a design document and create the record through PUT.

Here is the design document for the show above...

xml_show.json

Once you have the design document, create it...

curl -X PUT -H "Content-Type: application/json" -d @xml_show.json "http://localhost:5984/sample_db/_design/shows"

Note: in (..../_design/shows), shows is just a name of the design document, you can call it what ever you want

Now let's invoke the show...

curl -X GET "http://localhost:5984/sample_db/_design/shows/_show/toxml/record1"

Here is the output

So, that was super easy, we stored our document which required no code on our behalf and then we retrieved it with minimal effort by using ECMAScript's e4x facilities.

So how would I transform a record collection or view results into a different format? Well, this is where lists come in. Lists are similar to shows, but they are applied to the results of an already present view. Here is a sample list function.

Again, you encapsulate this list function into a design document, along with a simple view function...

xml_list.json

Now, we create the design document

curl -X PUT -H "Content-Type: application/json" -d @xml_list.json "http://localhost:5984/sample_db/_design/lists"

Once the design document is created, we can request our xml document listing all person records

curl -X GET http://localhost:5984/sample_db/design/lists/list/toxml/all

And the output is

So you can see how shows and lists are very useful and provide a convenient way to transform views into different formats.

As you can see, we created the database and stored data. No code was required to make that happen, just collect the data through your application and make a CouchDB REST request. We also added some custom functionality of transforming the data for multiple client consumption by using shows and views. In my opinion, CouchDB is a great step towards what one could call web/cloud scale database. It has awesome abilities to integrate with web technologies and it can scale to support the ever increasing web scale of data. In other words, it fits some application models like a glove.

I barely even scraped the tip of the iceberg of what CouchDB can do. We haven't talked about result aggregates which can be achieved with map/reduce, we also haven't discussed data validation and security. These features might be a top of some future posts.

The start of the Scala journey (concurrency and idiomatic Scala rant)

I've been following Scala off and on for about 2 years now. Mostly in spurts, I liked the language, but due to the workload and other priorities I never had the time to take it for a full ride. Well, over the last 2 weeks, I decided to take the full plunge. Full meaning, I'm taking a highly concurrent production application which power's a very critical component of our application, and rewriting it in Scala. I'm doing this for more than just fun. This application has grown from a very cleanly architected one, to one that is still rather nicely designed, but has accumulated a lot of technical debt. With everything I've learned about Scala, I think I can redesign it to be cleaner, more concise, and probably more scalable. The other big driving reason I'm looking to give Scala a shot, is due to its Actor based concurrency. I've worked with Java's threading primitives for many years and have accumulated a love/hate relationship. The JSE 5 concurrency package brought some nice gems to my world, but it didn't eliminate the fact that you're still programming to the imperative model of shared state synchronization. Scala actors hide some of the ugliness of thread synchronization, though don't eliminate the issue completely. Due to the nature of Scala, being a mix between imperative and functional language and the fact that actors are implemented as a library, nothing stops one from running into same issues as in more primitive thread state-sharing operations (i.e. race conditions, lock contentions, deadlocks/livelocks). Basically, if you're using actors as just an abstraction layer over old practices, you'll be in the same boat as you started with Java. With all of that said, unlike Java, Scala provides you the facilities for designing cleaner and more thread safe systems due to its functional programming facilities. Mutable shared state is the leading cause of non-determinism in Java concurrent applications, so immutability and message passing is a way into a more deterministic world.

I've also looked at other concurrent programming models, like STM/MVCC. STM is the basis of concurrent programming in Clojure and it's a different paradigm than Actors. STM is a simpler model if you're used to programming the old imperative threading, as they abstract you from concurrency primitives by forcing state modifications to occur in a transactional context. When this occurs, the STM system takes care of ensuring the state modifications occur atomically and in isolation. In my opinion this system suites the multi-core paradigm very well and allows smoother transition, the problem with it, at least in the context of MVCC, is that for each transaction and data structure being modified, a copy is made for the purposes of isolation (implementation of copying is system dependent, some might be more efficient than others), but you can already see an issue. For a system that has to handle numerous concurrent transactions involving many objects, this can become a bottleneck and the creation of copies can overburden system's memory and performance. There are some debates about that in the STM world, mostly involving finding the sweet spot for such systems, where the cost of MVCC is less relevant the the cost of constant synchronization through locking.

Actors model is different, it works in terms of isolated objects (actors), all working in isolation by message passing. None can modify or query the state of another, short of requesting such an operation by sending a message to that particular object (actor). In Scala, you can break that model, as you can send around mutable objects, but if you are to really benefit from the Actor model, one should probably avoid doing that. Actors lend themselves better to concurrent applications, that not only span multiple-cores, but also can easily be scaled to multiple physical nodes. Because messages being passed are immutable data structures that can be easily synchronized and shared, the underlying Actor system can share these message across physically dispersed actors just as it can for the actors within the same physical memory space.

So the world of concurrency is getting more exciting with these awesome paradigms. One thing to remember is that there is no one size fits all concurrency model and I don't see any one of the above becoming the de-facto standard any time soon. There is a sweet spot for each, so one should learn the ins and outs of each model.

Now that I got the concurrency out of the way, let's get back to the actual syntax of Scala. Scala is very powerful (at least compared to Java). This power comes with responsibility. You can use Scala to write beautiful/concise programs, or you can use it to write obscure/illegible programs that no one, including the original author, will be able to comprehend. Personally, I prefer and can responsible handle this responsibility. I'm a long time Perl programmer (way before I started programming Java), and I've seen (and even written at times), programs that Larry Wall himself wouldn't be able to comprehend.

Scala comes with operator overloading, but when not judiciously used, that power alone can be responsible for ineligibility of any system. This is one of the major reasons why languages like Java decided to not include it. Personally, I think operator overloading can be a beautiful addition to any API. It can make writing DSLs easier and using them more natural. Again, this power is great in the use of experienced and responsible programmers.

After having experience great power (Perl) and great restraint (Java), I'm leaning more towards power (who wouldn't :-). One one hand, it's nice to be able to read and comprehend anyone's Java program, even when it's not nicely written, on the other hand, it's a pain trying to write a program and jumping through all the hoops and limitations because of the various constraints. In a perfect AI world, the compiler would infer the capabilities of the programmer and restrict its facilities based on those, in some way as to not offend anyone:-) So if a novice is inferred, ah, there goes the operator overloading and implicit conversions, etc... But for now, I'd rather have a powerful tool to use when I write software and Scala seems to push the right buttons for me at this point.

I'm going to start of a list of posts, starting with this one, about my experiences with Scala.

Here is a little something I came up with a few hours ago. Our software has some limited interoperability with a SQL database and requires a light abstraction. We chose not to use any 3rd party ORM or SQL abstraction, mostly due to the fact that the dependency on these abstractions don't really provide any benefit for our limited use of SQL. So I developed a simple SQL variant abstraction layer, which allows us to execute SQL queries which are defined in the SQLVariant implementation. Moving from one database to another, just requires one to implement a SQLVariant interface to provide the proper abstraction. I initially wrote this in java and although it was decent, it required quite a bit more code and didn't look as concise as I wanted it. One issue was PreparedStatement and it's interface for placeholder bindings. How would one bind java's primitive and wrapper types as placeholders and how would the SQLVariant know which PreparedStatement.bind* method to call? I resorted to using an enumeration which defines these operations and reflection for the purpose of invoking these operations. I'm basically sidestepping static typing in a place I'm not sure I really want or have to. Here is the java implementation.

I got rid of a few methods, specifically dealing with resultset, statement, and connection cleanup, as they don't really emphasize my point here.

Now, here is how one would implement the SQLVariant interface. The below implementation is in groovy. I choose groovy when I have to do lots of string interpolation, which somehow java and scala refuse to support. The code was shortened to just demonstrate the bare minimum.

I started reimplementing the above in Scala and I ran across a very powerful and beautiful Scala implicit conversion feature. This allowed me to truly abstract the SQLVariant implementations from any bindings specific knowledge, through an implicit casting facility that normally only dynamically typed languages provide. Scala gives us this ability, but also ensures static type safety of implicit conversions during compilation.

Another wonderful feature, is lazy vals, which allows us to cleanly implement lazy evaluation that we (java programmers) are so used to doing by instantiating a member field as null and then checking it before initializing on the initial accessor call. If you've seen code similar to below a lot, you'll rejoice to find out that you no longer have to do this in Scala.

The above, besides not being ideal, is also error prone if say a type is used anywhere else in SomeClass and you don't use the accessor method to retrieve it. You must ensure the use of accessor through convention or deal with the fact that it could be non-instantiated. This is no longer the case in Scala as its runtime handles lazy instantiation for you. See below code.

Note: I still allow the client data access abstractions to work with a raw jdbc ResultSet returned from the SQLVariant. I don't see this as an issue at this point, first since these abstractions are SQL specific and also because ResultSet is a standard interface for any JDBC SQL interaction. Here is my concise Scala implementation. I'm still learning, so this might change as I get more familiar with Scala idioms and start writing more idiomatic Scala code.

And the obligatory unit test using the o' so awesome Scala Specs framework.

Although I barely scraped the tip of the iceberg, I hope this helps you see some of what Scala has to offer. More to come as I progress.

Annoying javax.net.ssl.SSLHandshakeException exception

This exception has to be the most annoying one I've faced over the years with Java. I'm not sure which moron's wrote the SSL library, but did they think about providing an option to disable ssl certificate validation? I wasn't sure it was a requirement to have a valid certificate. I mean sure, it's nice and provides that worm fuzzy security feeling, but when I'm developing and/or testing, can you please provide some way to disable this annoying thing? Either way, I dug into this today and figured it out. It's actually as anything else in standard JDK, 100+ lines of code which they could of provided out of the box a simple boolean switch, instead your have to implement factories, interfaces, etc... WTF? Just to turn off certificate validation? Talk about over-engineering stuff.

So here is the code, which you can copy and paste into your project, instructions on how to use it are below...

import org.apache.commons.httpclient.protocol.Protocol;
import org.apache.commons.httpclient.protocol.ProtocolSocketFactory;

import javax.net.ssl.SSLContext;
import javax.net.ssl.TrustManager;
import javax.net.ssl.X509TrustManager;

import java.io.IOException;
import java.net.InetAddress;
import java.net.InetSocketAddress;
import java.net.Socket;
import java.net.SocketAddress;
import java.net.UnknownHostException;

import javax.net.SocketFactory;

import org.apache.commons.httpclient.ConnectTimeoutException;
import org.apache.commons.httpclient.HttpClientError;
import org.apache.commons.httpclient.params.HttpConnectionParams;
import org.apache.commons.httpclient.protocol.SecureProtocolSocketFactory;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

public static class TrustAllSSLProtocolSocketFactory implements ProtocolSocketFactory {

    public static void initialize() {
        Protocol.registerProtocol("https", new Protocol("https", new TrustAllSSLProtocolSocketFactory(), 443));
    }

    private SSLContext sslcontext = null;

    private static TrustManager trustAllCerts =
            new X509TrustManager() {
                public java.security.cert.X509Certificate[] getAcceptedIssuers() { return null; }
                public void checkClientTrusted( java.security.cert.X509Certificate[] certs, String authType) {}
                public void checkServerTrusted(java.security.cert.X509Certificate[] certs, String authType) {}
            };

    /**
     * Constructor for TrustAllSSLProtocolSocketFactory.
     */
    private TrustAllSSLProtocolSocketFactory() {
        super();
    }

    private static SSLContext createSSLContext() {
        try {
            SSLContext context = SSLContext.getInstance("SSL");
            context.init(null, new TrustManager[]{trustAllCerts}, null);
            return context;
        } catch (Exception e) {
            throw new HttpClientError(e.toString());
        }
    }

    private SSLContext getSSLContext() {
        if (this.sslcontext == null) {
            this.sslcontext = createSSLContext();
        }
        return this.sslcontext;
    }

    public Socket createSocket(String host, int port, InetAddress clientHost, int clientPort)
            throws IOException, UnknownHostException {
        return getSSLContext().getSocketFactory().createSocket(host, port, clientHost, clientPort);
    }


    public Socket createSocket(final String host, final int port, final InetAddress localAddress,
                               final int localPort, final HttpConnectionParams params
    ) throws IOException, UnknownHostException, ConnectTimeoutException {
        if (params == null) throw new IllegalArgumentException("Parameters may not be null");
        int timeout = params.getConnectionTimeout();
        SocketFactory socketfactory = getSSLContext().getSocketFactory();
        if (timeout == 0) return socketfactory.createSocket(host, port, localAddress, localPort);
        else {
            Socket socket = socketfactory.createSocket();
            SocketAddress localaddr = new InetSocketAddress(localAddress, localPort);
            SocketAddress remoteaddr = new InetSocketAddress(host, port);
            socket.bind(localaddr);
            socket.connect(remoteaddr, timeout);
            return socket;
        }
    }

    public Socket createSocket(String host, int port) throws IOException, UnknownHostException {
        return getSSLContext().getSocketFactory().createSocket(host, port);
    }

    public Socket createSocket(Socket socket, String host, int port, boolean autoClose)
            throws IOException, UnknownHostException {
        return getSSLContext().getSocketFactory().createSocket(socket, host, port, autoClose);
    }

    public boolean equals(Object obj) {
        return ((obj != null) && obj.getClass().equals(TrustAllSSLProtocolSocketFactory.class));
    }

    public int hashCode() {
        return TrustAllSSLProtocolSocketFactory.class.hashCode();
    }
}

Now all you have to do is call TrustAllSSLProtocolSocketFactory.initialize() anywhere in your application initialization code or right before you access any https resources, either through the URL class or through any other library, like HttpClient.

Hope this helps, though it's still a pretty ugly hack IMO.

Heap Sort in Scala

Heap sort is one of the more efficient sorting algorithms, being that it sorts in constant space (not including the memory space of course to store the n elements). Elements are sorted in place, though the constant space O(1). Total space is O(n) of course if you consider the storage of the elements in memory or on disk.

There is lots of literature on heap sorts out there, so I'm not going to go into it in more details. The reason it's sometimes preferred over say insertion sort or quick sort, is that the worst case (which one always wants to account for, is O(n log n), which is far better than quadratic O(n²) worst case performance of both insertion and quick sort algorithms.

Here is an implementation of quick sort in Scala. Please note, I wrote this with readability in mind, not conciseness. Sometimes they go hand in hand, but at times, as I o' so learned with Perl over the years, that's not true in all cases. A good balance between conciseness and readability should be reached and that comes only with experience :-)

There are only 3 methods that matter here, rest are just auxiliaries (I highlighted the important methods). The code here can be run independently and serves as a benchmark, as you can run it by specifying the size of the initial array (generated randomly) and the # of benchmarks to run. The benchmark is run, best and worst are disposed and the mean of the rest is displayed.

import scala.util._
import scala.collection.mutable._ 
import scala.util.Random

object HeapSort {

  private val randGen = new Random()

  def main(args: Array[String]) {
    val arraySize = args.first.toInt
    val repeat = args(1).toInt
    var times = perform(repeat, arraySize)
    println("Average: "+averageOf(times)+" ms for "+times.size+" runs.")
  }

  private def heapSort(arr:Array[Int]):Array[Int] = {
    buildHeap(arr)
    (arr.length-1 until 0 by -1).foreach( i => {
      swap(arr, 0, i)
      heapify(arr, 0, i)
    })
    arr
  }

  def buildHeap(arr:Array[Int]) {
    ((arr.length/2.0D).floor.toInt-1 until -1 by -1).foreach( i => heapify(arr, i, arr.length) )
  }

  def heapify(arr:Array[Int], idx:Int, max:Int) {
    val l = left(idx)
    val r = right(idx)               
    var largest = if (l < max && arr(l) > arr(idx)) l else idx
    largest = if (r < max && arr(r) > arr(largest)) r else largest
    if (largest != idx) {
      swap(arr, idx, largest)
      heapify(arr, largest, max)
    }
  }

  private def parent(idx:Int):Int = (idx/2.0D).floor.toInt                          
  private def left(idx:Int):Int = 2*idx+1  
  private def right(idx:Int):Int = (2*idx)+2

  def swap(s:Array[Int], i: Int, j: Int):Unit = { 
    val v = s(i); 
    s(i) = s(j); 
    s(j) = v 
  }


  private def perform(times:Int, initListSize:Int):ListBuffer[Int] = {
    val benchmarks:ListBuffer[Int] = new ListBuffer[Int]
    (0 until times).foreach(idx => {
      val arr:Array[Int] = initArrayWith(initListSize)
      val start = System.currentTimeMillis()
      heapSort(arr)
      val end = System.currentTimeMillis()
      benchmarks += (end-start).toInt
    });                             
    benchmarks
  }

  def initArrayWith(limit:Int):Array[Int] = {
    val list:ListBuffer[Int] = new ListBuffer()
    val randGen = new Random()
    (0 until limit).foreach( i => list += randGen.nextInt(1000000) )
    return list.toArray
  }

  def averageOf(benchmarks:ListBuffer[Int]):Long = {
    var sortedBm:Array[Int] = benchmarks.toArray
    heapSort(sortedBm)
    var sum:Int = 0;                 
    val sumFunc = (t:Int) => sum += t
    // Get rid of best and worst if we ran it more than twice
    if (sortedBm.length > 2)
      sortedBm.slice(1,sortedBm.size-2).foreach(sumFunc)
    else
      sortedBm.foreach(sumFunc)
    return sum/sortedBm.length
  }
}  

You can run this code by saving it to HeapSort.scala file and from command line...

scala -i HeapSort.scala -e 'HeapSort.main(Array("400000", "10"))'

This will run the file through Scala's interpreter and execute a benchmark 10 times by sorting a random array of 400,000 elements with randomly chosen values from 1 to 1 million.

Insertion Sort in Scala

Here is an implementation of insertion sort using Scala. Learning the ins/outs of Scala idioms and collections.

import scala.util._
import scala.collection.mutable._

object InsertSort {

  def main(args: Array[String]) : Unit = {
    val list:ListBuffer[Int] = initListWith(args.first.toInt)
    println("Before: "+list)
    println("After: "+insertSort(list))
  }                   

  private def insertSort(list:ListBuffer[Int]):ListBuffer[Int] = {
    (1 until list.length).foreach( (i:Int) => {
      rewindCompare(list, i)
    })             
    list
  }                 

  private def rewindCompare(list:ListBuffer[Int], idx:Int):Unit = {
    val value = list(idx)                                           
    def swap(i: Int, j: Int) { val v = list(i); list(i) = list(j); list(j) = v }
    for (revIdx <- idx until 0 by -1) {
      if (value < list(revIdx-1)) swap(revIdx, revIdx-1)
      else return
    }
  }

  private def initListWith(limit:Int):ListBuffer[Int] = {
    val list:ListBuffer[Int] = new ListBuffer()
    val randGen = new Random()
    (0 until limit).foreach( i => list += randGen.nextInt(1000000) )
    return list
  }  
}

Compile and run as...

$ scalac InsertionSort.java
$ scala InsertionSort 20

Outputs:

Before: ListBuffer(548915, 963275, 872581, 284656, 52299, 261918, 222533, 288234, 340859, 546783, 428115, 659633, 450991, 693520, 15495, 108540, 402193, 48479, 701302, 269521)

After: ListBuffer(15495, 48479, 52299, 108540, 222533, 261918, 269521, 284656, 288234, 340859, 402193, 428115, 450991, 546783, 548915, 659633, 693520, 701302, 872581, 963275)

Your output will vary, as the initial list which is sorted is generated randomly.

Apache Ivy resolving local maven artifacts

Just submitted a fix to GRAILS-5327. This bug was really bothering me, mostly because ivy's API documentation is non-existent. Even the user docs are begging to be enriched with more clarity and content.

Either way, for those of you facing the same issue. The problem is that sometimes you use maven to publish your modules to your local repository usually in ~/.m2/repository directory. Ivy has a FileSystemResolver which allows one to resolve to the file system using the maven2 patterns. It can be set up very easily, but the problem I ran into is that although ivy resolves the local dependencies, it does nothing about its transitive dependencies. WTF? Why would I even want to use ivy then. So I went looking, online through posting, bad documentation, and javadocs to no avail. There was one posting which specified that one should use the pom ending vs. [ext]. So my previous artifact pattern...

${repoPath}/[organisation]/[module]/[revision]/[module]-[revision](-[classifier]).[ext]

should be changed to

${repoPath}/[organisation]/[module]/[revision]/[module]-[revision](-[classifier]).pom

I did this, but still not go. After trying a few combinations, I finally figured it out. Notice, the above artifact pattern is bolded. This is because ivy also has an ivy pattern. Because I'm not really interested in diving into ivy's source (I seldom use it) and docs suck, I just took a dumb down brute force approach, let's try a few combination and see how ivy behaves. Well, one of them worked. Basically, you must set both ivy and artifact patterns...

localFileSystemMavenResolver.addIvyPattern("${repoPath}/[organisation]/[module]/[revision]/[module]-[revision](-[classifier]).pom")
localFileSystemMavenResolver.addArtifactPattern("${repoPath}/[organisation]/[module]/[revision]/[module]-[revision](-[classifier]).[ext]")

Why? I have no freaking idea. I'm not even going to guess, since even the posts by the core ivy team on the post linked above, seem to be stabbing in the dark. "try this..." they say. Well, it works. Maybe some day, I'll have the interest and the time to look at ivy source, for now, I'm happy with using maven for most java projects and Grails' new dependency management (using ivy for dep resolution) for my Grails projects.

Hope this helps anyone battling ivy. I would think a dependency resolution library that claims it can do for ant what maven does with dependency management, would at least properly and transitively resolve maven dependencies without too much poking around. I mean, are there any viable non-maven repositories out there? I really don't think so.

Merge sort implementation and performance in Scala and Ruby

I'm not trying to turn this into language A vs. B debate, its just that something interesting happened last night. I'm trying to learn both Scala and Ruby. I'm a bit more enthused by Scala at this point, mostly because I somewhat prefer static typing and I'm a long time Java guy. Now, I am also a long time Perl guy, so I'm not necessarily choosing Scala over Ruby because of lack of experience with dynamic languages.

So, with this said, the best way to learn language idioms is to start actually implementing something. A sample application is good, but due to frameworks and relatively low business logic/algorithm ration to these sample apps, at least the ones I can conceive, you mostly spend time learning the framework idioms vs. actual languages ones.

So I thought I'd start by implementing some algorithms in these languages. I decided on Merge Sort. It's a O(n log n) divide and conquer algorithm. See the link for more info.

Let's start off with the code. Again, this is not done in an OO and/or reusable manner, this is mostly procedural/functional code to test mostly functional idioms.

Scala code:

  import java.math._
  import scala.util._
  import scala.collection.mutable._
  object MergeSort extends Application  {  

    println("Starting...");

    val list = initListWith(1000)

    val start = System.currentTimeMillis()  
    println("Sorted " + merge_sort(list.toList).length + " elements.")
    val end = System.currentTimeMillis()
    println("Total time: " + (end - start))

    def merge_sort(list:List[Int]): List[Int] = {
      if (list.length <= 1) {return list}    
      var (left: List[Int], right: List[Int]) = list splitAt Math.round(list.length/2.0).toInt
      left = merge_sort(left); right = merge_sort(right)
      if(left.last > right.head)
        merge(left, right);
      else
        left ::: right
    }

    def merge(l:List[Int], r:List[Int]):List[Int] = {
      var result:ListBuffer[Int] = new ListBuffer()
      var left = l; var right = r;
      while(left.length > 0 && right.length > 0) {
        if(left.head <= right.head) {
          result += left.head
          left = left.tail
        } else {
          result += right.head
          right = right.tail
        }
      }
      if(left.length > 0)
        result.toList ::: left
      else
        result.toList ::: right
    }

    def initListWith(limit:Int):List[Int] = {
      val list:ListBuffer[Int] = new ListBuffer()
      val randGen = new Random()
      (0 until limit).foreach( i => list += randGen.nextInt(1000000) )
      return list.toList
    }

  }

And Ruby code:

  def merge_sort(*list)
    return list if list.size <= 1

    result = []
    middle = (list.size/2.0).round
    left = list[0, middle]
    right =  list[middle..-1]

    left = merge_sort(*left)
    right = merge_sort(*right)

    if left[-1] > right[0]
      result = merge(left, right);
    else
      result = left + right
    end
    return result  
  end

  def merge(left, right)
    result = Array.new()
    while left.size > 0 && right.size > 0
      if left.first <= right.first
        result << left.slice!(0)
      else
        result << right.slice!(0)
      end
    end

    if left.size > 0
      result.concat(left)
    else
      result.concat(right)
    end
    return result
  end

  list = (1..1000).collect {|i| rand(1000000); }

  puts "Starting..."
  start = (1000 * Time.now.to_f).to_i
  puts "Sorted " + merge_sort(*list).size.to_s + " elements."
  end_time = (1000 * Time.now.to_f).to_i
  total_time = end_time - start
  puts "Total time: #{total_time}"  

So all works great, they both perform the operation correctly. But here is the weird part. JVM bytecode (Scala is very similar to Java) is supposed to be super fast. That's the assumption I've always made on various readings as well as empirical data. Now, check out these benchmarks...

  $ scalac merge_sort.scala && scala MergeSort
  Starting...
  Sorted 10000 elements.
  Total time: 374

  $ ruby merge_sort.rb
  Starting...
  Sorted 10000 elements.
  Total time: 138

I'm not timing the compilation/startup phase, as you can see from the code. In the case of 10K records, ruby performs almost 3 times as fast. It the case of 100K records:

  $ scalac merge_sort.scala && scala MergeSort
  Starting...
  Sorted 100000 elements.
  Total time: 31213

  $ ruby merge_sort.rb
  Starting...
  Sorted 100000 elements.
  Total time: 7681

Ruby is 4 times faster than Scala in this case, of course the growth is relative to the (n log n) performance.

I'm not focusing on Ruby here, since Scala is what I'm concerned about. I used a List for most operations that didn't require in place modifications. I used a ListBuffer for mutable lists, which advertises constant time append/prepend operations. I'm not sure what I'm missing. I'm going to play with it a bit more to see where the culprit is, but again, I'm not a Scala expert, though not very familiar with its collections library and the ins/outs of each implementation.

Any ideas?

** Update **

So after Maxim's comment, I updated Scala to use

while(left.lengthCompare(0) > 0 && right.lengthCompare(0) > 0)

vs.

while(left.length > 0 && right.length > 0)

All I can say, Scala #$@%^ing rocks. So it seems like the length calculation on a mutable collection is the culprit, which makes perfect sense.

Using lengthCompare(l:Int):Int gets rid of the brute force length calculation. Here is what I get from the docs...

Result of comparing length with operand l. This method is used by matching streams against right-ignoring (...,_*) patterns.

I'm going to dig into the source to figure out how it does this comparison in a bit, but I can only guess that if say, we're comparing it to length 0, all it needs is to get to the first element in the collection to figure out that the result is false, no need to actually get the full length.

Did I say culprit, well, let me say, BIG culrpit. Here are the benchmark results now...

Scala:

  $ scalac merge_sort.scala && scala MergeSort
  Starting...
  Sorted 100000 elements.
  Total time: 387

Ruby:

  $ ruby merge_sort.rb
  Starting...
  Sorted 100000 elements.
  Total time: 7667

Wow, what a drastic improvement.

*** Disclaimer: This means nothing in terms of benchmarking! Please don't waste your time disqualifying this benchmark, because I know it really means nothing in this small context as well as it means nothing without a true R2 valid measurement. Benchmarks are crap unless properly and fairly compared. This post is not about benchmarking languages, rather I wanted to see how the various idioms and libraries perform while learning both languages. It turned out to be very useful, as a small recommended tuning in Scala's collections lib completely turned things inside out ***

Any ruby folks out there care to comment?

Java multiple class loaders issue

I was facing a rather subtle bug building a decision engine using Drools. Not to get into details of drools here, but the following mostly applies to many rules engines. The basic architecture of the decisions engine is that rules are written using a drools-based rule DSL. These rules are then applied to "facts", which in the context of java, are just POJOs. These POJOs can be defined using standard java classes, or using Drools declare facilities which allow you to declare fact types in the actual rules file and then query it using JavaBean like helper utilities in the java application. In our decisions engine, we allow to define types either using drools declare and/or using groovy to define the fact object, which is then parsed, defined, and linked by GroovyClassLoader at runtime, making it available to the working memory of the drools engine as well as its rule parser.

Everything seemed like it was working using Drools defined facts using declare. I was able to dynamically create and query the fact types using reflection. This was great, as we can inject different rules and deploy functionality on the fly. I then created a groovy class, parsed it and injected into the drools package builder as well as its working memory.

Code I used to test the rule inference on the fact type.

def domainClass = '''
  package com.buycentives.types
  import com.buycentives.incengine.* 
  class Input {
    String name
    int age 
    boolean valid
  }
'''            
Class inputClass = new GroovyClassLoader().parseClass(domainClass)
def input = inputClass.newInstance()
input.name = "Ilya"
input.age = 25    

/// Here we inject the fact and fire the rules, see the following java code snippet

// This code was originally failing
assertEquals input.valid, true  

Here is the code I used to assemble the working memory. This code is more modularized in my code and I tried to compile it into a snippet, though I might of missed something and some object instantiations are not shown.

                    
ClassLoader loader = new GroovyClassLoader()
PackageBuilderConfiguration config = new PackageBuilderConfiguration();
config.setClassLoader(loader);

KnowledgeBuilder kBldr = KnowledgeBuilderFactory.newKnowledgeBuilder(config);
kBldr.add(ruleResource, ResourceType.DRL);

if (kBldr.hasErrors())
  throw new RuntimeException("Unable to compile rules. " + kBldr.getErrors().toString());

KnowledgeBase kb = KnowledgeBaseFactory.newKnowledgeBase(new RuleBaseConfiguration(loader));
kb.addKnowledgePackages(kBldr.getKnowledgePackages());  
StatelessKnowledgeSession kSession = kBase.newStatelessKnowledgeSession();
kSession.execute(factObject);

The rule that was being asserted

package com.buycentives.incengine.rules

import java.util.Date
import com.buycentives.types.Input

rule "Assert for age"
  when
    $input: Input( age >= 20, age < 30 )
  then
    $input.setValid(true);
end  

To make the story short, the rule never fired, although I verified that the Input object instance was injected into the working memory, though never changing the fact's valid property. I beat my head against the wall over and over and over and finally I realized what was going on. It's java's class loader caveat. It's not really a bug, rather a feature I guess. It's not really documented in the javadocs, but I've seen references to this caveat before.

When you load the same class using two different class loaders, inside the jvm, they are considered two different classes, although logically they are the same, therefore failing the Class.isAssignableFrom and instanceof conditional test.

So the following test would fail...

def domain = "class Test {}"

GroovyClassLoader loader1 = new GroovyClassLoader()
Class clazz1 = loader1.parseClass(domain)

GroovyClassLoader loader2 = new GroovyClassLoader()
Class clazz2 = loader2.parseClass(domain)

assertTrue clazz1.isAssignableFrom(clazz2)

So the lesson here, beware of injecting class loaders, especially when you're comparing classes that were loaded with a different class loader than the class loader of the thread that's inferring equality.

Also, beware of GroovyClassLoader.parseClass method. It parses, defines, and links the class, but if you then use it again on the same class, the resulting classes are different.

The following test fails...

GroovyClassLoader loader = new GroovyClassLoader()
Class clazz1 = loader.parseClass(domain)
Class clazz2 = loader.parseClass(domain)

assertTrue clazz1.isAssignableFrom(clazz2)

Also, this link from "Java Specialist Newsletter" is a good source of some interesting class loader information.

Installing couchdb on Snow Leopard

Usually the process is pretty easy. If you have MacPorts, and if you don't, I recommend you get it, you just type sudo port install couchdb.

With Snow Leopard, this installation is a bit broken. The port install works, but then you get an exception, something like Trace/BPT trap. It's not really due to CouchDB, but rather one of its dependencies, SpiderMonkey (Mozilla's embeddable JS engine written in C).

So here is a simple solution...

  sudo port install couchdb
  sudo port uninstall -f spidermonkey
  cd /tmp
  curl -O http://ftp.mozilla.org/pub/mozilla.org/js/js-1.7.0.tar.gz
  curl -O http://svn.macports.org/repository/macports/trunk/dports/lang/spidermonkey/files/patch-jsprf.c
  tar xvzf js-1.7.0.tar.gz
  cd js/src
  patch -p0 -i ../../patch-jsprf.c
  make -f Makefile.ref
  sudo su
  JS_DIST=/usr/local/spidermonkey make -f Makefile.ref export
  exit
  sudo ranlib /usr/local/spidermonkey/lib/libjs.a
  # if you get an error here, ignore it

  sudo ln -s /usr/local/spidermonkey/include /usr/local/include/js
  sudo ln -s /usr/local/spidermonkey/lib/libjs.dylib /usr/local/lib/libjs.dylib
  # If you're feeling saucey, the js shell can be useful for quick syntax checking and the like.
  sudo ln -s /usr/local/spidermonkey/bin/js /usr/local/bin/js

That's it, you should be able to do sudo couchdb and it should run startup fine.

Let me know if you find any issues during this install and/or after.