6 ms·
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, i
by userbinator 9y ago
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 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.
- saagarjha 9y agoMight 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/df3ec55fe6c162d590a7653d89ad669c2b9716b1/CoreFoundation/Collections.subproj/CFArray.c#L951 https://github.com/apple/swift-corelibs-foundation/blob/df3e...
- snaily 9y agoI suppose Excel data is often almost sorted with a few new additions, which makes bubble sort an arguably better choice?
- xrisk 9y agoNope, 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.
- JoeSmithson 9y agoBubble 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.
- umanwizard 9y agoNot 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)
- xrisk 9y agoHmm I suppose you're right. My bad!
- ape4 9y agoIf 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.
- kalleboo 9y agoI 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.
- snaily 9y agoAgreed, 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.
- krotton 9y agoWhich 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?
- arghwhat 9y agoIt'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.
- deleted 9y ago[deleted]
- kalleboo 9y agoWhile 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.
- hornetblack 9y agoInsert sort should also be pretty fast for almost stored list, (and works better for not almost sorted).
- iainmerrick 9y agoFriends 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.
- iainmerrick 9y agoOh, wait, bubble sort is stable so it can't be that. Any other theories?
- anonymfus 9y ago>Any other theories? 1. Excel needs stable sort but OSX sort is unstable. 2. Performance deoptimisation to make Excel perform worse.
- iainmerrick 9y agoThere 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.
- saagarjha 9y agoMaybe because the software has a race condition around sorting which requires the use of a slower sort?
- r00fus 9y agoIs 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)
- xxs 9y agoBubble 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 https://www.youtube.com/watch?v=k4RRi_ntQc8
- AlotOfReading 9y agoBubble sort is perfectly acceptable when you can only swap adjacent elements, which occasionally comes up in memory management.
- iainmerrick 9y agoThat’s the only time it would ever be acceptable, and I don’t think that comes up very often at all.
- xxs 9y agoHmm, do you have a good example? Even linked lists allow swapping elements at arbitrary positions.
- AlotOfReading 9y agoAt 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.
- MichaelDickens 9y ago
- pducks32 9y agoI 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.
- tinus_hn 9y agoWindows also ships with a large number of compatibility fixes (‘shims’) and even has a tool to create your own.
- ridiculous_fish 9y agoI 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.