https://dlang.org/blog/2020/05/14/lomutos-comeback/ gives a 404 error. And archive.org ( http://web.archive.org/cdx/search/cdx?url=https://dlang.org/... ) is also getting nothing but 404s, so it's not a problem on my end. I'm not really sure what's wrong with this site, since other commenters seem not to have noticed a problem.
Lomuto's Comeback
71–80 of 104 posts
Re: Lomuto's Comeback
#72Earlier quoted context omitted.
Branches also can't be vectorized, so going branch free can lead to a substantial speedup if you can use vector instructions (you might be doing twice the work, but your vector instruction may let you do it 4-16 times faster).
Indeed, AVX512 instructions can sort 16 int32 or well-behaved float values optimally, with no branches. It is a good final pass to any other algorithm.
You mean sorting within a vector register? Can you provide a link or something? I can't find info on this
Re: Lomuto's Comeback
#73Notice that this is on random longs . Of course branch misprediction and memory bandwidth is going to crush you for a branchy sort... you'll be wrong like half the time, and the comparisons and swapping are trivial! Real world data isn't random, so I'd expect branch predictors to do much better with recognizing patterns. And your sorting isn't going to be as simple as sorting integers according to their values all th…
(Author here.) That is incorrect. The difficult case is and the real benchmark is with unpredictable data. The low-entropy cases will be about as fast with both partitioning schemes. This is only a smart part of the benchmarks I've run because I wanted to drive one point home within a limited space. I've run many tests on various data types and shapes, and Lomuto does better than Hoare on most. (E.g. its improvement…
I'm confused, what exactly is incorrect? I said if we don't have more realistic benchmarks then I wouldn't just assume it's faster. Now you're saying you did in fact do more realistic benchmarks, and you found lower entropy ones to exhibit the same performance (which is not faster). They all seem consistent with each other?
I also said that sorting is often more complicated than just comparing integers by their values, which you didn't really address except to mention doubles, which missed the point I was making (I was trying to say sorting often needs e.g. satellite information).
In any case though, if you've done other benchmarks, it'd be nice if you could post them on GitHub or something. Maybe I'm missing something.
Re: Lomuto's Comeback
#74I'm not sure I've ever sorted an array or list. Rather I put things into sets or maps or built in index---I always wanted to access things later, or have an on-line data structure (which a sorted flat thing is not). This whole field is a waste of time, and anachronism from when the master copy was paper/pre-computer and computers were just doing the analytics.
Putting things in a map or set is almost invariably slower, often much slower, than a smart sort. If performance doesn't matter, then go ahead. Most often sort performance doesn't matter, or anyway most of the time is spent elsewhere. People do use Python or Bash in production, without shame. But some of us work on problems where performance of the sort does matter.
Not really true, putting things in a hash map is pretty fast, and generally faster than a comparison based sort.
Re: Lomuto's Comeback
#75Earlier quoted context omitted.
Putting things in a map or set is almost invariably slower, often much slower, than a smart sort. If performance doesn't matter, then go ahead. Most often sort performance doesn't matter, or anyway most of the time is spent elsewhere. People do use Python or Bash in production, without shame. But some of us work on problems where performance of the sort does matter.
Not really true, putting things in a hash map is pretty fast, and generally faster than a comparison based sort.
A hash map is unsorted so it's not a useful way to sort data
Re: Lomuto's Comeback
#76Earlier quoted context omitted.
My comment wasn't inherently about sorting either. Branch-free in general is faster in the worst cases, i.e. if the branch is difficult to predict. Except most real-world branches are predictable... that's why we have branch predictors. So in general you should expect branch-free to be slower, unless you have reason to assume your branches are actually close to random.
> unless you have reason to assume your branches are actually close to random. I mean, to the degree that you need to sort the data at all, it contains informational entropy. Many "presents as sorted" data structures trade space for time by keeping track of the internal sortedness of chunks of the data, between sortation passes. Heck, any insert-optimized data structure (B+ trees; LevelDB's sorted-string-tables; N-ar…
I'm struggling to follow your comment. I said real-world data have patterns and aren't completely random, so you can in general expect branch predictors to help (unless, obviously, your data is actually known to be random like in the example). You rebutted with "because load balancers evenly spread their key space, you will frequently find that your inputs can be guaranteed random", as if that somehow contradicts the point I was making...? It's also clearly not true that it's "highly likely" your data has "no branch-predictability" just because "you don't already have metadata attached to it asserting it's sorted"... right? That's not only both obviously not the case on its own, but also, why would you even sort data that's already guaranteed to be sorted? I can't make sense of this, so I feel like we must be speaking past each other somehow? But I'm confused how.
Re: Lomuto's Comeback
#77I'm not sure I've ever sorted an array or list. Rather I put things into sets or maps or built in index---I always wanted to access things later, or have an on-line data structure (which a sorted flat thing is not). This whole field is a waste of time, and anachronism from when the master copy was paper/pre-computer and computers were just doing the analytics.
Putting things in a map or set is almost invariably slower, often much slower, than a smart sort. If performance doesn't matter, then go ahead. Most often sort performance doesn't matter, or anyway most of the time is spent elsewhere. People do use Python or Bash in production, without shame. But some of us work on problems where performance of the sort does matter.
Sure, it is slower, but my point is not that I sort by doing `Map.toList . map.fromList` but that I don't immediately turn the map back to a list. The sorting literature is optimizing a thing I don't need to to do.
Re: Lomuto's Comeback
#78I'm not sure I've ever sorted an array or list. Rather I put things into sets or maps or built in index---I always wanted to access things later, or have an on-line data structure (which a sorted flat thing is not). This whole field is a waste of time, and anachronism from when the master copy was paper/pre-computer and computers were just doing the analytics.
Your dismissal of “sorted flat thing” as being necessarily not online is incorrect or unnecessarily strict to your detriment. I wrote this comparing the high-level performance of a “set” (AVL or red-black tree) against just that: Faster lookups, insertions, and in-order traversal than a red-black or AVL tree [0] [0]: https://neosmart.net/blog/2019/sorted-list-vs-binary-search-... (Spoiler: it depends on the nature of…
To be clear I am not against "small sorted flat thing" is an optimization for smaller data structures.
My point is I care about the map or set interface. I don't use temporary sets or quicksort to sort....because I don't sort---I don't want a list/array of things in order, basically ever.
Re: Lomuto's Comeback
#79Earlier quoted context omitted.
Not really true, putting things in a hash map is pretty fast, and generally faster than a comparison based sort.
A hash map is unsorted so it's not a useful way to sort data
Very true. I like rich keys with non-trivial comparison cost. I even better like nested maps which no only are often useful in their own right, but also server to cache the cost of comparison wrt the original map---a domain-specific trie.
Map are just far more the bread and butter of programming than sorting, and not just if you are using the one of the languages satirized by https://elbenshira.com/blog/the-universal-data-structure/
Re: Lomuto's Comeback
#80Earlier quoted context omitted.
Putting things in a map or set is almost invariably slower, often much slower, than a smart sort. If performance doesn't matter, then go ahead. Most often sort performance doesn't matter, or anyway most of the time is spent elsewhere. People do use Python or Bash in production, without shame. But some of us work on problems where performance of the sort does matter.
Sure, it is slower, but my point is not that I sort by doing `Map.toList . map.fromList` but that I don't immediately turn the map back to a list . The sorting literature is optimizing a thing I don't need to to do.
Just because you’re not using it directly doesn’t mean that you’re not benefiting from those optimization in those layers you are depending on.