Extremely inefficient instantiating a distant local date

[autarch]

Migrated from rt.cpan.org #47671 (status was 'open')

Requestors:

• mschwern@cpan.org (@schwern)

From mschwern@cpan.org (@schwern) on 2009-07-08 02:01:30:

$ time perl -wle 'use DateTime; print DateTime->new( year => 3058,
time_zone => "local" )'
3058-01-01T00:00:00

real 0m9.558s
user 0m8.619s
sys 0m0.165s

This occurs whether time_zone is "local" or set to a zone like
"America/Chicago".

Profiling reveals that this makes tens of thousands of method calls.
The big hog is 10000 calls to DateTime::set_time_zone which is being
called by add_duration() which all traces back to
DateTime::TimeZone::_generate_spans_until_match looping over OlsenDB
calls 2000+ times.

This all traces back to DateTime->offset called by
DateTime::_handle_offset_modifier and DateTime::_calc_local_rd

Its possible one could hold off doing whatever it is that calc_local_rd
does, considering that information is not necessary just to instantiate
an object, but the root problem is _generate_spans_until_match's
algorithm. I'm not sure what its purpose is, but it appears to be
iterative by year resulting in Y iterations where Y is the year being
search for (minus some arbitrary lower limit).

If the whole purpose is to determine the time zone offset, this
algorithm is much more efficiently done as a binary search. Even if we
assume a 64 bit year it will take at most 64 iterations to zero in on
the right year. And so on for the month, day, hour, minute and second.

If its just searching the Olsen DB for applicable zone changes I don't
pretend to understand how that works but there's got to be a better way
to do it. C libraries can do it in milliseconds and Perl is just not
that slow. Perhaps with some sort of... database?

[autarch]

From autarch@urth.org (@autarch) on 2009-07-08 02:08:38:

On Tue, 7 Jul 2009, Michael G Schwern via RT wrote:

Its possible one could hold off doing whatever it is that calc_local_rd
does, considering that information is not necessary just to instantiate
an object, but the root problem is _generate_spans_until_match's
algorithm. I'm not sure what its purpose is, but it appears to be
iterative by year resulting in Y iterations where Y is the year being
search for (minus some arbitrary lower limit).

It's generating all the time zone changes from X years out (by default,
each time zone ships with 10 years of pre-calculated data. The rest is
generated as needed.

Note that this only affects zones with DST rules in effect.

If the whole purpose is to determine the time zone offset, this
algorithm is much more efficiently done as a binary search. Even if we
assume a 64 bit year it will take at most 64 iterations to zero in on
the right year. And so on for the month, day, hour, minute and second.

The problem being that there's nothing to search until it's generated.

While I'm sure this could be made faster, I'm not sure it's worth too much
effort. Project Olson time zones that far in the future is pretty silly.
Time zones are political entities, and it's almost certain that rules in
effect now won't be in effect in the year 3058.

Just use UTC.

-dave

/============================================================
http://VegGuide.org http://blog.urth.org
Your guide to all that's veg House Absolute(ly Pointless)
============================================================/

[autarch]

From mschwern@cpan.org (@schwern) on 2009-07-08 03:02:01:

On Tue Jul 07 22:08:38 2009, autarch@urth.org wrote:

The problem being that there's nothing to search until it's generated.

Are you saying it regenerates the database at run time every time? How
about doing it once when DateTime::TimeZone is installed?

While I'm sure this could be made faster, I'm not sure it's worth too
much
effort. Project Olson time zones that far in the future is pretty silly.
Time zones are political entities, and it's almost certain that rules in
effect now won't be in effect in the year 3058.

Just use UTC.

What the hell kind of answer is that?! I'll take "yeah, that sucks but
I don't have the tuits to optimize it. Here's some thoughts on how to
do it..." but not "use UTC". Come on. While time zones are annoying,
you can't just blow them off! Especially as the maintainer of the most
heavily used date module in Perl!

While I agree worrying about the niggling details of historical time
zone changes 1000 years from now is silly, THE SUN WILL STILL BE IN THE
SKY and that's what a time zone offset basically reflects. And while
optimizing the code might be hard we're not talking milliseconds here.
That's 10 seconds to go forward a mere 1000 years. Even calculating
2109 takes a full second. 2150 is 1.3 seconds. That's unacceptable.

Another simple optimization would be to cache what the latest Olsen
entry is and then just not bother looking beyond that.

Somewhat apropos, for dates far in the past, before time zones, I've
seen 64 bit Linuxen use the lat/long for the city in question which is
pretty clever.

[autarch]

From autarch@urth.org (@autarch) on 2009-07-08 03:37:39:

On Tue, 7 Jul 2009, Michael G Schwern via RT wrote:

  Queue: DateTime

Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=47671 >

On Tue Jul 07 22:08:38 2009, autarch@urth.org wrote:

The problem being that there's nothing to search until it's generated.

Are you saying it regenerates the database at run time every time? How
about doing it once when DateTime::TimeZone is installed?

