Slashdot Mirror

Sorts have been parallelized and distributed for decades. It would be interesting to benchmark Google's approach against SyncSort. SyncSort is parallel and distributed, and has been heavily optimized for exactly such jobs. Using map/reduce will work, but there are better approaches to sorting.

The original US patent (5,440,676) that opened the door to patenting software...

That's bogus information. Software patents go back much further than that. The first software patent was filed in 1965, issued in 1968, and expired in 1981. It's Martin Goetz's U.S. "Sorting System", Patent #3,380,029, the sorting algorithm that broke the O(N log N) barrier. That's the technology behind SyncSort, and it powered mainframe sorting for a generation.

While radix sorts are limited, binned sorts, which are a superset of radix sorts, are more powerful. Binned sorts do work on a broad set of data types, but you have to use statistical techniques to dynamically pick a good distribution among the bins. SyncSort developed this technique in the 1960s, and had the first software patent, now long-expired. Mainframe batch systems have used such techniques for decades.

The general idea is that if you're sorting, say, text strings, you watch them go by for a while, accumulating statistics, then compute a set of bin division points which will divide them into bins of roughly equal size. The bins have to be watched, and if some get too big or too small, the bin division points have to be adjusted. It's a tree-rebalancing problem.

If your sort is too big for RAM, and you have to go out to disk (or, in early systems, tape) this is a huge win. It lets you beat O(N log N), both in theory and in practice. SyncSort times grow at worse than O(N), but better than O(N log N).

Few people bother for in-memory sorts, though.

However, I believe that a version of IBM's DITTO was available on System/360 in 1965. I've not been able to confirm this, though.

However, I believe that a version of IBM's DITTO was available on System/360 in 1965. I've not been able to confirm this, though.

How about forking a few hundred times more for a version of sort ? :)

SyncSort was the first useful sort program to break the O(N log N) barrier (yes, this is possible, CS101 kiddies). This was a huge win for mainframe shops with their big tape-to-tape sort jobs. That's what all those spinning tape reels were doing on early computers. SyncSort cut days off some batch jobs.

You can buy current versions of SyncSort. The old versions for IBM mainframes are still available, and you can get it as an Active-X control for Windows. So that's a 34-year old product, little changed in decades and still doing a useful job today.

I did maintenance programming on a competitive product, UNIVAC Exec II Sort/Merge, around 1969. SyncSort was faster. They really did have a better, and patented, algorithm.

CA is the most egregiously arrogant company I have dealt with in over 15 years of doing computer support. Besides the support issues that have already been mentioned, just trying to *buy* their products can be a nightmare. Several years ago they tried to sell me Unicenter. The salesman and I went round and round for months over one central issue: Pricing.

It wasn't that the pricing was too much, it was that they couldn't tell me what it was. I insisted that I wasn't going to invest any time in evaluating Unicenter until I was convinced that it would fit in my budget. I wanted a price schedule -- you know, like a price per server of various sizes, and a price per client, a price per management station, etc. They wouldn't give me any prices until I'd given them a complete inventory of all the hardware on our network, identifying which machines were servers, which workstations, etc., etc., etc. I tried to explain that this was a Sun environment and, what with NFS and all, just about *all* the machines could be considered servers, and that for the purposes of determining affordability, he could just assume that all of our approximately 150 Sun machines were servers. I explained that doing the kind of documentation he wanted, in the form he wanted, was exactly the kind of thing I didn't have time for until I knew that I could afford the product. After a long time of this, I finally told him to just stop calling me.

We went through the same thing again a few months ago with ARCserve. We'd been using ARCserve for NT since the Cheyenne days -- Cheyenne was actually a pretty good company before CA slaughtered it -- and we wanted to (a) upgrade it to the latest version and (b) buy copies for our Unix machines. It boggles the mind, but we never, ever did get a price for it. There appeared to be no one in CA who was authorized to give us a price, and we tried, repeatedly, for months to get this information out of them. At one point they sent us a single license for evaluation, but by that time we were pretty far along evaluating an alternative, Backup Express from SyncSort. Backup Express works great, and SyncSort's service is excellent.

Really, CA offering products for Linux is a very mixed blessing.

CA is the most egregiously arrogant company I have dealt with in over 15 years of doing computer support. Besides the support issues that have already been mentioned, just trying to *buy* their products can be a nightmare. Several years ago they tried to sell me Unicenter. The salesman and I went round and round for months over one central issue: Pricing.

It wasn't that the pricing was too much, it was that they couldn't tell me what it was. I insisted that I wasn't going to invest any time in evaluating Unicenter until I was convinced that it would fit in my budget. I wanted a price schedule -- you know, like a price per server of various sizes, and a price per client, a price per management station, etc. They wouldn't give me any prices until I'd given them a complete inventory of all the hardware on our network, identifying which machines were servers, which workstations, etc., etc., etc. I tried to explain that this was a Sun environment and, what with NFS and all, just about *all* the machines could be considered servers, and that for the purposes of determining affordability, he could just assume that all of our approximately 150 Sun machines were servers. I explained that doing the kind of documentation he wanted, in the form he wanted, was exactly the kind of thing I didn't have time for until I knew that I could afford the product. After a long time of this, I finally told him to just stop calling me.

We went through the same thing again a few months ago with ARCserve. We'd been using ARCserve for NT since the Cheyenne days -- Cheyenne was actually a pretty good company before CA slaughtered it -- and we wanted to (a) upgrade it to the latest version and (b) buy copies for our Unix machines. It boggles the mind, but we never, ever did get a price for it. There appeared to be no one in CA who was authorized to give us a price, and we tried, repeatedly, for months to get this information out of them. At one point they sent us a single license for evaluation, but by that time we were pretty far along evaluating an alternative, Backup Express from SyncSort. Backup Express works great, and SyncSort's service is excellent.

Really, CA offering products for Linux is a very mixed blessing.