Adam Tuttle

In Search of Performance

One of the more fun tasks in the new product I'm building has been a method to find the intersection (or in SQL terms, Inner Join) of an arbitrary set of arrays.

While this task would be well suited for SQL, some of our requirements prohibit that from being an option. Not all of the data will come from a database; some will come from web service calls. So I need a method that returns an array that contains only the elements that were present in all of the input arrays, and satisfies this interface:

array function intersection( array arrays ){}

Whatever the solution is, it needs to be fast because each of these input arrays could theoretically contain several hundred thousands of elements. The only other requirement was that it needs to run on Adobe ColdFusion 10 (as opposed to 11, which I will come back to in due time).

Counting

As you can imagine, there are dozens of ways to skin this cat. The first that came to mind was to count the instances of each element and then build a new array of only the elements whose count matched the number of input arrays:

array function arrayInnerJoinByCounting( array arrays ){
    var ht = {};
    var reqCount = arrayLen( arrays );
    var result = [];
    //count instances of each array value
    for (var arr in arrays){
        //if any array is empty, the result will be an empty array
        //so just short-circuit the whole process
        if (arrayLen(arr) == 0){
            return [];
        }
        for (var i in arr){
            if (!structKeyExists(ht,i)){
                ht[i] = 1;
            }else{
                ht[i]++;
            }
        }
    }
    //make a new array of values that appear the minimum number of times
    for (var k in ht){
        if (ht[k] == reqCount){
            arrayAppend(result, k);
        }
    }
    return result;
}

This method works, but as you probably expect, is not the most performant option. Counting is easy to understand, but turns out to be pretty unperformant inperformant imperformant slow.

Pairing Off

My next thought was to iterate over the set of arrays, reducing them a pair at a time. If I start with the shortest array, it should help reduce memory usage and the number of insertion operations on my hashtable. Note that I'm not sorting the actual arrays, I'm just arranging them in order of shortest array to longest array.

array function arrayInnerJoinByCFHashtableSorted( array arrays ){
    arraySort(arrays, function(a, b){ return (arrayLen(a) < arraylen(b) ? -1 : 1); });

    var left = arrays[1];
    var right = 0;
    for (var cursor = 2; cursor <= arrayLen(arrays); cursor++){
        right = arrays[cursor];
        left = arrayIntersectionByCFHashtable( left, right );
    }
    return left;
}
array function arrayIntersectionByCFHashtable( array left, array right ){
    var ht = {};
    var result = [];
    var smaller = larger = [];
    if (arrayLen(left) > arrayLen(right)){
        smaller = right;
        larger = left;
    }else{
        smaller = left;
        larger = right;
    }

    for (var i in smaller){
        ht[i] = 1;
    }
    for (var i in larger){
        if ( structKeyExists( ht, i ) ){
            arrayAppend( result, i );
        }
    }
    return result;
}

I also put together a benchmarking harness to measure the performance of these methods with different array sizes. I wanted something semi-realistic in terms of amount of items in the arrays and their expected overlap, and I also made sure to run each method 10 times and average their scores, to help smooth out any differences due to other system load. I'll share the benchmarking harness at the end of the post, but here are the results of comparing these two methods with ~200k items. The values are all times in milliseconds. The arrays are the times for each iteration, and the root named keys are their averages.

first benchmark results

In order to save a little bit of space, I'm going to suppress the details of the benchmark iterations and only show the averages, but the benchmark methodology will be the same: average of 10 iterations.

So this new method was faster than my original counting approach by a small but consistent margin — but I wondered if it could be beaten. I also wondered if the sorting was costing more than its benefit, so I made a copy that did the same thing with unsorted arrays:

Pairing Off (Unsorted)

array function arrayInnerJoinByCFHashtable( array arrays ){
    var left = arrays[1];
    var right = 0;
    for (var cursor = 2; cursor <= arrayLen(arrays); cursor++){
        right = arrays[cursor];
        left = arrayIntersectionByCFHashtable( left, right );
    }
    return left;
}

Is sorting worth it? Not in this case!

At least with these inputs, sorting did in fact cost ever so slightly more than it was worth. However, when cranked up to ~400k items in each array, the tables turned ever so slightly in favor of sorting. I'm calling the difference here statistically insignificant.

Java RetainAll

Then my coworker Steve turned me on to Java's retainAll() method, and I figured that was worth a shot. The code was certainly simpler! If you're not familiar, retainAll will remove items from the original array that don't appear in the argument.

array function arrayInnerJoinByJavaRetainAll( array arrays ){
    var shortestIx = 1;
    var minLength = arrayLen(arrays[1]);
    for ( var i=2; i <= arrayLen( arrays ); i++ ){
        var length = arrayLen( arrays[i] );
        if ( length < minLength ){
            minLength = length;
            shortestIx = i;
        }
    }
    var shortest = arrays[ shortestIx ];
    for (var i=1; i<=arrayLen(arrays); i++){
        if ( i != shortestIx ){
            //java voodoo
            shortest.retainAll( arrays[i] );
        }
    }
    return shortest;
}

With this method, it made sense to start with the shortest array, but a full sort was not necessary. To my surprise, retainAll() was extremely slow! I figured that being closer to the metal would give it an unfair advantage, but that doesn't seem to be the case. I would guess that it is designed with smaller datasets in mind.

Java does not have an unfair advantage here

In fact, I had to turn down the number of items in the array to 10k instead of the usual 200k just to get this benchmark to run. As you can see, retainAll() gets blown out of the water.

Java HashSet

By this time, I was talking about the fun I was having in IRC, too, and was getting a few more suggestions there. One particularly good one came from Ryan Guill: A fork of my pairing-off technique but using a Java Hashset class instead of a CF structure. If I understand it correctly, it works very similarly to my CF structure, except that there's no "value" associated with the key. Either the key is in the hash table or it is not. (Please do correct me if this understanding is incorrect!)

array function arrayInnerJoinByJavaHashset( array arrays ){
    var shortestIx = 1;
    var minLength = arrayLen(arrays[1]);
    for ( var i=2; i <= arrayLen( arrays ); i++ ){
        var length = arrayLen( arrays[i] );
        if ( length < minLength ){
            minLength = length;
            shortestIx = i;
        }
    }
    var shortest = arrays[ shortestIx ];
    for (var i=1; i<=arrayLen( arrays ); i++){
        if ( i != shortestIx ){
            shortest = arrayIntersectionByJavaHashset( shortest, arrays[ i ] );
        }
    }
    return shortest;
}
array function arrayIntersectionByJavaHashset( required array shorter, required array longer ){
    var hs = createObject("java", "java.util.HashSet").init( arrayLen(shorter) );
    for (var i in shorter){
        hs.add(i);
    }
    var result = [];
    for (var i in longer){
        if (hs.contains(i)){
            arrayAppend( result, i );
        }
    }
    return result;
}

And the results:

Java Hashset results

As it turns out, the Hashset is significantly faster for these inputs. (Who knows how performance will change with more/less and larger/smaller arrays?)

So far, this has been the best approach I've been able to find. (Thanks, Ryan!)

Use SQL Anyway

Another approach that I thought of, and that was suggested by others as well, was to inject the data into a temp table in my database and let SQL do the heavy lifting in the joining department. It seemed like a decent enough idea, so I took a stab at creating a file that I could use with MySQL's LOAD DATA LOCAL directive, which I've had success with in other tasks; because running almost a million insert statements before doing the join would have no chance of winning. (If I were using MSSQL, I would consider something like fnSplit)

I tried using a StringBuilder to put together one string per array, and append each of them to a file, but CF couldn't even get that done for reasonably small sets of data without choking and eventually timing out. For that reason I never finished this approach, but I thought it was worth sharing how far I got so that people can point out any flaws they might see.