Storing the changes in memory uses up a fair bit of memory.

Generating 1000+ years worth would make loading each time zone take much
much more memory. It does it at runtime to optimize for the common case of
not needing to look too far in the future.

Just use UTC.

What the hell kind of answer is that?! I'll take "yeah, that sucks but
I don't have the tuits to optimize it. Here's some thoughts on how to
do it..." but not "use UTC". Come on. While time zones are annoying,
you can't just blow them off! Especially as the maintainer of the most
heavily used date module in Perl!

It's the right answer. Using Olson time zones with far future dates just
doesn't make any sense. These time zones exist for the purpose of dealing
with the dictates of modern political entities.

While I agree worrying about the niggling details of historical time
zone changes 1000 years from now is silly, THE SUN WILL STILL BE IN THE
SKY and that's what a time zone offset basically reflects. And while

Yes, that's what the offset reflects. However, the DST changes reflect
the random whims of idiot politicians.

If you just want an offset, use a static offset like '-0500'. That will be
fast, since there's no DST rules to deal with.

Another simple optimization would be to cache what the latest Olsen
entry is and then just not bother looking beyond that.

That doesn't make any sense. The last Olson entry is purely arbitrary
based on how many years of pre-calculation the module ships with, and when
I happen to generate it.

Or do you mean the offset without DST? Then someone else will complain
that it's broken at some arbitrary date (like 11 years out).

For people who need to calculate far future dates, there are other
solutions (UTC or some other fixed offset) that work. But either way, you
as the user need to make a decision about what you want. I can't make that
decision for you, I just provide the options.

If you want to take a stab at optimizing the changes generation, that's
fine with me, but personally I don't think it's wortwhile, since there's
no sane use case for Olson time zones in the far future.

Somewhat apropos, for dates far in the past, before time zones, I've
seen 64 bit Linuxen use the lat/long for the city in question which is
pretty clever.

A DT::TZ::LatLong would be very cool.

Actually, the Olson database approximates this, since pre-modern times it
uses local mean time, which is an offset based off the lat/long of the
named city.

-dave

/============================================================
http://VegGuide.org http://blog.urth.org
Your guide to all that's veg House Absolute(ly Pointless)
============================================================/

[autarch]

From schwern@pobox.com on 2009-07-08 09:57:18:

autarch@urth.org via RT wrote:

On Tue Jul 07 22:08:38 2009, autarch@urth.org wrote:

The problem being that there's nothing to search until it's generated.
Are you saying it regenerates the database at run time every time? How
about doing it once when DateTime::TimeZone is installed?

Storing the changes in memory uses up a fair bit of memory.

Generating 1000+ years worth would make loading each time zone take much
much more memory. It does it at runtime to optimize for the common case of
not needing to look too far in the future.

Generating 1000+ years of what? The Olsen database doesn't go forward that
far. And who says it has to all be in memory? There's any number of
techniques to leave things on disk.

The C code figured this out 20 years ago!

Just use UTC.
What the hell kind of answer is that?! I'll take "yeah, that sucks but
I don't have the tuits to optimize it. Here's some thoughts on how to
do it..." but not "use UTC". Come on. While time zones are annoying,
you can't just blow them off! Especially as the maintainer of the most
heavily used date module in Perl!

It's the right answer. Using Olson time zones with far future dates just
doesn't make any sense. These time zones exist for the purpose of dealing
with the dictates of modern political entities.

While I agree worrying about the niggling details of historical time
zone changes 1000 years from now is silly, THE SUN WILL STILL BE IN THE
SKY and that's what a time zone offset basically reflects. And while

Yes, that's what the offset reflects. However, the DST changes reflect
the random whims of idiot politicians.

You're absolutely correct, it sucks and its broken. However, you maintain a
date/time library which deals with time zones. You have to deal with the
reality. Full stop.

If you just want an offset, use a static offset like '-0500'. That will be
fast, since there's no DST rules to deal with.

I, in fact, don't want an offset at all. I just want a DateTime object
representing the date I gave it. Why is it calculating the offset just to
instantiate? Can't it wait until I ask for it?

Another simple optimization would be to cache what the latest Olsen
entry is and then just not bother looking beyond that.

That doesn't make any sense. The last Olson entry is purely arbitrary
based on how many years of pre-calculation the module ships with, and when
I happen to generate it.

Or do you mean the offset without DST? Then someone else will complain
that it's broken at some arbitrary date (like 11 years out).

Ok, maybe I'm missing something here. If I hand you something like "July 9th,
2009 America/Chicago" and ask what the offset is taking into account DST you
look at the last DST rule before that date and apply it. Let's say the last
rule change was 2007 (which I think it was) so you look at that and apply it
and that's that, right?

Why would the algorithm be any different for 3009? What's all this extra
calculation you're talking about? Are you generating rules for every year up
to 3009 or something? Wouldn't that just be repeating the same calculation
over and over?

