-
Notifications
You must be signed in to change notification settings - Fork 779
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
The performance of Comparing and Ordering things #9348
Comments
@KevinRansom @abelbraaksma well there you go, I have thrown it out to the Emperor for the thumbs up or thumbs down! |
@manofstick, so your algorithm, basically consists of figuring out which types can use the default comparer? What are the circumstances where the behavior of existing code may change, can it be detected? I would say that we can't leave a 20-25 * speed up on the table, we just added a new library level special case for DateTime, and @TIHan is eager to improve the performance of structural equality. So if you will consider re-submitting the work, I will commit to fighting for it to be included, I can't guarantee that we will win the argument, but we can durned well try. How does that sound? Kevin |
OK; I'll see if I can make some time over the next week or so... But I would like confirmation that calling a bit of refection code (i.e. the above snippet contains |
This looks surprisingly much like a piece of code I have in my XPath implementation, where I've tried to get native type performance, and needed to cater for @manofstick If I understand this correctly, the biggest slowdown is with struct types that are not native types, or that are not recognized specially (like now I don't yet totally know what you do to get a comparer,and how that comparer looks, but I was thinking, if the type isn't special, would it be sufficient to do bitwise comparison? Isn't that what the default is in .NET land? And another way forward: can we detect, at compile time, if there's a genetic compare/equate interface present, and use that? Would it be helpful to set up a little brainstorm session on Slack or a call? It'll help to get our heads around this and in the same direction :) |
Little side note: your |
@manofstick , if the measurements support the approach, then it wins. Otherwise not ... of course there may be issues of reliability, reproducibility that impact the outcome. But at the end of the day, numbers are the most convincing rhetoric I know. Thanks Kevin |
Very illuminating post by @manofstick . F# equality has a lot of technical debt:
I believe we need to take a breaking change to remove all the special cases. If it's possible:
|
The most basic comparison instruction dealing with equality is the
I know from our discussion on Slack that you disagree with this point. And I've also come to understand that in C# (unfortunately I don't have a "one size fits all" solution either) |
In regards to But yeah, if it was to exist it would have to have something like: type IComparerFactory =
abstract Get<'a> : unit -> IStructuralComparable<'a>
and IStructuralComparable<'a> =
abstract CompareTo : item:'a -> IComparerFactory -> int Given that, if anything, there has been a push to reduce generics reliance in the BCL, I highly doubt that such a interface, requiring such magic, will ever exist. In regards to NaN. Meh, it is what it is. ...and I highly, highly, doubt any breaking change would ever happen... |
All I do is use Now really my code should only be used when the type isn't known at runtime (i.e. in libraries, such as the use of |
@KevinRansom over to you. Feel free to close this issue; the code is all there in #9404 - let's see if can make it past the gatekeepers this time!! |
Arrays and structural comparison may cause problems Maybe should just copy the snippet from dotnet#9348
Arrays and structural comparison may cause problems Maybe should just copy the snippet from dotnet#9348
Arrays and structural comparison may cause problems Maybe should just copy the snippet from dotnet#9348
Arrays and structural comparison may cause problems Maybe should just copy the snippet from dotnet#9348
Things would already not be as bad if the (>) operator could compile as a call to IEquatable<'T>.CompareTo() without going through the Microsoft.FSharp.Core.LanguagePrimitives+HashCompare.GenericGreaterThanIntrinsic function that is very expensive...
This is the benchmark on 100 iteration to compare 2 instances of a struct containing an int.
Some remarks for progressive enhancement... F# (>) seams to call CompareTo (leading to boxing) even when the struct implements CompareTo<>. Calling the generic version of CompareTo<> would already eliminate a jump and a boxing. |
the call to op_GreaterThan is conceptualy faster than passing through IComparable<'T> because op_GreaterThan must return a bool, and can directly implement it a a "cgt" il instrustion, while IComparable<'T> must return an int and has to test both for greater and lower with a conditional jum... and then the result is tested for > 0... In fact, the timing is quite close. A problem is IComparable<'t> is that you cannot call it on null value. This is not a problem on structs, and should not be a problem on F# types that are not Null. This problem doesn't exist with op_GreaterThan: 't *'t -> bool . The code in GenericComparisonWithComparerFast for primitive types is:
which is jitted with a conditional jump:
There is a non conditional version that is exactly as long:
jitted:
|
For reference, here is the code for a structure:
a comparison through IComparable<'T>:
is jitted as:
while the version with op_GreaterThan:
is doing nothing more than necessary:
|
This story began half a decade ago with an adventurous implementation, and received a more reasonable, albeit more limited, implementation a mere two years ago yet as the tides of time go neither of these is (trivially) merge-able into current master. So rather than continuing to hit myself in the head with a hammer making an updated version, I'd rather put this out to the people who actually pull the strings of Pull Requests in order to determine if this effort will yield any fruit (or just a completely mashed head).
So, why's this a problem anyway? Here's a little use of structural comparison within a dictionary setting with NodaTime's
Instant
as the key...So I'm not sure if you notice there the slight difference in performance...
* ?? Huh what ?? *
That not a slight difference, that's a difference of ~20-25x slower using Structural comparison.
So why is this a problem and what can we do about it (well besides going back in a time machine and slurp in those PRs when they were ready...)
Well first of all we need to know why the decision was made to do this, why it doesn't cause pain with built in types, and then decide what we can do about it.
In original .net land, by default, reference types were equal only if
ReferenceEquals
is true and value types were only equal if, in a bitwise comparison, they were true (which meant if they had embedded reference types they were only considered equal if those ReferenceEquals were equal), but this didn't provide the type of experience that fsharp wanted to provide. Containers (array, ResizeArray, Dictionary, etc) were just seen as ordinary reference types.In f-sharp land, by default, records and discriminated unions (of both the reference and value type flavours) implement a series of methods/interfaces so that their compare ever element, and if the elements are all equal, then the object is declared equal. Containers (array, list, map, etc.) also implemented these rules so they too could do comparisons.
To facilitate the f-sharp rules, new interfaces
IStructuralComparable
andIStructuralEquatable
were introduced. The first thing here to recognise is that these interface were not generic, which meant that in order to use the comparisons for value types boxing must occur. But they had to be non-generic, because the one comparer was passed through chains of objects of different types to do the comparison. Rock and hard place land.There was one more rule that f-sharp comparisons had that wasn't part of "normal" .net equality, and this was for floating point numbers NaN <> NaN.
So yeah that is basically the state of play. So what did I do about it? In my first attempt I created who comparison objects using lots of runtime magic to try to create efficient comparison objects that implemented all of the fsharp rules and was then dynamically created using
Type.MakeGenericType
. At the time this came across two obstacles. The first was that whilst the old 64-bit JIT did lots of runtime optimizations to make this very efficient, the new Ryu JIT didn't (fair enough, I really was bending, albeit not breaking, the rules). The second was that, at the time, AOT compilation was gaining traction andMakeGenericType
was an obstacle to that path.My second attempt recognised that the same magic that I was performing is basically performed by
(Equality)?Comparer.Default
(and AOT catered for that) that in most cases the fsharp compilers implementation ofIStructural(Comparable|Equatable)
was the same as it's implementation ofI(IComparable|Equatable)<>
. And so with a bit of RTTI I could filter out problematic cases (i.e. those that used floating point numbers due to the NaN case) and then just return the default comparer in most cases. In fact this is basically what the standard f-sharp library is doing, as it just contains a list of known types (i.e intrinsic types) where it returns an efficient, non-boxing comparer. But they have no mechanism to make is available for non-built in types.So the crux of my implementation relies on the following recursive type check:
So yeah, that's about it really. The rest of the PR was just tying this in so that it was efficiently used (i.e. only called once for any type) and attaching the various operators etc.
Anyway, this has come way, way, way too late to save my work code-base (where I have just ended up never using Structural Equality basically, not using default implementations of data structures, etc. sigh... maybe I'm the only one who cares about efficiency... why bother eh when you can just spin up another x number of cloud machines, he says, shaking his head...) but _if _ people are going to take this as a PR seriously then I'll update it and submit a new request...
But I ain't getting any younger!
(So yeah, if the answer is no, just close this Issue...)
The text was updated successfully, but these errors were encountered: