Technical Difficulties from on Top of the Mountain
2013-09-25
  Relearning sorting.
I had a prospective client ask me to provide some code samples doing sorting. They asked for three different sorts, but I ended up doing 12. Ok, so I kind of got into it.

The first version (testsort1.cpp), had some warts. I used inline macros for some boilerplate expansion, inheritance for the different sorters, and I used a self organizing global singleton list to collect the tasks to run. Plus the version I turned in had an error in one of the three versions of merge sort I wrote. Not that surprising that they didn't call back.

But I decided to press on, and see if I could do better. For one thing, the timing I was getting from shell sort (one of my favorites) was not that great; and I was watching a lot of industry experts in online conferences railing against inheritance (see Sean Parent, an Adobe principal scientist, talk about how Inheritance Is The Base Class of Evil). So my second version (testsort2.cpp), used initializer lists, but needed this really ugly adapter to deal with having two different signatures for the sort functors depending on whether they operated on iterators or raw pointers. I also had a little fight with formatting floating point numbers with iostreams, but that's a whole other story.

Finally, after running over the type erasure/pimpl pattern several times in the Going Native 2013 lectures, I decided to give it a try. Its a really convoluted strategy. Basically, instead of having an abstract base class and a descendant with its own data and extra stuff that implements the base interface, you create a concrete object that doesn't do anything, but has a safe pointer to a virtual base class, which is implemented by a descendant adapter class which is templated to dispatch all its calls to a helper object which it owns. Hopefully the compiler is cleaning up most of this mess.

Anyways, I implemented all of this in version three (testsort3.cpp) which I think is pretty good. I also templated some of the sort routines, though I should use the traits of containers to make the interface a little nicer. One interesting thing though were the results.

I ran GCC and Clang on a 1U server first, and realized these days that -O0 is pretty horrible, especially on the iterator based code:

CompilernBubble SortSelectionInsertion Sort
IterRawIterRawIterRaw
gcc -O0100002515.88836.98711.25156.54304.9860.87
gcc -O210000191.08182.4173.08173.0722.2922.17
gcc -O310000197.23213.6587.4987.4522.3522.2
Clang -O0100001952.49686.21675.17158.1287.8179.07
Clang -O210000215.3210.1263.9363.9222.1522.08
Clang -O310000212.86213.7263.6763.6722.4922.51

Thankfully with some optimization the difference between iterators and raw pointers is down to noise, though it also seems these days that -O3 vs -O2 is pretty much a wash.

It was also amazing how wide the spread was between the worst and best sorts:

Compilern BubbleSelectionInsertionShellMerge buf-Mergeqsort()std::sort
gcc -O2500005226.384353.58576.494.447.675.156.753.3
gcc -O3500005347.932198.94580.264.847.613.976.883.36
clang -O2500005361.561587.31578.194.777.364.816.973.12
clang -O3500005345.021587.3584.164.598.134.836.883.18

Everybody knows that bubble sort is just the worst sort ever, but I was surprised that it was 1000X worse than the cluster of the fast ones. Even selection and insertion sort are way out there, being 300X and 100X times the best times. But I was also curious how well the fast ones would fare as the set sizes continued to grow.

So I pushed on into bigger datasets with the fast ones (sorry, I wasn't going to time n=1000000 for bubble sort with it growing at O(n^2)). Letting it run overnight, I let the fast ones push the bounds of the server's physical memory:

Compilern ShellMergebuf-Mergeqsort()std::sort
gcc -O31000000121.52174.8398.2176.6983.99
gcc -O3100000001519.971950.481124.861984.32967.28
gcc -O310000000018622.1821343.2512492.7622463.410886.02
gcc -O3100000000067849.88171505.77204308.42204446.4947208.55
clang -O31000000124.86176.53119.42174.1879.76
clang -O3100000001564.631982.011392.442010.94926.81
clang -O310000000019084.5421694.5915671.1322861.9410585.51
clang -O3100000000073168.251040334.6144162.16187819.6245389.01

Here we see performance between clang and gcc varying a bit more (though not in a consistent fashion). Strangely enough as the set size gets huge, qsort() takes the biggest hit under gcc, while merge sort goes off the rails under clang.

Clearly std::sort is the winner hands down, though shell sort keeps right up with it until the end. This is important to keep in mind as shell sort's implementation is compact (the key loop is 8 lines long), and its non-recursive. Two very useful properties in embedded applications. It also remains mysterious, as academia can still not explain why it works so well. That's probably one of the reasons I like it so much.

Ok, and now for some pretty pictures:
gcc clang

And a comparison between the timings of gcc and clang for shell & std::sort. I think the units are in ns/N.
diff

Not as fancy as using Google Visualization charts live like in this benchmark of std::containers, but it will have to do for now.

Labels: , ,

 
Comments: Post a Comment

<< Home
Life in the middle of nowhere, remote programming to try and support it, startups, children, and some tinkering when I get a chance.

ARCHIVES
January 2004 / February 2004 / March 2004 / April 2004 / May 2004 / June 2004 / July 2004 / August 2004 / September 2004 / October 2004 / November 2004 / December 2004 / January 2005 / February 2005 / March 2005 / April 2005 / May 2005 / June 2005 / July 2005 / August 2005 / September 2005 / October 2005 / November 2005 / December 2005 / January 2006 / February 2006 / March 2006 / April 2006 / May 2006 / June 2006 / July 2006 / August 2006 / September 2006 / October 2006 / November 2006 / December 2006 / January 2007 / February 2007 / March 2007 / April 2007 / June 2007 / July 2007 / August 2007 / September 2007 / October 2007 / November 2007 / December 2007 / January 2008 / May 2008 / June 2008 / August 2008 / February 2009 / August 2009 / February 2010 / February 2011 / March 2011 / October 2011 / March 2012 / July 2013 / August 2013 / September 2013 / October 2013 / November 2013 / December 2013 / December 2014 / February 2015 / March 2015 / July 2016 / September 2016 / December 2016 / April 2017 / June 2017 / July 2018 / November 2018 / January 2019 / February 2019 / April 2019 / December 2019 / March 2020 / April 2020 / May 2020 / September 2020 / November 2020 / March 2021 / May 2023 /


Blogroll
Paul Graham's Essays
You may not want to write in Lisp, but his advise on software, life and business is always worth listening to.
How to save the world
Dave Pollard working on changing the world .. one partially baked idea at a time.
SnowDeal
Eric Snowdeal IV - born 15 weeks too soon, now living a normal baby life.
Land and Hold Short
The life of a pilot.

The best of?
Jan '04
The second best villain of all times.

Feb '04
Oops I dropped by satellite.
New Jets create excitement in the air.
The audience is not listening.

Mar '04
Neat chemicals you don't want to mess with.
The Lack of Practise Effect

Apr '04
Scramjets take to the air
Doing dangerous things in the fire.
The Real Way to get a job

May '04
Checking out cool tools (with the kids)
A master geek (Ink Tank flashback)
How to play with your kids

Powered by Blogger