Hacker News Reader

Comment by userbinator | Hacker News Reader

Microsoft Excel/PowerPoint/Word have a patch in _CFArraySortValues to change the sorting algorithm slightly. How do you break sorting?!

To take a wild guess, it could be a change from a stable to unstable sort: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Apple gets a bad reputation for their supposed lack of backwards compatibility. Nothing is further from the truth: macOS includes tweaks for specific important apps to keep them working on new OS versions.

I read it more as "even Apple is willing to put in patches for backwards compatibility, if your app is important enough." If your app is not, then Apple couldn't care less. MS is more conservative about not breaking things even for relatively obscure apps.

View on HN

I authored many check fixes like these in Cocoa.

Cocoa would not change from a stable sort, even if undocumented, to an unstable one. There's large compatibility risk and no benefit, since any app that is bound by sorting speed should do something custom anyways.

As to why the sorting hot fix: My first guess is that the app modifies the array from within the comparator. My second guess is that the comparator is not actually transitive, e.g. there can be "less than" cycles. In either case, Cocoa could work around this by employing a naive sorting algorithm.

Might be. I took a look at _CFArraySortValues, and the "normal" path through it ends up calling CFQSortArray. However, the "com.microsoft.*" path performs what appears to be a bubble sort. Interestingly, the public facing version of CoreFoundation doesn't have the special-case paths: https://github.com/apple/swift-corelibs-foundation/blob/df3e...

I suppose Excel data is often almost sorted with a few new additions, which makes bubble sort an arguably better choice?

Nope, bubble sort always performs the same number of ops regardless of whether the array is partially sorted or not. You might be thinking about insertion sort, which has that feature.

Bubble sort's number of operations can vary from n, if the list is sorted already, up to O(n*n) if the list is reversed.

Not true.

(3 2 1) -> (2 3 1) -> (2 1 3) -> (1 2 3) (3 passes, 3 swaps)

Compare: (1 3 2) - > (1 2 3) (2 passes, 1 swap)

Hmm I suppose you're right. My bad!

If you write it really poorly that might happen - but its easy to add a check to see if any swaps occurred. If none, you are done.

I can't imagine they're using the OS sort for actual spreadsheet data. It's probably for something else like filenames or whatever, and it ends up not finding the file it's expecting in the place it's expecting.

Agreed, especially since I (the GP) thought about this the wrong way - _Apple_ has chosen to use bubble sort as a compatibility measure for some Microsoft apps, not the other way around.

Which was possible because Microsoft decided to use Core Foundation APIs for sorting instead of their own implementation for spreadsheet data. Or maybe it's not for spreadsheet data, but just their custom file picker or something?

It's a framework-provided sort, not an OS sort. Its use is no weirder than using stdlib sorts, such as Go's "sort" package (which does either a quicksort, heapsort or shellsort, depending on the input length).

However, relying on stability if it is not specified is a bad thing.

While I'm not a big fan of reinventing the wheel, when you're maintaining a 31-year-old cross-platform app that the majority of the planet's businesses rely on for their calculations, I'd be using a custom cross-platform math/sorting/etc engine rather than delegating to any OS, framework, stdlib, third-party anything. Considering this is Microsoft, where Office 4.2 for Mac was as close to WINE as you could get in the 90's, I'm assuming they're doing the same.

They are in platform specific code, manipulating CoreFoundation types (specifically a CFMutableArray), so your cross-platform homebrew sort suggestion is out of scope here. Any sorting function would need to be CoreFoundation (iOS/watchOS/macOS) specific.

When possible, it would of course be best to use stdlib functionality, which would implicitly be cross-platform. Writing it yourself, or pulling in third-party libs to do it ranks way below stdlib, although I can't agree with myself whether doing so is better or worse than using OS-specific standard frameworks. Regardless, it is out of scope in this example.

The post I was replying to was talking about "Excel data", which I interpret as spreadsheet data.

Do you really think that when you sort a column in Excel, it puts the whole thing into a CFMutableArray and asks CoreFoundation to sort that?

