You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@apr.apache.org by Brian Pane <br...@apache.org> on 2002/07/15 22:21:55 UTC
approximating division by a million Re: Why not POSIX time_t?
Building upon Cliff's formulas, here's another idea
for doing faster conversions of the current apr_time_t
format to seconds:
What we want is t/1000000
What we can do easily is t/1048576
But what can we add to t/1048576 to approximate t/1000000?
If I solve for 'C' in
t/1000000 = t/1048576 + t/C
I get C= ~21,586,297
That's not a power of 2, but what if use 2^24 (~16M) as an
approximation:
seconds = (t >> 20) + (t >> 24)
That probably isn't accurate enough, but you get the basic idea:
sum a couple of t/(2^n) terms to approximate t/1000000.
What do you think?
--Brian
Re: approximating division by a million Re: Why not POSIX time_t?
Posted by Brian Pane <br...@apache.org>.
Ben Laurie wrote:
> Brian Pane wrote:
>
>> Building upon Cliff's formulas, here's another idea
>> for doing faster conversions of the current apr_time_t
>> format to seconds:
>>
>> What we want is t/1000000
>>
>> What we can do easily is t/1048576
>>
>> But what can we add to t/1048576 to approximate t/1000000?
>>
>> If I solve for 'C' in
>> t/1000000 = t/1048576 + t/C
>> I get C= ~21,586,297
>> That's not a power of 2, but what if use 2^24 (~16M) as an
>> approximation:
>>
>> seconds = (t >> 20) + (t >> 24)
>>
>> That probably isn't accurate enough, but you get the basic idea:
>> sum a couple of t/(2^n) terms to approximate t/1000000.
>>
>> What do you think?
>
>
> I think you're all nuts. Are you seriously saying we compute time
> stuff often enough to care how long it takes?
Yes. The product of:
frequency of time manipulation * cost of time manipulation
is high enough to make 64-bit division one of the top 5 most
expensive functions in the httpd. (See Bill Stoddard's dev@httpd
posts on performance profiling for some examples.)
This result doesn't mean that time manipulation is naturally
an expensive part of the httpd, though; rather, it means that
we're using a time representation that's mismatched to the
needs of the application.
--Brian
Re: approximating division by a million Re: Why not POSIX time_t?
Posted by Ben Laurie <be...@algroup.co.uk>.
Brian Pane wrote:
> Building upon Cliff's formulas, here's another idea
> for doing faster conversions of the current apr_time_t
> format to seconds:
>
> What we want is t/1000000
>
> What we can do easily is t/1048576
>
> But what can we add to t/1048576 to approximate t/1000000?
>
> If I solve for 'C' in
> t/1000000 = t/1048576 + t/C
> I get C= ~21,586,297
> That's not a power of 2, but what if use 2^24 (~16M) as an
> approximation:
>
> seconds = (t >> 20) + (t >> 24)
>
> That probably isn't accurate enough, but you get the basic idea:
> sum a couple of t/(2^n) terms to approximate t/1000000.
>
> What do you think?
I think you're all nuts. Are you seriously saying we compute time stuff
often enough to care how long it takes?
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
Re: approximating division by a million Re: Why not POSIX time_t?
Posted by Brian Pane <br...@apache.org>.
Cliff Woolley wrote:
>On Mon, 15 Jul 2002, Brian Pane wrote:
>
>
>
>>seconds = (t >> 20) + (t >> 24)
>>
>>That probably isn't accurate enough, but you get the basic idea:
>>sum a couple of t/(2^n) terms to approximate t/1000000.
>>
>>What do you think?
>>
>>
>
>
>Sounds like the right idea. But I'm still not sure this isn't too
>complicated. ;-]
>
>
At least this localizes the complexity, though: instead of a
redesign of the time representation, we'd just need a new macro
for retrieving seconds. If that macro looks like
#define apr_macro_name_TBD(t) "(t >> 20) + (t >> 24) + (2 >> 29)"
(or whatever the right series might be), it's still less complicated
than many of the other designs we've been considering.
--Brian
Re: approximating division by a million Re: Why not POSIX time_t?
Posted by Cliff Woolley <jw...@virginia.edu>.
On Mon, 15 Jul 2002, Brian Pane wrote:
> seconds = (t >> 20) + (t >> 24)
>
> That probably isn't accurate enough, but you get the basic idea:
> sum a couple of t/(2^n) terms to approximate t/1000000.
>
> What do you think?
Sounds like the right idea. But I'm still not sure this isn't too
complicated. ;-]
Re: approximating division by a million Re: Why not POSIX time_t?
Posted by Brian Pane <br...@apache.org>.
Bill Stoddard wrote:
>Work up a patch to the apr_time macros and I'll benchmark it. This should be
>an easy and non intrusive thing to do.
>
I tried to create a patch yesterday, but no luck. Given the
wide range of values over which the macro has to work, I couldn't
come up with with a macro that was accurate to within a second for
all inputs.
--Brian
RE: approximating division by a million Re: Why not POSIX time_t?
Posted by Bill Stoddard <bi...@wstoddard.com>.
Work up a patch to the apr_time macros and I'll benchmark it. This should be
an easy and non intrusive thing to do.
FWIW, I mentioned this in an earlier thread and I'll mention it again. 64
bit divisions are horribly expensive on 32 bit hardware (or 32 bit kernels
running on 64 bit hardware). I would expect 64 bit divisions running with a
64 bit kernel on 64 bit hardware would be in the noise.
Bill
> -----Original Message-----
> From: Brian Pane [mailto:brianp@apache.org]
> Sent: Monday, July 15, 2002 4:22 PM
> To: Cliff Woolley
> Cc: APR Development List
> Subject: approximating division by a million Re: Why not POSIX time_t?
>
>
> Building upon Cliff's formulas, here's another idea
> for doing faster conversions of the current apr_time_t
> format to seconds:
>
> What we want is t/1000000
>
> What we can do easily is t/1048576
>
> But what can we add to t/1048576 to approximate t/1000000?
>
> If I solve for 'C' in
> t/1000000 = t/1048576 + t/C
> I get C= ~21,586,297
> That's not a power of 2, but what if use 2^24 (~16M) as an
> approximation:
>
> seconds = (t >> 20) + (t >> 24)
>
> That probably isn't accurate enough, but you get the basic idea:
> sum a couple of t/(2^n) terms to approximate t/1000000.
>
> What do you think?
>
> --Brian
>
>