On Mon, Nov 6, 2017 at 6:58 PM, Юрий Соколов <funny.fal...@gmail.com> wrote: > > 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 haven't seen this trick used in postgres, nor do I know whether it would be well received, so this is more like throwing an idea to see if it sticks... But a way to do this without macros is to have an includable "template" algorithm that simply doesn't define the comparison function/type, it rather assumes it: qsort_template.h #define QSORT_NAME qsort_ ## QSORT_SUFFIX static void QSORT_NAME(ELEM_TYPE arr, size_t num_elems) { ... if (ELEM_LESS(arr[a], arr[b])) ... } #undef QSORT_NAME Then, in "offset_qsort.h": #define QSORT_SUFFIX offset #define ELEM_TYPE offset #define ELEM_LESS(a,b) ((a) < (b)) #include "qsort_template.h" #undef QSORT_SUFFIX #undef ELEM_TYPE #undef ELEM_LESS Now, I realize this may have its cons, but it does simplify maintainance of type-specific or parameterized variants of performance-critical functions. > 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. I didn't suggest getting rid of insertion sort. But the trick above is equally applicable to insertion sort. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers