Closed Bug 1828326 Opened 1 year ago Closed 10 months ago

Improve performance of date algorithms

Categories

(Core :: JavaScript Engine, enhancement, P5)

Firefox 111
enhancement

Tracking

()

RESOLVED FIXED
117 Branch
Tracking Status
firefox117 --- fixed

People

(Reporter: cassio.neri, Assigned: cassio.neri)

References

(Blocks 1 open bug)

Details

Attachments

(1 file)

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

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.

Component: Untriaged → JavaScript Engine
Product: Firefox → Core

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

Assignee: nobody → cassio.neri
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Blocks: sm-runtime
Severity: -- → S4
Priority: -- → P5
Pushed by andre.bargull@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/e0b04ffcf96f
Tenfold performance improvement of date calculations. r=anba

Backed out for date calculations related wpt failures.

Flags: needinfo?(cassio.neri)
Flags: needinfo?(andrebargull)

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.

Flags: needinfo?(cassio.neri)

(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.

Flags: needinfo?(andrebargull)

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

(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.

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

Flags: needinfo?(andrebargull)

(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.

Flags: needinfo?(andrebargull)
Pushed by andre.bargull@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/54ebf8bd2e11
Tenfold performance improvement of date calculations. r=anba,emilio,smaug
Status: ASSIGNED → RESOLVED
Closed: 10 months ago
Resolution: --- → FIXED
Target Milestone: --- → 117 Branch
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: