Re: [ANNOUNCE] ktimers subsystem

[Thomas Gleixner]

On Sat, 2005-09-24 at 12:35 +0200, Roman Zippel wrote:
> Hi,
> 
> On Sat, 24 Sep 2005, Ingo Molnar wrote:
> 
> > > Anyway, the biggest cost is the conversion from/to the 64bit ns value 
> > > [...]
> > 
> > Where do you get that notion from? Have you personally measured the 
> > performance and code size impact of it? If yes, would you mind to share 
> > the resulting data with us?
> > 
> > Our data is that the use of 64-bit nsec_t significantly reduces the size 
> > of a representative piece of code (object size in bytes):
> > 
> >                 AMD64    I386        ARM          PPC32       M68K
> >    nsec_t_ops   226      284         252          428         206
> >    timespec_ops 412      324         448          640         342
> > 
> > i.e. a ~40% size reduction when going to nsec_t on m68k, in that 
> > particular function. Even larger, ~45% code size reduction on a true 
> > 64-bit platform.
> 
> Without any source these numbers are not verifiable. You don't even 
> mention here what that "representative piece of code" is...

struct base {
        nsec_t now;
        struct ktimer *timers[16];
        struct ktimer *running;
};

void nsec_t_ops(struct base *base, struct ktimer *next,
                  nsec_t *tim, int mode)
{
        int i;
        nsec_t now = base->now;

        for (i = 0; i < 16; i++) {

                void (*fn)(void *);
                void *data;
                struct ktimer *timer = base->timers[i];

                if (timer->expires > now)
                        break;
                timer->expired = now;
                fn = timer->function;
                data = timer->data;
                base->running = timer;
                fn(data);
                base->running = NULL;
        }

        switch(mode) {
        case 0:
                next->expires = *tim;
                break;
        case 1:
                next->expires = now + *tim;
                break;
        case 2:
                next->expires += *tim;
                break;
        case 3:
                while (next->expires > now) {
                        next->expires += *tim;
                }
                break;
        }
        base->timers[0] = next;
}


versus:

#define NSEC_PER_SEC 1000000000
struct base {
        struct timespec now;
        struct ktimer *timers[16];
        struct ktimer *running;
};

#define timespec_gt(a,b)                       	\
        (((a).tv_sec > (b).tv_sec) ? 1 :        \
        (((a).tv_sec < (b).tv_sec) ? 0 :        \
        ((a).tv_nsec > (b).tv_nsec)))

#define timespec_addptr(a,b)                            \
        (a)->tv_sec = ((a)->tv_sec + (b)->tv_sec);      \
        (a)->tv_nsec = ((a)->tv_nsec + (b)->tv_nsec);   \
        if ((a)->tv_nsec >= NSEC_PER_SEC){               \
                (a)->tv_nsec -= NSEC_PER_SEC;           \
                (a)->tv_sec++;                          \
        }

#define timespec_addppp(c,a,b)                          \
        (c)->tv_sec = ((a)->tv_sec + (b)->tv_sec);      \
        (c)->tv_nsec = ((a)->tv_nsec + (b)->tv_nsec);   \
        if ((c)->tv_nsec >= NSEC_PER_SEC){               \
                (c)->tv_nsec -= NSEC_PER_SEC;           \
                (c)->tv_sec++;                          \
        }


void timespec_ops(struct base *base, struct ktimer *next,
                  struct timespec *tim, int mode)
{
        int i;
        struct timespec now = base->now;

        for (i = 0; i < 16; i++) {

                void (*fn)(void *);
                void *data;
                struct ktimer *timer = base->timers[i];

                if (timespec_gt(timer->expires, now))
                        break;
                timer->expired = now;
                fn = timer->function;
                data = timer->data;
                base->running = timer;
                fn(data);
                base->running = NULL;
        }

        switch(mode) {
        case 0:
                next->expires = *tim;
                break;
        case 1:
                timespec_addppp(&next->expires, &now, tim);
                break;
        case 2:
                timespec_addptr(&next->expires, tim);
                break;
        case 3:
                while (timespec_gt(now, next->expires)) {
                        timespec_addptr(&next->expires, tim);
                }
                break;
        }
        base->timers[0] = next;
}


> Anyway, Thomas mentioned that this would be from the insert/remove code 
> and here you omitted the most important part of my mail:
> 
> typedef union {
> 	u64 tv64;
> 	struct {
> #ifdef __BIG_ENDIAN
> 		u32 sec, nsec;
> #else
> 		u32 nsec, sec;
> #endif
> 	} tv;
> } ktimespec;
> 
> IOW this would allow to keep the time value in timespec format and use 
> your nsec_t_ops for sorting.

Yes, it works for comparisons. 

But for any other operation this construct has the same problem than
struct timespec itself. You need at least an add function which is
always an add and a comparison / correction vs. nsec >= NSEC_PER_SEC. 

The 64 bit nsec_t value can just be used as is without inventing a
wrapper macro for each operation.

The only point, where (k)timespec has an advantage is that the userspace
value must not be converted to nsec_t, but deducing therefor this is the
better overall solution is a fallacy.

nsec_t				ktimespec

syscall:
32x32 mul
64bit add			2 x 32bit move

arm timer:
64 bit add			2 x 32 bit add
				  32 bit compare
				  32 bit sub
				  32 bit add

The 3 operation compensate for the 32x32 
multiplication.

For interval timers you have the 
				  32 bit compare
				  32 bit sub
				  32 bit add
additional overhead for each rearm.

The backward conversion from nsec_t to timespec is almost a non issue.
The vast majority of callers dont provide the second argument to
nanosleep(), setitimer(), set_timer() which makes the conversion
necessary and I think we optimize for the common use case.

Besides that the representation of time in nsec_t values is much
clearer. 

I know that we have to deal with timespecs vs. userspace, but keeping
this representation for kernel internal usage reminds me on the BCD
calculations which were a similar 2^x vs 10^x oddity in the early days
of microprocessors. Of course they were obstinate and survived a
surprisingly long time.

tglx


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/