Re: Small improvement to compactify_tuples

From: Heikki Linnakangas <hlinnaka(at)iki(dot)fi>
To: Sokolov Yura <funny(dot)falcon(at)postgrespro(dot)ru>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: Small improvement to compactify_tuples
Date: 2017-05-15 09:06:33
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

On 05/14/2017 09:47 PM, Sokolov Yura wrote:
> Good day, everyone.
> I've been playing a bit with unlogged tables - just random updates on
> simple
> key-value table. I've noticed amount of cpu spent in a compactify_tuples
> (called by PageRepareFragmentaion). Most of time were spent in qsort of
> itemidbase items.

Ah, I played with this too a couple of years ago, see, but
got distracted by other things and never got around to commit that.

> itemidbase array is bounded by number of tuples in a page, and
> itemIdSortData
> structure is simple, so specialized version could be a better choice.
> Attached patch adds combination of one pass of prefix sort with
> insertion
> sort for larger array and shell sort for smaller array.
> Insertion sort and shell sort are implemented as macros and could be
> reused.

Cool! Could you compare that against the bucket sort I posted in the
above thread, please?

At a quick glance, your "prefix sort" seems to be the the same algorithm
as the bucket sort that I implemented. You chose 256 buckets, where I
picked 32. And you're adding a shell sort implementation, for small
arrays, while I used a straight insertion sort. Not sure what these
differences mean in practice.

- Heikki

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Magnus Hagander 2017-05-15 09:08:19 Re: Typos in pg_basebackup.c
Previous Message tushar 2017-05-15 08:04:59 Create publication syntax is not coming properly in pg_dump / pg_dumpall