On Sun, Sep 10, 2000 at 09:23:29PM +0200, Ralf S. Engelschall wrote:
> On Sun, Sep 10, 2000, Vladimir Kondratiev wrote:
>
> > I analyzed Pth performance for application that performs lots of context
> > switch. I found huge amount of time spent in just 2 functions :
> > sigismember() and sigdelset(). This functions are called from
> > pth_sched_eventmanager in loop for each thread and each signal.
> > pth_sched_eventmanager itself is called for each context switch. This
> > provides O(n**2) calls for functions mentioned, where n is number of
> > threads.
>
> Hmmmm... sorry, this complexity analysis seems not quite correct to me. An
> O(N^2) complexity you only can get if for every thread in an outer loop
> another inner loop exists which again performs an operation which is again
> directly proportional to the number of total threads. But that's not the case
> for Pth - both the way you explained it above and as far as I know details.
> I'm convinced that the complexity of the event manager is just O(n)
> - which is the expected one and should be acceptable.
>
Well - you are both well on the way to being right. The code, as Vladimir
said, does a "loop for each thread and each signal". It is:
for (t = pth_pqueue_head(&pth_WQ); t != NULL;
t = pth_pqueue_walk(&pth_WQ, t, PTH_WALK_NEXT)) {
/* determine signals we block */
for (sig = 1; sig < PTH_NSIG; sig++)
if (!sigismember(&(t->mctx.sigs), sig))
sigdelset(&pth_sigblock, sig);
So - the complexity is actually O(n*m), when n is the number of threads, and m
is the number of signals. Vladimir was confused I believe when he said n*n.
Of course, since PTH_NSIG is constant (on my box it's 64), the complexity
reduces to O(64*n) - which we all know is the same as O(n). So as Ralph
correctly said, the complexity is O(n) in the number of threads.
Chris
______________________________________________________________________
GNU Portable Threads (Pth) http://www.gnu.org/software/pth/
User Support Mailing List [EMAIL PROTECTED]
Automated List Manager (Majordomo) [EMAIL PROTECTED]
