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

Perform arithmetic in decimal rather than BigInteger (was: Some BigInteger performance measurements) #838

Closed
willdean opened this Issue Jun 4, 2017 · 5 comments

Comments

Projects
None yet
2 participants
@willdean

willdean commented Jun 4, 2017

I was most surprised by our experience in #837, so I've done a little bit of bench-marking of the relative performance of various ways Duration does some of its stuff - and also threw-in Decimal as an alternative to BigInteger.

The results look like this:

                        Method |      Mean |      Error |    StdDev |  Gen 0 | Allocated |
------------------------------ |----------:|-----------:|----------:|-------:|----------:|
   DurationFromNanosecondsLong |  39.98 ns |  0.8061 ns | 0.8626 ns |      - |       0 B |
 DurationFromNanosecondsBigInt | 518.35 ns | 10.2473 ns | 9.0840 ns | 0.0391 |     124 B |
               ConstructBigInt | 493.81 ns |  4.9034 ns | 4.3467 ns | 0.0448 |     144 B |
                 ConstructLong |  36.76 ns |  0.5417 ns | 0.5067 ns |      - |       0 B |
              ConstructDecimal | 254.47 ns |  2.8259 ns | 2.6433 ns |      - |       0 B |

The two 'DurationFromxxx' methods are using NodaTime's Duration constructors, and the three 'Construct' methods are really the innards of the Duration.FromNanoseconds methods, implemented with BigInt, long and Decimal respectively.

I have not bothered to check any of this for correctness - obviously BigInteger goes places that long doesn't, but it's very slow getting there.

I guess, though I haven't tried it, that many uses of BigInteger could be got rid of if there was a desire to do this - this would be a very direct trade-off of clean, simple code against performance. With a 12:1 perf advantage this might feel worthwhile?

This isn't just pointless micro-bench-marking, there are clearly situations that run through these paths are lot, and even if in #837 the threshold between fast and slow gets tweaked to avoid the slow path more often, it's still going to be very slow when you do hit it.

@jskeet

This comment has been minimized.

Show comment
Hide comment
@jskeet

jskeet Jun 6, 2017

Member

#837 will be fixed in a way that doesn't require BigInteger arithmetic at all (see #841) but it's interesting to see that decimal is faster than BigInteger. We used to (2.0 prereleases) use decimal instead of BigInteger, but BigInteger is a more reasonable external representation... that doesn't stop us using decimal internally where it would help.

Member

jskeet commented Jun 6, 2017

#837 will be fixed in a way that doesn't require BigInteger arithmetic at all (see #841) but it's interesting to see that decimal is faster than BigInteger. We used to (2.0 prereleases) use decimal instead of BigInteger, but BigInteger is a more reasonable external representation... that doesn't stop us using decimal internally where it would help.

@willdean

This comment has been minimized.

Show comment
Hide comment
@willdean

willdean Jun 6, 2017

@jskeet Thanks for that - I think Decimal (which I think is a 64.64 format) is probably a closer match for what you're doing really (effectively a sort of 32.64). The fact that BigInteger does heap allocation seems really unattractive for NodaTime. I think 'Big' is meant to imply >>64, not 96 :-)

I saw the bit in an issue somewhere about BigInteger not expressing negative numbers being a clearer signal of intent than Decimal, which is nice but I personally I wouldn't want to pay much performance penalty for that.

willdean commented Jun 6, 2017

@jskeet Thanks for that - I think Decimal (which I think is a 64.64 format) is probably a closer match for what you're doing really (effectively a sort of 32.64). The fact that BigInteger does heap allocation seems really unattractive for NodaTime. I think 'Big' is meant to imply >>64, not 96 :-)

I saw the bit in an issue somewhere about BigInteger not expressing negative numbers being a clearer signal of intent than Decimal, which is nice but I personally I wouldn't want to pay much performance penalty for that.

@jskeet

This comment has been minimized.

Show comment
Hide comment
@jskeet

jskeet Jun 6, 2017

Member

Not negative numbers: non-integer numbers. BigInteger is overkill but does emphasize "this is an integer" - whereas decimal is more "this is a floating point number where it's important that it's a floating decimal point", which is inappropriate. What we really want is Int96 or Int128 of course :)

If we do all the internal arithmetic in decimal, we should be fine - the public methods accepting/returning BigInteger are really there for completeness; I don't expect them to be used very often. (And I can check that we're not using them internally.)

Member

jskeet commented Jun 6, 2017

Not negative numbers: non-integer numbers. BigInteger is overkill but does emphasize "this is an integer" - whereas decimal is more "this is a floating point number where it's important that it's a floating decimal point", which is inappropriate. What we really want is Int96 or Int128 of course :)

If we do all the internal arithmetic in decimal, we should be fine - the public methods accepting/returning BigInteger are really there for completeness; I don't expect them to be used very often. (And I can check that we're not using them internally.)

@willdean

This comment has been minimized.

Show comment
Hide comment
@willdean

willdean Jun 6, 2017

@jskeet Oh right - I must have misread that - makes more sense, thanks. As you say an Int128 would be useful, though I think time is about the only earthly property that ever needs so much dynamic range to express so there may not be much appetite for such a thing...

I have a 10 year old Win CE-based product which needs 100ps resolution, so brace yourself for the disappointment when people start complaining that 1ns isn't fine enough for serious applications and you have to find a new format for NT3.

I'll close this now as it's just info.

willdean commented Jun 6, 2017

@jskeet Oh right - I must have misread that - makes more sense, thanks. As you say an Int128 would be useful, though I think time is about the only earthly property that ever needs so much dynamic range to express so there may not be much appetite for such a thing...

I have a 10 year old Win CE-based product which needs 100ps resolution, so brace yourself for the disappointment when people start complaining that 1ns isn't fine enough for serious applications and you have to find a new format for NT3.

I'll close this now as it's just info.

@willdean willdean closed this Jun 6, 2017

@jskeet jskeet reopened this Jun 6, 2017

@jskeet

This comment has been minimized.

Show comment
Hide comment
@jskeet

jskeet Jun 6, 2017

Member

Reopened this as a good placeholder for "let's do arithmetic in decimal".

As for picosecond precision: eek... I'll have to keep hoping that's not a sufficiently common feature request. I don't want to go through all that work again!

Member

jskeet commented Jun 6, 2017

Reopened this as a good placeholder for "let's do arithmetic in decimal".

As for picosecond precision: eek... I'll have to keep hoping that's not a sufficiently common feature request. I don't want to go through all that work again!

@jskeet jskeet changed the title from Some BigInteger performance measurements to Perform arithmetic in decimal rather than BigInteger (was: Some BigInteger performance measurements) Jun 6, 2017

@jskeet jskeet closed this in #851 Jun 10, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment