Fewer CalendarDateAdd/DateUntil calls during relative rounding

[arshaw]

To the extent we care about reducing calls to user-code, the relative-rounding algorithm (used by Duration::round and since/until) can be optimized for many fewer calls. I can explain in further detail if desired.

Reduced calls in tests (not comprehensive):
Branch: https://github.com/fullcalendar/test262/tree/temporal-fewer-calls-rounding-rel
Diff: tc39/test262@main...fullcalendar:test262:temporal-fewer-calls-rounding-rel

temporal-polyfill's algorithm:
https://github.com/fullcalendar/temporal-polyfill/blob/2d97b7a038b99b0d491e79ed903f36f5275cb365/packages/temporal-polyfill/src/internal/round.ts#L311
(sorry for the code dump... I can explain it more thoroughly in the future...)

[ptomato]

@arshaw I did not originally realize this, but when I went to make a test implementation of this, it seems that it would not be possible without #2758. Am I correct about this? If so, I think we should absorb it into that PR, as it's essentially an optimization that you discovered while reviewing it.

[arshaw]

Hi @ptomato, upon looking at #2758 more closely, yes I feel that optimizing relative rounding (this ticket) should be done in on top of #2758.

You'll want to refactor these code blocks:

• within DifferenceZonedDateTimeWithRounding, calls to...
  • RoundDuration
  • AdjustRoundedDurationDays
  • BalanceDateDurationRelative
• within DifferencePlainDateTimeWithRounding, calls to...
  • RoundDuration
  • BalanceTimeDuration
  • BalanceDateDurationRelative

[arshaw]

Status update: While attempting to make spec-like pseudocode to describe my algorithm, I encountered two bugs cataloged in these TODO list items for improved test coverage:

• Improve test coverage for balancing up to weeks (when year/month) #2813
• Improve test coverage for AdjustRoundedDurationDays #2814

I'm reworking the algorithm a bit to fix these bugs and making things more DRY in the process. It's taking a while because many things are interconnected when super-DRY: Duration::total(), Duration::round(), Duration::add(), ZDT/PDT/PD::until/since.

It'd be great to get some feedback on bug #2811 because, believe it or not, it will affect how I DRY-up the various utilities.

This might take few more days, so if you want to deliver something for the April 2nd meeting, I'd recommend submitting #2758. This ticket depends on that, but no vice-versa.

[arshaw]

I'm having further delays because of this (problem in my polyfill, incidentally also wrong in spec):

• Duration::round incorrectly bubbling time units for DST gaps #2816

Still working on coming up w/ some bug-free pseudocode...

[arshaw]

I finally have the pseudo-code written for this. Please take a look and lemme know what you think @ptomato and others. I plan to implement this when I DRY up all duration arithmetics. It's already implemented in fullcalendar's temporal-polyfill.

https://gist.github.com/arshaw/36d3152c21482bcb78ea2c69591b20e0

[ptomato]

I'd like to incorporate this into #2758 before starting on #2825 or #2826, because #2758 is a normative change that was already approved in February and for the stuff we will present in June I'd like to start from a clean base where we are not juggling old PRs.

Also it should make #2825 simpler since you've gotten rid of the AddDuration with zonedRelativeTo call in what was previously known as AdjustRoundedDurationDays.

I can start on it this week if that works for you.

[arshaw]

Sounds good @ptomato. I'll help with PR reviewing. After #2825 and #2826 are done, I'm available to help DRY up all arithmetic utilities.

[ptomato]

@arshaw I had a start on this today. If you have a moment I'm wondering about a few things. (If you don't, no worries, I can figure them out myself by looking at fullcalendar)

• when largestUnit is >hour (for zonedRelativeTo) or >day (for plainRelativeTo), it looks like RoundDurationRelative is meant to be called instead of RoundDuration, is that right? (so, we'd simplify RoundDuration to not take a relativeTo parameter at all)
• where does clampDuration0 come from?
• can we get a total from RoundDurationRelative as well, like we do from RoundDuration?

[arshaw]

Hi @ptomato,

1. When >hour (for zonedRelativeTo) or >day (for plainRelativeTo), the function I've named roundRelativeDuration in the gist is meant to be called, yes. For all other cases, rounding can be done via nanoseconds because unit lengths are constant. Essentially this block of the current RoundDuration. I would consider naming it something less generic, like RoundDayOrTimeDuration or something.
2. Woops, that was a typo. I corrected it in the gist.
3. It'd be possible calculate the total in the same code path, yes, but then you end up doing extra work that's discarded (what I'm calling "nudging" and "bubbling"). FullCalendar's polyfill breaks down operations into smaller composable utility functions and is able to reuse quite a lot for total. If you'd like to couple the totalling logic with the relative-rounding logic for now, it might be stepping stone to a more ideal composable solution later down the line (as an editorial change I do during the DRY-up perhaps).

[ptomato]

Status of this

I have a tentative version of this available in d988b1a (note, most of the diff is hidden by default. You have to expand ecmascript.mjs to view it.)

It's written as closely as possible to how I'd expect to write the spec text, so it's obviously a lot less elegant than the gist 😅

Test262 tests are here: tc39/test262@385a621
Most of them pass. 16 do not. I've only adjusted the test262 tests that have to do with user calls, so far. So the remaining failures (well, 14 of them) are caused by actual numerical changes to rounding results. These I still have to track down and debug.

There are also several FIXMEs in the code that I have to address. Addressing these may also fix the test262 tests.

Next steps

Here's what's on my to do list:

• I suspect the calculation of progress in nudgeToCalendarUnit is susceptible to floating point precision loss in some cases. I think I can rewrite it to work with integer epoch nanoseconds instead of division.
• I calculate total from progress as well and I think aside from possible FP precision loss, it's also not correct in some cases. (e.g., this, and this. I'm not sure, but my current hunch is that it has to do with the old code calculating total from fractional days, not nanoseconds. (The fullcalendar polyfill seems to get these cases wrong too.)
• I suspect endDateTime in nudgeToZonedTime could be calculated by just adding one ISO day to startDateTime avoiding the calendar call. I haven't tested this yet.
• Apparently we have no test coverage of calls to total() that would take the nudgeToZonedTime path, so I'll have to add coverage.
• There are incorrect results when rounding to smallestUnit: 'weeks'. This is probably just a bug in my implementation, because I don't see these incorrect results using the fullcalendar polyfill.
• This test fails because the rounding increment of 1e9 puts the UTC epoch nanoseconds out of the allowed range. The old code would be able to calculate this result without epoch nanoseconds. This is an obscure case and so maybe we don't care.

@arshaw If any of these items ring a bell for you, or seem obviously wrong, I'd appreciate your insights.

Goal

Ideally, the end state is one of these two:

1. We determine that the optimization does not actually cause any results to be numerically different, only user calls. In that case, we can just deprioritize the optimization for now, merge Normative: Fix Duration rounding relative to ZonedDateTime #2758 as it was already reviewed/approved, and move on to implementing Remove options parameter from Duration.p.add/subtract #2825/Remove time zone and calendar protocols and classes #2826, after which we can optimize to our hearts content because there will be no observable user calls anymore.
2. We determine that the optimization does change results numerically. In that case, we need to figure out whether those changes are (1) correct; (2) wanted. If both, then I will proceed to write the spec text corresponding to this optimization.

[arshaw]

Nice work @ptomato. Here are my responses to the specific test failures

built-ins/Temporal/Duration/prototype/round/roundingmode-*.js (8)

This is a problem when smallestUnit is weeks. You current Duration::round implementation offloads the balancing to DifferenceZonedDateTimeWithRounding and DifferencePlainDateTimeWithRounding, which does a point-to-point diff. This is great for balancing days->months->years, but if smallestUnit is weeks AND largestUnit is greater than weeks, we need to separately balance day->weeks and then months->years. This requires a three-point diffing algorithm which fullcalendar has implemented here.

built-ins/Temporal/Duration/prototype/round/dst-rounding-result.js
built-ins/Temporal/Duration/prototype/total/dst-rounding-result.js
staging/Temporal/Duration/old/total.js

These are failing because, IMO, the original algorithm was incorrect, and now the bug-free results are unexpected.
Here are the WIP test262 modifications I needed to make to these test to adapt to the more "correct" behavior:
fullcalendar/test262@fd9a0d7
fullcalendar/test262@fea3b3f

I created a bug report previously (for Duration::total only):
#2817

built-ins/Temporal/Duration/prototype/total/precision-exact-mathematical-values-4.js

FullCalendar's polyfill was failing here as well. I don't have an opinion about what the correct precision is.

built-ins/Temporal/ZonedDateTime/prototype/since/roundingincrement-non-integer.js
built-ins/Temporal/ZonedDateTime/prototype/until/roundingincrement-non-integer.js

IMO, an error should be thrown. Modified test for fullcalendar's polyfill:
fullcalendar/test262@887e0b5

built-ins/Temporal/PlainDate/prototype/since/calendar-dateadd-called-with-plaindate-instance.js
built-ins/Temporal/PlainDate/prototype/until/calendar-dateadd-called-with-plaindate-instance.js

Will go away when observable CalendarProtocol removed.

Here are my responses to your misc other comments:

I suspect endDateTime in nudgeToZonedTime could be calculated by just adding one ISO day to startDateTime avoiding the calendar call. I haven't tested this yet.

I think you're right.

Apparently we have no test coverage of calls to total() that would take the nudgeToZonedTime path, so I'll have to add coverage.

I believe nudgeToZonedTime should NEVER be called for Duration::total. It makes sense to me that it's only for Duration::round. Rounding via time units could cause a ZDT day overflow, but for Duration::total, there's no rounding, and thus no overflowing.

[ptomato]

@arshaw Thanks for the responses. This has been really helpful.

endDateTime in nudgeToZonedTime: implemented, but didn't actually save a calendar call because AddDateTime would already avoid the call if years/months/days were 0.

Re. #2817, I'll have a closer look at these and respond there. At first glance, it seems you might be right about the number of hours being calculated from the wrong day.

I believe nudgeToZonedTime should NEVER be called for Duration::total. It makes sense to me that it's only for Duration::round. Rounding via time units could cause a ZDT day overflow, but for Duration::total, there's no rounding, and thus no overflowing.

Makes sense, thanks.

built-ins/Temporal/ZonedDateTime/prototype/since/roundingincrement-non-integer.js
built-ins/Temporal/ZonedDateTime/prototype/until/roundingincrement-non-integer.js

IMO, an error should be thrown.

🤷 I guess, since these intrinsically have a relativeTo? But I don't care all that much. "rounding increment 1 billion" is an entirely unimportant use case. I guess if you still want it you can take the duration and round it yourself while omitting relativeTo.

built-ins/Temporal/Duration/prototype/round/roundingmode-*.js (8)

This is a problem when smallestUnit is weeks. You current Duration::round implementation offloads the balancing to DifferenceZonedDateTimeWithRounding and DifferencePlainDateTimeWithRounding, which does a point-to-point diff. This is great for balancing days->months->years, but if smallestUnit is weeks AND largestUnit is greater than weeks, we need to separately balance day->weeks and then months->years. This requires a three-point diffing algorithm which fullcalendar has implemented here.

I think there must be more going on with these.

I'm using

const d = new Temporal.Duration(5, 6, 7, 8, 40, 30, 20, 123, 987, 500);
const relativeTo = new Temporal.PlainDate(2020, 4, 1);
const result = d.round({ smallestUnit: 'weeks', relativeTo });

as a test case, adapted from the test262 test.

• Current main branch of proposal-temporal: P5Y6M8W
• Fullcalendar polyfill: P5Y6M8W
• Previous state of branch, with DifferencePlainDateTimeWithRounding: P5Y7M4W
• Current state of branch: P5Y7M1W

You could argue that the P5Y6M8W result is correct (and I did for a long time). But we opened #2728 about this because it still resulted in cases that people found 'unnatural'. I resolved #2728 when it seemed like DifferencePlainDateTimeWithRounding/DifferenceZonedDateTimeWithRounding produced results that were more 'natural'.

The original duration represents a span of 2067 days from that relativeTo. Rounded to P5Y7M4W it is 2068 days, i.e. rounded 1 day up. Rounded to P5Y6M8W it is 2065 days, i.e. rounded 2 days down.

All that said, I think that in no case is P5Y7M1W correct. P5Y7M1W is 2047 days, or rounded by 20 days! So there must be a bug in my interpretation of the algorithm.

[ptomato]

Current state of this is in 2845e80 (with corresponding modifications to tests in ptomato/test262@12a9cd8; the tests are a work in progress and still need a few tweaks/additions).

I fixed a few things that were unambiguously bugs. The weeks rounding problem I fixed by adding a special case for weeks to NudgeToCalendarUnit, to compensate for the fact that Fullcalendar's diffing algorithm is different.

I also am convinced that #2817 is correct, although this change doesn't entirely sit well with me:

const duration = new Temporal.Duration(0, 1, 0, 15);
let relativeTo = new Temporal.ZonedDateTime(
  951991200_000_000_000n /* = 2000-03-02T10Z */,
  'America/Vancouver'
); /* = 2000-03-02T02-08 in local time */
const result = duration.total({ unit: 'months', relativeTo });
  // Previously: 1.5
  // New: 1.4993045897079276

I suppose this is technically correct because the month lasts 1 hour less, but seems unintuitive. However, if you want the intuitive result, then use a PlainDate relativeTo, I guess?

I'll proceed to finish up the tests and work on the spec text for this. If anyone has time to take a look at the reference code from which I will build the spec text, I'd much appreciate that. Hopefully we can land #2758 by mid-next week.

[ptomato]

If reviewing, best to look at the current state of #2758.

[ptomato]

Addressed as part of @arshaw's review comments on #2758.