Thanks,@axelheer. Will take a look, but in the meantime, do you know why the 64/10K case suffers a 33% regression?

@stephentoub nope, that's a bit odd and needs further investigation. Maybe the Barrett reduction backfires for smaller numbers.

@stephentoub is it of equal value to just "amend" further changes? Or has the push further commits / squash in the end process any pros?

In this case I'd suggesting adding additional commits and then squashing later. Personally, I prefer to just ammend the existing commit when the changes are small / trivial and I don't expect anyone to need to re-review, e.g. fixing up typos or making simple one-line fixes. For larger things, I prefer to have the additional commits so that it's clear to a reviewer what's changed. That's just me, though.

@stephentoub@mellinoe the two internal helpers are structures now, the reducer seems to pay off already at 256 bits -- below that an ordinary remainder is used. But I still measure that regression at 64 bits, a bit smaller but still there. I have no idea what's wrong here...

@jasonwilliams200OK a DNX console app doesn't produce an .exe. And a classic .NET 4.6 console application does not work since there are type forwards fromSystem.Runtime.Numberics toSystem.Numerics. Thus, just putting the modified DLL to the build / run directory as describedhere doesn't work.

Ah, I thought you are using coreclr:CoreRun.exe yours.exe.

@dotnet-bot test this please

Update: it seems that the currentmod implementation is faster at 64 bits, and since this is the most used operation here (if we don't use the "reducer") we have a regression. (And the "reducer" isn't that fast at 64 bits either...) But themod operation has already been replaced with#1618, because I only compared performance data ofdiv there. (I assumed no difference, because the algorithms are the same, butBigIntegerBuilder is better within this special case...) Yeah, that sucks.

Thus, I don't think right here is much more to optimize. But, I should review integer division for 64 bit numbers (for 64 bit divisors?) and prepare a separate PR when I figured out a solution.

@stephentoub What do you think?

But the mod operation has already been replaced with#1618, because I only compared performance data of div there

Just so I understand, you're saying we already took a regression in the previous change, and that's what you'll be looking to repair in a subsequent one? Can you quantify that regression?

Just so I understand, you're saying we already took a regression in the previous change, and that's what you'll be looking to repair in a subsequent one?

Yeah. If that's a problem we can rollback this stuff and wait until I figured out why it gets stuck at 64 bits.

Can you quantify that regression?

It's the same situation formod as here formodpow, only a regression at 64 bits, but about 80%.

I finally rewrote the integer division, I just combined the algorithms ofBigIntegerBuilder andBigIntegerCalculator.Bonus: no more allocations within integer division.

The performance regression seems to be fixed now:

ModPow

I'm still not happy with the division code, maybe I tweak it a bit tomorrow.

@stephentoub since the last commit the temporary memory of buffers can be shared between them, which means n / 2 - 1 less allocations (okay, just 3 instead of 4 in our case). I'm quite sure doing it with less allocations isn't possible.

Agreed?

Also, I know we don't have any formal performance harnesses set up, but are your perf tests checked in anywhere? If not, could you please add them? You could check them in as unit tests with an [ActiveIssue("PerfTest")] or something like that for now, until we have a better performance-measurement system in place.

@stephentoub thanks, I pushed a few changes addressing your input so far. For your debug / release concern I don't came up with a solution, maybe you've an idea what I should do? The performance tests I've made are based on a very primitive console app (I linked to its gist in the PR message), it's far from a bunch of unit tests. If you want me to check in that code (although I don't think it's that exciting), where? If you want me to write some tests based on it, how?

For your debug / release concern I don't came up with a solution, maybe you've an idea what I should do?

What is the time distribution like amongst the various tests? Are there any we could move to be [OuterLoop] such that we'd be able to always use the 32 value, still have reasonably good inner-loop test coverage, have that inner-loop coverage run relatively quickly, but still have the full suite available to run as part of outer loop?

If you want me to write some tests based on it, how?

I was thinking you could do something like this:

1. Create a PerformanceTests.cs file in the tests project.
2. Add to it one [Fact] per perf test, something like:

[Fact][ActiveIssue("PerformanceTest")]publicstaticvoidModPow(){    ...// most of the contents of your existing console test for ModPow}

Then when someone wants to run the test, they can just remove the [ActiveIssue] attribute, or something like that. And it should hopefully make it easier for us to promote these to real and harnessed performance tests when we have the infrastructure available publically.

Is that reasonable? I was aiming for something easy for you to do and with minimal ceremony.

What is the time distribution like amongst the various tests?

JustModPow3LargeInt is already a bit slow for values < 32.

Are there any we could move to be [OuterLoop] such that we'd be able to always use the 32 value

What doesOuterLoop mean? I didn't find any documentation on it. Note that we don't have tests for >= 32 values -- if I remove the debug / release stuff, we won't cover the reducer code. And skipping the whole reducer code for an "ordinary" test run... ?

I might add, that the changed behavior should be very harmless, it's just a threshold when to switch to the "more sophisticated" code, which doesn't depend on that value. On the contrary, if it works even for smaller values, it's a good thing.

I was thinking you could do something like this [...]

I see, I can add that for all those operations, but I'd prefer to do that separately on a subsequent date.

By the way, I did more cleanup on the "modpow" code based on your inputs and will push that shortly.

What does OuterLoop mean?

We currently have two main classes of tests. The first, called "inner loop", are meant to be fast, do basic validation, and run whenever you do a build locally or as part of CI on the server. The second, called "outer loop", are meant to be more robust and are ok to take longer; these don't run by default when you build locally, nor as part of normal CI runs... we have a special job on the server that runs them a few times a day. You can also run them locally with xunit by not passing "-notrait category=outerloop" on the command-line (this argument is specified by default when you do a test run locally).

Note that we don't have tests for >= 32 values -- if I remove the debug / release stuff, we won't cover the reducer code

That feels like a gap... doesn't that mean that the reducer stuff won't be used at all when tests are run on release builds?

it's just a threshold when to switch to the "more sophisticated" code

That also means that we're not testing the normal algorithm in debug for values between 8 and 32 bits, yeah that's the algorithm we'll be using on that range in production. That feels wrong.

How important is it to performance that ReducerThreshold be a const? If it were, for example, a static int that was read each time it was needed, would that be measurable? If that wouldn't affect anything, we could potentially test things by mucking with the threshold value from the tests via reflection at runtime. Not ideal, for sure, but could be the least evil thing.

I can add that for all those operations, but I'd prefer to do that separately on a subsequent date.

That's fine, thanks.

Hm, we've that debug / release thing already three times: multiply, square, modpow.

I can remove this "trick" and change the thresholds to static values as you've suggested, which should work since xunit runs the tests at class level single threaded, and add further tests / extend existing tests to change the thresholds accordingly. That should do it, yeah. Not ideal, but better than the current one.

@stephentoub the last commit should test as discussed. I actually like that solution now. The (new) tests for three big values becameOuterLoop tests, since they only add coverage for a very small function but take a long time.

Left a few minor comments, but otherwise LGTM. Feel free to squash when ready.

LGTM. Thanks for doing this,@axelheer.

@KrzysztofCwalina, look good to you?

Looks good. Thanks!

@dotnet-bot test this please

Thanks!