No-Merge

It seems people choose ignorance over strength.

Although things are comfortably contained at the moment, they've not completely immobile. The other day - perhaps a week ago now - we happened upon a report in social media that venerable FreeBSD, after more than thirty years, had updated some of their system startup routines.

In particular they'd replaced a bubble sort with a merge sort.

Why that? And why so long for the update? Because things like this get overlooked at times, was the explanation.

Who was responsible for using bubble sort in the first place? That wasn't revealed, but it can be noted that the original head of FreeBSD now works at... Apple.

Whatever. Is a merge sort something to look into? Why not qsort in such case? The information didn't reveal that. So we set about readying for a test of merge sort.

We normally do this by setting a compiler directive in our Xscan, so the app can time a scan. 'Before' and 'after' are of course necessary. We did a 'before' run and came up with about five minutes to scan and list some million plus files.

Fine. Now onto merge scan.

Our system header files are set up to recognise one of three or four sort methods, and to report if no method is specified. The assumption's always been that the same algorithm will work well for all possible application domains.

And, it should be pointed out, it's been a while since we delved into this.

The idea was to make an alternate provisional copy of a core header file, rebuild Xscan, and get the 'after' report for the same scan. This can conceivably take a run or two, as the system can cache data, making subsequent runs faster, so it was necessary to hold onto both the 'before' and 'after' Xscan builds.

We ran into an issue almost immediately, for the default form of merge sort doesn't take all the parameters we're used to using - necessitating consultation of the relevant manpage.

It turns out that merge sort requires lots of memory, specifically nel * width, meaning the size of a record times the number of records. This is clearly unacceptable. What are they doing at FreeBSD?

Further reading reveals the following.

The qsort() and qsort_r() functions are an implementation of C.A.R. Hoare's ``quicksort'' algorithm, a variant of partition-exchange sorting; in particular, see D.E. Knuth's Algorithm Q. Quicksort takes O N lg N average time. This implementation uses median selection to avoid its O N**2 worst-case behavior.

Anything with Tony Hoare's name on it gets a seal of approval.

So, end of story? No change to the ACP.

The World Around

Before things get too hot - and they shall shortly - perhaps a few short remarks on what's been happening around. These distractions are just that - and come from stupidity and idiocy and evil.

Anyway. Tucker Carlson had a sit-down with Donald Trump which aired on Twitter last night, to intentionally collide with Kathryn's non-event on Fox. It got over 100 million views in no time, crushing Fox of course.

And it was an OK chat, some 45 minutes in length, and the Donald was looking fit and fab, well-groomed, etc. Things seemed to veer off into self-promotion a bit, but we're not picky.

What disappointed us was the end where Tucker asks Donald to pinpoint the most important issue in his coming presidency. Many of course expected him to say 'Ukraine' as he's repeatedly said he'll end that war in a day, the very day the election results are finalised, not waiting until the second inauguration.

Instead Donald said it's the border that's #1.

This, to us, is a bad move.

Why? Simply because avoiding a nuclear Armageddon weighs more heavily than wetbacks on the Rio Grande.

This might send the right message to the people in the US, but it doesn't do that for the rest of the world. And as long as the rest of the world - that 90% of humanity who dislike the US - are trying to deal with the crumbling Pax Americana, showing that in such a situation you still ignore what's going on: that's a bad move.

Bernhard of MoA recently advised the White House to get a new PR team. But it's not just the White House.

The Twitter copy of the above interview, after far less than 24 hours, has already 128 million views. By contrast, the far more important chat with Doug Macgregor, a few days ago, has less than one-tenth as many views.

It seems people choose ignorance over strength.