Marginal performance improvement: replace bms_first_member loops

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-hackers(at)postgreSQL(dot)org
Subject: Marginal performance improvement: replace bms_first_member loops
Date: 2014-11-27 19:20:43
Message-ID: 4218.1417116043@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Another thing that came out of the discussion at
http://www.postgresql.org/message-id/flat/CAOR=d=3j1U_q-zf8+jUx1hkx8ps+N8pm=EUTqyFdJ5ov=+fawg(at)mail(dot)gmail(dot)com
was that there was a significant amount of palloc/pfree traffic blamable
on the bms_first_member() loop in plpgsql's setup_param_list(). I've
been experimenting with a variant of bms_first_member() called
bms_next_member(), which doesn't modify the input bitmapset and therefore
removes the need to make a working copy when iterating over the members
of a set.

In isolation, bms_next_member() is fractionally slower than
bms_first_member() because it has to do a bit more shifting-and-masking,
but of course we more than win that back from eliminating a palloc/pfree
cycle. It's also worth noting that in principle, a bms_first_member()
loop is O(N^2) for large sets because it scans from the start of the
set each time; but I doubt this is much of an issue in practice, because
the bitmapsets we work with just aren't very large. (I did some
microbenchmarking and found that if one ignores the palloc overhead
question, a bms_next_member loop is a tad slower up to about four words
in the bitmapset, and faster beyond that because the rescans start to
make a difference. But four words would be 128 bits and very very few
bitmapsets in PG would have more members than that.)

The attached proposed patch adds bms_next_member() and replaces
bms_first_member() calls where it seemed to make sense. I've had a
hard time measuring much speed difference for this patch in isolation,
but in principle it should be less code and less cycles. It also seems
safer and more natural to not use destructive looping techniques.

regards, tom lane

Attachment Content-Type Size
bms_next_member.patch text/x-diff 17.3 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Alvaro Herrera 2014-11-27 19:24:20 Re: no test programs in contrib
Previous Message Noah Misch 2014-11-27 18:43:01 Re: The problems of PQhost()