RE: [Linux-ia64] Re: web page on O(1) scheduler

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Boehm, Hans]

Thanks for the pointer.  In the statically linked case, I get 200/568/345
for custom/pthread_mutex/pthread_spin.

I agree that this is not a fair comparison.  That was my point.  An implementation
with custom yield/sleep
code can do things that you can't do with blocking pthreads primitives at the
same performance.  (Of course pthreads_mutex_lock will win in other cases.)

Please forget about the abort() in the contention case.  I put that there for
brevity since it is not exercised by the test.  The intent was to time the
noncontention performance of a custom lock that first spins, then yields,
and then sleeps, as was stated in the comment.

You are forgetting two issues in your analysis of what pthreads is/should be doing
relative to the spin-lock-like code:

1) The unlock code is different.  If you potentially do a waitforunlocks()
in the locking code, you need to at least check whether the corresponding
notification is necessary when you unlock().  For NPTL that requires another
atomic operation, and hence another dozen to a couple of hundred cycles,
depending on the processor.  You need to look at both the lock and unlock
code.

2) (I hadn't mentioned this before.) The (standard interpretation of)
the memory barrier semantics of the pthreads primitives is too strong.
Arguably they need to be full memory barriers in both directions.
The pthread_spin_lock code inserts an extra full
memory barrier on IA64 as a result, instead of just
using the acquire barrier associated with the cmpxchg.acq instruction. 
(I think the spin unlock code doesn't do this.  One could argue that that's a bug,
though I would argue that the bug is really  in the pthreads spec.)

Hans

> -----Original Message-----
> From: Davide Libenzi [mailto:davidel@xmailserver.org]
> Sent: Friday, May 23, 2003 5:20 PM
> To: Boehm, Hans
> Cc: 'Arjan van de Ven'; Hans Boehm; MOSBERGER, DAVID
> (HP-PaloAlto,unix3); Linux Kernel Mailing List; 
> linux-ia64@linuxia64.org
> Subject: RE: [Linux-ia64] Re: web page on O(1) scheduler
> 
> 
> On Fri, 23 May 2003, Boehm, Hans wrote:
> 
> > Pthread_spin_lock() under the NPTL version in RH9 does 
> basically what my
> > custom locks do in the uncontested case, aside from the 
> function call.
> > But remember that this began with a discussion about whether it was
> > reasonable for user locking code to explicitly yield rather 
> than relying
> > on pthreads to suspend the thread.  I don't think 
> pthread_spin_lock is
> > relevant in this context, for two reasons:
> >
> > 1) At least the RH9 version of pthread_spin_lock in NPTL 
> literally spins
> > and makes no attempt to yield or block.  This only makes 
> sense at user
> > level if you are 100% certain that the processors won't be
> > overcommitted. Otherwise there is little to be lost by 
> blocking once you
> > have spun for sufficiently long.  You could use 
> pthread_spin_trylock and
> > block explicitly, but that gets us back to custom blocking code.
> 
> Yes, that would be a spinlock. Your code was basically a spinlock that
> instead of spinning was doing abort() in contention case. Again, you
> measured two different things. Even if the pthread mutex does 
> something
> very simple like :
> 
> 	spinlock(mtx->lock);
> 	while (mtx->busy) {
> 		spinunlock(mtx->lock);
> 		waitforunlocks();
> 		spinlock(mtx->lock);
> 	}
> 	mtx->busy++;
> 	spinunlock(mtx->lock);
> 
> Only the fact that this code likely reside inside a deeper 
> call lever will
> make you pay in a tight loop like your.
> 
> 
> > 2) AFAICT, pthread_spin_lock is currently a little too 
> bleeding edge to
> > be widely used.  I tried to time it, but failed.  Pthread.h doesn't
> > include the declaration for pthread_spin_lock_t by default, 
> at least not
> > yet.  It doesn't seem to have a Linux man page, yet.  I 
> tried to define
> > the magic macro to get it declared, but that broke something else.
> 
> $ gcc -D_GNU_SOURCE ...
> 
> 
> 
> - Davide
> 

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Davide Libenzi]

On Fri, 23 May 2003, Boehm, Hans wrote:

> Thanks for the pointer.  In the statically linked case, I get 200/568/345
> for custom/pthread_mutex/pthread_spin.
>
> I agree that this is not a fair comparison.  That was my point.  An implementation
> with custom yield/sleep
> code can do things that you can't do with blocking pthreads primitives at the
> same performance.  (Of course pthreads_mutex_lock will win in other cases.)
>
> Please forget about the abort() in the contention case.  I put that there for
> brevity since it is not exercised by the test.  The intent was to time the
> noncontention performance of a custom lock that first spins, then yields,
> and then sleeps, as was stated in the comment.
>
> You are forgetting two issues in your analysis of what pthreads is/should be doing
> relative to the spin-lock-like code:
>
> 1) The unlock code is different.  If you potentially do a waitforunlocks()
> in the locking code, you need to at least check whether the corresponding
> notification is necessary when you unlock().  For NPTL that requires another
> atomic operation, and hence another dozen to a couple of hundred cycles,
> depending on the processor.  You need to look at both the lock and unlock
> code.

That code was completely independent by what pthread might do. I didn't
look at the code but I think the new pthread uses futexes for mutexes.
The code wanted only to show that a mutex lock does more than a spinlock.
And this "more" is amplified by your tight loop.



> 2) (I hadn't mentioned this before.) The (standard interpretation of)
> the memory barrier semantics of the pthreads primitives is too strong.
> Arguably they need to be full memory barriers in both directions.
> The pthread_spin_lock code inserts an extra full
> memory barrier on IA64 as a result, instead of just
> using the acquire barrier associated with the cmpxchg.acq instruction.
> (I think the spin unlock code doesn't do this.  One could argue that that's a bug,
> though I would argue that the bug is really  in the pthreads spec.)

You need a write memory barrier even on the unlock. Consider this :

	spinlock = 1;
	...
	protected_resource = NEWVAL;
	spinlock = 0;

( where spinlock = 0/1 strip down, but do not lose the concept, the lock
operation ). If a CPU reorder those writes, another CPU might see the lock
drop before the protected resource assignment. And this is usually bad
for obvious reasons.



- Davide

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Davide Libenzi]

On Fri, 23 May 2003, Davide Libenzi wrote:

> You need a write memory barrier even on the unlock. Consider this :
>
> 	spinlock = 1;
> 	...
> 	protected_resource = NEWVAL;
> 	spinlock = 0;
>
> ( where spinlock = 0/1 strip down, but do not lose the concept, the lock
> operation ). If a CPU reorder those writes, another CPU might see the lock
> drop before the protected resource assignment. And this is usually bad
> for obvious reasons.

David made me notice about a brain misfire here. You need protection even
for loads crossing the unlock. For the same obvious reasons :) Yes, a
realease barrier will be sufficent for ia64, while you'll need an mfence
on P4.



- Davide

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Jan Harkes]

On Wed, Jun 04, 2003 at 09:13:43AM +0200, Mike Galbraith wrote:
> Using sched_yield() as a mutex is exactly the same as using a party line 
> for private conversation.

I actually used sched_yield for the 'inverse' mutex case. One thread was
pretty much exclusively holding a mutex, but other threads sometimes try
to get through the same critical section and block on mutex_lock. 

The first thread then occasionally does,

    mutex_unlock()
    sched_yield()
    mutex_lock()

Without the sched_yield, other threads never get a chance to wake up and
grab the mutex before the mutex hogging thread is back in the critical
section.

This is ofcourse the simple explanation, this was actually part of a
wrapper around pthreads that needed to provide non-concurrent
co-routines that in specific situations could run concurrently for a bit
to do DNS lookups and such.

Not sure how different semantics affect this because I went with a
different solution a while ago.

Jan

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

At 11:52 PM 6/3/2003 -0400, Bill Davidsen wrote:
>On Thu, 29 May 2003, Mike Galbraith wrote:
>
> > That would still suck rocks for mutex usage... as it must with any
> > implementation of sched_yield() in the presence of peer threads who are 
> not
> > playing with the mutex.  Actually, using sched_yield() makes no sense what
> > so ever to me, other than what Arjan said.  It refers to yielding your
> > turn, but from userland "your turn" has no determinate meaning.  There is
> > exactly one case where it has a useable value, and that is  when you're 
> the
> > _only_ runnable thread... at which time it means precisely zero. (blech)
>
>No, it works usefully without threads at all, with processes sharing a
>spinlock in shared memory. If the lock is closed process does a
>sched_yeild() to allow whoever has the lock to run. Yes to all comments
>WRT order of running, if you care you don't do this, clearly. But in the
>case where a process forks to a feeder and consumer it's faster than
>semaphores, signal, etc.

It can only be faster when there is no other source of competition for the 
cpu.  If there is no other competition, the current implementation won't 
hurt, because you'll switch arrays at very high speed... the queue rotation 
will be that which I described earlier.

There's only one real difference between going to sleep and waiting for a 
signal and your description of a proper yield.  Both place you at the end 
of your queue.  One immediately, the other upon wakeup.  How much "other 
stuff" is in the system determines task throughput in both cases.

>All that's needed is to put the yeild process on the end of the
>appropriate run queue and reschedule. Doing anything else results in bad
>performance and no gain to anything else.

And if either party has expired it's timeslice, who is the active task 
yielding to?  Why do you insist that those who have expired their slice 
should not be considered eligible players?  Now, let's throw a real 
monkey-wrench into the works...

What happens with your version of sched_yield() if one of your producer 
consumer pair is SCHED_RR, or worse - SCHED_FIFO [no timeslice, "turn" 
means until it blocks whether that be voluntary or not], and sched_yield() 
is the only way it can get rid of the cpu (ie it's a high priority pure cpu 
burner)?  If all you do is rotate the active queue and reschedule, you have 
just guaranteed that sched_yield() will have zero meaning.  The same exact 
thing (but less exaggerated) will happen if producer and consumer are not 
at the same dynamic priority.  You can call schedule() all you want if 
you're the highest priority runnable task... you get to keep the cpu 
whether you really want it or not.  I still say that sched_yield() makes 
zero sense for this usage.  There is only one guaranteed way to give up the 
cpu, and that is to sleep.

Using sched_yield() as a mutex is exactly the same as using a party line 
for private conversation.

         -Mike 

RE: [Linux-ia64] Re: web page on O(1) scheduler

[David Schwartz]

> No, it works usefully without threads at all, with processes sharing a
> spinlock in shared memory. If the lock is closed process does a
> sched_yeild() to allow whoever has the lock to run. Yes to all comments
> WRT order of running, if you care you don't do this, clearly. But in the
> case where a process forks to a feeder and consumer it's faster than
> semaphores, signal, etc.
>
> All that's needed is to put the yeild process on the end of the
> appropriate run queue and reschedule. Doing anything else results in bad
> performance and no gain to anything else.
>
> --
> bill davidsen <davidsen@tmr.com>
>   CTO, TMR Associates, Inc
> Doing interesting things with little computers since 1979.

	I've found sched_yield to be most useful in a case where you can't afford
to wait for a lock, but your processing will be much more efficient if you
have that lock. So you do this:

bool TryYieldLock(lock *f)
{
 if(TryLock(f)) return true;
 sched_yield();
 return TryLock(f);
}

	And you use it like this:

if(TryYieldLock(f))
{ /* great, we got the lock, just do it */
 DoItNow(x);
 Unlock(f);
}
else
{ /* oh well, we didn't get the lock */
 schedule_thread(DoItLater, f);
}

	In other words, you try a bit harder than the usual 'trylock' function but
not as hard as waiting for the lock. If you don't get the lock, you have to
process it a more expensive way (perhaps scheduling another thread to come
around later and wait for the lock).

	Consider a 'free' function for a custom allocator. If there's contention,
you might be willing to do a sched_yield to free it immediately. But you
really don't want to block while some other thread tries to do some
expensive coalescing, in that case you'd rather schedule another thread to
come around later and free it.

	This is much less useful on an MP machine though. It's unlikely that
'sched_yield()' will give the other thread enough time to release the lock
since odds are it's running on the other CPU.

	DS

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Bill Davidsen]

On Mon, 2 Jun 2003, Ingo Molnar wrote:

> 
> On Thu, 29 May 2003, Mike Galbraith wrote:
> 
> > [...] What makes more sense to me than the current implementation is to
> > rotate the entire peer queue when a thread expires... ie pull in the
> > head of the expired queue into the tail of the active queue at the same
> > time so you always have a player if one exists.  (you'd have to select
> > queues based on used cpu time to make that work right though)
> 
> we have tried all sorts of more complex yield() schemes before - they
> sucked for one or another workload. So in 2.5 i took the following path:  
> make yield() _simple_ and effective, ie. expire the yielding task (push it
> down the runqueue roughly halfway, statistically) and dont try to be too
> smart doing it. All the real yield() users (mostly in the kernel) want it
> to be an efficient way to avoid livelocks. The old 2.4 yield
> implementation had the problem of enabling a ping-pong between two
> higher-prio yielding processes, until they use up their full timeslice.
> 
> (we could do one more thing that still keeps the thing simple: we could
> re-set the yielding task's timeslice instead of the current 'keep the
> previous timeslice' logic.)
> 
> OpenOffice used to use yield() as a legacy of 'green thread'
> implementation - where userspace threads needed to do periodic yield()s to
> get any sort of multitasking behavior.

The way I use it is in cases when I fork processes which communicate
through a state machine (I'm simplifying) gated by a spinlock, both in
shared memory. On SMP machines the lock time is trivial and the processes
run really well. On uniprocessor you can get hangs for a full timeslice
unless a shed_yeild() is used if the lock is not available.

Since the processes have no shared data other than the small bit of shared
memory, it seems that threads give no benefit over fork, and for some o/s
much worse. Use of a mutex seems slightly slower in Linux, and quite
slower elsewhere.

The method you describe seems far more useful than some other discussion
which seems to advocate making the yeild process the lowest priority thing
in the system. That really doesn't seem to fit SuS, although I think they
had a single queue in mind. Perhaps not, in any case you seem to provide a
workable solution.

I'm not sure if there would any any significant difference by pushing down
halfway, all the way in the same queue, or just down one. The further down
it goes the better chance there is that the blocking process will run, but
the slower the access to the shared resource and the more chance that
another process will grab the resource. Perhaps down one the first time
and then to the end of the queue if there has not been a timeslice end or
i/o block before another yeild. That would prevent looping between any
number of competitors delaying dispatch to the holder of the lock.

Feel free to disagree, that just came to me as I typed.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Bill Davidsen]

On Thu, 29 May 2003, Mike Galbraith wrote:

> That would still suck rocks for mutex usage... as it must with any 
> implementation of sched_yield() in the presence of peer threads who are not 
> playing with the mutex.  Actually, using sched_yield() makes no sense what 
> so ever to me, other than what Arjan said.  It refers to yielding your 
> turn, but from userland "your turn" has no determinate meaning.  There is 
> exactly one case where it has a useable value, and that is  when you're the 
> _only_ runnable thread... at which time it means precisely zero. (blech)

No, it works usefully without threads at all, with processes sharing a
spinlock in shared memory. If the lock is closed process does a
sched_yeild() to allow whoever has the lock to run. Yes to all comments
WRT order of running, if you care you don't do this, clearly. But in the
case where a process forks to a feeder and consumer it's faster than
semaphores, signal, etc.

All that's needed is to put the yeild process on the end of the
appropriate run queue and reschedule. Doing anything else results in bad
performance and no gain to anything else.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

At 10:05 AM 6/2/2003 +0200, Ingo Molnar wrote:

>On Thu, 29 May 2003, Mike Galbraith wrote:
>
> > [...] What makes more sense to me than the current implementation is to
> > rotate the entire peer queue when a thread expires... ie pull in the
> > head of the expired queue into the tail of the active queue at the same
> > time so you always have a player if one exists.  (you'd have to select
> > queues based on used cpu time to make that work right though)
>
>we have tried all sorts of more complex yield() schemes before - they
>sucked for one or another workload. So in 2.5 i took the following path:
>make yield() _simple_ and effective, ie. expire the yielding task (push it
>down the runqueue roughly halfway, statistically) and dont try to be too
>smart doing it. All the real yield() users (mostly in the kernel) want it
>to be an efficient way to avoid livelocks. The old 2.4 yield
>implementation had the problem of enabling a ping-pong between two
>higher-prio yielding processes, until they use up their full timeslice.

(yeah, i looked at that in ktracer logs.  cpu hot-potato sucks;)

>(we could do one more thing that still keeps the thing simple: we could
>re-set the yielding task's timeslice instead of the current 'keep the
>previous timeslice' logic.)

(more consistent) 

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Ingo Molnar]

On Thu, 29 May 2003, Mike Galbraith wrote:

> [...] What makes more sense to me than the current implementation is to
> rotate the entire peer queue when a thread expires... ie pull in the
> head of the expired queue into the tail of the active queue at the same
> time so you always have a player if one exists.  (you'd have to select
> queues based on used cpu time to make that work right though)

we have tried all sorts of more complex yield() schemes before - they
sucked for one or another workload. So in 2.5 i took the following path:  
make yield() _simple_ and effective, ie. expire the yielding task (push it
down the runqueue roughly halfway, statistically) and dont try to be too
smart doing it. All the real yield() users (mostly in the kernel) want it
to be an efficient way to avoid livelocks. The old 2.4 yield
implementation had the problem of enabling a ping-pong between two
higher-prio yielding processes, until they use up their full timeslice.

(we could do one more thing that still keeps the thing simple: we could
re-set the yielding task's timeslice instead of the current 'keep the
previous timeslice' logic.)

OpenOffice used to use yield() as a legacy of 'green thread'
implementation - where userspace threads needed to do periodic yield()s to
get any sort of multitasking behavior.

	Ingo

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

At 06:12 PM 5/28/2003 -0400, Bill Davidsen wrote:
>On Wed, 21 May 2003, Olivier Galibert wrote:
>
> > On Wed, May 21, 2003 at 03:12:12PM +0200, Arjan van de Ven wrote:
> > > if you had spent the time you spent on this colorful graphic on reading
> > > SUS or Posix about what sched_yield() means, you would actually have
> > > learned something. sched_yield() means "I'm the least important thing in
> > > the system".
> >
> > Susv2:
> >
> > DESCRIPTION
> >
> >  The sched_yield() function forces the running thread to relinquish
> >  the processor until it again becomes the head of its thread list. It
> >  takes no arguments.
> >
> >
> > Aka "I skip the rest of my turn, try the others again once", not "I'm
> > unimportant" nor "please rerun me immediatly".
> >
> > What is it with you people wanting to make sched_yield() unusable for
> > anything that makes sense?
>
>Have to agree, I have a context switching benchmark which uses a spinlock
>in shared memory for do-it-yourself gating, and it wants sched_yeild() to
>be useful on uni. The SuS is pretty clear about this, the useful behaviour
>is also the required behaviour, why are people resisting doing it that
>way?

It can be argued that the current implementation does exactly what SuS 
describes.  The thread's list can be considered to be the sum of the active 
queue and the expired queue.  Merely rotating the active queue and 
scheduling away excludes the yielding thread's equally important expired 
peers from participation in the game.  Furthermore, if you are the only 
thread left in the active array, (you are at the head obviously), and all 
of your peers are currently expired, yielding would become meaningless... 
the thing you're trying to yield (the remainder of your slice) sticks to you.

Having said that, it can also be argued that we are violating the SuS 
description in that yielding the remainder of your slice yields to all 
threads in all lists, not only it's list.  What makes more sense to me than 
the current implementation is to rotate the entire peer queue when a thread 
expires... ie pull in the head of the expired queue into the tail of the 
active queue at the same time so you always have a player if one 
exists.  (you'd have to select queues based on used cpu time to make that 
work right though)

That would still suck rocks for mutex usage... as it must with any 
implementation of sched_yield() in the presence of peer threads who are not 
playing with the mutex.  Actually, using sched_yield() makes no sense what 
so ever to me, other than what Arjan said.  It refers to yielding your 
turn, but from userland "your turn" has no determinate meaning.  There is 
exactly one case where it has a useable value, and that is  when you're the 
_only_ runnable thread... at which time it means precisely zero. (blech)

         -Mike 

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Bill Davidsen]

On Wed, 21 May 2003, Olivier Galibert wrote:

> On Wed, May 21, 2003 at 03:12:12PM +0200, Arjan van de Ven wrote:
> > if you had spent the time you spent on this colorful graphic on reading
> > SUS or Posix about what sched_yield() means, you would actually have
> > learned something. sched_yield() means "I'm the least important thing in
> > the system".
> 
> Susv2:
> 
> DESCRIPTION
> 
>  The sched_yield() function forces the running thread to relinquish
>  the processor until it again becomes the head of its thread list. It
>  takes no arguments.
> 
> 
> Aka "I skip the rest of my turn, try the others again once", not "I'm
> unimportant" nor "please rerun me immediatly".
> 
> What is it with you people wanting to make sched_yield() unusable for
> anything that makes sense?

Have to agree, I have a context switching benchmark which uses a spinlock
in shared memory for do-it-yourself gating, and it wants sched_yeild() to
be useful on uni. The SuS is pretty clear about this, the useful behaviour
is also the required behaviour, why are people resisting doing it that
way? 

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Davide Libenzi]

On Fri, 23 May 2003, Boehm, Hans wrote:

> Pthread_spin_lock() under the NPTL version in RH9 does basically what my
> custom locks do in the uncontested case, aside from the function call.
> But remember that this began with a discussion about whether it was
> reasonable for user locking code to explicitly yield rather than relying
> on pthreads to suspend the thread.  I don't think pthread_spin_lock is
> relevant in this context, for two reasons:
>
> 1) At least the RH9 version of pthread_spin_lock in NPTL literally spins
> and makes no attempt to yield or block.  This only makes sense at user
> level if you are 100% certain that the processors won't be
> overcommitted. Otherwise there is little to be lost by blocking once you
> have spun for sufficiently long.  You could use pthread_spin_trylock and
> block explicitly, but that gets us back to custom blocking code.

Yes, that would be a spinlock. Your code was basically a spinlock that
instead of spinning was doing abort() in contention case. Again, you
measured two different things. Even if the pthread mutex does something
very simple like :

	spinlock(mtx->lock);
	while (mtx->busy) {
		spinunlock(mtx->lock);
		waitforunlocks();
		spinlock(mtx->lock);
	}
	mtx->busy++;
	spinunlock(mtx->lock);

Only the fact that this code likely reside inside a deeper call lever will
make you pay in a tight loop like your.


> 2) AFAICT, pthread_spin_lock is currently a little too bleeding edge to
> be widely used.  I tried to time it, but failed.  Pthread.h doesn't
> include the declaration for pthread_spin_lock_t by default, at least not
> yet.  It doesn't seem to have a Linux man page, yet.  I tried to define
> the magic macro to get it declared, but that broke something else.

$ gcc -D_GNU_SOURCE ...



- Davide

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Boehm, Hans]

Pthread_spin_lock() under the NPTL version in RH9 does basically what my custom locks do in the uncontested case, aside from the function call.  But remember that this began with a discussion about whether it was reasonable for user locking code to explicitly yield rather than relying on pthreads to suspend the thread.  I don't think pthread_spin_lock is relevant in this context, for two reasons:

1) At least the RH9 version of pthread_spin_lock in NPTL literally spins and makes no attempt to yield or block.  This only makes sense at user level if you are 100% certain that the processors won't be overcommitted.  Otherwise there is little to be lost by blocking once you have spun for sufficiently long.  You could use pthread_spin_trylock and block explicitly, but that gets us back to custom blocking code.

2) AFAICT, pthread_spin_lock is currently a little too bleeding edge to be widely used.  I tried to time it, but failed.  Pthread.h doesn't include the declaration for pthread_spin_lock_t by default, at least not yet.  It doesn't seem to have a Linux man page, yet.  I tried to define the magic macro to get it declared, but that broke something else.

Hans

> -----Original Message-----
> From: Davide Libenzi [mailto:davidel@xmailserver.org]
> Sent: Friday, May 23, 2003 11:05 AM
> To: Boehm, Hans
> Cc: 'Arjan van de Ven'; Hans Boehm; MOSBERGER, DAVID
> (HP-PaloAlto,unix3); Linux Kernel Mailing List; 
> linux-ia64@linuxia64.org
> Subject: RE: [Linux-ia64] Re: web page on O(1) scheduler
> 
> 
> On Fri, 23 May 2003, Boehm, Hans wrote:
> 
> > Sorry about the typo and misnaming for the test program.  I 
> attached the correct version that prints the right labels.
> >
> > The results I posted did not use NPTL.  (Presumably OpenMP 
> wasn't targeted at NPTL either.)  I don't think that NPTL has 
> any bearing on the underlying issues that I mentioned, though 
> path lengths are probably a bit shorter.  It should also 
> handle contention substantially better, but that wasn't tested.
> >
> > I did rerun the test case on a 900 MHz Itanium 2 machine 
> with a more recent Debian installation with NPTL.  I get 
> 200msecs (20nsecs/iter) with the custom lock, and 768 for 
> pthreads.  (With static linking that decreases to 658 for 
> pthreads.)  Pthreads (and/or some of the other 
> infrastructure) is clearly getting better, but I don't think 
> the difference will disappear.
> 
> To make things more fair you should test against pthread 
> spinlocks. Also,
> for tight loops like that, even an extra call deep level 
> (that pthread is
> likely to do) is going to matter.
> 
> 
> 
> - Davide
> 

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Davide Libenzi]

On Fri, 23 May 2003, Boehm, Hans wrote:

> Sorry about the typo and misnaming for the test program.  I attached the correct version that prints the right labels.
>
> The results I posted did not use NPTL.  (Presumably OpenMP wasn't targeted at NPTL either.)  I don't think that NPTL has any bearing on the underlying issues that I mentioned, though path lengths are probably a bit shorter.  It should also handle contention substantially better, but that wasn't tested.
>
> I did rerun the test case on a 900 MHz Itanium 2 machine with a more recent Debian installation with NPTL.  I get 200msecs (20nsecs/iter) with the custom lock, and 768 for pthreads.  (With static linking that decreases to 658 for pthreads.)  Pthreads (and/or some of the other infrastructure) is clearly getting better, but I don't think the difference will disappear.

To make things more fair you should test against pthread spinlocks. Also,
for tight loops like that, even an extra call deep level (that pthread is
likely to do) is going to matter.



- Davide

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Boehm, Hans]

[-- Attachment #1: Type: text/plain, Size: 1526 bytes --]

Sorry about the typo and misnaming for the test program.  I attached the correct version that prints the right labels.

The results I posted did not use NPTL.  (Presumably OpenMP wasn't targeted at NPTL either.)  I don't think that NPTL has any bearing on the underlying issues that I mentioned, though path lengths are probably a bit shorter.  It should also handle contention substantially better, but that wasn't tested.

I did rerun the test case on a 900 MHz Itanium 2 machine with a more recent Debian installation with NPTL.  I get 200msecs (20nsecs/iter) with the custom lock, and 768 for pthreads.  (With static linking that decreases to 658 for pthreads.)  Pthreads (and/or some of the other infrastructure) is clearly getting better, but I don't think the difference will disappear.

I don't have a Xeon with NPTL handy.  On an old PPro, the results were 1133 and 4379 msecs for custom and NPTL respectively.

Hans

> -----Original Message-----
> From: Arjan van de Ven [mailto:arjanv@redhat.com]
> Sent: Friday, May 23, 2003 1:31 AM
> To: Hans Boehm
> Cc: Arjan van de Ven; davidm@hpl.hp.com; linux-kernel@vger.kernel.org;
> linux-ia64@linuxia64.org
> Subject: Re: [Linux-ia64] Re: web page on O(1) scheduler
> 
> 
> On Thu, May 22, 2003 at 06:07:46PM -0700, Hans Boehm wrote:
> > case.
> > 
> > On a 1GHz Itanium 2 I get
> > 
> > Custom lock: 180 msecs
> > Custom lock: 1382 msecs
> > 
> > On a 2GHz Xeon, I get
> > 
> > Custom lock: 646 msecs
> > Custom lock: 1659 msecs
> 
> is the pthreads one with nptl ?
> 


[-- Attachment #2: time_lock.c --]
[-- Type: application/octet-stream, Size: 1760 bytes --]

#include <pthread.h>
#include <stdio.h>
#include <sys/time.h>
#include "atomic_ops.h"

/* Timing code stolen from Ellis/Kovac/Boehm GCBench.			*/
#define currentTime() stats_rtclock()
#define elapsedTime(x) (x)

unsigned long
stats_rtclock( void )
{
  struct timeval t;
  struct timezone tz;

  if (gettimeofday( &t, &tz ) == -1)
    return 0;
  return (t.tv_sec * 1000 + t.tv_usec / 1000);
}

AO_TS_T my_spin_lock = AO_TS_INITIALIZER;

pthread_mutex_t my_pthread_lock = PTHREAD_MUTEX_INITIALIZER;

void spin_lock_ool(AO_TS_T *lock)
{
  /* Should repeatly retry the AO_test_and_set_acquire, perhaps		*/
  /* after trying a plain read.  Should "exponentially" back off	*/
  /* between tries.  For short time periods it should spin, for 	*/
  /* medium ones it should use sched_yield, and for longer ones usleep. */

  /* For now we punt, since this is a contention-free test.		*/
      abort();
}

inline void spin_lock(AO_TS_T *lock)
{
  if (__builtin_expect(AO_test_and_set_acquire(lock) != AO_TS_CLEAR, 0))
    spin_lock_ool(lock);
}

inline void spin_unlock(AO_TS_T *lock)
{
  AO_CLEAR(lock);
}

int main()
{
  unsigned long start_time, end_time;
  int i;
  
  start_time = currentTime();
  for (i = 0; i < 10000000; ++i) {
    spin_lock(&my_spin_lock);
    spin_unlock(&my_spin_lock);
  }
  end_time = currentTime();
  fprintf(stderr, "Custom lock: %lu msecs\n",
	  elapsedTime(end_time - start_time));
  start_time = currentTime();
  for (i = 0; i < 10000000; ++i) {
    pthread_mutex_lock(&my_pthread_lock);
    pthread_mutex_unlock(&my_pthread_lock);
  }
  end_time = currentTime();
  fprintf(stderr, "Pthread lock: %lu msecs\n",
	  elapsedTime(end_time - start_time));
  return 0;
}

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Arjan van de Ven]

On Thu, May 22, 2003 at 06:07:46PM -0700, Hans Boehm wrote:
> case.
> 
> On a 1GHz Itanium 2 I get
> 
> Custom lock: 180 msecs
> Custom lock: 1382 msecs
> 
> On a 2GHz Xeon, I get
> 
> Custom lock: 646 msecs
> Custom lock: 1659 msecs

is the pthreads one with nptl ?

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Hans Boehm]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2114 bytes --]

On Wed, 21 May 2003, Arjan van de Ven wrote:

> oh you mean the OpenMP broken behavior of calling sched_yield() in a
> tight loop to implement spinlocks ?
> 
> I'd guess that instead of second guessing the runtime, they should use
> the pthreads primitives which are the fastest for the platform one would
> hope.. (eg futexes nowadays)
> 

That really depends on the circumstances.  I think there will always
be applications that use custom synchronization because they need the
last bit of performance in their specific environment.

I just ran a quick test to compare

a) 10,000,000 lock/unlock pairs with a rudimentary custom user-level spinlock
implementation, and
b) 10,000,000 pthread_mutex_lock/pthread_mutex_unlock pairs.

All locking is done by a single thread; this is the completely contention-free
case.

On a 1GHz Itanium 2 I get

Custom lock: 180 msecs
Custom lock: 1382 msecs

On a 2GHz Xeon, I get

Custom lock: 646 msecs
Custom lock: 1659 msecs

There are good reasons for the differences:

1) The pthread implementation needs an atomic operation on lock exit to
check whether waiters need to be awoken.  The spin lock just needs a
release barrier, which is cheap on both platforms.

2) The custom lock can be inlined.  The pthread one normally involves a
dynamic library call.  That has to be the case if you want to be able
to plug in different thread implementations.

3) Pthread locks come in various flavors, and the interface is designed
such that you have to check at runtime which flavor you have.

In the contention case there are other interesting issues, since it's
often far more efficient to spin before attempting to yield, and pthreads
implementations don't always do that.

The original case may also have involved barrier synchronization instead
of locks, in which case there is probably at least as much motivation to
"roll your own".

To reproduce my results from attached files (ao is my current attempt at
a portable atomic operations library):

tar xvfz ao-0.2.tar.gz
cp time_lock.c ao-0.2
cd ao-0.2
gcc -O2 time_lock.c -lpthread
./a.out

-- 
Hans Boehm
(hboehm@hpl.hp.com)

[-- Attachment #2: ao-0.2.tar.gz --]
[-- Type: APPLICATION/x-gzip, Size: 13274 bytes --]

[-- Attachment #3: time_lock.s --]
[-- Type: TEXT/PLAIN, Size: 1759 bytes --]

#include <pthread.h>
#include <stdio.h>
#include <sys/time.h>
#include "atomic_ops.h"

/* Timing code stolen from Ellis/Kovac/Boehm GCBench.			*/
#define currentTime() stats_rtclock()
#define elapsedTime(x) (x)

unsigned long
stats_rtclock( void )
{
  struct timeval t;
  struct timezone tz;

  if (gettimeofday( &t, &tz ) == -1)
    return 0;
  return (t.tv_sec * 1000 + t.tv_usec / 1000);
}

AO_TS_T my_spin_lock = AO_TS_INITIALIZER;

pthread_mutex_t my_pthread_lock = PTHREAD_MUTEX_INITIALIZER;

void spin_lock_ool(AO_TS_T *lock)
{
  /* Should repeatly retry the AO_test_and_set_acquire, perhaps		*/
  /* after trying a plain read.  Should "exponentially" back off	*/
  /* between tries.  For short time periods it should spin, for 	*/
  /* medium ones it should use sched_yield, and for longer ones usleep. */

  /* For now we punt, since this is a contention-free test.		*/
      abort();
}

inline void spin_lock(AO_TS_T *lock)
{
  if (__builtin_expect(AO_test_and_set_acquire(lock) != AO_TS_CLEAR, 0))
    spin_lock_ool(lock);
}

inline void spin_unlock(AO_TS_T *lock)
{
  AO_CLEAR(lock);
}

int main()
{
  unsigned long start_time, end_time;
  int i;
  
  start_time = currentTime();
  for (i = 0; i < 10000000; ++i) {
    spin_lock(&my_spin_lock);
    spin_unlock(&my_spin_lock);
  }
  end_time = currentTime();
  fprintf(stderr, "Custom lock: %lu msecs\n",
	  elapsedTime(end_time - start_time));
  start_time = currentTime();
  for (i = 0; i < 10000000; ++i) {
    pthread_mutex_lock(&my_pthread_lock);
    pthread_mutex_unlock(&my_pthread_lock);
  }
  end_time = currentTime();
  fprintf(stderr, "Custom lock: %lu msecs\n",
	  elapsedTime(end_time - start_time));
  return 0;
}

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Alan Cox]

On Mer, 2003-05-21 at 20:18, Duraid Madina wrote:
> "A process can relinquish the processor voluntarily without blocking by 
> calling sched_yield. The process will then be moved to the end of the 
> queue for its static priority and a new process gets to run."
> 
> How you get from there to "I'm the least important thing in the system" 
> is, once again, beyond me. And even if that were a reasonable 


Assuming nobody is niced the two say the same thing. Note "for its
_static_ priority" not for its dynamic priority. So sched_yield puts you
at the back of a pile of cpu hogs cos thats what the spec says it does

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Helge Hafting]

