Optimize chinese_based and astronomy

[atcupps]

There are many places in chinese_based and astronomy which involve searching for the next of a given astronomical phenomenon. For example, fn winter_solstice_on_or_before in chinese_based, with the goal of finding the first winter solstice on or before a given RataDie, searches for the date near the given RataDie at which the solar longitude first exceeds 270 degrees. This is done with a while loop which goes through each day and compares the solar longitude to 270 degrees.

There are several similar functions which search for astronomical events in this way; most of these are based off Calendrical Calculations functions which do this, however @echeran mentioned that the book's authors make clear these algorithms are not optimized. To improve the efficiency of lunar calendars now being added to icu_calendar, we should examine and optimize these functions where possible.

This is separate to the possible optimizations we could make by caching certain information as part of ArithmeticDate or ChineseBasedDateInner/ChineseDateInner.

@sotam1069 @echeran @sffc @Manishearth

[Manishearth]

cc @eggrobin, our resident expert in practical implementations of moon math

[atcupps]

I don't think this is as much of an issue for islamic since most of the math there seems to be extracted to astronomy, but @sotam1069 can give more information on that than I can

[eggrobin]

fn winter_solstice_on_or_before in chinese_based, with the goal of finding the first winter solstice on or before a given RataDie, searches for the date near the given RataDie at which the solar longitude first exceeds 270 degrees. This is done with a while loop which goes through each day and compares the solar longitude to 270 degrees.

My first guess would be to unwind the solar longitude, at which point you have reduced the problem to root finding on a monotonic function; at which point they're good algorithms for finding a zero of a function Brent.

Conveniently, the solar longitude is appears to be computed unwound using some sort of Poisson series, and then reduced to [0°, 360°[, so unwinding is trivial:

icu4x/components/calendar/src/astronomy.rs

Line 1103 in 553f49d

div_rem_euclid_f64(lambda + Self::aberration(c) + Self::nutation(moment), 360.0).1

I am out at RAI 68 next week and at UTC 176 the week after that, so it will be a while before I get back to this.

[sffc]

Also investigate whether we can use a more efficient numerical algorithm like gradient descent.

[eggrobin]

That is what I meant by

they're good algorithms for finding a zero of a function Brent

[atcupps]

I added Chinese to the benchmark tests for creating new dates in different calendars; here are the results:

Calendar	Benchmark time of try_new_..._date()
Iso	158.83 ns
Buddhist	128.88 ns
Coptic	1.0043 µs
Ethiopic	988.33 ns
Indian	366.14 ns
Julian	1.0911 µs
Gregorian	188.45 ns
Chinese	12.466 ms

While all the other listed calendars can be created on the order of hundreds of nanoseconds or of microseconds, Chinese performs much worse with 12.466 ms. This is obviously relatively very slow, but is it slow enough to be an issue? I don't have very good context to whether this speed requires optimization or not.

I think the main reason for this particular function being so much slower is the need to identify whether the current year is a leap year, something which is much harder to do in Chinese than in other calendars simply by the nature of the calendar, and I'm not sure (very genuinely not sure, I will investigate further) how much of that can be optimized versus just being a result of its inherent complexity.

@sffc @Manishearth @echeran

[sffc]

12 ms is definitely on the scale where we should be worried. The line I like to draw is that we need to render a spreadsheet of data at 120 fps (frames per second). For dates and times, let's say that we want a ballpark of 1000 dates formatted at 120 fps, which gives us about 8 µs per item. Let's see how close we can get to that.

[sffc]

Also: in my opinion, the critical path operation should be converting from ISO to the calendar and then loading the formattable pieces from it (FormattableYear, etc).

[atcupps]

So just to be clear, creating an ISO date -> converting to a calendar -> getting the FormattableYear/Month and day via .year(), .month(), and .day_of_month() should be done in < 8 microseconds? Or is it a different path you had in mind

[Manishearth]

Yep.

[atcupps]

I misread the function, the table of values is actually for:

• Creating a new date (try_new_..._date())
• Creating an ISO date
• Converting from ISO to the calendar
• Adding a DateDuration to a date x2
• Getting year, month, and day of month x2
• Conversion to ISO x2

So it's doing pretty much the complete path and some more.

[Manishearth]

Ah, I would have a separate benchmark for creation vs arithmetic vs getting formatting data

[Manishearth]

I suspect the DateDuration math is the really slow part and we have a path to optimize it

[atcupps]

I used the debugger to trace through functions like winter_solstice_on_or_before and num_of_new_moon_at_or_after, and it turns out the approximations used in these functions are very good - for all values I put in as arguments, these functions only iterated through the while loop 1-3 times. I don't know if there is much room for optimizing these using things like numerical methods; I think it will need to be done using different approaches.

[atcupps]

I ran the function new_moon_before (which calls num_of_new_moon_at_or_after) for Moments -100000..=100000 and got the following frequencies for the number of iterations of the while loop within the fn:

Num. Iterations	Frequency
1	199734
2	267
3	0

[atcupps]

Similar table for winter_solstice_on_or_before:

Num. Iterations	Frequency
1	130395
2	69606
3	0

[atcupps]

I think I misinterpreted what these functions were doing in their searches before, and it seems like Reingold's approximations used in these functions are pretty good. However, ChineseBased calendars are still quite slow, so we should continue to investigate ways to optimize these. @Manishearth and I are planning to work with caching, as well as potentially creating a lookup table for dates near the present time to improve efficiency for most common use cases.

[sffc]

The optimizations described in this issue to the best of my knowledge are resolved. There are follow-up issues such as #3934 for the Islamic calendar and #3933 for loading cache data.