Re: [HACKERS] Small improvement to compactify_tuples - Mailing list pgsql-hackers
| From | Юрий Соколов |
|---|---|
| Subject | Re: [HACKERS] Small improvement to compactify_tuples |
| Date | |
| Msg-id | CAL-rCA2toMO_NwXb6N85wGJ_KRYSCxwzEEc0-hTV0Oyr86wotw@mail.gmail.com Whole thread Raw |
| In response to | Re: [HACKERS] Small improvement to compactify_tuples (Alvaro Herrera <alvherre@2ndquadrant.com>) |
| Responses |
Re: [HACKERS] Small improvement to compactify_tuples
(Claudio Freire <klaussfreire@gmail.com>)
|
| List | pgsql-hackers |
2017-11-07 17:15 GMT+03:00 Claudio Freire <klaussfreire@gmail.com>:
>
> On Mon, Nov 6, 2017 at 9:08 PM, Юрий Соколов <funny.falcon@gmail.com> wrote:
> > 2017-11-07 1:14 GMT+03:00 Claudio Freire <klaussfreire@gmail.com>:
> >>
> >> 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.
> >
> > This trick is used in simplehash.h . I agree, it could be useful for qsort.
> > This will not make qsort inlineable, but will reduce overhead much.
> >
> > This trick is too heavy-weight for insertion sort alone, though. Without
> > shellsort, insertion sort could be expressed in 14 line macros ( 8 lines
> > without curly braces). But if insertion sort will be defined together with
> > qsort (because qsort still needs it), then it is justifiable.
>
> What do you mean by heavy-weight?
I mean, I've already made reusable sort implementation with macros
that is called like a function (with type parameter). If we are talking
only about insertion sort, then such macros looks much prettier than
BTW, there is example of defining many functions with call to template
macro instead of including template header:
But it looks ugly.
>
> Aside from requiring all that include magic, if you place specialized
> sort functions in a reusable header, using it is as simple as
> including the type-specific header (or declaring the type macros and
> including the template), and using them as regular functions. There's
> no runtime overhead involved, especially if you declare the comparison
> function as a macro or a static inline function. The sort itself can
> be declared static inline as well, and the compiler will decide
> whether it's worth inlining.
I will add template header for qsort. Since qsort needs insertion sort,
it will be in a same file.
Do you approve of this?
With regards,
Sokolov Yura
pgsql-hackers by date: