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.

Sign up for GitHub

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

Jump to bottom

Investigate using Span in BigInteger implementation #22609

Closed
axelheer opened this issue Jul 3, 2017 · 6 comments
Closed

Investigate using Span in BigInteger implementation #22609

axelheer opened this issue Jul 3, 2017 · 6 comments
Labels
area-System.Numerics Cost:M Work that requires one engineer up to 2 weeks enhancement Product code improvement that does NOT require public API changes/additions help wanted [up-for-grabs] Good issue for external contributors tenet-performance Performance related issue
Milestone
7.0.0

Comments

@axelheer
Copy link
Contributor

axelheer commented Jul 3, 2017

As already mentioned within #22387 the all-new Span should bring many benefits to BigInteger.

  • We currently use pointers to spare some index calculations (performance) and "abstract" the differences between ordinary arrays and stackalloc based stuff --> use spans instead
  • We currently copy the array containing the actual number after every operation to trim leading zeros --> use span.slice instead?
  • And maybe there's more...

We cannot get grid of unsafe code completely since there are stack-vs-heap paths based on stackalloc, but all the pointer based stuff should gracefully disappear; I think.

I'm interested to dive into this, after the summer or so.
@karelz
Copy link
Member

karelz commented Jul 4, 2017

cc @stephentoub

@stephentoub
Copy link
Member

stephentoub commented Jul 4, 2017 •
edited
Loading

We cannot get grid of unsafe code completely since there are stack-vs-heap paths based on stackalloc

If that's the only need for unsafe, you might be able to. C# may end up supporting stackalloc'ing directly into a Span, in which case it likely would not require using unsafe.

@stephentoub stephentoub changed the title BigInteger goes Span Investigate using Span in BigInteger implementation Jul 18, 2017
@ahsonkhan
Copy link
Member

If that's the only need for unsafe, you might be able to. C# may end up supporting stackalloc'ing directly into a Span, in which case it likely would not require using unsafe.

It supports this now.
https://github.com/dotnet/corefxlab/blob/master/docs/specs/span.md

Span<byte> stackSpan = stackalloc byte[100];

@msftgits msftgits transferred this issue from dotnet/corefx Jan 31, 2020
@msftgits msftgits added this to the Future milestone Jan 31, 2020
@maryamariyan maryamariyan added the untriaged New issue has not been triaged by the area owner label Feb 23, 2020
@tannergooding tannergooding added help wanted [up-for-grabs] Good issue for external contributors and removed untriaged New issue has not been triaged by the area owner labels Mar 4, 2020
@tannergooding
Copy link
Member

Marking this as up-for-grabs. Anyone should feel empowered to pick this up and prototype the improvements detailed.

@sakno sakno mentioned this issue Apr 28, 2020
Merged
8 tasks
@monojenkins monojenkins mentioned this issue Apr 29, 2020
Closed
8 tasks
monojenkins pushed a commit to monojenkins/mono that referenced this issue Apr 29, 2020
@sakno
[WIP] Spannified internals of BigInteger
8df5f13 
Proposed refactoring according with issue: dotnet/runtime#22609. The implementation plan consists of the following steps:

- [x] Replace unmanaged pointers with managed ones as well as remove unsafe code and pinning
- [x] Beautify stack allocation
- [x] Use spans wherever possible, especially for memory slicing
- [ ] Simplify (or probably remove at all) `BitsBuffer` value type
- [ ] Spannify `FastReducer` value type
- [ ] Attempt to replace some array allocations with span slicing
- [ ] Square, Multiply and bitwise operations use heap-based allocation of arrays if their length is greater than or equal to stack allocation threshold. Maybe replace it with array pooling using shared `ArrayPool<T>`?
- [ ] BMI intrinsics??

Spannified versions of internal and private static methods look pretty nice. However, I'm not sure about performance of passing span to the method. If RyuJIT uses scalar replacement then it's good news. Otherwise, maybe pass length and managed pointer to the first element as separate arguments to ensure that they passed through registers. This version was implemented in the first commit. I need advice here as well as preliminary code review because further work fully based on signatures of spannified methods.

cc @tannergooding , @stephentoub
@stephentoub stephentoub mentioned this issue Jan 13, 2021
Merged
@tannergooding tannergooding added the Cost:M Work that requires one engineer up to 2 weeks label Jan 15, 2021
@sakno
Copy link
Contributor

sakno commented Oct 8, 2021

@jeffhandley , PR has been merged so maybe we can close this issue?

@jeffhandley
Copy link
Member

Indeed! Thanks again, @sakno!! 💯

@jeffhandley jeffhandley modified the milestones: Future, 7.0.0 Oct 8, 2021
@ghost ghost locked as resolved and limited conversation to collaborators Nov 8, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
area-System.Numerics Cost:M Work that requires one engineer up to 2 weeks enhancement Product code improvement that does NOT require public API changes/additions help wanted [up-for-grabs] Good issue for external contributors tenet-performance Performance related issue
Projects
None yet
Milestone
7.0.0
Development

No branches or pull requests
9 participants
@jeffhandley @sakno @stephentoub @axelheer @karelz @maryamariyan @ahsonkhan @msftgits @tannergooding