* Enable Regex to use SearchValues<string> in compiled / source generator TryFindNextStartingPosition
The analyzer determines a set of prefixes that can start any match, and then uses SearchValues with IndexOfAny to find the next one from that set. It's currently only enabled for case-insensitive; we need to do some more perf validation before enabling for case-sensitive.
* Address PR feedback
* Fix unit test
* Vectorize TensorPrimitives.Sin/Cos
* Clean up implementation
* Split Sin/CosOperator into separate float/double types
* Manually inline POLY_EVAL_ODD_*
And make a few things more consistent
* Address remaining PR feedback
Also move some tests to outerloop to decrease inner loop testing time
Most of them use NotSupportedException on code paths that shouldn't be used, but a few were using NotImplementedException. Just for consistency, standardize on the former.
* Fix TensorPrimitives.FusedMultiplyAdd
What we currently have for FusedMultiplyAdd is actually MultiplyAddEstimate, so rename it. Then add the actual FusedMultiplyAdd.
* Address PR feedback
* Add guard check
* Update TensorPrimitives to vectorize for size(T) is 1 or 2
It was previously only 4 or 8. This does the work previously skipped to enable the "less than largest available vector" path to handle these smaller sizes as well.
* Remove some unnecessary aggregations from small paths
* Fix copy/paste comments
* Vectorize TensorPrimitives.Cosh/Sinh/Tanh for double
This just replicates the float path to be used for double as well, expanding out the constants used to be more precise.
* Address PR feedback
* Separate float/double constants
* Fix regex lazy loop handling of backtracking state at max iteration limit
Upon entering a lazy loop, state is pushed onto the backtracking stack if the lazy loop might be backtracked into. That state is then dutifully popped off when unwinding the loop due to failure to match. However, if the loop successfully matches its maximum number of times but still fails because of a failure after the lazy loop, the state still needs to be popped off the stack, but isn't. This fixes that.
* Add a few more test variations
* Vectorize TensorPrimitives.Pow, Exp2, Exp10, Cbrt
While there are likely more accurate and better performing options that involve more code, for now we can:
- Implement Pow for now as Exp(y * Log(x))
- Implement Exp2 for now as Exp(x * Log(2))
- Implement Exp10 for now as Exp(x * Log(10))
- Implement Cbrt for now as Exp(Log(x) / 3)
- (The way Exp2M1 and Exp10M1 are already implemented, they implicitly vectorize now as well.)
* Vectorize RootN in a similar manner
* Add simple vectorized impls for Log(x, y), Log10, Hypot
* Address PR feedback
* Fix S.T.Json's ArrayPool threshold
A few code paths hardcoded "current" knowledge of the ArrayPool's upper bound. But that bound changed in .NET 6, so now STJ is allocating large byte arrays in places it could be using pooling. This fixes the limit.
Also, most STJ code paths that use the ArrayPool try to stackalloc instead, but a few paths don't. This fixes them to do so as well where possible.
* Update src/libraries/System.Text.Json/src/System/Text/Json/JsonConstants.cs
* Vectorize TensorPrimitives shift and rotate operators
This adds a new IStatefulUnaryOperator interface, which differs from IUnaryOperator simply in that its Invoke members are instance rather than static. It then copies the existing InvokeSpanIntoSpan into a new helper that's then tweaked to accept an instance of an IStatefulUnaryOperator, calling its instance members instead of its static.
That helper is then used to implement new ShiftLeftOperator, ShiftRightLogicalOperator, ShiftRightArithmeticOperator, RotateLeftOperator, and RotateRightOperator, which utilize methods on VectorXx to accelerate their implementation.
It also adds ScaleBOperator, RootNOperator, and RoundOperator implementations used with the same helper, but these currently only have scalar implementations.
* Address PR feedback
* Address PR feedback
* Add more special value tests
* Address PR feedback
ConvertToHalf and ConvertToSingle contain their own vectorized algorithms. Now that we have a framework for handling other conversions, we can move the core of their implementations into operators and then have them share the same logic as the rest of the conversions. Then ConvertToHalf/Single just delegate to ConvertTruncating and exist only as legacy.
When there's no ThenBy, we can take a more optimized path that uses the TKey's comparer directly. We already have a fast path for this case that converts the O(n log n) operation into O(n), but it employs a comparer that's much more complicated, and as that comparer is used in the inner loop, it makes a meaningful difference.
The Regex compiler and source generator weren't uncapturing captures inside of a negative lookaround. That then leads both to subsequent backreferences matching when they shouldn't.
`Vector<T>` is being updated to support 512-bit vectors. Update Enumerable.Range to support it as well. In the future hopefully this can be replaced by a method that'll just do the "right thing" regardless of vector size.
* Simplify regex code gen for whitespace search
Rather than emitting a custom helper, we can just use IndexOfAny{Except} with a SearchValues for the whitespace characters.
* Use a nicer field name for the known whitespace search values
* Reduce code size impact of `ArrayPool<T>`
Every `SharedArrayPool<T>` brings with it several types, including several array types and all of their interface implementations. This makes the internals of SharedArrayPool a bit less generic to try to reduce that impact. The changes are effectively:
- Move the nested Partition, Partitions, and ThreadLocalArray types out from being nested types to being peers
- Rename them, since they're no longer inheriting the parent's name
- Make them non-generic in terms of Array rather than generic in terms of T[]. These types never index into the array, so other than accessing Length for logging purposes, it could even have used object.
- Use Unsafe.As in the two places arrays are dequeued and need to be T[] rather than Array.
- Pass in the sizeof(T) rather than using it in the implementation. The size is used only when trimming to determine how much to trim.
* Fix throughput regression from covariance check
* Reduce asm size of CollectionsMarshal.AsSpan
Using the span constructor brings with it some branches and code we don't need due to knowledge of `List<T>`'s implementation, in particular that a) it always has an array (even if empty), and b) its array is invariant.
Erroneous use of AsSpan while the list is being mutated could have also led to an ArgumentOutOfRangeException, which doesn't make much sense in this context. I've changed it to be an InvalidOperationException about the invalid concurrent use.
* Update src/libraries/System.Private.CoreLib/src/System/Runtime/InteropServices/CollectionsMarshal.cs
* Update src/libraries/System.Private.CoreLib/src/System/Runtime/InteropServices/CollectionsMarshal.cs
Co-authored-by: Jan Kotas <jkotas@microsoft.com>
---------
Co-authored-by: Jan Kotas <jkotas@microsoft.com>
* Add debug-only use of new AssemblyBuilder.Save in Regex.CompileToAssembly
To aid in debugging RegexCompiler issues and to help vet the new AssemblyBuilder.Save support.
* Fix IL2121 warnings
---------
Co-authored-by: Sven Boemer <sbomer@gmail.com>
* Add .NET 8 test project for System.Numerics.Tensors
* Update src/libraries/System.Numerics.Tensors/tests/Net8Tests/System.Numerics.Tensors.Net8.Tests.csproj
Co-authored-by: Viktor Hofer <viktor.hofer@microsoft.com>
---------
Co-authored-by: Viktor Hofer <viktor.hofer@microsoft.com>
There's a lot of code involved in these, some of which we special-case to only build into some of the targets, and it's unnecessarily complicated. We can get most of the benefit with a simpler solution, which this attempts to provide. This commit removes those three types and replaces them with a SegmentedArrayBuilder.
The changes to ToArray also obviate the need for the old Buffer type. It existed to avoid one array allocation at the end of loading an enumerable, where we'd doubled and doubled and doubled in size, and then eventually have an array with all the data but some extra space. Now that we don't have such an array, we don't need Buffer, and can just the normal Enumerable.ToArray.
The one thing the new scheme doesn't handle as well is when there are multiple sources being added (specifically in Concat / SelectMany). Previously, the code used a complicated scheme to reserve space in the output for partial sources known to be ICollections, so it could use ICollection.CopyTo for each consistuent source. But CopyTo doesn't support partial copies, which means we can only use it if there's enough room available in an individual segment. The implementation thus tries to use it, and falls back to normal enumeration if it can't. For larger enumerations where the cost would end up being more apparent, the expectation is we'd quickly grow to a segment size where the subsequent appends are able to fit into the current segment. Hopefully.
The implementations are special-casing most of the built-in ones, in order to delegate to the IBinaryInteger-constrained helper, but it was missing Int128, UInt128, and char. ?hese won't be vectorized, but they'll at least use the more streamlined non-vectorized implementations.
* Revamp empty special-casing in LINQ
Enumerable.Empty used to return Array.Empty. Towards the beginning of .NET Core, LINQ was imbued with an internal "partition" concept for flowing more information around between operators, and as part of that, Empty was changed to return a singleton instance of a specialized partition implementation. The upside of this was that methods typed to return IPartition could return the same singleton as Empty. There are multiple downsides, however. For one, the whole IPartition concept is only built into a "speed-optimized" build of LINQ; builds that care more about size (e.g. browser) end up not having it, and thus Empty there ends up being Array.Empty, such that a different type ends up being returned based on the build, which is not ideal. Further, any paths that check for empty now effectively have two things to check for: the empty partition or an empty array, making those checks more expensive, if they're even done at all, or in some cases missing out on possible optimization. This is more pronounced today, now that `[]` with collection expressions will produce Array.Empty, and it'd be really nice if there wasn't a difference between Enumerable.Empty and `[]` assigned to `IEnumerable<T>`.
This change puts Enumerable.Empty back to always being Array.Empty. The internal IPartition-based APIs that drove us to need the EmptyPartition are changed to just use null as an indication of empty. Places we were already checking for `is EmptyPartition` are changed to check for an empty array (if they weren't already), and other APIs that weren't checking at all now have a check if it makes sense to do so (I audited all of the APIs, and didn't include checks in ones where it could meaningfully affect semantics, e.g. a fast path that might cause us not to get an enumerator from a secondary enumerable input).
* Rename IsImmutableEmpty to IsEmptyArray per PR feedback
* Remove bogus PLINQ tests
The tests were validating the underlying type of the operator returned for Concat, which is not material.
* Fix Skip special-casing
The check needs to be moved to before the count <= 0 check... otherwise calling Skip on an empty array with a count of 0 would still allocate an iterator.
Either the dedicate helper should be deleted or used. Since it exists, I changed the code to use it and avoid the closure allocation. If we instead want to reuse the same helper, the method can instead be changed to just call the other overload, and the unused helper can be deleted.
* Add generic overloads to TensorPrimitives
This overhauls the implementation and tests to have a generic overload for each existing float-based overload. I've avoided touching the core logic, but have augmented the structure in a few ways, e.g. only taking vectorized code paths when the type supports vectorization. To keep the shared definitions of the float-based APIs, on .NET 9 they delegate to shims that are implemented on top of the generic variants.
The tests have all been made instance members, with an abstract base class containing most of the tests, and calling into abstract methods for the core operations and validation routines. Derived types then fill in this logic, letting us use all the tests for both the non-generic and generic overloads. Generic tests are validating most of the primitive types that implement the required interfaces.
This does not yet:
- Provide generic overloads for the IndexOfMin/Max{Magnitude} methods
- Vectorize the trig-related functions for Ts other than floats
* Disable tests on mono due to Vector128 bug
* Change "Float" to "Single" in various file, type, and member names
We currently use IndexOf(literal), but every call to that incurs a little overhead to determine how best to do the search. Now that we have `SearchValues<string>`, even though it's bread-and-butter is searching for multiple substrings, we can use it to search for a single substring, in which case it's effectively the same as IndexOf(literal) but caching the result of that examination in order to only do it once rather than on every call.
This also introduces some of the infrastructure necessary to subsequently enable multi-substring search.
* Change several more arrays to be assembly data spans (w/ collection expressions)
* Update src/libraries/System.Private.CoreLib/src/System/TimeZoneInfo.Unix.NonAndroid.cs
Co-authored-by: Jan Kotas <jkotas@microsoft.com>
---------
Co-authored-by: Jan Kotas <jkotas@microsoft.com>
* Make Deflate/GZip/ZlibStream empty writes have the same impact as no writes
If you create such a compression stream, don't write to it, and close it, it won't write out any bytes. But today if you perform an empty write, it'll result in the stream thinking data was written, and it'll end up writing out an empty chunk, which will result in several bytes of output. Logically it's strange that there's such a difference between an empty write and no write; this seeks to make them the same.
* Put back ConcatenatedEmptyGzipStreams test
...but with hard-coded bytes rather than using GZipStream to generate them
* Expose ChannelReader.ReadAllAsync from non-core builds as well
I'm not sure why we didn't fix this before when we shipped Microsoft.Bcl.AsyncInterfaces, but with IAsyncEnumerable available downlevel, there's no need to hide this method away; it can be in all builds. Doing so makes it easier for others to create their own channel implementations, as they don't _need_ to multitarget in order to override everything they might want to.
I've not changed any C# code, just moved it between files.
* Address PR feedback
* Improve scalability of monitored Counter / UpDownCounter
Avoid locking around every Update. Instead, use interlocked operations, and for CounterAggregator, partition the value being updated into one per core rather than one all-up.
* Address PR feedback
* Limit additional memory consumption
* Clean up S.N.Tensors project in main
- Remove stale build targets
- Remove ifdefs for .NET 8
- Remove stale IVT
* Add CompatibilitySupressions
* Address request to add net6.0/net7.0 package suppressions
* Improve literal-after-loop regex optimization
Regex currently has an optimization that looks to see whether the pattern begins with a set loop followed by some literal, in which case it can optimize the search for matches by searching for the literal and then walking backwards through the starting set. However, it's missing a handful of cases we can easily support:
- It currently gives up if the set loop is wrapped in an atomic and/or a capture.
- It currently gives up if the literal is a set that's wrapped in an atomic, capture, concatenate, loop, or lazy loop.
- If the set loop is followed by an ignore-case string, it currently only searches for the starting set of that string, rather than more of it.
- If the literal is a set, we'd only examine it if it was exactly one iteration (RegexNodeKind.Set) rather than a loop with at least one iteration.
This fixes all of those issues, such that the optimization extends to more patterns.
* Add a few more tests and comments
* Address PR feedback
* Avoid a few array allocations with DefaultBinder
In places where we're not handing out a `T[]` and thus actually need a `T[]`, we can instead just get a span from the `ListBuilder<T>` being used.
* Fix mono and nativeaot call sites, and share identical ListBuilder between coreclr/mono
* Dedup ListBuilder in nativeaot
* FEATURE_MANAGED_ETW and FEATURE_MANAGED_ETW_CHANNELS are always defined
Remove the compilation constants and keep all code they were guarding.
* FEATURE_ADVANCED_MANAGED_ETW_CHANNELS is never defined
Delete all code guarded by it.
* EVENT_SOURCE_LEGACY_NAMESPACE_SUPPORT is never defined
Delete the code guarded by it.
* Fix TensorPrimitives.IndexOfXx corner-case when first element is seed value
Found as part of adding more tests for Min/Max{Magnitude} to validate they match their IndexOfXx variants.
* Address PR feedback
* Replace confusing `new T[] { ... }` optimization with collection expressions
We rely heavily on the compiler rewriting:
```C#
ReadOnlySpan<T> span = new T[] { /* const data */ };
```
into variants that don't actually allocate and instead blit the data into the assembly data section and create a span that points directly to that data. But the syntax is very confusing and looks like it allocates on every use.
Now that we have collection expressions and they handle the same optimizations (and more), we can avoid the confusion and simplify the code by switching to use them. This does so for all the uses I could find with some greping around.
* Fix asn template
* Vectorize TensorPrimitives.Tanh/Cosh/Sinh
Tanh and Cosh are based on AOCL-LibM.
AOCL-LibM doesn't appear to have a sinh implementation, so this Sinh is just based on the sinh formula based on exp(x).
I also augmented the tests further, including:
- Added more tests for sinh/cosh/tanh
- Add an equality routine that supports comparing larger values with a tolerance
- Tightened the tolerance for most functions
- Changed some tests to be theories to be consistent with style elsewhere in the tests
- Fixed some use of Math to be MathF
* Remove unnecessary special-handling path from cosh
* Remove unnecessary special-handling path from tanh
* Redo sinh based on cosh
* Address PR feedback
* Move internal BitOperations.LeadingZeroCount({U}Int128)
With no other signed overloads exposed, it's easy to accidentally use these for int/long/etc. They exist only for the implementation of {U}Int128 at this point, so just move them to be in those types.
* Address PR feedback
* Vectorize TensorPrimitives.Sigmoid and TensorPrimitives.SoftMax
- Adds a SigmoidOperator that just wraps the ExpOperator
- Vectorizes both passes of SoftMax, on top of ExpOperator. Simplest way to do this was to augment the existing InvokeSpanScalarIntoSpan to take a transform operator.
- In doing so, found some naming inconsistencies I'd previously introduced, so I did some automatic renaming to make things more consistent.
- Added XML comments to all the internal/private surface area.
- Fleshes out some tests (and test values).
* Disable tests on mono
* Address PR feedback
* Improve throughput / allocations of JsonNode.GetPath
The current implementation is creating a `List<string>` and appending each segment to it, which in most of the cases is allocating a `string`. Then it iterates through that list in reverse order appending to a newly-created `StringBuilder`, which it then `ToString`s. In this change, it instead just uses `ValueStringBuilder`, appending to it as it goes.
In doing so, it does reverse the order of enumeration. Previously each node would effectively do:
```C#
void GetPath()
{
AddNode(this);
parent?.GetPath();
}
```
and now it's doing:
```C#
void GetPath()
{
parent?.GetPath();
AddNode(this);
}
```
While C# doesn't emit tail calls, with optimizations enabled, it's feasible the JIT might emit the recursive call as a jmp rather than a call, in which case it would avoid possible stack dives. However, that's not guaranteed, and doesn't happen today in tier 0 and other unoptimized code. On top of that, to get such a deep nesting in a JsonNode, you need to either go out of your way to create one manually using the JsonNode/Object/Array/Value constructors, or you need to use JsonSerializer.Deserializer, overriding its default MaxDepth, and in the case of a really deep input, it's also recursive and will stack overflow in smaller situations. I have a different version of this change that keeps the same ordering, passing around a span and a length separately, and prepending to the end of the span, but it results in more complicated code, so I'd prefer this variation that just uses ValueStringBuilder unless we have real concerns.
* Address PR feedback
Some operations would produce incorrect results if the same span was passed as both an input and an output. When vectorization was employed but the span's length wasn't a perfect multiple of a vector, we'd do the standard trick of performing one last operation on the last vector's worth of data; however, that relies on the operation being idempotent, and if a previous operation has overwritten input with a new value due to the same memory being used for input and output, some operations won't be idempotent. This fixes that by masking off the already processed elements. It adds tests to validate in-place use works, and it updates the docs to carve out this valid overlapping.
* Flesh out TensorPrimitives XML docs
* Address PR feedback
- Remove use of FusedMultiplyAdd from all but CosineSimilarity
- Remove comments about platform/OS-specific behavior from Add/AddMultiply/Subtract/Multiply/MultiplyAdd/Divide/Negate
- Loosen comments about NaN and which exact one is returned
* Address PR feedback
* Vectorize TensorPrimitives.Min/Max{Magnitude}
* Use AdvSimd.Max/Min
* Rename some parameters/locals for consistency
* Improve HorizontalAggregate
* Move a few helpers
* Avoid scalar path for returning found NaN
* Normalize some test naming
* Alphabetize tests
* Improve mistmatched length tests with all positions of the shorter tensor
* Alphabetize methods in TensorPrimitives.cs
Change a few of the static abstract interface methods to be virtual, as most implementations throw from these methods; we can consolidate that throwing to the base.
* Address feedback and fix some TensorPrimitives issues
- Added a few APIs based on initial feedback: Abs (vectorized), Log2, and element-wise Max/Min{Magnitude}
- Renamed L2Normalize to Norm
- Fixed semantics of Min/MaxMagnitude to return original value rather than the absolute value
- Renamed a few helper types for consistency
- Added tests
* Add a few more uses of Tolerance
* Change GetParametersNoCopy to GetParametersAsSpan and use it in a few more places
The internal GetParametersNoCopy avoids a defensive ParameterInfo[] copy, but it requires the callers to promise not to mutate the array. I'm changing the method to return a `ReadOnlySpan<ParameterInfo>`, which means a caller can't mutate it without using unsafe code, and enabling the compiler to flag any misuse. I've then used it in a few more places. We might subsequently want to consider exposing it publicly.
* Update src/libraries/Common/src/System/Runtime/InteropServices/ComEventsMethod.cs
* Fix downlevel build break in TensorPrimitives
* Make net6.0 Tensors use ns2.0 implementation
* Add net6.0 and net7.0 to Tensors temporarily since those are shipping in 8.0 branch
* Only build net6.0 and net7.0 Tensors when not in source-build
---------
Co-authored-by: Eric StJohn <ericstj@microsoft.com>
* Optimize Random{NumberGenerator}.GetItems for power-of-two choices
When possible, make a single call to get the required randomness rather than one per element.
* Address PR feedback
* Address PR feedback
Use separate scratch buffer instead of destination buffer. Upside, we don't need to be concerned about temporarily corrupt Ts, and it can work for managed Ts. Downside, it requires separate scratch space, which means an ArrayPool rental for larger sizes.
* Address PR feedback, again
Loop over a stackalloc'd buffer rather than using ArrayPool
* Tweak test to validate variable number of choices
Stephen Toub