array function arrayInnerJoinBySQL( array arrays ){
    //didn't get any further than this because CF has been choking either on the string
    //building or the file writing. Either way, it has not been a successful avenue thus far.
    var namespace = CreateUUID();
    var filePath = sanitizePath(getTempDirectory()) & '/iq-arrayjoin-data-load-#namespace#.txt';
    if ( fileExists( filePath ) ){
        fileDelete( filePath );
    }
    fileWrite( filePath, "" );
    var fileObj = fileRead( filePath, "append" );
    for (var a = 1; a <= arrayLen( arrays ); a++){
        fileWrite( fileObj, arrayToString( arrays[a], a ) );
    }
    fileClose( fileObj );
}
string function arrayToString( array data, numeric ix ){
    var sb = createObject("java", "java.lang.StringBuilder").init("");
    for(var i in data){
        sb.append(ix);
        sb.append(',');
        sb.append(i);
        sb.append(chr(10));
    }
    return sb.toString();
}
function sanitizePath( path ){
    path = replace( path, "\", "/", "ALL" );
    if ( right( path, 1 ) == '/' ){
        path = left( path, len( path ) - 1 );
    }
    return path;
}

Honorable Mention: CF 11 Closure Functions

This approach was suggested by Adam Cameron and looks pretty slick, if for no other reason than its brevity and use of Closure. Unfortunately most of these functions are only available in CF11, even ignoring the member-functions aspect; for example, there is no arrayReduce() method in CF10. But I thought it worth mentioning here, for anyone that might come along later and not have the same constraint as I do. (Bear in mind, you should benchmark it against other method(s) before going ahead with it!)

array function arrayInnerJoinByCFClosures( array arrays ){
    var result = arrays.reduce( function( reduction, current, index ){
        if ( index == 1 ) return reduction;
        return current.filter( function( element ){
            return reduction.contains( element );
        });
    }, arrays[1]);
    return result;
}

Benchmarking Harness

I promised I would share my code for getting these benchmarks, so here you go. It's a little bit of a mess as I was changing things around a good bit in order to get the right screen shots for this post. You will, of course, just have to uncomment various blocks and copy in the functions from above in order to run it.

<cfsetting requesttimeout="600" />
<cfscript>

    variables.size = 200000;
    variables.samples = 10;
    variables.data = [ [], [], [], [] ];

    /* GENERATE TEST DATA */
    for ( i = 1; i <= size; i++ ){
        arrayAppend(variables.data[1], i);
    }
    for ( i = 1; i <= size*2; i = i+2 ){
        arrayAppend(variables.data[2], i);
    }
    for ( i = 1; i <= size*2; i = i+3 ){
        arrayAppend(variables.data[3], i);
    }
    for ( i = 1; i <= size*4; i = i+4 ){
        arrayAppend(variables.data[4], i);
    }
    /* END DATA GENERATION */

    // for ( i = 1; i <= samples; i++){
    //  start("counting");
    //  arrayInnerJoinByCounting( data );
    //  end("counting");
    // }

    // for ( i = 1; i <= samples; i++ ){
    //  start("Java Hashset");
    //  arrayInnerJoinByJavaHashset( data );
    //  end("Java Hashset");
    // }

    // for ( i = 1; i <= samples; i++ ){
    //  start("retainAll");
    //  arrayInnerJoinByJavaRetainAll( data );
    //  end("retainAll");
    // }

    // for ( i = 1; i <= samples; i++){
    //  start("cf hashtable unsorted");
    //  arrayInnerJoinByCFHashtable( data );
    //  end("cf hashtable unsorted");
    // }

    // for ( i = 1; i <= samples; i++ ){
    //  start("cf hashtable sorted");
    //  arrayInnerJoinByCFHashtableSorted( data );
    //  end("cf hashtable sorted");
    // }

    //===============================================

    function start( string metricName ){
        param name="request.metrics" default={ _detail: {}, _instances: {} };
        request.metrics._detail[ metricName ] = getTickCount();
    }

    function end( string metricName ){
        var tick = getTickCount();
        if ( !structKeyExists( request.metrics._detail, metricName ) ){
            throw(message="Metric named `#arguments.metricName#` hasn't been started.");
        }
        if (!structKeyExists(request.metrics._instances, metricName)){ request.metrics._instances[ metricName ] = []; }
        arrayAppend(request.metrics._instances[ metricName ], (tick - request.metrics._detail[ metricName ]) );
    }

    function computeAverages(){
        structDelete( request.metrics, "_detail" );
        for (var k in request.metrics._instances){
            var total = 0;
            var count = 1;
            for (count; count <= arrayLen(request.metrics._instances[k]); count++){
                total += request.metrics._instances[k][count];
            }
            request.metrics[k] = round( total / count );
        }
        structDelete( request.metrics, "_instances" );
    }

</cfscript>

<cfset computeAverages() />
<cfdump var="#request.metrics#" label="metrics" />

Conclusion

For now, I'll be using the Hashset-based algorithm. If you think you can do better, by all means, post proof!

Published 2014-09-03 @ 01:00 in ColdFusion

Framework Is No Longer a 4-Letter Word

Raise your hand if you have ever used Fusebox, Model Glue, or Mach-II. (Do jazz-hands if you've used ColdSpring.)

Keep it up if you've ever seen your application time out on the first request while trying to load the framework configuration.

If you raised it for the first prompt, chances are you still have it up after the second prompt. I'm right there with you. You can put your hands down now.

I started coding web-spaghetti in CF 4.5, and learned about frameworks at around the same time CF8 was starting private beta (I don't think I was in that one). Model-Glue became my weapon of choice mostly because Joe was a captivating speaker and his sessions at CFUnited were awesome. I ended up maintaining some Fusebox apps later on in my career. And more recently I worked in a shop that was 100% Mach-II for the better part of the last decade.

They all suffer from the same problem: They were slow because object-creation was still slow in CF back then, and unless you were very careful and deliberate (and sometimes not even then), you were very prone to burying things too deep. XML that defines Listeners that proxy requests to Controllers that call Services that use DAOs. It was painful to make a tiny change because I had to make that change in 5 files... And I'm guilty of it too. Much of my code from this era is equally—if not more—cringe-worthy.

I don't think the developers behind these frameworks are guilty of anything. The tools they gave us were leaps ahead of what we had earlier (see also: <cfswitch>).

BUT... Depending on how bitter you allowed this experience to make you, the reputation that "frameworks" earned in your mind may have been deserved. Most people's experiences with frameworks (and I include myself here) was poor... and the jerk that originally wrote the app you're stuck maintaining is to blame.

Always code like the person that will inherit the app when you leave is a deranged serial killer that knows where you live.

Whether you blame the developer that came before you, or the system that allowed it to happen, many of us have painful memories of frameworks past.

I'm here to tell you that Framework is no longer a 4-letter word.

Modern frameworks use much (much!) less configuration, if any, and orders of magnitude fewer objects. FW/1 (a badass MVC framework) is one object. DI/1 (a badass Dependency Injection framework) is also just one file. And if I may be so bold as to place my own work on the same stage as Sean's, Taffy is only a small handful of files, has super-terse syntax that almost forces you to write as little code as possible, and runs fast as hell.

How well you know your tool matters much more than what tool you know.

At the end of the day, you can still write terrible messes of code with new tools. Just because you have a bad experience doesn't mean the tool is to blame. But framework developers are learning the common pitfalls their users (a.k.a. you and I) run into, and putting up police tape and stanchions to keep us on the path to success. If the word framework gives you sweaty palms and makes you start looking for the exit, I would urge you to come back and try more modern iterations.

You might be surprised.

Published 2014-09-02 @ 09:15 in ColdFusion Frameworks

Taffy 3.0.0-alpha

The first alpha of Taffy version 3.0.0 is ready for public testing!

There was a recent burst of development, thanks to some corporate sponsorship in the form of this conversation with my employer:

"Taffy can do that, right?"

"No, but it's something I've wanted to add for a while."

"Go do it."

There have been a lot of changes and improvements, and one of those is that the documentation now includes a What's new section, so I'm not going to copy over all of that content into the blog post. There are a few breaking changes from 2.x to 3.0 that you should be aware of, but in terms of how long it will take you to update your code, the impact is only a minute or two of your time.

The test suite is fully updated as well, so please run the tests on your environment and report back if you have any troubles! I've verified things are working well on Adobe ColdFusion 8.0.1 and 10u13, and Railo 4.2 (Cheers to Adam Cameron for helping out with this!), but I can't check every platform. As always, if you run into any problems, we've got the mailing list and you can file bug reports.

Also important: If you try out v3 and don't have any problems, please let me know that, too! Silence either means nobody is testing or nobody is having problems, and there's a world of difference.

As always, thank you to everyone that submits bug reports and feature requests, participates on the mailing list, and talks about Taffy in the #ColdFusion channel on IRC. My biggest thanks this time go out to Dan Short, Jean-Bernard van Zuylen, and phipps73 for their pull requests.

If all goes well with the alpha over the next few weeks, I'll release an official v3.0.0 by the end of the month.

Published 2014-08-15 @ 09:00 in Taffy

Jakarta Redirect Error when adding new IIS Websites to an existing ColdFusion 10 Install

Does this look familiar to you?

IIS HTTP Error 404 jakarta/isapi_redirect.dll

I spent a few hours on 3 different days trying to figure out what was wrong, here. I was trying to add a new website to an existing CF10 installation on a Windows Server Box with IIS7.5. The other sites were working fine.

What led me astray was that as part of the initial setup of this new site, I also added a web.config file with a port of the old .htaccess URL Rewriting rules from the site's previous hosting. This whole time I was chasing what I thought were edge cases in Rewrite rules, when in fact the answer was so obvious that "if it was a snake, it would have bit me" (to borrow a phrase from my mom)...

I thought it was a problem with the rewrite rules, and the presence of the "isapi_rewrite.dll" in the error reinforced this assumption. If I had only remembered that as of ColdFusion 10, we now have to add a "jakarta" Virtual Directory in IIS that points to the wsconfig path (in my case: C:\ColdFusion10\config\wsconfig\1\). I think this is taken care of for you if/when you run the web-server connector tool, but I hadn't done that.

So there you go. Just add your virtual directory named "jakarta" and you'll be on your way.

Published 2014-08-12 @ 10:30 in ColdFusion