[GSOC][weekly report 8] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions

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

Browse pgsql-hackers by date

  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