Hmm, so in the benchmarks I'm trying top-down wins consistently with a margin of a few percent (across tiny-sizes up to much larger than L3)... you wouldn't happen to have your benchmarks lying around for comparison somewhere?

@EamonNerbonne - consolidating comments. Links c++ merge only tsort.zip c# merge only tsortcs.zip c++ merge + insertion tsorti.zip. C++ times: top down 1.63 bottom up 1.56, C++ with insertion sort: top down 1.43, bottom up 1.40. C# times: top down 1.98, bottom up 1.91. I haven't converted insertion sort hybrids yet, but my question was about pure merge sorts, not hybrids with insertion sort. Side note - Visual Studio do+while is significantly slower than just while.

One thing I've noticed in my testing is that larger insertion sort windows tend to help top-down more than bottom up (as you also noted). Also, it's worth mentioning that since you're using power-of-two insertion sort windows and power-of-two array sizes, that means your bottom-up sort is in it's best case: a perfectly balanced merge tree! My defaults were insertion sort windows of 48 elements (since that seemed on average slightly faster), and that disbalanced bottom-up, but less so top-down.

I've got to call it a day; but the current code I'm working with is github.com/progressonderwijs/ProgressOnderwijsUtils/blob/eam‌​on/… - I'll try to extract a minimal benchmark tomorrow.

complete code with benchmark harnass: github.com/EamonNerbonne/SortAlgoBench Timings including stderr of the mean over 30 runs (total time around 5min): BottomUpMergeSort2(arr): 1618~2.1 (ms) BottomUpMergeSort(arr): 1606.5~0.75 (ms) TopDownMergeSort(arr): 1522.8~0.98 (ms) QuickSort(arr): 1210~1.5 (ms) Array.Sort(arr): 1273~1.4 (ms) AltTopDownMergeSort(arr): 1556~2.9 (ms) BottomUpMergeSort2 is essentially the C++ BottomUp with insertion sort you provided, just in C#.

@EamonNerbonne - Since this is C#, are you using Visual Studio on a 64 bit version of Windows? Are you doing a release build for x64, which has 16 registers? Is there a reason for not testing with C++ if you do have Visual Studio?

@EamonNerbonne - optimal insertion sort size - I tested some boundary cases using specific array sizes for the testing, 32 is 3% faster than 96 or 128, 2% faster than 80, ... , so now I'm thinking just choosing 32 or 64 as done in my code is probably good enough.

There's no build-time difference between x64 or x86 in (purely) managed code like this, but yes, the machine is x64 and it'll run using the x64 jit.

(If it were x86, I imagine the 64-bit ints would be painfully slow).

And yes - release mode.

As to why C#: I was writing a few sorts for actual usage, and that means I already have a benchmarking harness and a test-set lying around. Sticking to that is simply convenient, especially since C++ lacks decent package management, so that boring infrastructure stuff is a time-consuming pain (I mean, even in this pretty minimal case, just look at the cruft you needed to run a truly minimal benchmark!)

Also: although C++ is undoubtably faster, it's not a huge difference, and it strikes me as unlikely (though not impossible!) that the cache-friendliness of an algorithm depends on whether it's expressed in C# or C++, especially since the data structures are pretty much the same - there's not much managed cruft floating around inside a simple array.

But I'm all for a more minimalist, less-distoring factors C++ benchmark; I'm just explaining why that's not what I came up with first.

My concern about doing release x64 build is that my usage of all those local variables in my bottom up merge sort is relying on the x64's 16 registers. Otherwise, it's probably better to use fewer variables and let the compiler optimize expressions like i + width or i + width + width.

There's also a general issue with doing benchmarks that involve relatively small loops, these are very location sensitive, as seen in one of my prior questions at code review where total time went from 1.4 seconds to 2.0 seconds due to location of a key loop in otherwise identical code indexed branch overhead versus loop .

Yeah, this kind of stuff can be unpredictable. I don't think sorting it the typical hairy case, but you never know. In any case: x64 :-)

Then there are compiler issues. In my C++ version of merge(), replacing the while()'s with do...while()'s which should be faster instead increased time in one of my benchmarks from 1.4 to 1.6 seconds.

That's just really weird.

Then again, C++ does weird stuff

(and the last time I microoptimized C++ is a few years ago, and back then MSC was really bottom of the barrel at this kind of stuff)

Apparently the compiler was radically rewritten since then, so hopefully it's better now ;-)

But to o(n) style fundamentals

the 32 vs 64 choice is not quite good enough

Either the compiler has an issue with do..while(), or the do..while() ended up with a tight loop on an unfriendly location. If you look at that post I made in code review, I rewrote it in assembly to eliminate compiler issues, it's strictly a location issue, at least with my cpu Intel 3.5ghz 3770k.

Given the actual timings this is going to be hard to convincingly measure, but the abstract argument is as follows:

consider an array of length 96

that's 2^7 (rounding up), so 7 passes without insertion sort

so that means (in the 32vs64 choice algo): 32

so you sort [0,32), [32,64), [64,96)

then merge

so [0,64) - efficiently merged

[64,96) - wasteful copy

and then another merge

You'd probably be better off using a size of 48 and a copy-ing insertion sort

or a size 24 and inplace insertion sort

or, unlikely, simply insertion sort 96

and that's the point where top-down is simpler to implement efficiently

top-down always does maximally balanced merges without any effort

I've confirmed that 32 with more passes is better than >= 80 with fewer passes. 16 with more passes is only slightly slower than 64 with fewer passes.

Yeah, sounds like what I saw too

there's a big difference between no insertion sort and some insertion sort

but it does not appear to make a whole lot of difference exactly how large that window is

Even with all those runs and carefully measuring the stderr

I couldn't (e.g.) make a reasonable choice at all between 40 and 48

let alone a choice that isn't just statistically measurable but actually matters too

so that's actually good news, since you get to pick your window

So the sweet spot range, at least for my system is a size between 32 and 64. The upper limit is somewhere between 64 and 80. I get more variation in run times, both C++ and C#, probably related to my cpu changing clock speed from 3.5ghz to 3.9ghz.

You can fix the frequency that (I did), and since you have the luxury of C++ you could even choose to use clock ticks instead of elapsed time

Also that "wasteful" copy is faster than a merge, so it's not that bad.

eah

not very bad

but we're talking small differences here anyhow

clock ticks as in rdtsc?

no, as in cpu clock ticks

ehh

lemme go see...

rdtsc is cpu clock ticks. And there's still that issue of location of a tight loop changing overall time between 1.4 and 2.0 seconds (maybe an issue with my cpu?).

Yeah, I do mean that

but I could have sworn there was some win32 api that returned that result without cpu-core switching risks

oh well

too long ago

randomascii.wordpress.com/2011/07/29/…

suggests rdtsc isn't reliable even on a single core?

oh well; let's not get sidetracked to much by microbenchmarking annoyances.

The main point of my original post is that most libraries use some variation of bottom up merge sort if using a merge sort. If you look at <algorithms> for std::stable_sort() for Visual Studio, it allocates an working array (or vector) 1/2 the size of the original array, does one level of recursion to then call a bottom up merge sort that does use insertion sort with a fixed size of 32.

And I wonder why they do that too

The final step ends up with the first half of data in the working array, and the second half of data in the second half of the original array, then it merges back into the original array (overwrite won't be an issue).

But performance does not appear to be a huge factor, if indeed it's a factor at all

Yeah, there's a common trick to reduce the scratch space size

I was too lazy for that ;-)

look at the copyright at the bottom, it's based on code from the 1990's, perhaps memory size was more of an issue back then.

Maybe

wow

that's kind of impressive if it's really that old and even stuff like that insertion-upto-32 hasn't changed notably since then

I would have guessed that the newer cpus prefer larger insertion sorts, but I guess not

