The 2 best things since sliced bread

Not going to talk a lot here, but I wanted to share 2 quick things. If you are not using Cloudflare…..use it. It’s a CDN, but also so much more. It can protect your site from attacks and has a handy firewall, also a handy interface to handle your DNS, some nifty analytics, and can also handle your SSL cert to make it dead simple to go https. One of my favorite things is the speed optimizations where it can automatically minify your CSS and JS as well as do some very cool image optimization. Best of all it’s free for small companies and cheap for large….I use it on all my work sites and when I get some time I’m switching this site to it. They’ve also just implemented a new geocentric load balancer that I’m excited to try.
The other things I wanted to mention was this site HTACCESS Tester. If you’ve ever had to deal with an htaccess file, and who hasn’t if you’re doing serious web dev for SEO, you know it’s a pain in the ass….it can do remarkable things w/url rewrites and 301’s, BUT it can be incredibly evil as well. You probably already know about the tag you can insert into your virtual host configuration to turn on logging for htaccess (LogLevel alert rewrite:trace6), but that log is waaaay too much info, especially with a large .htaccess file. Enter htaccess tester. Now you can write a rule and check if it gets applied the way you think it will…seriously, it’s a life saver.

Dual Pivot Quicksort Kicks Butt!

So while I was checking out different flavors of quicksort after taking the Coursera Algorithms class I found out about a new version of quicksort that was much faster then I had anticipated.  Java 7 had recently modified their sort function to use a new algorithm called Dual Pivot Quicksort, so I thought I’d check it out.  I found a java version and recoded it to be javascript.  It works well, but currently only sorts integers and in ascending order.  Ideally I should modify it to work the same way the normal array sort algorithm works, that way I’d be comparing apples to apples.  I believe under the hood that the V8 javascript engine has upgraded to the new dual pivot algorithm, but it does have some additional checks and improved functionality where you can pass in the sorting algorithm, which may be why it’s consistently slower then my javascript version of dual pivot quicksort that I coded up.  It’s consistently 10%-50% faster then the default array.sort() algorithm.  The default sort is going to work well enough for 90% of your sorting cases, but if you are following the 10/90 rule and have narrowed down the bottleneck in your code and want to optimize sort, then I would advise taking this code and modifying it for your needs since it will always be faster then the default array.sort().  Check it out on JSPerf http://jsperf.com/javascript-quicksort-comparisons

Technically JS Perf says it’s ±10.25% faster then the default sort the last time I ran it, but it does vary quite a bit. My guess is that it probably varies based on how random the shuffle is.  I suppose it could be because we are comparing a lion to a cheetah….the default sort sorts any object, and lets you pass in the sorting function, while the dual pivot quicksort I coded up only works on integers and in ascending order, but I’d still say it’s worth looking into, ESPECIALLY if whatever language you are coding in hasn’t rewritten their quicksort to use the new algorithm.  I made it a single variable module, and you call it with DualPivotQuicksort.sort(arr). Here’s the code.


/******** Dual Pivot QuickSort ***************/

var DualPivotQuicksort = (function() {

    var dualPivotQS = {};

    dualPivotQS.sort = function(arr, fromIndex, toIndex) {
        if(fromIndex === undefined && toIndex === undefined){
            this.sort(arr, 0, arr.length);
        } else{
            rangeCheck(arr.length, fromIndex, toIndex);
            dualPivotQuicksort(arr, fromIndex, toIndex - 1, 3);
        }
        return arr;
    }

    function rangeCheck(length, fromIndex, toIndex) {
        if (fromIndex > toIndex) {
            console.error("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            console.error(fromIndex);
        }
        if (toIndex > length) {
            console.error(toIndex);
        }
    }

    function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    function dualPivotQuicksort( arr, left, right, div) {
        var len = right - left;

        if (len < 27) { // insertion sort for tiny array
            for (var i = left + 1; i <= right; i++) {
                for (var j = i; j > left && arr[j] < arr[j - 1]; j--) {
                    swap(arr, j, j - 1);
                }
            }
            return;
        }
        var third = Math.floor(len / div); //TODO: check if we need to round up or down or just nearest

        // "medians"
        var m1 = left  + third;
        var m2 = right - third;

        if (m1 <= left) {
            m1 = left + 1;
        }
        if (m2 >= right) {
            m2 = right - 1;
        }
        if (arr[m1] < arr[m2]) {
            swap(arr, m1, left);
            swap(arr, m2, right);
        }
        else {
            swap(arr, m1, right);
            swap(arr, m2, left);
        }
        // pivots
        var pivot1 = arr[left];
        var pivot2 = arr[right];

        // pointers
        var less  = left  + 1;
        var great = right - 1;

        // sorting
        for (var k = less; k <= great; k++) {
            if (arr[k] < pivot1) {
                swap(arr, k, less++);
            }
            else if (arr[k] > pivot2) {
                while (k < great && arr[great] > pivot2) {
                    great--;
                }
                swap(arr, k, great--);

                if (arr[k] < pivot1) {
                    swap(arr, k, less++);
                }
            }
        }
        // swaps
        var dist = great - less;

        if (dist < 13) {
            div++;
        }
        swap(arr, less  - 1, left);
        swap(arr, great + 1, right);

        // subarrays
        dualPivotQuicksort(arr, left,   less - 2, div);
        dualPivotQuicksort(arr, great + 2, right, div);

        // equal elements
        if (dist > len - 13 && pivot1 != pivot2) {
            for (var k = less; k <= great; k++) {
                if (arr[k] == pivot1) {
                    swap(arr, k, less++);
                }
                else if (arr[k] == pivot2) {
                    swap(arr, k, great--);

                    if (arr[k] == pivot1) {
                        swap(arr, k, less++);
                    }
                }
            }
        }
        // subarray
        if (pivot1 < pivot2) {
            dualPivotQuicksort(arr, less, great, div);
        }
    }
    return dualPivotQS;
}());

/************************************************/

Javascript Modular Design

So I just completed my update of my Facebook app My Amazon Wishlist  I converted all of my messy initialization and jquery UI event handling code into a nice neat single variable javascript module.  It is sooooo much prettier….cleaner, more modular (it’s right there in the name!), less likely to interfere with any other javascript includes.  I briefly contemplated creating javascript objects for the lists….if I were to recode it from the start that’s how I would do it, but for now I’ll leave it as is because cloning the objects is faster and it can stay as is until I decide to implement more features.  The back-end is all php objects, and has made it incredibly easy to update and add features, as well as re-use in my wordpress plugin.  I also updated from jQuery 1.8.1 to 1.10 and had to update a few deprecated function calls that were removed in 1.9 ….GO $(document).on(‘click’, ‘id’, function(){});!…I also had to replace window.parent.document calls inside an iframe with  with jQuery postmessage calls….they actually turned out quite nicely….you have to setup a listener in the parent frame, then in the iframe (or another website even..it solves the cross-domain problem). post the message to the parent.  In my case I was sending multiple pieces of data, so I put it into an array, stringified it and passed it to the parent.  One thing I would note….in the listener you should make it so that it only accepts messages from the website you expect to be sending messages.  Here’s the code from the iframe:

var msgArray = new Object();
msgArray[‘newHeight’] = $(‘#aws-item’).height().toString();
msgArray[‘listNo’] = listNo;
msgArray[‘itemNo’] = itemNo;
msgArray[‘iframeID’] = iframeID;
var message = JSON.stringify(msgArray);
parent.window.postMessage(message, ‘*’);

And so ends my first article for my new website!  I think I’ll write the next one on how I localized (L10N) my WordPress plugin http://wordpress.org/plugins/easy-amazon-wishlist/