Re: [PoC] Improve dead tuple storage for lazy vacuum

Hi,

On 2021-07-25 19:07:18 +0300, Yura Sokolov wrote:
> I've dreamed to write more compact structure for vacuum for three
> years, but life didn't give me a time to.
>
> Let me join to friendly competition.
>
> I've bet on HATM approach: popcount-ing bitmaps for non-empty elements.

My concern with several of the proposals in this thread is that they
over-optimize for this specific case. It's not actually that crucial to
have a crazily optimized vacuum dead tid storage datatype. Having
something more general that also performs reasonably for the dead tuple
storage, but also performs well in a number of other cases, makes a lot
more sense to me.

> (Bad radix result probably due to smaller cache in notebook's CPU ?)

Probably largely due to the node dispatch. a) For some reason gcc likes
jump tables too much, I get better numbers when disabling those b) the
node type dispatch should be stuffed into the low bits of the pointer.

> select prepare(1000000, 2, 100, 1);
>
> attach size shuffled
> array 6ms 12MB 53.42s
> intset 23ms 16MB 54.99s
> rtbm 115ms 38MB 8.19s
> tbm 186ms 100MB 8.37s
> vtbm 105ms 59MB 9.08s
> radix 64ms 42MB 10.41s
> svtm 73ms 10MB 7.49s

> Test4
>
> select prepare(1000000, 100, 1, 1);
>
> attach size shuffled
> array 304ms 600MB 75.12s
> intset 775ms 98MB 47.49s
> rtbm 356ms 38MB 4.11s
> tbm 539ms 100MB 4.20s
> vtbm 493ms 42MB 4.44s
> radix 263ms 42MB 6.05s
> svtm 360ms 8MB 3.49s
>
> Therefore Specialized Vaccum Tid Map always consumes least memory amount
> and usually faster.

Impressive.

Greetings,

Andres Freund