Re: Resource Owner reassign Locks - Mailing list pgsql-hackers

On 10.06.2012 23:39, Jeff Janes wrote:
> The attached patch fixes that by remembering up to 10 local locks, and
> pushing them up specifically rather than digging through the entire
> lock table.  If the list overflows, then it reverts to the old
> behavior of digging through the entire local lock table.

I'm a bit uncomfortable with having a fixed limit like that, after which
you fall off the cliff. But I guess we can live with that, since we've
had the quadratic behavior for years, and haven't heard complaints about
it until recently. We can devise some more complex scheme later, if
people still run into this.

One idea for a more complex scheme, should we need one in the future, is
to make the cache in the ResourceOwner expandable, like all the other
arrays in ResourceOwner. It would not overflow when new entries are
added it. However, if you try to forget a lock, and it's not found in
the bottom 10 entries or so of the cache, mark the cache as overflowed
at that point. That way reassigning the locks would be fast, even if the
current resource owner holds a lot of locks, as longs as you haven't
tried to release any of them out of LIFO order.

> When it needs to  forget a lock, it searches backwards in the list of
> released lock and then just moves the last lock into the place of the
> one to be forgotten.  Other ResourceOwner Forget functions slide the
> entire list down to close the gap, rather than using the
> selection-sort-like method.  I don't understand why they do that.  If
> Forgets are strictly LIFO, then it would not make a difference.  If
> they are mostly LIFO but occasionally not, maybe the insertion method
> would win over the selection method.

Yeah, I think that's the reason. We try to keep the arrays in LIFO
order. If you move the last entry into the removed slot, then even a
single out-of-order removal will spoil the heuristic that removals are
done in LIFO order. Imagine that you insert 5 entries in order:

1
2
3
4
5

Now imagine that you first remove 1 (out-of-order), and then 5, 4, 3,
and 2 (in order). The removal of 1 moves 5 to the beginning of the
array. Then you remove 5, and that has to traverse the whole list
because 5 is now at the beginning. Then you swap 4 into the beginning of
the list, and so forth. Every subsequent removal scans the list from
bottom to top, because of the single out-of-order removal.

>  From what I can tell, Locks are
> mostly released in bulk anyway at transaction end, and rarely released
> explicitly.

Hmm, if they are released in bulk, then it doesn't matter either way. So
the decision on whether to do the slide or swap has to be made on the
assumption that some locks are released out-of-order. With an array of
10-15 entries, it probably doesn't make any difference either way, though.

> For degrading performance in other cases, I think the best test case
> is "pgbench -P" (implemented in another patch in this commitfest)
> which has a loop which pushes one or two locks up from a portal to the
> parent (which already owns them, due to previous rounds of the same
> loop) very frequently.  There might be a performance degradation of
> 0.5% or so, but it is less than the run to run variation.  I plan to
> run some longer test to get a better estimate.  If there is a
> degradation in that range, how important is that?

I think that would be acceptable.

I found the interface between resowner.c and lock.c a bit confusing.
resowner.c would sometimes call LockReassignCurrentOwner() to reassign
all the locks, and sometimes it would call LockReassignCurrentOwner() on
each individual lock, with the net effect that's the same as calling
LockReleaseCurrentOwner(). And it doesn't seem right for
ResourceOwnerRemember/ForgetLock to have to accept a NULL owner.

I rearranged that so that there's just a single
LockReassignCurrentOwner() function, like before this patch. But it
takes as an optional argument a list of locks held by the current
resource owner. If the caller knows it, it can pass them to make the
call faster, but if it doesn't it can just pass NULL and the function
will traverse the hash table the old-fashioned way. I think that's a
better API.

Please take a look to see if I broke something.

--
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com