From: | "Mengxing Liu" <liu-mx15(at)mails(dot)tsinghua(dot)edu(dot)cn> |
---|---|
To: | "Alvaro Herrera" <alvherre(at)2ndquadrant(dot)com>, kgrittn <kgrittn(at)gmail(dot)com> |
Cc: | "pgsql-hackers(at)postgresql(dot)org" <pgsql-hackers(at)postgresql(dot)org> |
Subject: | [GSOC][weekly report 8] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions |
Date: | 2017-07-30 16:54:36 |
Message-ID: | 382f2a1b.2543.15d946bc112.Coremail.liu-mx15@mails.tsinghua.edu.cn |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
In the last week, I focused on tuning the performance of skip list and fixed several bugs.
1. As only out-conflicts are checked in RWConflictExists, I removed all modification concerned with in-conflicts;
2. If the conflict list is too short, I inserted an item just like inserting into an ordered linked list, that is,
comparing items existing in the list one by one to find the right position. Using skip list is slow when the list is short.
3. Not using the abstract skip list interface; I was afraid that it would bring a little overhead. But results showed that
it had no influence. I will roll it back if necessary.
Sadly, The performance is not better than the original version. But it's highest one among all efforts I did before.
It likes hash table. Tracking conflict is faster but inserting conflicts is slower.
In a quick test, cpu cycles consumed by two functions RWConflictExists/SetRWConflict is as below.
| | RWConflictExists | SetRWConflict |
| linked list | 1.39% | 0.14% |
| skip list | 1.15% | 0.35% |
According to the suggestions of Alvaro, I'll give a detailed performance report tomorrow.
--
Sincerely
Mengxing Liu
Attachment | Content-Type | Size |
---|---|---|
skip-list-for-conflict-tracking.patch | application/octet-stream | 12.3 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | Tels | 2017-07-30 17:45:51 | Re: PL_stashcache, or, what's our minimum Perl version? |
Previous Message | Mengxing Liu | 2017-07-30 16:53:02 | Re: [GSOC] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions |