Lockless uidinfo.

[Jeff Roberson]

On Sun, 19 Aug 2007, Pawel Jakub Dawidek wrote:

> On Sun, Aug 19, 2007 at 12:07:56AM +0200, Pawel Jakub Dawidek wrote:
>> Two more things...
>>
>>> The patch below remove per-uidinfo locks:
>>>
>>> 	http://people.freebsd.org/~pjd/patches/uidinfo_lockless.patch
>>
>> We could upgrade from lock-free algorithm I used here to wait-free
>> algorithm, but we don't have atomic_fetchadd_long(). How hard will it be
>> to implement it?
>>
>> We could then change:
>>
>> 	do {
>> 		old = uip->ui_proccnt;
>> 		if (old + diff > max)
>> 			return (0);
>> 	} while (atomic_cmpset_long(&uip->ui_proccnt, old, old + diff) == 0);
>>
>> to something like this:
>>
>> 	if (atomic_fetchadd_long(&uip->ui_proccnt, diff) + diff > max) {
>> 		atomic_subtract_long(&uip->ui_proccnt, diff);
>> 		return (0);
>> 	}
>
> Ok, after implementing atomic_fetchadd_long() on amd64, we get additional
> 6% of performance improvement:
>
> x ./uidinfo_lockfree.txt (atomic_cmpset_long loop)
> + ./uidinfo_waitfree.txt (atomic_fetchadd_long)
> +------------------------------------------------------------------------------+
> |                                                                             +|
> |                                                                             +|
> |x   xx    xx                                                              + ++|
> |  |__MA___|                                                                |AM|
> +------------------------------------------------------------------------------+
>    N           Min           Max        Median           Avg        Stddev
> x   5       1561566       1575987       1568964       1569767     5853.1399
> +   5       1662362       1665936       1665810     1664881.8     1541.2693
> Difference at 95.0% confidence
>        95114.8 +/- 6241.96
>        6.05917% +/- 0.397636%
>        (Student's t, pooled s = 4279.88)

How does this effect the single-threaded performance?  Do you attribute 
this to atomic fetchadd being cheaper than atomic cmpset?  What is your 
processor?

Thanks,
Jeff

>
> -- 
> Pawel Jakub Dawidek                       http://www.wheel.pl
> pjd at FreeBSD.org                           http://www.FreeBSD.org
> FreeBSD committer                         Am I Evil? Yes, I Am!
>