No, as I wrote, I would assume any use of CoreFoundation types are only used in platform specific code (dealing with UI, system events, etc.), which would be a minority of the code base, and entirely unique to the platform.

Using CoreFoundation in such code is entirely sensible. Generalizing a sort for something like this would be a waste of time with no gains (as long as the functionality is used correctly, like not assuming a non-specified sort to be stable).

However, for the actual business logic, the hierarchy would be:

    stdlib > large third-party cross-platform lib > small third party cross-platform lib ≈ homegrown implementation.

Insert sort should also be pretty fast for almost stored list, (and works better for not almost sorted).

Friends don't let friends use bubble sort.

In fact friends don't even let enemies use bubble sort, if they have an ounce of humanity.

Edit to actually answer the question: I wonder if it's something to do with some specific dataset having to be sorted in a particular way? i.e. where you'd normally use a stable sort, but the code accidentally depends on a specific unstable sort.

Oh, wait, bubble sort is stable so it can't be that. Any other theories?

>Any other theories?

1. Excel needs stable sort but OSX sort is unstable.

2. Performance deoptimisation to make Excel perform worse.

There are any number of better ways to fix 1, though!

2 occurred to me too, but surely that’s too cynical. It would make Macs look bad more than Excel itself.

Maybe it’s a bit of both. They needed a fix for 1, but they didn’t care about Excel performance at all so someone just spent 20 seconds doing a quick bodge job.

Maybe because the software has a race condition around sorting which requires the use of a slower sort?

Is it wrong to ask if Microsoft intended it to be slow?

Mac Outlook on a recent MBP is noticeably slower (usability impact) than a similar version of Outlook on my Windows VM on the same machine against the same account (30k items, 5GB-ish)

Bubble sort is never a good choice unless so extremely lazy or what to impersonate Obama...[0]

There are dual-pivot quicksort, smooth sort (in-place, based on Leonardo numbers and takes O(n) time to process a presorted array and O(n log n) in the worst case, and achieves nearly-linear performance on many nearly-sorted inputs), TimSort (that's stable as plus).

Morealso changing stable to unstable sort is usually a very bad move.

[0]: https://www.youtube.com/watch?v=k4RRi_ntQc8

Bubble sort is perfectly acceptable when you can only swap adjacent elements, which occasionally comes up in memory management.

That’s the only time it would ever be acceptable, and I don’t think that comes up very often at all.

Hmm, do you have a good example? Even linked lists allow swapping elements at arbitrary positions.

At one point I was implementing managed memory on a highly memory constrained system. The system pretty quickly ran into issues with having enough memory to fulfill a request, but no contiguous block long enough. The solution to this is of course defragmentation. The issue is that allocations are irregularly sized and all swaps have to be done in-place. There was also a need to collect blocks of similar size together so the GC could work faster. Bubble sort was the only way to meet all these constraints cleanly, and better yet it only took 10 lines. It still felt dirty though.

How is it that your data was too big to fit in memory, but small enough that bubble sort ran in a reasonable amount of time? Did you have really tight memory constraints (not sure I'm guessing you'd have to have <100KB of memory)?

Because the sort is done, not when all memory is sorted, but when there's a memory region large enough to malloc.

The comparator here is "used" or "empty", where "used" is either > or < "empty".

The data wasn't too big to fit in memory, but rather defragmentation meant that the amount of free memory available was less than the amount of contiguous space, which will be an issue in any dynamically allocating system that doesn't translate pointers.

That said, bubble sort is only n^2 and computers are fast. The real solution was that defrag was an alternative to crashing, so it didn't matter how long it took. Calling it meant a bug report needed to be filed.

>... size together so the GC could work faster.

So you wrote a non-compacting(copy)/generation garbage collector that used bubble sort?

A compacting gc with zero space overhead and complete memory utilization, yes.

I believe the open source Swift versions are not supposed to have any check fixes. They are not the ones that are run on Apple OSes and probably never will be. They’re more meant to help Linux and other non Darwin platforms adapt. Which kinda sucks because it means the repos are a little lacking.

Windows also ships with a large number of compatibility fixes (‘shims’) and even has a tool to create your own.

Reply on news.ycombinator.com