Linux Scalability Effort

Hi John,

	Would you be interested in talking about this at the
LSE Conference Call tomorrow?

Hanna


--On Thursday, December 13, 2001 12:56:10 -0800 john stultz <johnstul@...> wrote:

> Recently, I've been working w/ semi-numa-aware locks, and in doing so,
> I've written an implementation of MCS locks. Its probably no surprise to
> locking old-timers, but I've been very impressed w/ its performance, so
> I figured I'd kick this implementation out for comments. I replaced the
> runqueue_lock spinlock w/ an mcs lock, and I've been testing using
> Rusty's hackbench (3 runs each). The results from an 8way netvista
> server are below.
> 
> 
> 2.4.16 vanilla
> ./hackbench 10: 5.478 4.048 2.976
> ./hackbench 50: 112.087 107.449 118.891
> ./hackbench 75: 298.866 315.150 340.870
> 
> 2.4.16 mcslock
> ./hackbench 10: 3.742 2.971 4.185
> ./hackbench 50: 89.073 98.930 98.947
> ./hackbench 75: 193.571 230.564 238.080
> 
> Improvement: ~13%(10) ~15%(50) ~30%(75)
> 
> As far as additional overhead, In a single threaded user-space test
> acquiring and releasing the lock one million times in a tight loop, the
> mcs lock takes 30-130% (depending on cpu) more time then a spinlock.
> 
> Also, the MCS lock is a bit more complicated to use as it is a queued
> lock and requires each cpu to have its own node to spin on. Rather then
> bloat out each lock w/ an array of nodes, I've allocated the nodes on
> the stack of the calling function. This however requires that the lock
> be locked and unlocked within the same function. 
> 
> For more info about MCS locks, you find the paper at:
> ftp://ftp.cs.rochester.edu/pub/papers/systems/91.TOCS.Scalable_Synch.ps.Z
> 
> I've attached a patch for the mcs lock implementation as well as the
> runqueue_lock replacement. Let me know if you have any comments on them.
> 
> Thanks
> -john

On Thu, Dec 13, 2001 at 12:56:10PM -0800, john stultz wrote:
> As far as additional overhead, In a single threaded user-space test
> acquiring and releasing the lock one million times in a tight loop, the
> mcs lock takes 30-130% (depending on cpu) more time then a spinlock.

John,

In your kernel with the runqueue lock replaced, you might want to
run the lat_ctx program of LMbench.  It would be interesting to see
if the additional overhead shows up here.

-- 
Mike

> In your kernel with the runqueue lock replaced, you might want to
> run the lat_ctx program of LMbench.  It would be interesting to see
> if the additional overhead shows up here.

With lat_ctx on a 4way box, I'm getting a ~6-17% improvement.

More numbers to come
-john

On Fri, 2001-12-14 at 11:38, john stultz wrote:
> > In your kernel with the runqueue lock replaced, you might want to
> > run the lat_ctx program of LMbench.  It would be interesting to see
> > if the additional overhead shows up here.
> 
> With lat_ctx on a 4way box, I'm getting a ~6-17% improvement.
> 
> More numbers to come

Alrighty, I ran on an 8way and found the numbers to be a little less
consistent. There varying from -2% to 10% improvement. This being the
average of only 3 runs of each test, I'm assuming I'm just not getting
enough sample points for a consistent picture. 

Numbers are attached for those who care.

thanks
-john

8x

vanilla
2 3.48
2 4.74
2 4.72
4 4.82
4 4.80
4 4.82
8 4.90
8 3.76
8 4.93
16 4.72
16 4.79
16 5.07
32 5.14
32 5.13
32 5.15
64 4.99
64 5.54
64 5.60
128 7.46
128 8.01
128 7.69
256 9.79
256 9.45
256 9.81

mcs
2 3.79
2 3.69
2 4.64
4 4.69
4 4.72
4 3.96
8 4.81
8 4.81
8 4.04
16 4.18
16 4.88
16 4.18
32 4.06
32 4.12
32 4.89
64 4.76
64 4.41
64 5.24
128 8.15
128 7.72
128 7.86
256 10.57
256 10.52
256 7.63

Hi John,

On Thu, Dec 13, 2001 at 12:56:10PM -0800, john stultz wrote:
> Recently, I've been working w/ semi-numa-aware locks, and in doing so,
> I've written an implementation of MCS locks. Its probably no surprise to
> locking old-timers, but I've been very impressed w/ its performance, so
> I figured I'd kick this implementation out for comments.

Sometime back, I implemented mcs spin and reader writer locks on x86 linux
for my school project.  I did some user space tests on the locks and
the locks worked fine. But, when i did some kernel stress testing on a 4way,
the tests did not complete in reasonable time.  I guess there might have 
been a deadlock. I haven't put enough time into it to find out if there was 
a problem with my implementation.
 
Out of curiosity, I put ur implementation through the same test
 
The test goes like this,
I create smp_num_cpus-1  threads, use a barrier mechanism and start running
the test routine on each thread in parallel.
 
The test routine goes something like this:

#define TOT_LOCK_ACS 200000000

static void test_mcslock(int num)
{
        int i;
        mcsnode_t node;
        unsigned int flags;
        local_irq_save(flags);
        cycb3[num] = get_cycles();
        for (i=0; i< TOT_LOCK_ACS; i++) {
                mcs_lock(&mcslock, &node);
                mb();
                mcs_unlock(&mcslock, &node);
        }
        cyca3[num] = get_cycles();
        local_irq_restore(flags);
}

The test completed, but took way too long. Just thought I'd let u know.

I have egcs-2.91.66 on the test machine - a 4 way pIII Xeon at 700MHz.

I can put out the reader writer lock implementation, if anybody is interested.

Thanks,
Kiran
-- 
Ravikiran G Thirumalai <kiran@...>
Linux Technology Center, IBM Software Labs,
Bangalore.

| 
|The test routine goes something like this:
|
|#define TOT_LOCK_ACS 200000000
|
|static void test_mcslock(int num)
|{
|        int i;
|        mcsnode_t node;
|        unsigned int flags;
|        local_irq_save(flags);

(1)        cycb3[num] = get_cycles();
|        for (i=0; i< TOT_LOCK_ACS; i++) {
|                mcs_lock(&mcslock, &node);
|                mb();
|                mcs_unlock(&mcslock, &node);
|        }
(2)        cyca3[num] = get_cycles();
|        local_irq_restore(flags);
|}


Are u sure there is no overflow between (1) and (2)? Do the
threads call this routine from an IRQ context?

Balbir

On Thu, Dec 27, 2001 at 01:54:55PM +0530, BALBIR SINGH wrote:
> | 
> |The test routine goes something like this:
> |
> |#define TOT_LOCK_ACS 200000000
> |
> |static void test_mcslock(int num)
> |{
> |        int i;
> |        mcsnode_t node;
> |        unsigned int flags;
> |        local_irq_save(flags);
> 
> (1)        cycb3[num] = get_cycles();
> |        for (i=0; i< TOT_LOCK_ACS; i++) {
> |                mcs_lock(&mcslock, &node);
> |                mb();
> |                mcs_unlock(&mcslock, &node);
> |        }
> (2)        cyca3[num] = get_cycles();
> |        local_irq_restore(flags);
> |}
> 
> 
> Are u sure there is no overflow between (1) and (2)? Do the

Overflow? There might be. But the delay i reported was not by measuring cycles,
The tests took quite some time to complete. 

> threads call this routine from an IRQ context?

Nope not from irq context. I run the routine with kernel threads.

> 
> Balbir
> 
> 

Kiran
-- 
Ravikiran G Thirumalai <kiran@...>
Linux Technology Center, IBM Software Labs,
Bangalore.

> Sometime back, I implemented mcs spin and reader writer locks on x86 linux
> for my school project.  I did some user space tests on the locks and
> the locks worked fine. But, when i did some kernel stress testing on a 4way,
> the tests did not complete in reasonable time.  I guess there might have 
> been a deadlock. I haven't put enough time into it to find out if there was 
> a problem with my implementation.
>  
> Out of curiosity, I put ur implementation through the same test
<snip>
> The test completed, but took way too long. Just thought I'd let u know.

Hmmm, that's interesting, is there a kernel patch you can send me of
this test? Under no contention (one thread), MCS locks are ~2x slower
then spinlocks in the tests I've run, but they perform very well under
high contention where starvation becomes a problem (again, in my own
tests). Is there any more data you can give me then "way too long"? Was
this comparing MCS locks w/ spinlocks? How was the test_mcslock()
function called?

> I can put out the reader writer lock implementation, if anybody is interested.

I would be very interested, send me a pointer to the code and I'll take
a look at it.

Thanks,
-john