Re: [PATCH] lib: add statsort(), a distribution/bucket sort

[Jonathan Corbet]

Peter Taraba <peter.schuster.taraba@xxxxxxxxx> writes:

> 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 :)

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