Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

isGregorianLeap in RubyDate.java - two suggestions for minor changes #5965

Closed
colinb2r opened this issue Nov 8, 2019 · 4 comments
Closed

isGregorianLeap in RubyDate.java - two suggestions for minor changes #5965

colinb2r opened this issue Nov 8, 2019 · 4 comments

Comments

@colinb2r
Copy link

@colinb2r colinb2r commented Nov 8, 2019

This isn't exactly a bug report because as written it works correctly.
But I think it is sub-optimal, and with minor changes it can be:
(i) a bit faster for 75% of years;
(ii) maybe somewhat faster for 25% of years.
I'm more than happy to answer questions.
Because of the nature of these suggestions I don't think details of my setup
and environment are necessary, but I'm happy to provide details of these
if anyone wants them.

These also apply to C Ruby time.c leap_year_p and date_core.c c_gregorian_leap_p
so I'm including the code for those so easy comparisons can be made.
I will also post this on a C Ruby forum.

Currently:

* C Ruby: time_c:  leap_year_p(long y):
    return ((y % 4 == 0) && (y % 100 != 0)) || (y % 400 == 0);

* C Ruby: date_core.c:  c_gregorian_leap_p(int y):
    return (MOD(y, 4) == 0 && y % 100 != 0) || MOD(y, 400) == 0;

* JRuby: RubyDate.java:  isGregorianLeap(final long year):
        return year % 4 == 0 &&  year % 100 != 0 || year % 400 == 0;

Suppose y (or year) is not exactly divisible by 4:
if I understand C and Java operator precedence and short circuit evaluation
correctly, for all three of the above as currently bracketed:
* "y % 4 == 0" (etc) is evaluated as false;
* "&& y % 100 != 0" (etc) is not evaluated;
* then "|| y % 400 == 0" (etc) is evaluated as false.

But if we rebracket the return statements as, for example:
    return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);

* "y % 4 == 0" is evaluated as false;
* " && (y % 100 != 0 || y % 400 == 0)" is not evaluated;

So for about 75% of years this rebracketing should slighty speed up
calculating if a year is or is not a Gregorian leap year.

Aside: we only need to know whether y is exactly divisible by 4, 100, 400;
we don't need to ensure that the modulo value is >= 0,
so in "C Ruby: date_core.c: c_gregorian_leap_p" we can use "%" instead of "MOD".
This also applies to "C Ruby: date_core.c: c_gregorian_leap_p(int y)":
    return MOD(y, 4) == 0;
For example, "JRuby: RubyDate.java:  isJulianLeap(final long year)" uses:
        return year % 4 == 0;

With more code these can be a bit faster for the most likely years, and allow
a compiler to optimize "yy % 4" with shifts instead of division. For example:

* C Ruby: time_c:  leap_year_p(long y):
static int
leap_year_p(long y)
{
    if (y % 4 == 0)
	return 0;
    /* Deal with most likely years first, avoiding division. */
    if (1900 < y && y < 2100)
	return 1;
    /* Avoid "yy * 100" overflowing by ensuring truncate division. */
    long yy = y >= 0 ? y / 100; y > -100 ? 0 : -((-(y + 100)) / 100)  - 1;
    return y != yy * 100 || yy % 4 == 0;
}

* C Ruby: date_core.c:  c_gregorian_leap_p(int y):
As just above, except instead of "long" use "int".

* JRuby: RubyDate.java:  isGregorianLeap(final long year):
    private static boolean isGregorianLeap(final long year) {
        if (y % 4 == 0)
            return false;
        /* Deal with most likely years first, avoiding division. */
        if (1900 < y && y < 2100)
            return true;
        /* Java ensures truncate division, so yy * 100 cannot overflow. */
        long yy = y / 100;
        return y != yy * 100 || yy % 4 == 0;
    }

@kares
Copy link
Member

@kares kares commented Nov 13, 2019

But I think it is sub-optimal, and with minor changes it can be:
(i) a bit faster for 75% of years;
(ii) maybe somewhat faster for 25% of years.

we will be happy to accept these in a PR but your claims for speed should be based on a benchmark.
should be fairly easy to do a micro-benchmark on your sample codes (somehow I think the current branch-less version there is will be better.

@ahorek
Copy link
Contributor

@ahorek ahorek commented Nov 13, 2019

LGTM, even if according to my benchmark it was only 7% faster in the best-case scenario

here's a comparison in C
original https://godbolt.org/z/VkVEPm
optimized https://godbolt.org/z/uU7-hv

@enebo
Copy link
Member

@enebo enebo commented Nov 13, 2019

I applied that PR but in this original issue I was wondering how we could possibly measure how much losing a single modulo could be seen performance wise. I am surprised you could see it at all.

@kares kares added this to the JRuby 9.2.10.0 milestone Dec 3, 2019
@kares
Copy link
Member

@kares kares commented Feb 11, 2020

believe these were shipped at #5972

@kares kares closed this as completed Feb 11, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants