lib: add statsort(), a distribution/bucket sort
A message that is not in the archive (sent off-list or not yet received): CAMKTnsb-PZ7_4Zd1ZAtmSWnTk8vyoP07WZUDsLuZ21j7OawQ9g@mail.gmail.com
Quoted 5 lines · On Tue, 4 Aug 2026 17:15:36 -0700 Peter <[email protected]> wrote:
because it's much faster than current alternatives and linux kernel will need it in future. don't forget the unknown is much larger than known.
FYI - this alg is even faster than C++ Boost library:
https://github.com/drpt78stu2/fspclib
OK, thanks.
Some measurements which help us understand the performance difference would be useful.
I'm not aware of any kernel code which spends significant time sorting things(?), so the motivation here won't be high.
The existing sort() has a little self-test in lib/tests/test_sort.c.
here are again benchamrks for large arrays:
== n = 100000000 distribution = uniform ==
statsort_longs best of 1: 9.0722 s ( 90.72 ns/elem) sort (kernel) best of 1: 171.2293 s (1712.29 ns/elem) qsort (libc) best of 1: 18.4959 s ( 184.96 ns/elem)
== n = 100000000 distribution = gaussian ==
statsort_longs best of 1: 8.6535 s ( 86.54 ns/elem) sort (kernel) best of 1: 170.0339 s (1700.34 ns/elem) qsort (libc) best of 1: 17.1339 s ( 171.34 ns/elem)
Faster than qsort (~twice faster) and way faster than qsort(~19 times faster) for both uniform and gaussian distribution.
I only tested with other c file, which I have not included in this patch. Would you like me to add tests? I can easily do so.
As far as usage, just open your mind... I can't tell all my secrets, because I don't want Microsoft to steal them and pretend it was their idea :)
Quoted 15 lines · Peter Taraba
here are again benchamrks for large arrays:
== n = 100000000 distribution = uniform ==
statsort_longs best of 1: 9.0722 s ( 90.72 ns/elem) sort (kernel) best of 1: 171.2293 s (1712.29 ns/elem) qsort (libc) best of 1: 18.4959 s ( 184.96 ns/elem)== n = 100000000 distribution = gaussian ==
statsort_longs best of 1: 8.6535 s ( 86.54 ns/elem) sort (kernel) best of 1: 170.0339 s (1700.34 ns/elem) qsort (libc) best of 1: 17.1339 s ( 171.34 ns/elem)Faster than qsort (~twice faster) and way faster than qsort(~19 times faster) for both uniform and gaussian distribution.
Quoted 6 lines
I only tested with other c file, which I have not included in this patch. Would you like me to add tests? I can easily do so.
As far as usage, just open your mind... I can't tell all my secrets, because I don't want Microsoft to steal them and pretend it was their idea :)
We don't add new code to the kernel for users that are "secrets". If you have an intended user for this code, include it with the series, please.
There is a recursive function in there, which we tend to avoid for the kernel. At a minimum, you would need to provide a convincing explanation of how you prevent it from overrunning the kernel stack.
Until you showed up with this patch, you have never been seen on the kernel lists; what inspired you to make this change now? Was this code created with assistance from large language models?
Thanks,
jon
Hi Jon and anyone who is reading it,
here are your answers:
Quoted 3 lines
Quoted 3 lines
We don't add new code to the kernel for users that are "secrets". If you have an intended user for this code, include it with the series, please.
I guess I will just go ahead and do it through my work around and keep my secrets (dont need to get my ideas to Microsoft, Google or even worse - to Facebook, etc. for free). If you change your mind about it in future, please do let me know.
Quoted 3 lines
Quoted 3 lines
There is a recursive function in there, which we tend to avoid for the kernel. At a minimum, you would need to provide a convincing explanation of how you prevent it from overrunning the kernel stack.
I am fully aware. Wanted more feedback (not only feedback which I get from AI). Thank you.
Quoted 3 lines
Quoted 3 lines
Until you showed up with this patch, you have never been seen on the kernel lists; what inspired you to make this change now? Was this code created with assistance from large language models?
I wanted to contribute to linux kernel as I am linux user and it would be nice to contribute to Linux community (kind of a proud moment for me). Oh well.
Also, you should do code review, not ask useless questions if LLM wrote the code. Even if I answered your questions, you wouldn't have to believe me - so what's the point of asking. You should make decision based on the code and if it is good for Linux kernel purely.
Cheers,
Peter
Quoted 4 lines · Peter Taraba
Hi Jon and anyone who is reading it,
here are your answers:
Quoted 8 lines
Quoted 3 lines
Quoted 3 lines
We don't add new code to the kernel for users that are "secrets". If you have an intended user for this code, include it with the series, please.
I guess I will just go ahead and do it through my work around and keep my secrets (dont need to get my ideas to Microsoft, Google or even worse - to Facebook, etc. for free). If you change your mind about it in future, please do let me know.
OK, good luck with that. The kernel does not add code to support proprietary projects.
Quoted 6 lines
Quoted 3 lines
Quoted 3 lines
There is a recursive function in there, which we tend to avoid for the kernel. At a minimum, you would need to provide a convincing explanation of how you prevent it from overrunning the kernel stack.
I am fully aware. Wanted more feedback (not only feedback which I get from AI). Thank you.
Feedback is what you are getting, but you seem remarkably uninterested in it.
Quoted 7 lines
Quoted 3 lines
Quoted 3 lines
Until you showed up with this patch, you have never been seen on the kernel lists; what inspired you to make this change now? Was this code created with assistance from large language models?
I wanted to contribute to linux kernel as I am linux user and it would be nice to contribute to Linux community (kind of a proud moment for me). Oh well.
If you want to contribute to a community, you need to spend some time understanding how that community works. It is not just by chance that this project remains vital after all these years. You are asking us to take on a chunk of code that we will have to maintain indefinitely; we have learned not to do that without good reason.
Quoted 4 lines
Also, you should do code review, not ask useless questions if LLM wrote the code. Even if I answered your questions, you wouldn't have to believe me - so what's the point of asking. You should make decision based on the code and if it is good for Linux kernel purely.
You don't get to tell me what I should do, sorry.
The community's rules require disclosure of LLM use. Many first-time contributors fail to do that, and the reason is often ignorance of the rules; once informed, they play along. The question is anything but useless.
Plus, it seems clear that you have answered it.
Thanks,
jon
Hi Jon & others,
Quoted 2 lines
Quoted 2 lines
OK, good luck with that. The kernel does not add code to support proprietary projects.
I want this idea to go to Linux Kernel and not be proprietary, but I want to make sure Microsoft and Facebook copy cats don't import this idea into their Windows and their other own operating systems and continue forcing their ways on others thanks to their still large user base. I am not worried about Google, as it's in their best interest to get this code into Linux as they are heavy users & contributors to Linux.
There are at least three future scenarios:
1. Someone gives me 750$ + 250$ for filing preliminary patent, so there would be a trap to slow down Microsoft and Facebook and I will file prelimiary patent with Linux community, wait for a week for dust to settle and share my idea.
2. Someone gives a seed to my start-up Milky Winf:
https://temp-qiwnvtinynzgwimacpcb.webadorsite.com/
and as soon as the invetment hits my bank account, I will share my idea on this thread and let Linux community deal with Microsoft and Facebook.
3. Work around and let this idea live on my off-internet laptop without wifi and network card...
Quoted 2 lines
Quoted 2 lines
Feedback is what you are getting, but you seem remarkably uninterested in it.
I always appreciate feedback especially from Linux veterans :). I am answering and we are still having a discussion, so I do not really understad why you believe I am not interested in yours and others opinions.
Quoted 5 lines
Quoted 5 lines
If you want to contribute to a community, you need to spend some time understanding how that community works. It is not just by chance that this project remains vital after all these years. You are asking us to take on a chunk of code that we will have to maintain indefinitely; we have learned not to do that without good reason.
Maybe you should look up definition of word Liberty and how it aligns with Linux community. But feel free to ignore me if you wish to do so.
Quoted 1 line
Quoted 1 line
You don't get to tell me what I should do, sorry.
I never force anyone to do anything unless they want to do it themselves. Don't expect me to force you into anything today, nor in future days.
Quoted 4 lines
Quoted 4 lines
The community's rules require disclosure of LLM use. Many first-time contributors fail to do that, and the reason is often ignorance of the rules; once informed, they play along. The question is anything but useless.
People can lie, so what's the point:
https://randommathguystfu.blogspot.com/2026/07/who-steals-first-not-who-actually.html
Quoted 1 line
Quoted 1 line
Plus, it seems clear that you have answered it.
I will cite David Archuleta's song's lyrics 'OK, all right'
Cheers & Queers,
Peter
Hi Peter,
Quoted 25 lines · Peter Taraba
Hi Jon & others,
Quoted 2 lines
Quoted 2 lines
OK, good luck with that. The kernel does not add code to support proprietary projects.
I want this idea to go to Linux Kernel and not be proprietary, but I want to make sure Microsoft and Facebook copy cats don't import this idea into their Windows and their other own operating systems and continue forcing their ways on others thanks to their still large user base. I am not worried about Google, as it's in their best interest to get this code into Linux as they are heavy users & contributors to Linux.
There are at least three future scenarios:
1. Someone gives me 750$ + 250$ for filing preliminary patent, so there would be a trap to slow down Microsoft and Facebook and I will file prelimiary patent with Linux community, wait for a week for dust to settle and share my idea.
2. Someone gives a seed to my start-up Milky Winf:
https://temp-qiwnvtinynzgwimacpcb.webadorsite.com/
and as soon as the invetment hits my bank account, I will share my idea on this thread and let Linux community deal with Microsoft and Facebook.
3. Work around and let this idea live on my off-internet laptop without wifi and network card...
Quoted 7 lines
Quoted 2 lines
Quoted 2 lines
Feedback is what you are getting, but you seem remarkably uninterested in it.
I always appreciate feedback especially from Linux veterans :). I am answering and we are still having a discussion, so I do not really understad why you believe I am not interested in yours and others opinions.
I think the reason Jon felt you were ignoring feedback is that you were explicitly told the kernel does not accept code without an in tree user, yet you seemed determined to upstream your code while keeping your use case a secret. To get this merged, you need to submit the code that actually consumes this API together as a single patchset. Adding a new API with no existing callers is an automatic NAK in almost all cases.
Additionally, why introduce a completely new API instead of modifying the existing sort()?
Performance is not the only consideration for sort() in the kernel. The kernel currently uses heapsort not because it's the fastest, but because of other critical constraints. It requires only O(1) extra memory, which means we don't have to worry about stack overflows. There are also scenarios where sorting is needed early in the boot process before the memory allocator is fully initialized, meaning kmalloc() cannot be used.
Your sorting method appears to be specifically tailored for 64 bit integer keys. This is exactly why knowing the "user" is so important:
the community needs to evaluate what specific in kernel scenario is so heavily bottlenecked by sorting performance that it justifies merging and maintaining a specialized, extra API, rather than simply relying on (or improving) the existing sort().
Regards,
Kuan-Wei
Quoted 30 lines
Quoted 6 lines
Quoted 6 lines
If you want to contribute to a community, you need to spend some time understanding how that community works. It is not just by chance that this project remains vital after all these years. You are asking us to take on a chunk of code that we will have to maintain indefinitely; we have learned not to do that without good reason.
Maybe you should look up definition of word Liberty and how it aligns with Linux community. But feel free to ignore me if you wish to do so.
Quoted 1 line
Quoted 1 line
You don't get to tell me what I should do, sorry.
I never force anyone to do anything unless they want to do it themselves. Don't expect me to force you into anything today, nor in future days.
Quoted 4 lines
Quoted 4 lines
The community's rules require disclosure of LLM use. Many first-time contributors fail to do that, and the reason is often ignorance of the rules; once informed, they play along. The question is anything but useless.
People can lie, so what's the point:
https://randommathguystfu.blogspot.com/2026/07/who-steals-first-not-who-actually.htmlQuoted 1 line
Quoted 1 line
Plus, it seems clear that you have answered it.
I will cite David Archuleta's song's lyrics 'OK, all right'
Cheers & Queers,
Peter
Hi Kuan-Wei,
thank you for your response. In the meantime, I decided to have my own fork instead of submitting code to linux kernel. For anyone interested it can be found here:
https://github.com/drpt78stu2/milky-winf-linux
From 5 responses on this thread, I actually did not receive much feedback on code anyway, mostly only about your politics (which I am not that interested in anyway), so I don't see a reason for submitting any code here.
So no worries, Jon and hims alike do not have to feel like they are ignored in future, as my fork is my fork :). There will be some other issues in future because of this decision, but seems like an easiest road for me.
That being said (and sad), I appreciate your work as I have been using Linux for 5+ years and it's been way better experience than Microsoft Windows. Unlike in Microsoft, no one yelled at me, so hey, that's better as well ;) if you like to keep your standards low.
Cheers & Queers & All the best,
Peter
+CC Greg, he does conduct iirc
Lore link for context:
https://lore.kernel.org/all/[email protected]/
Quoted 1 line
Cheers & Queers
Is this some sort of signature?
IMHO, this is very homophobic..
This is very inappropriate to say in a kernel mailing list, I may be completely crazy and completely wrong here, but best to find out.
I'm new to the kernel still, I do a whole other subsystem, but from me seeing this, I have to say something.
Quoted 2 lines
So no worries, Jon and hims alike >do not have to feel like they are ignored in future
Imho this is rude, Jon was doing a pretty reasonable comment, if you would like a new file, or something that the kernel would
need to maintain then some file, even if its a small driver, would need to be used, if not, it's just a useless file, and the maintainer if they would like benefit of the functions provided, would have to add it themselves.
Quoted 1 line
mostly only about your politics
For good reason, you can't just have undeclared LLM code, because, here's a crazy scenario, if all the LLMs just cease to work, and there are still bugs on your file, whatever are you going to do? Since you don't understand particularly what you are submitting (and the fact that this is for some sort of Linux distro) then the file would be riddled with bugs, and higher level maintainers would have a hard time fixing it.
(I may be wrong here, don't tell me off to much if I am, but I'm sure this is a wrong way to go out)
Thanks!
PATCH 1/1 lib: add statsort(), a distribution/bucket sort
Quoted 3 lines
Quoted 1 line
Cheers & Queers
Is this some sort of signature?
IMHO, this is very homophobic..
lol - i have not been accused of being homophobic yet. that's a new one.
From Google AI (it takes less than 5 second to do the search):
/*
AI Overview
"Cheers and Queers" is a common celebratory phrase, toast, and event title used within the LGBTQIA+ community. It frequently appears as a title for local social mixers, pride gatherings, podcasts, and novelty merchandise. */
Cheers & Queers & Take care,
Peter
https://temp-qiwnvtinynzgwimacpcb.webadorsite.com/
Quoted 6 lines · Peter Taraba
Quoted 3 lines
Quoted 1 line
Cheers & Queers
Is this some sort of signature?
IMHO, this is very homophobic..lol - i have not been accused of being homophobic yet. that's a new one.
Quoted 8 lines
From Google AI (it takes less than 5 second to do the search):
/*
AI Overview
"Cheers and Queers" is a common celebratory phrase, toast, and event title used within the LGBTQIA+ community. It frequently appears as a title for local social mixers, pride gatherings, podcasts, and novelty merchandise. */
hmm, well, okay. I'll leave it up to others to decide if this signature is appropriate.
Im conflicted wether it is or not, so I'll let others have their opinions.
Quoted 4 lines
Cheers & Queers & Take care,
Peter
https://temp-qiwnvtinynzgwimacpcb.webadorsite.com/
Thanks!
Hi all,
I had some more time to think and realized for my scenario, I actually do not need (nor actually want) my code to be inside of linux kernel, so you can close this code submission down. Thank you.
Cheers & Queers & thank you for feedback.
Peter
https://milkywaytoinfinity.blogspot.com