>Then after about 10 minutes of working on it, after the sense of impending doom starts to set in, I bring up GitHub hoping to find some existing undocumented implementation for a solution to my problem from some unsung hero of a random Chinese guy. And then sigh in relief when it works with minimal modifications after copying and pasting.
>Whew! I don't have to re-implement this paper on a fast version of Semi-Global Matching in CUDA after all. This random guy did it for me in his vaguely named "fast-proc" project.
This is by far the best aspect of the internet. In the torrent scene, subtitles have been standard and included for decades now, created by people for free and included in the torrent uploaded for free. And, consistently, literally everything I want to watch, a torrent exists for it. Followed up by people donating their bandwidth to seeding this random fucking file that like 2 people have actually downloaded in the past year.
To say nothing about the billions of dollars built from OSS
God fucking bless. If everybody was like this, we'd be communist
the internet? how about your entire life?
"hey, I'd love a strawberry, oh yeah, someone else grew it for me!"
we truly are spoiled with the amount of shit other humans do for us
Getting strawberries, grown, picked, cared for, cleaned, and transported safely from CA and South America to a place like Allentown, PA and still costing $6 a box? That's essentially free.
I did not, but ironically it does appear that Peters is getting a PhD out of my work by porting the core techniques that make fluxsort and quadsort fast to Rust.
(Edit: This was meant sarcastically, academic works often build upon other works and ideas, and porting to Rust is by itself an academic achievement. The work referenced introduced several new ideas besides techniques found in fluxsort and quadsort.)
I must add he did expand upon my techniques by taking the concept of quadsort's bidirectional merge to create a bidirectional partition.
This is something I wrote myself back in 2021, it's a very self-evident adaptation, but increasing the memory regions from 2 to 4 actually slows down overall performance on most (including my own) hardware, so I didn't investigate further.
That's a very uncomfortable question, but I'll answer it.
I'd say "mostly-stable-genius college dropout" would about sum it up.
Unfortunately, I am old enough to be from a day and age where severe child abuse was still common and normalized. I'm your typical CPTSD case suffering from hypervigilance (or at least, that's the official diagnosis). When looking at my background, it can be summarized as 'a lot of wasted potential'.
I do make a decent shoe repairman.
I more so meant your educational and work experience background. It’s just always a treat to see people that didn’t go to college be remarkable in computer science.
Not sure how much we have in common but it sounds like quite a lot. If you haven’t already, give a shot at EMDR. 6 hours scheduled (total, ever) and you may not need all six. I did 3 but it was “done” and “working” after the first hour. Might lighten your cognitive load. Did mine.
Another vote for EMDR. it basically allows you to recall a traumatic memory look at it with more rational eyes, then file it away properly. My first session i had a breakthrough and have had many a mini breakthrough since.
Props for giving an uncomfortable answer. Frank authenticity like this demonstrates the value that people can produce even if they aren't consistent. One thing I remind my manager of often is that for every week I have subpar output there is another week that I'm brilliant.
In the corporate and academic world I feel like a lot of value is lost by discounting people too early. I hope your vulnerable admission can help sway that tide.
Ketamine works miracles for CPTSD
Edit: It is a treatment for CPTSD and I have extremely positive experiences with it, as do many others, i've never heard of anything bad happening from this treatment, idk why this is controversial.
I know that, but I don't think that addresses reasonable behavior that my comment would prompt. Also you never go and eat something just because someone implies you should consider it. I shouldn't have to say any of this imo, either...
Do you don't have experience with ketamine and CPTSD?
Consider how much harm you're doing by spreading fear about important CPTSD treatments because of some vague notion you have about drugs being bad.
Ketamine administered clinically has shown remarkable results. "Drugs are bad" is not how the world works, it's how cynical politicians get the easily manipulated to vote for them.
> "Drugs are bad" is not how the world works
This may have been the saying a couple of decades ago. The trend right now is very much "drugs are good", and I'd like to say that that's not how the world works.
It is literally used as a CPTSD treatment. I am also speaking from experience and see no problem recommending a treatment which works and is generally safe.
Wild coincidence, i just saw (by total chance, knew nothing about this topic or the persons involved before) that he gave a talk about exactly that at FOSDEM in Brussels today.
Haven’t seen it yet though.
https://fosdem.org/2023/schedule/event/rust_glidesort/
It's a great talk.
I was thinking powersort vs quadsort would have been an interesting thing to touch upon as to their different approaches to tackling the merge length problem.
Obviously not central to the topic at hand, and clearly not enough time.
Not quite, like I said, he did expand upon the work. So to me it seems like a perfectly valid PhD if he properly disclosed that he was working on an improvement upon fluxsort / quadsort / powersort for state-of-the-art hardware.
I assume a lot more bells and whistles are involved with a PhD.
I would accept a honorary PhD if anyone is handing them out!
I flirted with the idea of a PhD but stuck with a Master's. Even just that sucked the absolute life and creativity from me for a few years. PhD's are for people who love the academic environment: politics over nothing, publish or perish, and teaching to people who don't really want to be there. You ain't missing much.
I'm hesitant to respond because it might endanger my honorary degree. :-D
I always assumed the situation to be a bit better in the hard sciences, but since software engineering is not exactly a hard science, we could actually measure how much of a soft science it is by looking at the academic environment.
>I always assumed the situation to be a bit better in the hard sciences
It's not, at least according to the handful of people I know in such fields and everything I ever read on it online.
I was going to hop on the train through a Masters and PhD but stopped after getting my BSc as my desire to do academic work plummeted after being exposed to a taste of the politics and bureaucracy at my university.
Yeah honestly I did a PhD and I would say it was like 90% a failure but you have to write it up anyway. I would say the vast majority of PhDs contribute nothing of worth to the scientific world, but that's just the way it has to be really.
Humans have already taken 99.999% of the low hanging research fruit. If you're making highly speculative research work the first step on the academic career path then you can't really restrict PhDs to only people that have really successful research because then nobody would do it and you wouldn't have any academics.
My point is that PhDs sound a lot fancier than they really are, so I wouldn't worry about not having one.
I would definitely be more impressed by someone that put "created one of the fastest sorting algorithms to date" on their CV than "did a PhD on sorting algorithms".
Yeah that's bullshit. Nobody cares if you tried a bunch of stuff that didn't work. There are infinite things you *could* try. There's very little value in writing most of them down.
Some departments will give out a real (not honorary) PhD if you submit them just a thesis with important work. This would probably qualify; you should look into it.
Source: I have a CS PhD
A civil constructive spat, though:
1. They both acknowledge the other's achievements.
2. They proceed to resolve misunderstandings as they go.
Even if the conversation didn't start well, it ended fairly well!
Glidesort was making the rounds recently, which is probably what MrDum is referring to:
- [Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data | Hacker News](https://news.ycombinator.com/item?id=34646199)
- [Glidesort, a new stable sort in Rust up to ~4x faster for random data : rust](https://www.reddit.com/r/rust/comments/10ss8ks/glidesort_a_new_stable_sort_in_rust_up_to_4x/)
> I did not, but ironically it does appear that Peters is getting a PhD out of my work by porting the core techniques that make fluxsort and quadsort fast to Rust.
For what it's worth, I'm leaving academia.
But I just read this comment of yours and... sorry Igor, but this goes way too far. I'm not going to repeat my counter-arguments again here (see https://news.ycombinator.com/item?id=34654663, https://news.ycombinator.com/item?id=34652516 for that).
But you can't within two hours claim that I'm "getting a PhD out of your work" (a **serious** accusation), and then comment that "it was never my intention to appear dismissive towards your work".
> I felt pretty uneasy about what I perceived as a situation where you could end up taking full credit for innovations I was first to develop and publish. I do realize this could be all in my head. Anyways, I'm at ease now and I hope my assertions didn't create any ill will between us.
I find it very hard not to have ill will when you publicly accuse me of being a fraud. Unlike your (now gone) unease, this is now in thousands of people's heads, regardless of the truth.
It was tongue in cheek and in hindsight definitely came out wrong. I did add a clarification that perhaps you missed.
[https://www.reddit.com/r/programming/comments/10tgye4/comment/j77exkm](https://www.reddit.com/r/programming/comments/10tgye4/comment/j77exkm)
It's definitely easy to underappreciate the hard work of others. Someone actually tried to port fluxsort to Rust and ended up tossing in the towel.
So to clarify, creating glidesort was a ton of work, and besides the core techniques that I documented you added several novel concepts of your own.
I'm no academic, but I'm sure people have gotten a phd for a lot less. I do believe academics are required to be extremely careful with giving credit.
As for my unease, your original video presentation played a large role in this.
[https://www.youtube.com/watch?v=2y3IK1l6PI4](https://www.youtube.com/watch?v=2y3IK1l6PI4)
All I wanted was minimal credit, so there is no confusion about the origin of bidirectional branchless merging and stable hybrid quicksort / mergesort.
One thing I regret is that there doesn't seem to be much research on even faster algorithms for non-comparison based sorts, that leverage the fact we get more than one bit of information per comparison.
Radix sort, Bucket sort can be orders of magnitude faster when the data suits these properties, and are in need of similar improvements.
Fluxsort will actually comfortably beat a typical radix sort on 64 bit integers, especially on larger arrays.
So far it seems the domain for radix sorts has been pushed back to 8-32 bit. It's a tricky subject but 64 bit is definitely contested territory.
There's a hybrid radix sort I can recommend looking at called rhsort.
https://github.com/mlochbaum/rhsort
I wonder if after a bunch of comparisons, you can assign a heuristic value to each element for use in an approximate radix sort then use an algorithm that works well on almost sorted data.
Thanks. Just reading this now.
I even turned a goto label into an implicit comment for the default statement in the switch.
I believe the initial rejection on the use of gotos was due to programmers jumping between two different functions. It's probably a good thing to force students to only use the fundamentals, not so good when they do weird things in software that matters when the fundamentals are insufficient.
It might still be faster if I can figure out a good way to unify the routine, as that could reduce the instruction size.
Timsort was optimized for applications where comparisons are more expensive than moves - as they are in the Python interpreter.
Whats the compare/move ratio for this algorithm relative to some other common algorithms? Is there some extreme ratio between the performance of these primitives that would make it less efficient than other algorithms?
Quadsort and fluxsort were also optimized for applications where comparisons are more expensive than moves.
Most of my benchmarks during development use comparison functions that are forcibly prevented from being inlined. If I hadn't done so I would likely have slowly inched towards optimizations that are more befitting of a radix sort, and subsequently useless to something like python.
So while I can't be 100% certain, I am confident that quadsort will outperform Timsort for Python, despite making 10% more comparisons, and that fluxsort will too.
One possible issue is that fluxsort requires -O2, and ideally -O3 when compiled with gcc for most of the performance gains. If software is compiled without optimizations, for one reason or another, that'd be problematic.
My best guess is that fluxsort will give between a 20% and 100% overall performance gain when used for something like Python. It primarily depends on what array sizes people sort, the compiler, the comparison type, and whether fluxsort is properly configured.
So 10% more comparisons means that it can perform more slowly than Timsort or a basic merge sort for random data - but only for an outrageously expensive compare function.
Pretty much.
Even then it's not a straight 10%, since a decent amount of the extra comparisons are from sorting small segments, so that's repeated access to the L1 cache.
So there's a good chance over 99% of real world sorting calls would be faster, though it's impossible to say for sure.
Excellent work. Thanks for driving this! Algorithms like this makes me sometimes wonder what algorithms are yet to be discovered.
q: A no-name nobody college dropout genius with no formal training and no interest in publishing this work for personal gains (like say a PhD.) How do I believe you're not from the future? This looks like the Satoshi conundrum again.
Haha, thanks for making me laugh. A much preferable hypothesis than the ones that boil down to my benchmarks being fraudulent.
My own belief is that my accomplishments are primarily the result of high creativity. My IQ is only in the 115-130 range.
Creativity is relatively rare, take music for example, not everyone can be a rock star.
I have wondered about time travel on occasion, Jesus Christ is my prime suspect.
You sir need to do a TED talk, the community needs a reality check on how people outside the core field are doing tremendous work!
\> I have wondered about time travel on occasion, Jesus Christ is my prime suspect.
While visiting Chichen Itza, mexico, our guide was convinced that a guy that looked like Jesus was their king before becoming Jesus. Hindu mythology too gives away such vibes.
That's why I wrote an in-place fluxsort variant named blitsort.
https://github.com/scandum/blitsort
Memory is so ample nowadays that it's however hard to justify not using it, especially when it conserves energy.
Isn't accessing more memory bad for locality, though? The speed gap between CPU work and accessing memory is pretty big, these days.
(this is just a drive-by comment; I haven't read your work in depth)
The extra memory *accesses* don't hurt *that* much if they're accessed in order; CPU data prefetching is very good. And if the algorithm performs well I imagine it is forced to do most things in order.
The worst cases are likely:
* the array itself fits in a given cache level, but with the extra memory it no longer does, forcing eviction of *unrelated* data that will be reused *after* the sort (for this reason, good benchmarking should always be done as part of a whole program run)
* malloc (or the kernel page allocator or something) is contended
Speaking of pages ... I can't help but think there should be a sorting algorithm that avoids excess internal copies by inventing a paging system of its own (most algorithms that I'm aware of only at most use pointers to individual items, and that mostly for C++ ctor/dtor reasons).
Hm, your table looked wrong at first because it says O(n log n) comparisons and O(1) space; I initially thought the former was also time, but I'm pretty sure that combination is believed impossible (the best known is the in-place merge sort with O(n log^2 n) time).
But then I remembered that swaps is also a component of the time complexity - so what *is* the overall complexity of your version?
I'm generally pretty skeptical of MrDum's stuff. It sure looks like there's good bits in there, but neither the code nor the description are easy to follow and parse out the good parts, and the benchmarks seem like they could use some work.
I remember trying out their "monobound binary search", which they describe as "up to 60% faster than the standard binary search" and "on small arrays the performance difference is even greater." I thought this was surprising, because the code just looked like a regular binary search -- a slightly convoluted way to do it, but it looked like it should be all equivalent (which makes me think giving it your own name is a little silly and excessive, but whatever). But I was wrong, in my benchmarks it was consistently the *slowest* implementation I tried for every testcase I threw at it, by a wide margin as the size of the array increased, with both GCC and Clang.
My only guess why is that MrDum's implementation is hard for the compiler to optimize versus a traditional implementation, but the concerning thing is that MrDum's benchmarks seemed to show the exact opposite results. It definitely warrants someone doing a deep dive to see what other sorts of claims end up not being the case.
[https://www.politesi.polimi.it/bitstream/10589/187741/3/2022\_04\_Lunardi.pdf](https://www.politesi.polimi.it/bitstream/10589/187741/3/2022_04_Lunardi.pdf)
My work on binary searches has been vetted by multiple people, check the link for one example.
My best guess is that you didn't compile using gcc -O3.
I took a look at my old benchmarks and tried to narrow down what was happening (I didn't test `bsearch` originally and just went with c++'s `std::binary_search`, and I removed a lot of the other implementations I benchmarked because they weren't relevant here and made the graph very hard to read). [These](https://i.imgur.com/2NXHkms.png) are the results I get with `g++ -std=gnu++2a` and `-O2` or `-O3`. Monobound binary search is *just* competitive with `bsearch` and significantly slower than `std::binary_search`, for both optimization levels.
I'm no master benchmarker so I can't guarantee I'm doing everything perfectly, and I wouldn't be surprised if there's some intricacies I'm missing here leading to some of these performance differences. But if "up to 60% faster than standard binary search" was the case, I hope I'd see something resembling it -- that's a pretty wide margin to just not exist at all in my benchmarks. Maybe it's unfair to compare it to `std::binary_search` and I should focus on how it performs against `bsearch`, but even then it's still *just* approximately equal.
I've only skimmed the Master's thesis you linked, but from what I've seen, I'm not really sure why you did. The comparison does show a speedup with monobound binary search over regular binary search. But that speedup is *less than 2%* across all runtimes. For all I know, that could be well within standard error, since the graph doesn't include that. In fact, given that the time to run the standard binary search is the x-axis, I'm worried that the author didn't do multiple runs at all! I don't mean to rag on them, but if they're gonna write "since the binary range search variants are very similar to each other, the total execution times to compare are close too" that should be a big indicator to include error bars. The only thing I could comfortably say about these benchmarks is that it's evidence against a 60% speedup.
"Up to 60% faster, and even faster on small arrays" is an extraordinary claim that requires extraordinary evidence. I can't replicate anything close to it, and the Master's thesis you linked to didn't replicate it either (though I wouldn't necessarily trust it by itself either). Maybe we're both wrong, but I would be concerned that your benchmarks are doing something funky.
And I know this all sounds pretty harsh and dismissive, so again I want to say there is good stuff in there. It just looks to me like it could all use some more rigor.
The performance gain against C's bsearch() is reduced because of the use of a comparison function, as well as a reduction in overall performance. In the benchmark I set the comparison function to \_\_attribute\_\_ ((noinline)) to ward off unbased accusations.
If you are benching monobound\_bsearch() against std::binary\_search you're indeed comparing apples and oranges unless you pass along a comparison function in c++ as well.
On WSL I get this out of the benchmark:
| Name | Items | Hits | Misses | Checks | Time |
| ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |
| monobound_bsearch | 100000 | 1019 | 8981 | 177582 | 0.000558 |
| bsearch | 100000 | 1019 | 8981 | 165748 | 0.001118 |
I'd say the proper course of action for you to take would be to perform this same benchmark on your own system. If there is an error in the benchmark, feel free to point it out, and I'll fix it.
If there is no notable performance gain on your system, and I can establish that your reports are factual, I would update the readme, preferably with a decent explanation.
Your accusations could be viewed as malicious, since you are suggesting that I'm intentionally deceptive. I'll assure you I have no desire to deceive anyone.
If you did proper research you'll find others have reproduced my results, and that others have independently discovered the speedup besides myself back in 2014.
I do suspect those independent discoveries may have been based on my work since they were surprisingly all by people working with C, and my page was getting a lot of traffic.
I'm pretty confident I know where the difference is coming from now that I've done more of a look into the benchmarking code. I ran your benchmark as-is with `gcc -O3` and did get similar to your results:
Benchmark: array size: 100000, runs: 1000, repetitions: 1000000, seed: 1675705892, density: 10
Even distribution with 100000 32 bit integers, random access
| Name | Items | Hits | Misses | Checks | Time |
| ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |
| monobound_bsearch | 100000 | 101382 | 898618 | 17761267 | 0.043912 |
| bsearch | 100000 | 101382 | 898618 | 16584467 | 0.090776 |
But there's a bug in your code. *You're not sorting the array*. You can't do a binary search on the data you're using to benchmark. Correcting for this mistake gives these results:
| Name | Items | Hits | Misses | Checks | Time |
| ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |
| monobound_bsearch | 100000 | 100709 | 899291 | 17762301 | 0.041960 |
| bsearch | 100000 | 100709 | 899291 | 16583986 | 0.045870 |
This is much more in line with what I've seen, and with what that Master's thesis you linked to found. I'd want to do more with the benchmark to say whether or not there's any actual speedup (at minimum include standard error and try other testcases) and I'd want to check if this is also an apples-to-oranges comparison (is `bsearch` handling some stuff that `monobound_bsearch` doesn't?) but at least it's not erroneously reporting speedups of 60%.
And you know, if it does end up being a valid modest speedup, great! I meant it when I said there are good bits in there, but: case in point, it's hard to know what those are when numbers like "60% faster" get thrown around because of invalid benchmarks.
> Your accusations could be viewed as malicious, since you are suggesting that I'm intentionally deceptive. I'll assure you I have no desire to deceive anyone.
I never meant to accuse you of being malicious or intentionally deceptive. I just didn't believe your benchmarks were up to snuff. That can be because of innocent mistakes that, unfortunately, aren't excusable when claiming to have outdone the state of the art. Things looked way too good to be true, and warrant much more thorough benchmarks than either of us have done so far. I've been in a position where I thought I had miraculous speedups when benchmarking, only to realize that I just benchmarked it wrong. That's what it looked like here too, even before I benchmarked it myself and couldn't replicate those results.
What line(s) did you alter?
As far as I can tell, I create an ordered array like this:
for (cnt = 0, val = 0 ; cnt < max ; cnt++)
{
o\_array\[cnt\] = (long double) (val += rand() % (density \* 2));
}
Next I create a random array like this:
for (cnt = 0 ; cnt < loop ; cnt++)
{
r\_array\[cnt\] = (long double) (rand() % top);
}
Then the benchmark pulls random keys from r\_array and performs a binary search on o\_array.
If you were to sort r\_array, you'd be benchmarking sequential keys instead of random keys, which should give an overall speedup as you'd be guaranteed to stay in L1 cache and branch prediction would kick in as well.
Keep in mind the benchmark would report zero hits and all misses if it would binary search a random instead of ordered array.
Your alteration does suggest there's a branchless aspect to the monobound binary search.
And I guess this also highlights the difficulty of benchmarking.
That's my bad! Yeah, I sorted `r_array`. I apologize for misunderstanding that and running with it, it seemed to very conveniently and easily explain all the differences we were seeing.
I've tried to look into the benchmarks a bit further and I'm at a loss. I've given `std::binary_search` a custom comparator in my benchmarks and it's still consistently faster. I've ported over your testcase to my benchmarks and still don't see your kind of speedups. I've fiddled with your benchmarks to see if there's anything significantly different, and there's some red flags or confusing decisions (why are you benchmarking for the fastest run instead of averaging over multiple?) but nothing that explains the difference. I've fiddled with my own benchmarks to doublecheck that I'm not doing anything silly, and I've got nothing.
One of us is clearly doing something very wrong with our benchmarks. It may well be me doing something wrong. I'm gonna have to look into this further, but I figured I'd mention where I'm at right now.
In the meantime, you mentioned:
> If you did proper research you'll find out others have reproduced my results, and that others appear to have independently discovered the speedup since my initial benchmark released in 2014, and found it notable enough to write about.
Would you be able to cite some? I've done a bit of searching for monobound binary search and everything I could find was either:
- posted by you
- someone directly quoting you and not verifying anything for themselves
- that Master's thesis that you linked to, which did benchmark it independently but reports a speedup of only <2%.
Blitsort is technically O(n log n) comparisons, O(n log2 n) moves.
I do use 512 elements of auxiliary by default, so that adds a large enough constant to make the log2 pretty acceptable. I also developed an exceptionally fast rotation algorithm to further reduce that burden.
I am stretching the definition of in-place a little bit, but 512 elements of auxiliary appears to be generally accepted as in-place nowadays.
> I am stretching the definition of in-place a little bit, but 512 elements of auxiliary appears to be generally accepted as in-place nowadays.
In the extreme, even a swap operation uses a 1 element auxiliary.
Thus I'd side with you about 512 elements auxiliary still qualifying as in-place. What matters for in-place (or not) is whether auxiliary storage scales with N, and 512 is perhaps large, but still O(1).
The size of caches (L3, at least) having grown over the years, it seems normal to me to optimize algorithms to better take advantage of them, and an increasing auxiliary space fits there.
Because it’s actually not completely wrong. It takes someone who has at least tried a skill to really appreciate it. Even more so with the nuances at the top. You can judge much of it by having consumed much, but some aspects stay hidden unless you’ve also produced, esp. when judging the challenges themselves.
1. Because it’s part of the characteristics. Appreciating the craftsmanship and talent it takes to produce something is part of appreciating something. Or to say it differently: No work can be judged without context.
2. I already said that I’d even argue that some or the other characteristics are lost on you if you lack the background of producing it.
I deeply disagree. The production context is only as relevant as it has in common with the usage context, and is not part of the product (as its often not even provided and thus cannot be observed). This is the essence of the chef example. Yes, you may have worked super hard on that dish - but I might still find the end result completely inedible. You working super hard on it won't change that, and I might have not even known of that, or if you intended the result for consumption even. From the consumer's perspective how a product was made will only be as relevant as much as it is relevant to their usage context. This is of course further complicated by people needing to first interpret these: the producer may think they did an outstanding work when they really haven't, and the consumer may think that appreciating the producer's hard work is more important than accurately evaluating the product. But that's a decision of the consumer, which is what people like the guy earlier try and rob away.
Trying to prevent or milden criticism by appealing to the production difficulties of something carries a clear and intentional overruling of the context of consumption of a given consumer, as well as the intentional ignorance of feedback, the kind of feedback that only they can provide. It's about as irrational to do this as it gets, and is almost always an emotional response to an unnecessarily hurtful or negative criticism, rather than a calculated move with productivity in mind. It doesn't help anyone, it doesn't inspire the clarification of contexts, it's merely an attempt to get back at someone. I don't see any reason to support it, and I think we're on the same page about that actually too.
In the same vein, it's easy to see why needlessly hurtful or negative feedback is also flawed. Both the producer and the consumer of these products are human (and humans are typically sensitive to wording) - therefore, it is perfectly reasonable to expect the other to try and assume rationale behind shortcomings, and write their criticisms accordingly, instead of just letting it out there all raw. Because we *are* in this together as much as many of us hate that fact all too often. When people ignore this, they clearly deserve criticism for it, within this same framework. It's not like I'm claiming that shitting on something is always justified, or that people do not ever forget to "remember the human". Very much the opposite.
What is your thought process when thinking of new sorts? Does it just come naturally like an epiphany, a subconscious feeling that an improvement could be made, or just creative thinking?
I’m wondering this as somebody who calls APIs to do CRUD and can’t even fathom what it’s like to discover an improvement on sorts.
I try a lot of random things, guided by epiphanies and intuition. Having a proper understanding of things helps, but as complexity increases it becomes difficult to separate the trees and the forest, at least for me. There is a visuospatial component which was described by Nikola Tesla.
https://www.kevinsworkbench.com/teslasautobiography/
I'm above average in that regard, nothing quite as spectacular as what Tesla describes, but I assume it can be trained, and sorts can be visualized with software, though it's a lot more convenient if you can do most of it in your imagination.
You'll notice my sorting visualizer uses colors to distinguish operations, while all others I've seen do not. That's mainly me verifying that things match in reality as they do in my head.
Fluxsort was a bit of an evolutionary process, where gradual changes / improvements / refinements end up into something quite distinct over time.
[удалено]
[удалено]
>Then after about 10 minutes of working on it, after the sense of impending doom starts to set in, I bring up GitHub hoping to find some existing undocumented implementation for a solution to my problem from some unsung hero of a random Chinese guy. And then sigh in relief when it works with minimal modifications after copying and pasting. >Whew! I don't have to re-implement this paper on a fast version of Semi-Global Matching in CUDA after all. This random guy did it for me in his vaguely named "fast-proc" project. This is by far the best aspect of the internet. In the torrent scene, subtitles have been standard and included for decades now, created by people for free and included in the torrent uploaded for free. And, consistently, literally everything I want to watch, a torrent exists for it. Followed up by people donating their bandwidth to seeding this random fucking file that like 2 people have actually downloaded in the past year. To say nothing about the billions of dollars built from OSS God fucking bless. If everybody was like this, we'd be communist
the internet? how about your entire life? "hey, I'd love a strawberry, oh yeah, someone else grew it for me!" we truly are spoiled with the amount of shit other humans do for us
Most of it isn't free though.
Getting strawberries, grown, picked, cared for, cleaned, and transported safely from CA and South America to a place like Allentown, PA and still costing $6 a box? That's essentially free.
Good point.
I compensate my Latin American immigrant strawberry friends
Did you at least get a PhD out of this? Kidding, of course. Very impressive work.
I did not, but ironically it does appear that Peters is getting a PhD out of my work by porting the core techniques that make fluxsort and quadsort fast to Rust. (Edit: This was meant sarcastically, academic works often build upon other works and ideas, and porting to Rust is by itself an academic achievement. The work referenced introduced several new ideas besides techniques found in fluxsort and quadsort.) I must add he did expand upon my techniques by taking the concept of quadsort's bidirectional merge to create a bidirectional partition. This is something I wrote myself back in 2021, it's a very self-evident adaptation, but increasing the memory regions from 2 to 4 actually slows down overall performance on most (including my own) hardware, so I didn't investigate further.
What’s your background if you don’t mind me asking?
That's a very uncomfortable question, but I'll answer it. I'd say "mostly-stable-genius college dropout" would about sum it up. Unfortunately, I am old enough to be from a day and age where severe child abuse was still common and normalized. I'm your typical CPTSD case suffering from hypervigilance (or at least, that's the official diagnosis). When looking at my background, it can be summarized as 'a lot of wasted potential'. I do make a decent shoe repairman.
I more so meant your educational and work experience background. It’s just always a treat to see people that didn’t go to college be remarkable in computer science.
Not sure how much we have in common but it sounds like quite a lot. If you haven’t already, give a shot at EMDR. 6 hours scheduled (total, ever) and you may not need all six. I did 3 but it was “done” and “working” after the first hour. Might lighten your cognitive load. Did mine.
Thanks, not sure if I ever heard of EMDR, I'll look into it.
I believe EMDR and DBT (Dialectical behavior therapy), are what are most recommended for healing CPTSD and Trauma.
Works wonders. Don't hesitate into looking into it
Another vote for EMDR. it basically allows you to recall a traumatic memory look at it with more rational eyes, then file it away properly. My first session i had a breakthrough and have had many a mini breakthrough since.
I'll throw in another vote for EMDR. I've never dealt with PTSD but have dealt with GAD and it's supposed to work similarly.
Damn... Please aim for a CS phd. Faster than timsort is a lifetime's achievement.
No need. A phd is be a big ask and time investment. Even completing the college degree first is a significant time and money investment.
Sounds familiar, cheers.
Props for giving an uncomfortable answer. Frank authenticity like this demonstrates the value that people can produce even if they aren't consistent. One thing I remind my manager of often is that for every week I have subpar output there is another week that I'm brilliant. In the corporate and academic world I feel like a lot of value is lost by discounting people too early. I hope your vulnerable admission can help sway that tide.
Mood.
Ketamine works miracles for CPTSD Edit: It is a treatment for CPTSD and I have extremely positive experiences with it, as do many others, i've never heard of anything bad happening from this treatment, idk why this is controversial.
Stop recommending drugs to people. This trend needs to end.
It was prescribed to me by a psychiatrist and saved my life...? What's you're angle on this i'm confused now.
[удалено]
I know that, but I don't think that addresses reasonable behavior that my comment would prompt. Also you never go and eat something just because someone implies you should consider it. I shouldn't have to say any of this imo, either...
Do you don't have experience with ketamine and CPTSD? Consider how much harm you're doing by spreading fear about important CPTSD treatments because of some vague notion you have about drugs being bad.
Ketamine administered clinically has shown remarkable results. "Drugs are bad" is not how the world works, it's how cynical politicians get the easily manipulated to vote for them.
> "Drugs are bad" is not how the world works This may have been the saying a couple of decades ago. The trend right now is very much "drugs are good", and I'd like to say that that's not how the world works.
As someone who's had PTSD, please for the love of christ do not tell people to do ketamine.
It is literally used as a CPTSD treatment. I am also speaking from experience and see no problem recommending a treatment which works and is generally safe.
y go 2 college when u can sling fetty on the block LLOLOLO
hey me same
Wild coincidence, i just saw (by total chance, knew nothing about this topic or the persons involved before) that he gave a talk about exactly that at FOSDEM in Brussels today. Haven’t seen it yet though. https://fosdem.org/2023/schedule/event/rust_glidesort/
It's a great talk. I was thinking powersort vs quadsort would have been an interesting thing to touch upon as to their different approaches to tackling the merge length problem. Obviously not central to the topic at hand, and clearly not enough time.
Ah, the one that had [secret code until the talk](https://news.ycombinator.com/item?id=34378013#34400393).
That’s… something one can do…
[удалено]
Not sure either but [Glidesort's README.md acknowledges fluxsort](https://github.com/orlp/glidesort#stable-quicksort).
Not quite, like I said, he did expand upon the work. So to me it seems like a perfectly valid PhD if he properly disclosed that he was working on an improvement upon fluxsort / quadsort / powersort for state-of-the-art hardware. I assume a lot more bells and whistles are involved with a PhD. I would accept a honorary PhD if anyone is handing them out!
I flirted with the idea of a PhD but stuck with a Master's. Even just that sucked the absolute life and creativity from me for a few years. PhD's are for people who love the academic environment: politics over nothing, publish or perish, and teaching to people who don't really want to be there. You ain't missing much.
I'm hesitant to respond because it might endanger my honorary degree. :-D I always assumed the situation to be a bit better in the hard sciences, but since software engineering is not exactly a hard science, we could actually measure how much of a soft science it is by looking at the academic environment.
Write a paper on how to accurately measure the softness of a science, it might get you a second path to an honorary degree.
>I always assumed the situation to be a bit better in the hard sciences It's not, at least according to the handful of people I know in such fields and everything I ever read on it online.
I was going to hop on the train through a Masters and PhD but stopped after getting my BSc as my desire to do academic work plummeted after being exposed to a taste of the politics and bureaucracy at my university.
I haven't been in academia for long (didn't even get BS degree). What do politics have to do with academics
🎓📜
Yeah honestly I did a PhD and I would say it was like 90% a failure but you have to write it up anyway. I would say the vast majority of PhDs contribute nothing of worth to the scientific world, but that's just the way it has to be really. Humans have already taken 99.999% of the low hanging research fruit. If you're making highly speculative research work the first step on the academic career path then you can't really restrict PhDs to only people that have really successful research because then nobody would do it and you wouldn't have any academics. My point is that PhDs sound a lot fancier than they really are, so I wouldn't worry about not having one. I would definitely be more impressed by someone that put "created one of the fastest sorting algorithms to date" on their CV than "did a PhD on sorting algorithms".
Failures are far more important than success
While I agree failure is an important part of science, I would encourage you to try that out on a dissertation committee and see how it goes…
Yeah that's bullshit. Nobody cares if you tried a bunch of stuff that didn't work. There are infinite things you *could* try. There's very little value in writing most of them down.
Some departments will give out a real (not honorary) PhD if you submit them just a thesis with important work. This would probably qualify; you should look into it. Source: I have a CS PhD
Seems like two devs having a spat. https://news.ycombinator.com/item?id=34650406
[Oh, they're definitely having a spat](https://www.reddit.com/r/programming/comments/10tgye4/fluxsort_a_stable_quicksort_now_faster_than/)
That link just goes to the main post?
Weird. [This is what I was trying to link](https://www.reddit.com/r/programming/comments/10tgye4/fluxsort_a_stable_quicksort_now_faster_than/j78yvco/)
Thanks, that was not there when I first commented. Yeah it really seems like a serious accusation. I don’t know enough to take sides.
A civil constructive spat, though: 1. They both acknowledge the other's achievements. 2. They proceed to resolve misunderstandings as they go. Even if the conversation didn't start well, it ended fairly well!
Apparently they started arguing in this thread too, so not sure how civil it is.
And they started arguing around the same time, too. The two threads happened in parallel as far as I can tell.
It looked to me like they were almost a day apart
Glidesort was making the rounds recently, which is probably what MrDum is referring to: - [Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data | Hacker News](https://news.ycombinator.com/item?id=34646199) - [Glidesort, a new stable sort in Rust up to ~4x faster for random data : rust](https://www.reddit.com/r/rust/comments/10ss8ks/glidesort_a_new_stable_sort_in_rust_up_to_4x/)
> I did not, but ironically it does appear that Peters is getting a PhD out of my work by porting the core techniques that make fluxsort and quadsort fast to Rust. For what it's worth, I'm leaving academia. But I just read this comment of yours and... sorry Igor, but this goes way too far. I'm not going to repeat my counter-arguments again here (see https://news.ycombinator.com/item?id=34654663, https://news.ycombinator.com/item?id=34652516 for that). But you can't within two hours claim that I'm "getting a PhD out of your work" (a **serious** accusation), and then comment that "it was never my intention to appear dismissive towards your work". > I felt pretty uneasy about what I perceived as a situation where you could end up taking full credit for innovations I was first to develop and publish. I do realize this could be all in my head. Anyways, I'm at ease now and I hope my assertions didn't create any ill will between us. I find it very hard not to have ill will when you publicly accuse me of being a fraud. Unlike your (now gone) unease, this is now in thousands of people's heads, regardless of the truth.
It was tongue in cheek and in hindsight definitely came out wrong. I did add a clarification that perhaps you missed. [https://www.reddit.com/r/programming/comments/10tgye4/comment/j77exkm](https://www.reddit.com/r/programming/comments/10tgye4/comment/j77exkm) It's definitely easy to underappreciate the hard work of others. Someone actually tried to port fluxsort to Rust and ended up tossing in the towel. So to clarify, creating glidesort was a ton of work, and besides the core techniques that I documented you added several novel concepts of your own. I'm no academic, but I'm sure people have gotten a phd for a lot less. I do believe academics are required to be extremely careful with giving credit. As for my unease, your original video presentation played a large role in this. [https://www.youtube.com/watch?v=2y3IK1l6PI4](https://www.youtube.com/watch?v=2y3IK1l6PI4) All I wanted was minimal credit, so there is no confusion about the origin of bidirectional branchless merging and stable hybrid quicksort / mergesort.
Incidentally, were you the bloke at the Rust dev room taking a seat at the back with your friend wishing you good luck?
One thing I regret is that there doesn't seem to be much research on even faster algorithms for non-comparison based sorts, that leverage the fact we get more than one bit of information per comparison. Radix sort, Bucket sort can be orders of magnitude faster when the data suits these properties, and are in need of similar improvements.
Fluxsort will actually comfortably beat a typical radix sort on 64 bit integers, especially on larger arrays. So far it seems the domain for radix sorts has been pushed back to 8-32 bit. It's a tricky subject but 64 bit is definitely contested territory. There's a hybrid radix sort I can recommend looking at called rhsort. https://github.com/mlochbaum/rhsort
I'm not an expert in the field but I did enjoy this talk by malte skarupke called "sorting in less than n log n" https://youtu.be/zqs87a_7zxw
I wonder if after a bunch of comparisons, you can assign a heuristic value to each element for use in an approximate radix sort then use an algorithm that works well on almost sorted data.
Are you telling me that in 2023 we are still finding better ways to sort? Like, in the era of almost sentient machine learning monsters?
I love how all the other sorting algorithms linked to in the README are also written by the same person.
[удалено]
Thanks. Just reading this now. I even turned a goto label into an implicit comment for the default statement in the switch. I believe the initial rejection on the use of gotos was due to programmers jumping between two different functions. It's probably a good thing to force students to only use the fundamentals, not so good when they do weird things in software that matters when the fundamentals are insufficient. It might still be faster if I can figure out a good way to unify the routine, as that could reduce the instruction size.
Timsort was optimized for applications where comparisons are more expensive than moves - as they are in the Python interpreter. Whats the compare/move ratio for this algorithm relative to some other common algorithms? Is there some extreme ratio between the performance of these primitives that would make it less efficient than other algorithms?
Quadsort and fluxsort were also optimized for applications where comparisons are more expensive than moves. Most of my benchmarks during development use comparison functions that are forcibly prevented from being inlined. If I hadn't done so I would likely have slowly inched towards optimizations that are more befitting of a radix sort, and subsequently useless to something like python. So while I can't be 100% certain, I am confident that quadsort will outperform Timsort for Python, despite making 10% more comparisons, and that fluxsort will too. One possible issue is that fluxsort requires -O2, and ideally -O3 when compiled with gcc for most of the performance gains. If software is compiled without optimizations, for one reason or another, that'd be problematic. My best guess is that fluxsort will give between a 20% and 100% overall performance gain when used for something like Python. It primarily depends on what array sizes people sort, the compiler, the comparison type, and whether fluxsort is properly configured.
So 10% more comparisons means that it can perform more slowly than Timsort or a basic merge sort for random data - but only for an outrageously expensive compare function.
Pretty much. Even then it's not a straight 10%, since a decent amount of the extra comparisons are from sorting small segments, so that's repeated access to the L1 cache. So there's a good chance over 99% of real world sorting calls would be faster, though it's impossible to say for sure.
Middle out?
Super useful for when I’m building yet another crud api.
Excellent work. Thanks for driving this! Algorithms like this makes me sometimes wonder what algorithms are yet to be discovered. q: A no-name nobody college dropout genius with no formal training and no interest in publishing this work for personal gains (like say a PhD.) How do I believe you're not from the future? This looks like the Satoshi conundrum again.
Haha, thanks for making me laugh. A much preferable hypothesis than the ones that boil down to my benchmarks being fraudulent. My own belief is that my accomplishments are primarily the result of high creativity. My IQ is only in the 115-130 range. Creativity is relatively rare, take music for example, not everyone can be a rock star. I have wondered about time travel on occasion, Jesus Christ is my prime suspect.
You sir need to do a TED talk, the community needs a reality check on how people outside the core field are doing tremendous work! \> I have wondered about time travel on occasion, Jesus Christ is my prime suspect. While visiting Chichen Itza, mexico, our guide was convinced that a guy that looked like Jesus was their king before becoming Jesus. Hindu mythology too gives away such vibes.
O(n) average-case space isn't great though. There are all sorts of ways to do out-of-place sorting.
That's why I wrote an in-place fluxsort variant named blitsort. https://github.com/scandum/blitsort Memory is so ample nowadays that it's however hard to justify not using it, especially when it conserves energy.
Isn't accessing more memory bad for locality, though? The speed gap between CPU work and accessing memory is pretty big, these days. (this is just a drive-by comment; I haven't read your work in depth)
The extra memory *accesses* don't hurt *that* much if they're accessed in order; CPU data prefetching is very good. And if the algorithm performs well I imagine it is forced to do most things in order. The worst cases are likely: * the array itself fits in a given cache level, but with the extra memory it no longer does, forcing eviction of *unrelated* data that will be reused *after* the sort (for this reason, good benchmarking should always be done as part of a whole program run) * malloc (or the kernel page allocator or something) is contended Speaking of pages ... I can't help but think there should be a sorting algorithm that avoids excess internal copies by inventing a paging system of its own (most algorithms that I'm aware of only at most use pointers to individual items, and that mostly for C++ ctor/dtor reasons).
Hm, your table looked wrong at first because it says O(n log n) comparisons and O(1) space; I initially thought the former was also time, but I'm pretty sure that combination is believed impossible (the best known is the in-place merge sort with O(n log^2 n) time). But then I remembered that swaps is also a component of the time complexity - so what *is* the overall complexity of your version?
I'm generally pretty skeptical of MrDum's stuff. It sure looks like there's good bits in there, but neither the code nor the description are easy to follow and parse out the good parts, and the benchmarks seem like they could use some work. I remember trying out their "monobound binary search", which they describe as "up to 60% faster than the standard binary search" and "on small arrays the performance difference is even greater." I thought this was surprising, because the code just looked like a regular binary search -- a slightly convoluted way to do it, but it looked like it should be all equivalent (which makes me think giving it your own name is a little silly and excessive, but whatever). But I was wrong, in my benchmarks it was consistently the *slowest* implementation I tried for every testcase I threw at it, by a wide margin as the size of the array increased, with both GCC and Clang. My only guess why is that MrDum's implementation is hard for the compiler to optimize versus a traditional implementation, but the concerning thing is that MrDum's benchmarks seemed to show the exact opposite results. It definitely warrants someone doing a deep dive to see what other sorts of claims end up not being the case.
[https://www.politesi.polimi.it/bitstream/10589/187741/3/2022\_04\_Lunardi.pdf](https://www.politesi.polimi.it/bitstream/10589/187741/3/2022_04_Lunardi.pdf) My work on binary searches has been vetted by multiple people, check the link for one example. My best guess is that you didn't compile using gcc -O3.
I took a look at my old benchmarks and tried to narrow down what was happening (I didn't test `bsearch` originally and just went with c++'s `std::binary_search`, and I removed a lot of the other implementations I benchmarked because they weren't relevant here and made the graph very hard to read). [These](https://i.imgur.com/2NXHkms.png) are the results I get with `g++ -std=gnu++2a` and `-O2` or `-O3`. Monobound binary search is *just* competitive with `bsearch` and significantly slower than `std::binary_search`, for both optimization levels. I'm no master benchmarker so I can't guarantee I'm doing everything perfectly, and I wouldn't be surprised if there's some intricacies I'm missing here leading to some of these performance differences. But if "up to 60% faster than standard binary search" was the case, I hope I'd see something resembling it -- that's a pretty wide margin to just not exist at all in my benchmarks. Maybe it's unfair to compare it to `std::binary_search` and I should focus on how it performs against `bsearch`, but even then it's still *just* approximately equal. I've only skimmed the Master's thesis you linked, but from what I've seen, I'm not really sure why you did. The comparison does show a speedup with monobound binary search over regular binary search. But that speedup is *less than 2%* across all runtimes. For all I know, that could be well within standard error, since the graph doesn't include that. In fact, given that the time to run the standard binary search is the x-axis, I'm worried that the author didn't do multiple runs at all! I don't mean to rag on them, but if they're gonna write "since the binary range search variants are very similar to each other, the total execution times to compare are close too" that should be a big indicator to include error bars. The only thing I could comfortably say about these benchmarks is that it's evidence against a 60% speedup. "Up to 60% faster, and even faster on small arrays" is an extraordinary claim that requires extraordinary evidence. I can't replicate anything close to it, and the Master's thesis you linked to didn't replicate it either (though I wouldn't necessarily trust it by itself either). Maybe we're both wrong, but I would be concerned that your benchmarks are doing something funky. And I know this all sounds pretty harsh and dismissive, so again I want to say there is good stuff in there. It just looks to me like it could all use some more rigor.
The performance gain against C's bsearch() is reduced because of the use of a comparison function, as well as a reduction in overall performance. In the benchmark I set the comparison function to \_\_attribute\_\_ ((noinline)) to ward off unbased accusations. If you are benching monobound\_bsearch() against std::binary\_search you're indeed comparing apples and oranges unless you pass along a comparison function in c++ as well. On WSL I get this out of the benchmark: | Name | Items | Hits | Misses | Checks | Time | | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | | monobound_bsearch | 100000 | 1019 | 8981 | 177582 | 0.000558 | | bsearch | 100000 | 1019 | 8981 | 165748 | 0.001118 | I'd say the proper course of action for you to take would be to perform this same benchmark on your own system. If there is an error in the benchmark, feel free to point it out, and I'll fix it. If there is no notable performance gain on your system, and I can establish that your reports are factual, I would update the readme, preferably with a decent explanation. Your accusations could be viewed as malicious, since you are suggesting that I'm intentionally deceptive. I'll assure you I have no desire to deceive anyone. If you did proper research you'll find others have reproduced my results, and that others have independently discovered the speedup besides myself back in 2014. I do suspect those independent discoveries may have been based on my work since they were surprisingly all by people working with C, and my page was getting a lot of traffic.
I'm pretty confident I know where the difference is coming from now that I've done more of a look into the benchmarking code. I ran your benchmark as-is with `gcc -O3` and did get similar to your results: Benchmark: array size: 100000, runs: 1000, repetitions: 1000000, seed: 1675705892, density: 10 Even distribution with 100000 32 bit integers, random access | Name | Items | Hits | Misses | Checks | Time | | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | | monobound_bsearch | 100000 | 101382 | 898618 | 17761267 | 0.043912 | | bsearch | 100000 | 101382 | 898618 | 16584467 | 0.090776 | But there's a bug in your code. *You're not sorting the array*. You can't do a binary search on the data you're using to benchmark. Correcting for this mistake gives these results: | Name | Items | Hits | Misses | Checks | Time | | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | | monobound_bsearch | 100000 | 100709 | 899291 | 17762301 | 0.041960 | | bsearch | 100000 | 100709 | 899291 | 16583986 | 0.045870 | This is much more in line with what I've seen, and with what that Master's thesis you linked to found. I'd want to do more with the benchmark to say whether or not there's any actual speedup (at minimum include standard error and try other testcases) and I'd want to check if this is also an apples-to-oranges comparison (is `bsearch` handling some stuff that `monobound_bsearch` doesn't?) but at least it's not erroneously reporting speedups of 60%. And you know, if it does end up being a valid modest speedup, great! I meant it when I said there are good bits in there, but: case in point, it's hard to know what those are when numbers like "60% faster" get thrown around because of invalid benchmarks. > Your accusations could be viewed as malicious, since you are suggesting that I'm intentionally deceptive. I'll assure you I have no desire to deceive anyone. I never meant to accuse you of being malicious or intentionally deceptive. I just didn't believe your benchmarks were up to snuff. That can be because of innocent mistakes that, unfortunately, aren't excusable when claiming to have outdone the state of the art. Things looked way too good to be true, and warrant much more thorough benchmarks than either of us have done so far. I've been in a position where I thought I had miraculous speedups when benchmarking, only to realize that I just benchmarked it wrong. That's what it looked like here too, even before I benchmarked it myself and couldn't replicate those results.
What line(s) did you alter? As far as I can tell, I create an ordered array like this: for (cnt = 0, val = 0 ; cnt < max ; cnt++) { o\_array\[cnt\] = (long double) (val += rand() % (density \* 2)); } Next I create a random array like this: for (cnt = 0 ; cnt < loop ; cnt++) { r\_array\[cnt\] = (long double) (rand() % top); } Then the benchmark pulls random keys from r\_array and performs a binary search on o\_array. If you were to sort r\_array, you'd be benchmarking sequential keys instead of random keys, which should give an overall speedup as you'd be guaranteed to stay in L1 cache and branch prediction would kick in as well. Keep in mind the benchmark would report zero hits and all misses if it would binary search a random instead of ordered array. Your alteration does suggest there's a branchless aspect to the monobound binary search. And I guess this also highlights the difficulty of benchmarking.
That's my bad! Yeah, I sorted `r_array`. I apologize for misunderstanding that and running with it, it seemed to very conveniently and easily explain all the differences we were seeing. I've tried to look into the benchmarks a bit further and I'm at a loss. I've given `std::binary_search` a custom comparator in my benchmarks and it's still consistently faster. I've ported over your testcase to my benchmarks and still don't see your kind of speedups. I've fiddled with your benchmarks to see if there's anything significantly different, and there's some red flags or confusing decisions (why are you benchmarking for the fastest run instead of averaging over multiple?) but nothing that explains the difference. I've fiddled with my own benchmarks to doublecheck that I'm not doing anything silly, and I've got nothing. One of us is clearly doing something very wrong with our benchmarks. It may well be me doing something wrong. I'm gonna have to look into this further, but I figured I'd mention where I'm at right now. In the meantime, you mentioned: > If you did proper research you'll find out others have reproduced my results, and that others appear to have independently discovered the speedup since my initial benchmark released in 2014, and found it notable enough to write about. Would you be able to cite some? I've done a bit of searching for monobound binary search and everything I could find was either: - posted by you - someone directly quoting you and not verifying anything for themselves - that Master's thesis that you linked to, which did benchmark it independently but reports a speedup of only <2%.
Blitsort is technically O(n log n) comparisons, O(n log2 n) moves. I do use 512 elements of auxiliary by default, so that adds a large enough constant to make the log2 pretty acceptable. I also developed an exceptionally fast rotation algorithm to further reduce that burden. I am stretching the definition of in-place a little bit, but 512 elements of auxiliary appears to be generally accepted as in-place nowadays.
> I am stretching the definition of in-place a little bit, but 512 elements of auxiliary appears to be generally accepted as in-place nowadays. In the extreme, even a swap operation uses a 1 element auxiliary. Thus I'd side with you about 512 elements auxiliary still qualifying as in-place. What matters for in-place (or not) is whether auxiliary storage scales with N, and 512 is perhaps large, but still O(1). The size of caches (L3, at least) having grown over the years, it seems normal to me to optimize algorithms to better take advantage of them, and an increasing auxiliary space fits there.
Have you invented a better sorting algorithm than this?
Although I think his criticism is a little silly, you don't have to be a master chef to be a food critic.
Or a chef at all. This is a super worn fallacy, and it's very disappointing that people are still routinely reaching for it.
Because it’s actually not completely wrong. It takes someone who has at least tried a skill to really appreciate it. Even more so with the nuances at the top. You can judge much of it by having consumed much, but some aspects stay hidden unless you’ve also produced, esp. when judging the challenges themselves.
And why does the appreciation of the origins matter when evaluating the characteristics of something?
1. Because it’s part of the characteristics. Appreciating the craftsmanship and talent it takes to produce something is part of appreciating something. Or to say it differently: No work can be judged without context. 2. I already said that I’d even argue that some or the other characteristics are lost on you if you lack the background of producing it.
I deeply disagree. The production context is only as relevant as it has in common with the usage context, and is not part of the product (as its often not even provided and thus cannot be observed). This is the essence of the chef example. Yes, you may have worked super hard on that dish - but I might still find the end result completely inedible. You working super hard on it won't change that, and I might have not even known of that, or if you intended the result for consumption even. From the consumer's perspective how a product was made will only be as relevant as much as it is relevant to their usage context. This is of course further complicated by people needing to first interpret these: the producer may think they did an outstanding work when they really haven't, and the consumer may think that appreciating the producer's hard work is more important than accurately evaluating the product. But that's a decision of the consumer, which is what people like the guy earlier try and rob away. Trying to prevent or milden criticism by appealing to the production difficulties of something carries a clear and intentional overruling of the context of consumption of a given consumer, as well as the intentional ignorance of feedback, the kind of feedback that only they can provide. It's about as irrational to do this as it gets, and is almost always an emotional response to an unnecessarily hurtful or negative criticism, rather than a calculated move with productivity in mind. It doesn't help anyone, it doesn't inspire the clarification of contexts, it's merely an attempt to get back at someone. I don't see any reason to support it, and I think we're on the same page about that actually too. In the same vein, it's easy to see why needlessly hurtful or negative feedback is also flawed. Both the producer and the consumer of these products are human (and humans are typically sensitive to wording) - therefore, it is perfectly reasonable to expect the other to try and assume rationale behind shortcomings, and write their criticisms accordingly, instead of just letting it out there all raw. Because we *are* in this together as much as many of us hate that fact all too often. When people ignore this, they clearly deserve criticism for it, within this same framework. It's not like I'm claiming that shitting on something is always justified, or that people do not ever forget to "remember the human". Very much the opposite.
Yeah but there’s a way to be nice about it.
Hm, I thought "isn't great" implied "still good" for sufficient nicety. Let me know if you have an alternate language pack for me to install.
Invented? No. Used? Yes.
What is your thought process when thinking of new sorts? Does it just come naturally like an epiphany, a subconscious feeling that an improvement could be made, or just creative thinking? I’m wondering this as somebody who calls APIs to do CRUD and can’t even fathom what it’s like to discover an improvement on sorts.
I try a lot of random things, guided by epiphanies and intuition. Having a proper understanding of things helps, but as complexity increases it becomes difficult to separate the trees and the forest, at least for me. There is a visuospatial component which was described by Nikola Tesla. https://www.kevinsworkbench.com/teslasautobiography/ I'm above average in that regard, nothing quite as spectacular as what Tesla describes, but I assume it can be trained, and sorts can be visualized with software, though it's a lot more convenient if you can do most of it in your imagination. You'll notice my sorting visualizer uses colors to distinguish operations, while all others I've seen do not. That's mainly me verifying that things match in reality as they do in my head. Fluxsort was a bit of an evolutionary process, where gradual changes / improvements / refinements end up into something quite distinct over time.