2017-11-03 5:46 GMT+03:00 Tom Lane <
tgl@sss.pgh.pa.us>:
>
> Sokolov Yura <
funny.falcon@postgrespro.ru> writes:
> > [ 0001-Improve-compactify_tuples.patch, v5 or thereabouts ]
>
> I went to check the shellsort algorithm against Wikipedia's entry,
> and found that this appears to be an incorrect implementation of
> shellsort: where pg_shell_sort_pass has
>
> for (_i = off; _i < _n; _i += off) \
>
> it seems to me that we need to have
>
> for (_i = off; _i < _n; _i += 1) \
>
> or maybe just _i++.
Shame on me :-(
I've wrote shell sort several times, so I forgot to recheck myself once again.
And looks like best gap sequence from wikipedia is really best
( {301, 132, 57, 23, 10 , 4} in my notation),
2017-11-03 17:37 GMT+03:00 Claudio Freire <
klaussfreire@gmail.com>:
> On Thu, Nov 2, 2017 at 11:46 PM, Tom Lane <
tgl@sss.pgh.pa.us> wrote:
>> BTW, the originally given test case shows no measurable improvement
>> on my box.
>
> I did manage to reproduce the original test and got a consistent improvement.
I've rechecked my self using my benchmark.
Without memmove, compactify_tuples comsumes:
- with qsort 11.66% cpu (pg_qsort + med3 + swapfunc + itemoffcompare + compactify_tuples = 5.97 + 0.51 + 2.87 + 1.88 + 0.44)
- with just insertion sort 6.65% cpu (sort is inlined, itemoffcompare also inlined, so whole is compactify_tuples)
- with just shell sort 5,98% cpu (sort is inlined again)
- with bucket sort 1,76% cpu (sort_itemIds + compactify_tuples = 1.30 + 0.46)
(memmove consumes 1.29% cpu)
tps is also reflects changes:
~17ktps with qsort
~19ktps with bucket sort
Also vacuum of benchmark's table is also improved:
~3s with qsort,
~2.4s with bucket sort
Of course, this benchmark is quite synthetic: table is unlogged, and tuple is small,
and synchronous commit is off. Though, such table is still useful in some situations
(think of not-too-important, but useful counters, like "photo watch count").
And patch affects not only this synthetic benchmark. It affects restore performance,
as Heikki mentioned, and cpu consumption of Vacuum (though vacuum is more io
bound).
> I think we should remove pg_shell_sort and just use pg_insertion_sort.
Using shell sort is just a bit safer. Doubtfully worst pattern (for insertion sort) will
appear, but what if? Shellsort is a bit better on whole array (5.98% vs 6.65%).
Though on small array difference will be much smaller.
With regards,
Sokolov Yura aka funny_falcon
