2017-11-06 17:55 GMT+03:00 Claudio Freire <klaussfre...@gmail.com>: > > On Mon, Nov 6, 2017 at 11:50 AM, Юрий Соколов <funny.fal...@gmail.com> wrote: > >> Maybe leave a fallback to qsort if some corner case produces big buckets? > > > > For 8kb pages, each bucket is per 32 bytes. So, for heap pages it is at > > most 1 heap-tuple per bucket, and for index pages it is at most 2 index > > tuples per bucket. For 32kb pages it is 4 heap-tuples and 8 index-tuples > > per bucket. > > It will be unnecessary overhead to call non-inlineable qsort in this cases > > > > So, I think, shell sort could be removed, but insertion sort have to remain. > > > > I'd prefer shell sort to remain also. It could be useful in other places > > also, > > because it is easily inlinable, and provides comparable to qsort performance > > up to several hundreds of elements. > > I'd rather have an inlineable qsort.
But qsort is recursive. It is quite hard to make it inlineable. And still it will be much heavier than insertion sort (btw, all qsort implementations uses insertion sort for small arrays). And it will be heavier than shell sort for small arrays. I can do specialized qsort for this case. But it will be larger bunch of code, than shell sort. > And I'd recommend doing that when there is a need, and I don't think > this patch really needs it, since bucket sort handles most cases > anyway. And it still needs insertion sort for buckets. I can agree to get rid of shell sort. But insertion sort is necessary.
