1828326 - Improve performance of date algorithms

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P5)

Description

[Cassio Neri]

User Agent: Mozilla/5.0 (X11; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/111.0

Steps to reproduce:

I've looked at the implementations of YearFromTime, MonthFromTime and DateFromTime in js/src/jsdate.cpp and I've suspected that they had poor performance due to the large number of branches and the fact that they operate on double values.

An alternative algorithm described in [1] is branch free and uses only integer arithmetic. So far it has performed better than any other alternative that I could compare against and it has been implemented in the Linux Kernel [3-4], GCC's chrono [5] and in .NET 7 [6].

I've benchmarked the original implementations against my proposed alternatives and the results show tenfold performance improvements. (See [2].)

I have a patch ready for consideration.

Disclaimer: I'm an author of [1] and the implementer of the algorithm in the Linux Kernel and in GCC's chrono. I've also provided advise on .NET 7's implementation.

References.

[1] Neri C, Schneider L., "Euclidean affine functions and their
application to calendar algorithms."
Softw Pract Exper. 2023;53(4):937-970. doi: 10.1002/spe.3172
https://onlinelibrary.wiley.com/doi/full/10.1002/spe.3172

[2] https://quick-bench.com/q/yqkfx__BGCr_7Y6qBEDpMx9KSig

[3] https://tinyurl.com/ydyaf4nb

[4] https://tinyurl.com/44dv9b75

[5] https://tinyurl.com/bde4h9uf

[6] https://tinyurl.com/cvnu2h92

Comment 1

[BugBot [:suhaib / :marco]]

The Bugbug bot thinks this bug should belong to the 'Core::JavaScript Engine' component, and is moving the bug to that component. Please correct in case you think the bot is wrong.

Comment 2

[Cassio Neri]

Attachment: Bug 1828326 - Tenfold performance improvement of date calculations. r=#spidermonkey-reviewers

The original implementations contain unnecessary branches and operate on
double values. The new implementations, based on [1], are branch free on
x86_64 and mostly use integer arithmetic.

All tests pass and, in addition, [2] contains an exhaustive test that checks
all required dates, that is, in [-8.64e15 / msPerDay, 8.64e15 / msPerDay]
(as per ES5 15.9.1.1).

[1] Neri C, Schneider L., "Euclidean affine functions and their
application to calendar algorithms."
Softw Pract Exper. 2023;53(4):937-970. doi: 10.1002/spe.3172
https://onlinelibrary.wiley.com/doi/full/10.1002/spe.3172

[2] https://godbolt.org/z/oPvxzY6vx

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/e0b04ffcf96f
Tenfold performance improvement of date calculations. r=anba

Comment 4

[Serban Stanca [:SerbanS]]

Backed out for date calculations related wpt failures.

• Backout link
• Push with failures
• Failure Log
• Failure line: Assertion failure: StartOfTime - 2 * msPerDay <= t && t <= EndOfTime + 2 * msPerDay, at /builds/worker/checkouts/gecko/js/src/jsdate.cpp:243

Comment 5

[Cassio Neri]

I understand the crash and will commit a fix soon (likely on Monday as UK bank holiday.)

Long story short: my patch replaces the internals of JS::YearFromTime, JS::MonthFromTime, and JS::DayFromTime. These functions take a double time argument representing the number of milliseconds since 1970-Jan-01. ECMAScript 2024 (and earlier), 21.4.1.1, specifies that time should be in the range [-8.64e-15, 8.64e15]. I made my algorithm to work on a slightly larger range and added an assert for that. It turns out that this function is called outside SpiderMonkey for values outside the range and the assert fired.

My current plan is as follows. I'll make the algorithm to work on a much larger range (more than 5x what ECMAScript 2024 prescribes) and if time is outside this range, instead of asserting, the three functions above will return NaN as they currently do when std::isfinite(time) == false.

Comment 6

[André Bargull [:anba]]

(In reply to Cassio Neri from comment #5)

My current plan is as follows. I'll make the algorithm to work on a much larger range (more than 5x what ECMAScript 2024 prescribes) and if time is outside this range, instead of asserting, the three functions above will return NaN as they currently do when std::isfinite(time) == false.

I don't think it's actually needed to increase the range, let's just return NaN for values outside the range [-8.64e-15, 8.64e15] right away in all four public functions (JS::YearFromTime, JS::MonthFromTime, JS::DayFromTime, and JS::DayWithinYear). WeekInputType::ConvertNumberToString is currently able to call these functions with any (non-fractional, finite) double value, so even when increasing the range to 5 x [-8.64e-15, 8.64e15], WeekInputType::ConvertNumberToString can still use values outside the allowed range.

Comment 7

[Cassio Neri]

I've pushed a fix to my patch. Please review.

Comment 8

[Cassio Neri]

(In reply to André Bargull [:anba] from comment #6)

I've just pushed the patch with the plan I suggested. I'll follow your suggestion in a subsequent commit. It's going to be easy because my current patch implements function IsValidInput and sets JS::YearFromTime, JS::MonthFromTime and JS::DayFromTime to return Nan when IsValidInput(t) == false. So, I just need to change IsValidInput.

I did not change DayWithinYear but will do.

Comment 9

[Jan de Mooij [:jandem]]

André, is this ready to land? We got a question about this on Matrix.

Comment 10

[André Bargull [:anba]]

(In reply to Jan de Mooij [:jandem] from comment #9)

André, is this ready to land? We got a question about this on Matrix.

There's still a minor issue. I've added a comment to the Phabricator review.

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/54ebf8bd2e11
Tenfold performance improvement of date calculations. r=anba,emilio,smaug

Comment 12

[Noemi Erli[:noemi_erli]]

https://hg.mozilla.org/mozilla-central/rev/54ebf8bd2e11