(or maybe the greater out-of-order execution window just adds an element or two of leeway, and so it's too small an effect to matter)

Looks like 64 is as fast as 32. I have an alternative where the caller supplies both original and working arrays, and the sort returns a pointer to which array ended up with the sorted data to avoid a final copy pass.

Getting back to my original question, early merge sorts were external sorts and variations of bottom up merge sort, the most bizarre being polyphase merge sort (better than standard merge sort for 3 to 7 tape drives), but the internal merge sorts also tended to be bottom up. Although old text books include top down merge sort, I don't recall any library that uses top down merge sort, so I've always wondered why most merge sort discussions are about top down.

There's also en.wikipedia.org/wiki/Block_sort

A long time ago caching was less important

but prefetching (IIRC? I'm not sure)... was even less important

and bottom-up is more prefetcher friendly, and less cache-friendly

not that it's going to matter hugely.

Well there is one exception, std::list::sort was a bottom up merge sort for linked lists that used a small array of lists. In VS2015, support for no default constructors was added and some guy at Microsoft switched it to a significantly slower top down merge sort that only used iterators.

The author of the change stated that performance wasn't an issue for linked list sorts, since it would be faster to move the list to an array, sort the array, and create a new linked list.

well, I guess that's fair enough. Albeit weird.

So I'm still left wondering why we're seeing different results in C# vs. C++

I can't explain it

and sure, it's a really trivially small difference

but still werid

The bottom up could have been fixed in the small array of list declarations with an allocator defined in the initializer declaration for each of the 25 lists.

I mean I literally copy-pasted your bottom-up merge and replaced size_t with int, fixed the obvious syntax errors, used my preexisting merge method (they all share that anyhow)... and that's it.

and it's almost exactly as fast as my previous variant, and slower than the top down

Then someone at stack overflow defended the change by noting it was exception safe, if a compare through an exception, the list would be misarranged, but you wouldn't have to go through the small array to append back to the list.

but that top-down variant- I tried at least 4 different ways of implementing that, and it's again not hugely important how you do it - that's basically your AtoA and AtoB version

o_O

The AtoA and AtoB avoid having to pass a parameter for the level of recursion.

I did both

one with passing a parameter with level of recursion

one without

or having to do an initial copy pass, and then simply swapping array references in the recursive calls

makes almost no difference, but the one without (your AtoA+AtoB) seems slightly faster

the initial copy pass did appear to matter, that's consistently slower

but not much

The initial copy pass just makes the code simpler.

it would have surprised me too if it were faster, but it's not entirely inconceivable

copies can be very fast, and they prime the cache, and if the remaining simpler code is then somehow cpu friendlier, well... it might possibly be better

or so I thought

but it's clearly not.

That AtoA and AtoB being slower could be a location issue. My cpu seems very sensitive to jump or call to an address that is on an odd 16 byte boundary versus a 32 byte boundary. It could be coincidence with some other key piece of code conflicting with a code cache line.

You could try another compiler

This was done with assembly and forced code location. Look at my prior post I linked to above.

For C++, I could rearrange the order, or add in some public dummy function to occupy space and change locations of functions.

There's also a general issue with doing benchmarks that involve relatively small loops, these are very location sensitive, as seen in one of my prior questions at code review where total time went from 1.4 seconds to 2.0 seconds due to location of otherwise identical code indexed branch overhead versus loop .

copy of that link

I'll check it out

I need to take off for now. I'll try using C# to see if I get the same results as you. What version of Visual Studio are you using and what version of Windows?

windows 10 version whatever-is-current, visual studio same (15.5.7)

I have VS2015 on both Win 7 and Win 10.

I've been using Win 7, will redo with Win 10.

No VS2017?

You think it matters?

I doubt it

But for the .net version, the runtime may

VS2017 doesn't have express version, at least not yet.

It's got the "community edition

I'm not a fan of "community" versions.

If you're working for a company that may technically not be legal, but it's a free private download

I'm assuming you're doing this for fun, so it should be OK ;-)

Due to licensing?

Microsoft still has ISO downloads going back to VS2008 express, but the url's are hard to find.

I'd have to take a look at it again for what it was that bothered me about the "community" version.

If you have to run, then be sure to do so, but what's your issue with community?

ah ok

in any case, it's free even for commercial use if you have less that 250 pcs

a million in revenue

and even then its free for research (which this is)

or open source (which this probably is too)

Good night!

(or whatever timezone you're in ;-) )

That wasn't the issue. Perhaps something to do with having internet enabled and also logged in? Or maybe it was I couldn't select which components I wanted and instead it only comes as a bundle?

California, 12:33 pm here.

21:33 here in the netherlands

It's hard to get a full installer

ok, take care, I'll update this this chat with my results later.

that's for sure

but the web installer is pretty good now.

(you can use the web installer to make a full installer if you're really, really desperate, IIRC)

Side note - I may one of the few people in the world that has Win 7 and Win 10 on drives that are not re-lettered to "C:"

I have to start with XP X64 and install Win 7 from XP X64 where I can specify partition by drive letter and Win 7 will retain the letter and not change it.

For Win 10, I do yet another Win 7 from XP X64 install (I have a second purchased copy of Win 7), to yet another partition by letter, and then do a Win 10 upgrade on the second Win 7. Since that second Win 7 has an unused activation key, Win 10 will use it instead.

There's a simpler way to do this, as some at Microsoft support have similar setups, but they're unwilling to explain how to install Win 10 to a partition by letter without having Win 10 change it's partition letter to C:

ok, that's it for me for now. I'll update this chat later with my results.

I converted my C++ test code to C#. With C#, changing the even pass initial run size from 64 to 16 showed a slight improvement. Similar to your results with insertion sort added, top down is about 1% faster than bottom up. With C++, it's the other way, with bottom up about 1.75% faster than top down.

Since switching insertion sort size from 64 to 16 improved bottom up time, the insertion sort is taking relatively more time with C# than with C++.