On Thu, May 22, 2003 at 05:18:02AM +1000, Duraid Madina wrote:
> Arjan van de Ven wrote:
> 
> >if you had spent the time you spent on this colorful graphic on reading
> >SUS or Posix about what sched_yield() means
> 
> Quoth the man page,
> 
> "A process can relinquish the processor voluntarily without blocking by 
> calling sched_yield. The process will then be moved to the end of the 
> queue for its static priority and a new process gets to run."
>
This assumes the implementation uses queues, one per 
priority level.
And even if it does, the process may be the only one with that
priority, making this a useless way of giving up "some time".
It'll still get rescheduled over and over and prevent
lower-priority processes from running.

 
> How you get from there to "I'm the least important thing in the system" 
> is, once again, beyond me. And even if that were a reasonable 
> interpretation of the word 'yield', you would still hope that more than 
> one CPU would get something to do if there was enough work to go around. 
> Agreed, "spinning" on sched_yield is a very naive way of doing 
> spinlocks. But that doesn't change the fact that it's a simple and 
> correct way. One would have hoped that calling sched_yield every few 
> million cycles wouldn't break the scheduler.

The way I understand it, the scheduler doesn't "break".  You just
get a lot of useless busy waiting.

Helge Hafting

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Duraid Madina]

Arjan van de Ven wrote:

> if you had spent the time you spent on this colorful graphic on reading
> SUS or Posix about what sched_yield() means

Quoth the man page,

"A process can relinquish the processor voluntarily without blocking by 
calling sched_yield. The process will then be moved to the end of the 
queue for its static priority and a new process gets to run."

How you get from there to "I'm the least important thing in the system" 
is, once again, beyond me. And even if that were a reasonable 
interpretation of the word 'yield', you would still hope that more than 
one CPU would get something to do if there was enough work to go around. 
Agreed, "spinning" on sched_yield is a very naive way of doing 
spinlocks. But that doesn't change the fact that it's a simple and 
correct way. One would have hoped that calling sched_yield every few 
million cycles wouldn't break the scheduler.

	Duraid

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Olivier Galibert]

On Wed, May 21, 2003 at 03:12:12PM +0200, Arjan van de Ven wrote:
> if you had spent the time you spent on this colorful graphic on reading
> SUS or Posix about what sched_yield() means, you would actually have
> learned something. sched_yield() means "I'm the least important thing in
> the system".

Susv2:

DESCRIPTION

 The sched_yield() function forces the running thread to relinquish
 the processor until it again becomes the head of its thread list. It
 takes no arguments.


Aka "I skip the rest of my turn, try the others again once", not "I'm
unimportant" nor "please rerun me immediatly".

What is it with you people wanting to make sched_yield() unusable for
anything that makes sense?

  OG.

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Arjan van de Ven]

[-- Attachment #1: Type: text/plain, Size: 1561 bytes --]

On Wed, 2003-05-21 at 12:40, Duraid Madina wrote:
> Dear Arjan,
> 
> 
>        ///////
>        //    O
>       //      >                                    This is a graduate
>        / \__ ~                                     student, laboratory
>          ||                            /////       assistant, automotive
>        (\ \)   (~)                    //  o   <--- engineer or other
>        ( \ \  / /                    //    >       unfortunate soul
>        (  \ \/ /         ____________/ \__O        attempting to get
>        (   \__/         /  ___ ______\//           performance out of a
>        /   | /@        (  /  / ______)/            machine running Linux
>       (    |//          \ \ / /   (_)              by writing a simple
>        \   ()            \ \O/                     and correct
>         \  |              ) )                      multithreaded program.
>          ) )             / /
>         (  |_           / /_
>         (____>         (____>
> 
>            ^
>            |
>            |
>            |
>            |
> 
>       This is you.
> 
> 

if you had spent the time you spent on this colorful graphic on reading
SUS or Posix about what sched_yield() means, you would actually have
learned something. sched_yield() means "I'm the least important thing in
the system". It's the wrong thing for cross-cpu spinlocks; futexes are
optimal for that. For letting higher priority tasks run a sleep(0) is
also far more closer to the right behavior than a sched_yield().


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Christoph Hellwig]

*plonk*

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Duraid Madina]

Dear Arjan,


       ///////
       //    O
      //      >                                    This is a graduate
       / \__ ~                                     student, laboratory
         ||                            /////       assistant, automotive
       (\ \)   (~)                    //  o   <--- engineer or other
       ( \ \  / /                    //    >       unfortunate soul
       (  \ \/ /         ____________/ \__O        attempting to get
       (   \__/         /  ___ ______\//           performance out of a
       /   | /@        (  /  / ______)/            machine running Linux
      (    |//          \ \ / /   (_)              by writing a simple
       \   ()            \ \O/                     and correct
        \  |              ) )                      multithreaded program.
         ) )             / /
        (  |_           / /_
        (____>         (____>

           ^
           |
           |
           |
           |

      This is you.



	(with apologies to the haxor brothers,)

	Duraid.


Arjan van de Ven wrote:
 > oh you mean the OpenMP broken behavior of calling sched_yield() in a
 > tight loop to implement spinlocks ?