Improve performance of date algorithms
Categories
(Core :: JavaScript Engine, enhancement, P5)
Tracking
()
Tracking | Status | |
---|---|---|
firefox117 | --- | fixed |
People
(Reporter: cassio.neri, Assigned: cassio.neri)
References
(Blocks 1 open bug)
Details
Attachments
(1 file)
(deleted),
text/x-phabricator-request
|
Details |
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
Comment 1•1 year ago
|
||
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.
Assignee | ||
Comment 2•1 year ago
|
||
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
Updated•1 year ago
|
Updated•1 year ago
|
Pushed by andre.bargull@gmail.com: https://hg.mozilla.org/integration/autoland/rev/e0b04ffcf96f Tenfold performance improvement of date calculations. r=anba
Comment 4•1 year ago
|
||
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
Updated•1 year ago
|
Assignee | ||
Comment 5•1 year ago
|
||
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•1 year ago
|
||
(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 whenstd::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.
Assignee | ||
Comment 7•1 year ago
|
||
I've pushed a fix to my patch. Please review.
Assignee | ||
Comment 8•1 year ago
|
||
(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•1 year ago
|
||
André, is this ready to land? We got a question about this on Matrix.
Comment 10•1 year ago
|
||
(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•1 year ago
|
||
Pushed by andre.bargull@gmail.com: https://hg.mozilla.org/integration/autoland/rev/54ebf8bd2e11 Tenfold performance improvement of date calculations. r=anba,emilio,smaug
Comment 12•1 year ago
|
||
bugherder |
Description
•