gettime: minimize integer division
PATCH 1/1 gettime: minimize integer division
This patch generally converts a division to a subtraction in fio_gettime().
Shows ~1% better iops with synthetic benchmarking at roughly the same cpu time spent in fio_gettime().
gettime.c +9 -3
@@ -163,17 +163,23 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid) + delta = t - tv->last_cycles; tv->last_cycles = t; + } usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta >1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ; tp->tv_usec = usecs %1000000 ;break ; }
Quoted 26 lines · Sam Bradshaw
This patch generally converts a division to a subtraction in
fio_gettime().Shows ~1% better iops with synthetic benchmarking at roughly the same cpu time spent in
fio_gettime().Signed-off-by Sam Bradshaw <[email protected]>gettime.c +3
-2@@ -163,17 +163,23 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid)
gettime.c void fio_gettime(struct timeval *tp, void fio_unused *caller) · line 182
Quoted 10 lines
gettime.c +6
-1+ delta = t - tv->last_cycles; tv->last_cycles = t; + } usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta >1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ;
Shouldn't that be delta < 1000000? What am I missing? If the diff is more than 1M usecs, then do the division. If not, we can reuse the seconds from the last one.
Signature · 1 line
Jens Axboe
Quoted 31 lines · Jens Axboe
Quoted 30 lines · Sam Bradshaw
This patch generally converts a division to a subtraction in
fio_gettime().Shows ~1% better iops with synthetic benchmarking at roughly the same cpu time spent in
fio_gettime().Signed-off-by Sam Bradshaw <[email protected]>gettime.c +5
-2@@ -163,17 +163,23 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid) + delta = t - tv->last_cycles; tv->last_cycles = t; + }
Quoted 11 lines
gettime.c void fio_gettime(struct timeval *tp, void fio_unused *caller) · line 182
Quoted 6 lines
gettime.c +4
-1usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta >1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ;Shouldn't that be delta < 1000000? What am I missing? If the diff is more than 1M usecs, then do the division. If not, we can reuse the seconds from the last one.
Yes, my bad. Correct patch below.
gettime.c +0 -0
@@ -168,17 +168,23 @@ void fio_gettime(struct timeval *tp, void
fio_unused *caller)
}
#ifdef ARCH_HAVE_CPU_CLOCK
case CS_CPUCLOCK: {
- unsigned long long usecs, t;
+ unsigned long long usecs, t, delta = 0;
t = get_cpu_clock();
if (tv && t < tv->last_cycles) {
dprint(FD_TIME, "CPU clock going back in time\n"); t = tv->last_cycles;
- } else if (tv)
+ } else if (tv) {
+ if (tv->last_tv_valid)
+ delta = t - tv->last_cycles;
tv->last_cycles = t;
+ }
usecs = t / cycles_per_usec;
- tp->tv_sec = usecs / 1000000;
+ if (delta && delta < 1000000)
+ tp->tv_sec = tv->last_tv.tv_sec;
+ else
+ tp->tv_sec = usecs / 1000000;
tp->tv_usec = usecs % 1000000;
break;
}
Quoted 80 lines · Sam Bradshaw
Quoted 31 lines · Jens Axboe
Quoted 30 lines · Sam Bradshaw
This patch generally converts a division to a subtraction in
fio_gettime().Shows ~1% better iops with synthetic benchmarking at roughly the same cpu time spent in
fio_gettime().Signed-off-by Sam Bradshaw <[email protected]>gettime.c +5
-2@@ -163,17 +163,23 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid) + delta = t - tv->last_cycles; tv->last_cycles = t; + }Quoted 11 lines
gettime.c void fio_gettime(struct timeval *tp, void fio_unused *caller) · line 182
Quoted 6 lines
gettime.c +4
-1usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta >1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ;Shouldn't that be delta < 1000000? What am I missing? If the diff is more than 1M usecs, then do the division. If not, we can reuse the seconds from the last one.
Yes, my bad. Correct patch below.
gettime.c +9
-3@@ -168,17 +168,23 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid) + delta = t - tv->last_cycles; tv->last_cycles = t; + } usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta && delta <1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ; tp->tv_usec = usecs %1000000 ;break ;
Quoted 1 line
}
I was thinking about this... Is it actually guarenteed to work. If tv->last_tv.tv_usec is eg 900,000, you'd only need a 100k usec diff to need to wrap, not 1000k. And since this is about avoiding costly divs, since we know the number of cycles last time, it might make more sense to just do the single div to go from cycles to usecs, then add that to the tv->last_tv.
Signature · 1 line
Jens Axboe
Quoted 84 lines
-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf Of Jens Axboe
Sent: Thursday, December 20, 2012 10:03 AM
To: Sam Bradshaw (sbradshaw)
Cc: [email protected]
Subject: Re: [PATCH] gettime: minimize integer divisionQuoted 9 lines · Sam Bradshaw
Quoted 7 lines · Jens Axboe
Quoted 6 lines · Sam Bradshaw
This patch generally converts a division to a subtraction in
fio_gettime().Shows ~1% better iops with synthetic benchmarking at roughly the same cpu time spent in
fio_gettime().Quoted 7 lines
Quoted 7 lines
gettime.c void fio_gettime(struct timeval *tp, void fio_unused
Quoted 7 lines
Signed-off-by Sam Bradshaw <[email protected]>gettime.c +0
-0@@ -163,17 +163,23 @@ void fio_gettime(struct timeval *tp, void fio_unused*caller)
Quoted 56 lines
Quoted 17 lines
Quoted 17 lines
gettime.c +5
-2}#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid) + delta = t - tv->last_cycles; tv->last_cycles = t; + }Quoted 11 lines
gettime.c void fio_gettime(struct timeval *tp, void fio_unused · line 182
Quoted 6 lines
gettime.c +4
-1usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta >1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ;Shouldn't that be delta < 1000000? What am I missing? If the diff is more than 1M usecs, then do the division. If not, we can reuse the seconds from the last one.
Yes, my bad. Correct patch below.
gettime.c +5
-2@@ -168,17 +168,23 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid) + delta = t - tv->last_cycles; tv->last_cycles = t; + }
Quoted 16 lines
Quoted 9 lines
gettime.c +4
-1usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta && delta <1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ; tp->tv_usec = usecs %1000000 ;break ;}
I was thinking about this... Is it actually guarenteed to work. If
tv->last_tv.tv_usecis eg 900,000, you'd only need a 100k usec diff to need to wrap, not 1000k. And since this is about avoiding costly divs, since we know the number of cycles last time, it might make more sense to just do the single div to go from cycles to usecs, then add that to thetv->last_tv.
Good point. This patch is fundamentally broken as is. It could perhaps be fixed up with some additional reconciliation but that would add more arithmetic operations and may quickly approach the div latency and confound the branching logic. I'll think about it some more and try out your suggestion.
-Sam
Quoted 24 lines
Quoted 24 lines
gettime.c +5
-2@@ -168,17 +168,23 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid) + delta = t - tv->last_cycles; tv->last_cycles = t; + }
Quoted 17 lines
Quoted 9 lines
gettime.c +4
-1usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta && delta <1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ; tp->tv_usec = usecs %1000000 ;break ;}
I was thinking about this... Is it actually guarenteed to work. If
tv->last_tv.tv_usecis eg 900,000, you'd only need a 100k usec diff to need to wrap, not 1000k. And since this is about avoiding costly divs, since we know the number of cycles last time, it might make more sense to just do the single div to go from cycles to usecs, then add that to thetv->last_tv.
Something like this might work, though that amount of logic may be equivalent in terms of cycles to the divide.
gettime.c +0 -0
@@ -168,18 +168,25 @@ void fio_gettime(struct timeval *tp, void
fio_unused *caller)
}
#ifdef ARCH_HAVE_CPU_CLOCK
case CS_CPUCLOCK: {
- unsigned long long usecs, t;
+ unsigned long long usecs, t, delta = 0;
t = get_cpu_clock();
if (tv && t < tv->last_cycles) {
dprint(FD_TIME, "CPU clock going back in time\n"); t = tv->last_cycles;
- } else if (tv)
+ } else if (tv) {
+ if (tv->last_tv_valid)
+ delta = t - tv->last_cycles;
tv->last_cycles = t;
+ }
usecs = t / cycles_per_usec;
- tp->tv_sec = usecs / 1000000;
tp->tv_usec = usecs % 1000000;
+ if (delta && delta < 1000000 &&
+ tv->last_tv.tv_usec < tp->tv_usec)
+ tp->tv_sec = tv->last_tv.tv_sec;
+ else
+ tp->tv_sec = usecs / 1000000;
break;
}
#endif
Quoted 44 lines · Sam Bradshaw
Quoted 24 lines
Quoted 24 lines
gettime.c +5
-2@@ -168,17 +168,23 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid) + delta = t - tv->last_cycles; tv->last_cycles = t; + }Quoted 17 lines
Quoted 9 lines
gettime.c +4
-1usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta && delta <1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ; tp->tv_usec = usecs %1000000 ;break ;}
I was thinking about this... Is it actually guarenteed to work. If
tv->last_tv.tv_usecis eg 900,000, you'd only need a 100k usec diff to need to wrap, not 1000k. And since this is about avoiding costly divs, since we know the number of cycles last time, it might make more sense to just do the single div to go from cycles to usecs, then add that to thetv->last_tv.
Quoted 2 lines
Something like this might work, though that amount of logic may be equivalent in terms of cycles to the divide.
So I took a look at it. The costly bit is the division by cycles_per_usec, which the compiler has no other option than turn into a divq. The modulo and divide by 1M can be turned into something more clever, basically shifts and imull.
So how about the below? It turns the divq into multiplication and division by 10M, which should be considerably less expensive. Can you test and see how that works for you?
gettime.c +4 -1
@@ -15,6 +15,7 @@#ifdef ARCH_HAVE_CPU_CLOCK static unsigned long cycles_per_usec; +static unsigned long inv_cycles_per_usec;int tsc_reliable =0 ;#endif
@@ -177,7 +178,7 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }else if (tv) tv->last_cycles = t; - usecs = t / cycles_per_usec; + usecs = (t * inv_cycles_per_usec) /10000000UL ; tp->tv_sec = usecs /1000000 ; tp->tv_usec = usecs %1000000 ;break ;
@@ -277,6 +278,8 @@ static void calibrate_cpu_clock(void)dprint (FD_TIME ,"mean=%f, S=%f\n" , mean,S ); cycles_per_usec = avg; + inv_cycles_per_usec =10000000UL / cycles_per_usec; + dprint(FD_TIME, "inv_cycles_per_usec=%lu\n", inv_cycles_per_usec); }#else static void calibrate_cpu_clock (void )
Signature · 1 line
Jens Axboe
Quoted 48 lines · Jens Axboe
Quoted 44 lines · Sam Bradshaw
Quoted 24 lines
Quoted 24 lines
gettime.c +5
-2@@ -168,17 +168,23 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }#ifdef ARCH_HAVE_CPU_CLOCK case CS_CPUCLOCK : { -unsigned long long usecs, t; +unsigned long long usecs, t, delta =0 ; t =get_cpu_clock ();if (tv && t < tv->last_cycles) {dprint (FD_TIME ,"CPU clock going back in time\n" ); t = tv->last_cycles; - }else if (tv) + }else if (tv) { +if (tv->last_tv_valid) + delta = t - tv->last_cycles; tv->last_cycles = t; + }Quoted 17 lines
Quoted 9 lines
gettime.c +4
-1usecs = t / cycles_per_usec; - tp->tv_sec = usecs /1000000 ; +if (delta && delta <1000000 ) + tp->tv_sec = tv->last_tv.tv_sec; +else + tp->tv_sec = usecs /1000000 ; tp->tv_usec = usecs %1000000 ;break ;}
I was thinking about this... Is it actually guarenteed to work. If
tv->last_tv.tv_usecis eg 900,000, you'd only need a 100k usec diff to need to wrap, not 1000k. And since this is about avoiding costly divs, since we know the number of cycles last time, it might make more sense to just do the single div to go from cycles to usecs, then add that to thetv->last_tv.Quoted 2 lines
Something like this might work, though that amount of logic may be equivalent in terms of cycles to the divide.
Quoted 8 lines
So I took a look at it. The costly bit is the division by
cycles_per_usec, which the compiler has no other option than turn into a divq. The modulo and divide by 1M can be turned into something more clever, basically shifts and imull.So how about the below? It turns the divq into multiplication and division by 10M, which should be considerably less expensive. Can you test and see how that works for you?
Actually, it'd be dumb not to make it a power-of-2, since the actual number doesn't really matter. So this uses 2^24, try that.
gettime.c +4 -1
@@ -15,6 +15,7 @@#ifdef ARCH_HAVE_CPU_CLOCK static unsigned long cycles_per_usec; +static unsigned long inv_cycles_per_usec;int tsc_reliable =0 ;#endif
@@ -177,7 +178,7 @@ void fio_gettime(struct timeval *tp, void fio_unused *caller) }else if (tv) tv->last_cycles = t; - usecs = t / cycles_per_usec; + usecs = (t * inv_cycles_per_usec) /16777216UL ; tp->tv_sec = usecs /1000000 ; tp->tv_usec = usecs %1000000 ;break ;
@@ -277,6 +278,8 @@ static void calibrate_cpu_clock(void)dprint (FD_TIME ,"mean=%f, S=%f\n" , mean,S ); cycles_per_usec = avg; + inv_cycles_per_usec =16777216UL / cycles_per_usec; + dprint(FD_TIME, "inv_cycles_per_usec=%lu\n", inv_cycles_per_usec); }#else static void calibrate_cpu_clock (void )
Signature · 1 line
Jens Axboe
Quoted 14 lines
-----Original Message-----
From: Jens Axboe [mailto:[email protected]]
Sent: Friday, December 21, 2012 7:33 AM
To: Sam Bradshaw (sbradshaw)
Cc: [email protected]
Subject: Re: [PATCH] gettime: minimize integer divisionQuoted 4 lines · Sam Bradshaw
Something like this might work, though that amount of logic may be equivalent in terms of cycles to the divide.
Quoted 8 lines
So I took a look at it. The costly bit is the division by
cycles_per_usec, which the compiler has no other option than turn into a divq. The modulo and divide by 1M can be turned into something more clever, basically shifts and imull.So how about the below? It turns the divq into multiplication and division by 10M, which should be considerably less expensive. Can you test and see how that works for you?
That works much better. Several % lower execution time in fio_gettime(). IOPs look the same in my synthetic test but I'm not sure that's relevant; (it probably just needs some more tweaking).
I'll keep hunting for other hot spots.
-Sam
Quoted 19 lines · Sam Bradshaw (sbradshaw)
Quoted 19 lines
-----Original Message-----
From: Jens Axboe [mailto:[email protected]]
Sent: Friday, December 21, 2012 7:33 AM
To: Sam Bradshaw (sbradshaw)
Cc: [email protected]
Subject: Re: [PATCH] gettime: minimize integer divisionQuoted 4 lines · Sam Bradshaw
Something like this might work, though that amount of logic may be equivalent in terms of cycles to the divide.
So I took a look at it. The costly bit is the division by
cycles_per_usec, which the compiler has no other option than turn into a divq. The modulo and divide by 1M can be turned into something more clever, basically shifts and imull.
Quoted 5 lines
Quoted 3 lines
So how about the below? It turns the divq into multiplication and division by 10M, which should be considerably less expensive. Can you test and see how that works for you?
That works much better. Several % lower execution time in
fio_gettime().
Goodie
Quoted 2 lines
IOPs look the same in my synthetic test but I'm not sure that's relevant; (it probably just needs some more tweaking).
It'd probably need 3-4M IOPS from a single thread to have a big impact. But reduced CPU is leftover CPU for doing actual IO, so always a good thing.
And just as important, did the timing look correct?
Quoted 1 line
I'll keep hunting for other hot spots.
Thanks!
Signature · 1 line
Jens Axboe
Quoted 9 lines
Quoted 3 lines
IOPs look the same in my synthetic test but I'm not sure that's relevant; (it probably just needs some more tweaking).
It'd probably need 3-4M IOPS from a single thread to have a big impact. But reduced CPU is leftover CPU for doing actual IO, so always a good thing.
And just as important, did the timing look correct?
Yes, no spikes, latency average and std. dev. as expected.
-Sam
Quoted 11 lines · Sam Bradshaw (sbradshaw)
Quoted 9 lines
Quoted 3 lines
IOPs look the same in my synthetic test but I'm not sure that's relevant; (it probably just needs some more tweaking).
It'd probably need 3-4M IOPS from a single thread to have a big impact. But reduced CPU is leftover CPU for doing actual IO, so always a good thing.
And just as important, did the timing look correct?
Yes, no spikes, latency average and std. dev. as expected.
Excellent, now committed...
Signature · 1 line
Jens Axboe