For people who need to calculate far future dates, there are other
solutions (UTC or some other fixed offset) that work. But either way, you
as the user need to make a decision about what you want. I can't make that
decision for you, I just provide the options.

If you want to take a stab at optimizing the changes generation, that's
fine with me, but personally I don't think it's wortwhile, since there's
no sane use case for Olson time zones in the far future.

Look, all I know is every other datetime library that goes past 2038 doesn't
take 10 seconds to make this calculation. Something is wrong here.

Somewhat apropos, for dates far in the past, before time zones, I've
seen 64 bit Linuxen use the lat/long for the city in question which is
pretty clever.

A DT::TZ::LatLong would be very cool.

Actually, the Olson database approximates this, since pre-modern times it
uses local mean time, which is an offset based off the lat/long of the
named city.

That sounds like it.

The past has a vote, but not a veto.
-- Mordecai M. Kaplan

[autarch]

From mschwern@cpan.org (@schwern) on 2009-07-08 19:57:25:

I've dug into the DateTime::TimeZone code and now I understand why we're
talking past each other. I'm talking in terms of Olsen rules database
(after this year this time zone changes to DST at 2am on the 1st Sunday)
and you're talking in terms of these "span" things which cache the
calculation, one for every DST change. Now I see why you'd think it has
to be expensive and why you'd think it was untenable to store.

Since they're linear, and since the only way to search through them is
binary, I can see why TimeZone is locked into having to generate them
all and why it can't just leave them on disk. What are they indexed by?
Julian days? What's "rd" as in "ymd2rd"?

I understand the approach, but there's got to be a better way to do it
that doesn't involve calculating each DST change up to the current year.
Cached perhaps. I also think its possible to make use of the fact that
a DateTime object already knows what year it is to perhaps just cache
this all in a DBM file.

[autarch]

From autarch@urth.org (@autarch) on 2009-07-08 21:21:33:

On Wed, 8 Jul 2009, Michael G Schwern via RT wrote:

  Queue: DateTime

Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=47671 >

I've dug into the DateTime::TimeZone code and now I understand why we're
talking past each other. I'm talking in terms of Olsen rules database
(after this year this time zone changes to DST at 2am on the 1st Sunday)
and you're talking in terms of these "span" things which cache the
calculation, one for every DST change. Now I see why you'd think it has
to be expensive and why you'd think it was untenable to store.

Since they're linear, and since the only way to search through them is
binary, I can see why TimeZone is locked into having to generate them
all and why it can't just leave them on disk. What are they indexed by?
Julian days? What's "rd" as in "ymd2rd"?

They're indexed by UTC days.

I understand the approach, but there's got to be a better way to do it
that doesn't involve calculating each DST change up to the current year.
Cached perhaps. I also think its possible to make use of the fact that
a DateTime object already knows what year it is to perhaps just cache
this all in a DBM file.

Probably the quickest, most efficient way would be to have the time zone
generator spit out some code that encapsulates the decisions that need to
be made, one when given UTC values, another for local. This would require
some changes to DateTime as well, since right now it passes in just the
rata die day and seconds.

-dave

/============================================================
http://VegGuide.org http://blog.urth.org
Your guide to all that's veg House Absolute(ly Pointless)
============================================================/

[autarch]

From schwern@pobox.com on 2009-07-08 23:43:42:

autarch@urth.org via RT wrote:

<URL: https://rt.cpan.org/Ticket/Display.html?id=47671 >

On Wed, 8 Jul 2009, Michael G Schwern via RT wrote:

  Queue: DateTime

Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=47671 >

I've dug into the DateTime::TimeZone code and now I understand why we're
talking past each other. I'm talking in terms of Olsen rules database
(after this year this time zone changes to DST at 2am on the 1st Sunday)
and you're talking in terms of these "span" things which cache the
calculation, one for every DST change. Now I see why you'd think it has
to be expensive and why you'd think it was untenable to store.

Since they're linear, and since the only way to search through them is
binary, I can see why TimeZone is locked into having to generate them
all and why it can't just leave them on disk. What are they indexed by?
Julian days? What's "rd" as in "ymd2rd"?

They're indexed by UTC days.

Presumably this is the number of UTC days since some epoch? What's the epoch?

I understand the approach, but there's got to be a better way to do it
that doesn't involve calculating each DST change up to the current year.
Cached perhaps. I also think its possible to make use of the fact that
a DateTime object already knows what year it is to perhaps just cache
this all in a DBM file.

Probably the quickest, most efficient way would be to have the time zone
generator spit out some code that encapsulates the decisions that need to
be made, one when given UTC values, another for local. This would require
some changes to DateTime as well, since right now it passes in just the
rata die day and seconds.

Ah HA! That's the mysterious "rd".

Alligator sandwich, and make it snappy!

[autarch]

From autarch@urth.org (@autarch) on 2009-07-09 01:32:56:

Can we take this conversation to the datetime@perl.org list?

/============================================================
http://VegGuide.org http://blog.urth.org
Your guide to all that's veg House Absolute(ly Pointless)
============================================================/