Faster IndexOf for Substrings in .NET(github.com)
github.com
Faster IndexOf for Substrings in .NET
https://github.com/dotnet/runtime/pull/63285
90 comments
As a new joiner from Java on applications that are decades old, I wish it would be more backward compatible.
I cant forgive they didnt find a way to fix WinForms, that we cant find the budget to move away from and limp along trying to upgrade out of.
But at least unlike Java, their GUIs do work well enough for a fraction of the maintenance cost of what I know. So meh, begging the sky to find anyone willing to do .NET in 2022 so I can go back to my cave lol. All the OG experts we interview are interested by our path to Java because they want out and Im like "but dude we'll teach you Java but we really need someone who has a clue in C#/.NET and likes it" :s
I cant forgive they didnt find a way to fix WinForms, that we cant find the budget to move away from and limp along trying to upgrade out of.
But at least unlike Java, their GUIs do work well enough for a fraction of the maintenance cost of what I know. So meh, begging the sky to find anyone willing to do .NET in 2022 so I can go back to my cave lol. All the OG experts we interview are interested by our path to Java because they want out and Im like "but dude we'll teach you Java but we really need someone who has a clue in C#/.NET and likes it" :s
You can run your WinForms application on the latest LTS version of dotnet, .NET6. As always, upgrading to a new version of the framework, means you have to migrate some parts of the codebase, especially from an older .net3-4. That isn't really that different from Java
If I'd have candidates that want out from .NET I'd be very intrigued and want to know why. Specifically, I don't want any that want out because the tech was changing rapidly. I can understand the overhead is somewhat annoying, but it's for the better and it seems to be a lot more stable again.
If I'd have candidates that want out from .NET I'd be very intrigued and want to know why. Specifically, I don't want any that want out because the tech was changing rapidly. I can understand the overhead is somewhat annoying, but it's for the better and it seems to be a lot more stable again.
VS 2022 WinForms designer for .NET 3.0+ can still not handle non-MS custom controls. If you want to create a user control yourself you need to sign an NDA with MS.
The API and behavior also changed, so it's not like updating the SDK version is enough. You need to fix every single form and control.
MS didn't botch the transition completely but it's very far from being a small task for larger applications maintained by relatively small teams.
The API and behavior also changed, so it's not like updating the SDK version is enough. You need to fix every single form and control.
MS didn't botch the transition completely but it's very far from being a small task for larger applications maintained by relatively small teams.
> You need to fix every single form and control.
As anecdotal evidence, I certainly did not do this in my migration of several WinForms apps (one large and several small) to .NET 6. They flubbed the default font in .NET 5 so WinForms users had to wait a bit longer, but it's fixed in .NET 6. My forms all work fine in .NET 6 without change. It would have been infeasible to revisit all of the forms.
Do you have specific examples of APIs that changed? I can't think of any. I think changing the WinForms API would have taken a lot more effort than they actually invested to get it running on .NET Core. From where I'm sitting, it seems like they did the minimum necessary to get the existing DLL to run, and then spent 95% of their budget on the out-of-process designer rewrite.
Edit: I thought of one. They removed Menu; now there is only MenuStrip. I did have to make code changes for this and I totally forgot about it. It was minor though; we used MenuStrip anyway, there was just some code with optional support for Menu that I removed.
As anecdotal evidence, I certainly did not do this in my migration of several WinForms apps (one large and several small) to .NET 6. They flubbed the default font in .NET 5 so WinForms users had to wait a bit longer, but it's fixed in .NET 6. My forms all work fine in .NET 6 without change. It would have been infeasible to revisit all of the forms.
Do you have specific examples of APIs that changed? I can't think of any. I think changing the WinForms API would have taken a lot more effort than they actually invested to get it running on .NET Core. From where I'm sitting, it seems like they did the minimum necessary to get the existing DLL to run, and then spent 95% of their budget on the out-of-process designer rewrite.
Edit: I thought of one. They removed Menu; now there is only MenuStrip. I did have to make code changes for this and I totally forgot about it. It was minor though; we used MenuStrip anyway, there was just some code with optional support for Menu that I removed.
You cannot create your own controls. It's impossible to integrate them with the VS designer unless you sign an NDA.
I don't mean a composition of existing controls but completely new custom controls. Yes, you can continue developing in code but nobody will develop winforms without a designer. Once you use a custom control in the control/form you will not be able to use the designer again until you remove the custom control. That is simply not acceptable for many developers.
There is much more low-level stuff like background behavior, event order and more which most developers simply don't notice, especially when only using Microsoft's controls.
I don't mean a composition of existing controls but completely new custom controls. Yes, you can continue developing in code but nobody will develop winforms without a designer. Once you use a custom control in the control/form you will not be able to use the designer again until you remove the custom control. That is simply not acceptable for many developers.
There is much more low-level stuff like background behavior, event order and more which most developers simply don't notice, especially when only using Microsoft's controls.
I don't understand what you mean; we have tons of custom controls. I am looking at a .NET 6 project right now where I have a custom control that shows up in the toolbox under my project's group, and when you add it to the designer it renders (at design time) as it did before. It's clearly my OnPaint method drawing, etc.
I wonder if you're talking about a previous version of .NET Core? .NET 6, very recently released, is the first version where legacy WinForms apps can start to upgrade. There were blockers in previous .NET Core versions. If you're maybe talking about .NET Core 3.1, WinForms was not at all ready in that version. It was almost there in .NET 5 but they made a mistake with the default font handling that broke legacy apps, but they both fixed that bug and finished the designer for .NET 6.
I wonder if you're talking about a previous version of .NET Core? .NET 6, very recently released, is the first version where legacy WinForms apps can start to upgrade. There were blockers in previous .NET Core versions. If you're maybe talking about .NET Core 3.1, WinForms was not at all ready in that version. It was almost there in .NET 5 but they made a mistake with the default font handling that broke legacy apps, but they both fixed that bug and finished the designer for .NET 6.
They did reference in several occasions that the likes of Telerik, ComponentOne, DevExpress,... had to jump in to enable such transition.
So I assume you aren't using such component libraries.
So I assume you aren't using such component libraries.
Yeah, that's correct; we only use the built-in controls and our own controls. Perhaps we don't use the functionality that was changed. I just edited my post above because I remembered I did have a breakage related to the removal of the Menu class.
The designer isn't the runtime. Custom controls work fine in the application; it's the click-and-drag builder in Visual Studio that doesn't work. I don't miss it.
> If I'd have candidates that want out from .NET I'd be very intrigued and want to know why.
Every time I change jobs I always try. It's not that I hate .Net, it's just that I want to try something different.
.Net is awesome, but it's always useful to see how other languages and platforms do things. For example, compiler enforced null checking in C# is lousy compared to Swift or Rust.
Every time I change jobs I always try. It's not that I hate .Net, it's just that I want to try something different.
.Net is awesome, but it's always useful to see how other languages and platforms do things. For example, compiler enforced null checking in C# is lousy compared to Swift or Rust.
In .NET 6, there is new "EnableNullable" directive that will do that. It's on by default for new projects.
It's horrible.
For example, it treats Linq's .First() as nullable. (.First() throws an exception, .FirstOrDefault() returns null.)
Type.Name is also treated as nullable.
I didn't encounter any issues like that when I tried Swift and Rust.
For example, it treats Linq's .First() as nullable. (.First() throws an exception, .FirstOrDefault() returns null.)
Type.Name is also treated as nullable.
I didn't encounter any issues like that when I tried Swift and Rust.
That is not true.
LINQ's First() correctly returns a non-nullable type: https://source.dot.net/#System.Linq/System/Linq/First.cs,11
FirstOrDefault() correctly returns a nullable type: https://source.dot.net/#System.Linq/System/Linq/First.cs,33
typeof(type).Name is MemberInfo.Name, which is also not nullable: https://source.dot.net/#System.Private.CoreLib/MemberInfo.cs...
I checked both .NET 5 and .NET 6. They have identical nullability.
LINQ's First() correctly returns a non-nullable type: https://source.dot.net/#System.Linq/System/Linq/First.cs,11
FirstOrDefault() correctly returns a nullable type: https://source.dot.net/#System.Linq/System/Linq/First.cs,33
typeof(type).Name is MemberInfo.Name, which is also not nullable: https://source.dot.net/#System.Private.CoreLib/MemberInfo.cs...
I checked both .NET 5 and .NET 6. They have identical nullability.
Then how come I get a compiler error if I don't check the result?
Did you perhaps enable null checking for an older version of the framework (in which the standard assemblies don't have the appropriate annotations)? This works just fine when targeting .NET 6:
object[] xs = {};
var n = xs.First();
n.ToString();That is a very valid reason.
I’m not sure there is enough of a benefit from moving away from .Net Framework for Windows Forms applications. I’m not planning on migrating my apps for the foreseeable future.
No idea where this Java elitism is coming from, dotnet and Java are ridiculously similar. I'd do dotnet for you in 2022 if you're willing to pay me more than my current corp with the same benefits, the language/platform is just fine.
Winform is also fine its just bad at transparency and most applications that are written using it are poorly written.
Winform is also fine its just bad at transparency and most applications that are written using it are poorly written.
The usual stuff, Spectrum vs C64, Amiga vs Atari vs PC vs Mac, vi vs Emacs, Pascal vs C, C vs C++, ...... and naturally Java vs .NET, specially given J++ history and its relation to C#.
What do you mean about WinForms? Look at this https://devblogs.microsoft.com/dotnet/whats-new-in-windows-f... from a couple of months ago, you can still use it pretty well
As long as you are willing to put up with the bugs on the new .NET Core based designer, and can get new components that were rewritten for the new out-of-process architecture of the designer.
You can use it but maybe I didnt explain that I work mainly in performance optimization of heavy trading applications in electronic trading for a tier 1 investment bank.
No I cant explain why we wont finance a gigantic team to redo it all, but anyway: we need this to go faster, and I wish MS would fix WinForms to make them transparently faster rather than me profiling with despair "yes hum modals will always be a bit slow to redraw 50 controls, we could port to the new stuff but we're not sure it ll get better (but at least we ll benefit from more framework level optim) and it's so different we need a new guy" "then find a new guy", im told, and then every new guy who did some low latency GUI at our level (our app is very optimized but China will decuple volume eventually so...) will tell me he desperately wants out to move to java backend where all the fun is... which I cant deny since that s where I got extracted from urgently when half the .NET team left out of despair to go do Java in other banks lol.
I even grew to like .NET even if Ill never wrap my head around the build process and dependency management. Just a wish that MS would continue to optimize winform somehow so I wouldnt have to recode forms doing exactly the same thing. I suppose it s nonsensical since the new paradigm IS the optim but one can whine :D
No I cant explain why we wont finance a gigantic team to redo it all, but anyway: we need this to go faster, and I wish MS would fix WinForms to make them transparently faster rather than me profiling with despair "yes hum modals will always be a bit slow to redraw 50 controls, we could port to the new stuff but we're not sure it ll get better (but at least we ll benefit from more framework level optim) and it's so different we need a new guy" "then find a new guy", im told, and then every new guy who did some low latency GUI at our level (our app is very optimized but China will decuple volume eventually so...) will tell me he desperately wants out to move to java backend where all the fun is... which I cant deny since that s where I got extracted from urgently when half the .NET team left out of despair to go do Java in other banks lol.
I even grew to like .NET even if Ill never wrap my head around the build process and dependency management. Just a wish that MS would continue to optimize winform somehow so I wouldnt have to recode forms doing exactly the same thing. I suppose it s nonsensical since the new paradigm IS the optim but one can whine :D
WinForms sits on top of classic Win32 UI (HWND etc) architecturally, and that's what constrains its performance more than anything else. The way you get more perf is by taking over and rendering everything yourself, like WPF or WinUI does. But you can't do that while maintaining backwards compatibility - stuff like Control.Handle or IWin32Window.
There are millions of .NET developers ready and able to do whatever you need. I do find that the market for .NET is very underpaid though compared to the more popular stacks used at FAANG companies.
Are you really having that much trouble finding devs?
Are you really having that much trouble finding devs?
My group just hired our first .NET dev in years after many interviews.
Maybe they’re all working for the big banks. Or maybe all the .NET engineers realized they’re underpaid and have learned other technologies. My own experience is that outside of Azure, .NET has become extremely painful. FWIW, modern .NET and Visual Studio (anywhere other than ASP) is deserving of hazard pay, at the very least to compensate for the mental health cost of Visual Studio’s constant gaslighting.
I love my manager and team, but pretty soon I’m going to be telling them that I’m leaving, because .NET (on desktop and mobile) has given me 5+ years of very good reasons to hate it.
Maybe they’re all working for the big banks. Or maybe all the .NET engineers realized they’re underpaid and have learned other technologies. My own experience is that outside of Azure, .NET has become extremely painful. FWIW, modern .NET and Visual Studio (anywhere other than ASP) is deserving of hazard pay, at the very least to compensate for the mental health cost of Visual Studio’s constant gaslighting.
I love my manager and team, but pretty soon I’m going to be telling them that I’m leaving, because .NET (on desktop and mobile) has given me 5+ years of very good reasons to hate it.
In what concerns the desktop, it has become a mess with the UWP failure, so they are now shoting in all possible directions, unfortunely.
Where are you hiring? I'm primarily a .net dev at a uni in the states. I'm surprised you're having trouble finding someone.
We do both stacks, on the backend we have the problem that most shops don't really buy into the whole .NET Core stack for Linux workloads story unless they happen to be Azure shops.
I have a clue about C#/.NET. Did it professionally for almost 2 years. That's why I don't like it.
Can you elaborate on why?
Sure. I like Linux and OSS. If anything happens that is unexpected I can trace it back to the source code that makes up my programming environment. I actually like C# as a programming language. It's .NET that's effed up. .NET development happens behind clicks and VS interfaces. The resulting configuration ends up in REALLY unreadable XML files, sometimes obfuscated behind object ids even. I like flat-file human-readable configuration. Also, Entity Framework can just curl up in a ball and die somewhere alone and crying. It's the most useless ORM I have ever worked with. And the documentation on it is just plain wrong often. Following a basic example can lead to results different from those advertised in documentation.
This is all born from experience. I was working on a project I believed in and came to it after the stack used was crystallized and unchangeable. I ended up throwing my hands up in disgust and leaving.
This is all born from experience. I was working on a project I believed in and came to it after the stack used was crystallized and unchangeable. I ended up throwing my hands up in disgust and leaving.
> .NET development happens behind clicks and VS interfaces.
That hasn't really been the case since .Net Core (aka .Net 5/6) replaced .Net Framework. You can develop entirely from the terminal if that is your choice or use Rider instead of Visual Studio if you want a cross-platform IDE.
> The resulting configuration ends up in REALLY unreadable XML files
You can now put the entire framework straight into the executables' directory, no more system-wide XML files. The concept of pre-installed .Net is legacy.
> This is all born from experience.
Of .Net Framework, which is deprecated.
That hasn't really been the case since .Net Core (aka .Net 5/6) replaced .Net Framework. You can develop entirely from the terminal if that is your choice or use Rider instead of Visual Studio if you want a cross-platform IDE.
> The resulting configuration ends up in REALLY unreadable XML files
You can now put the entire framework straight into the executables' directory, no more system-wide XML files. The concept of pre-installed .Net is legacy.
> This is all born from experience.
Of .Net Framework, which is deprecated.
Consider this toast burnt for life. I am not about to trust anything coming from Redmond for life. This is in spite of having great respect for things coming from Microsoft Research. I'll happily use their toy OS for my games but if I intend to do serious work I will not interact with Microsoft offerings except ephemerally.
Let's untangle this:
- .Net Framework made a bunch of unfortunate design decisions.
- You hated .Net Framework as a direct result.
- .Net Core (aka .Net 5/6) fixed the problems, went OSS, went cross-platform, de-coupled from proprietary tooling.
"Consider this toast burnt for life." I don't understand; if your disdain for .Net is meant to be technically founded then technical (and governance) improvements should address it but yet it doesn't here.
Can you unravel why them essentially going through your laundry list of problems and fixing them one by one has left the "toast burnt for life?"
- .Net Framework made a bunch of unfortunate design decisions.
- You hated .Net Framework as a direct result.
- .Net Core (aka .Net 5/6) fixed the problems, went OSS, went cross-platform, de-coupled from proprietary tooling.
"Consider this toast burnt for life." I don't understand; if your disdain for .Net is meant to be technically founded then technical (and governance) improvements should address it but yet it doesn't here.
Can you unravel why them essentially going through your laundry list of problems and fixing them one by one has left the "toast burnt for life?"
Yes. I have never been burnt by these other software tools. I like them better. They work as advertised and any new features are new features, not fixes.
Not sure when your experiences are from, but in .net core they redid the csproj format which is much smaller and human readable (I often just edit the XML instead of using the designer). I think most (all?) of the source for .net core is available so well.
I dont know EF well but there is a rewritten core version
I dont know EF well but there is a rewritten core version
The replacement algorithm: http://0x80.pl/articles/simd-strfind.html#algorithm-1-generi... (basically, match the first and last character and extract possible candidates using vector predicates)
The original algorithm by comparison was doing IndexOf for the first character then match the rest naively and was very slow even compared to strstr and std::string::find compared in the Wojciech Muła's page.
The original algorithm by comparison was doing IndexOf for the first character then match the rest naively and was very slow even compared to strstr and std::string::find compared in the Wojciech Muła's page.
Nice improvement. I think one of the mistakes in .NET was to not have ordinal string comparison as the default for all string operations. Sometimes people forget it and it causes security and performance issues.
| Method | Mean | Error | StdDev |
|--------------- |----------:|---------:|---------:|
| IndexOfOrdinal | 47.71 ns | 0.963 ns | 2.344 ns |
| IndexOfDefault | 201.93 ns | 3.893 ns | 4.923 ns |
| Method | Mean | Error | StdDev |
|--------------- |----------:|---------:|---------:|
| IndexOfOrdinal | 47.71 ns | 0.963 ns | 2.344 ns |
| IndexOfDefault | 201.93 ns | 3.893 ns | 4.923 ns |
What is an "ordinal string comparison"? To contrast, what is a non-ordinal string comparison?
A string is encoded in memory as an array of numbers so in this case "ordinal" means that it simply compares the two arrays number by number.
A non-ordinal string comparison may take into account other things such as iterating by actual characters and comparing them in language and culture-aware ways. This is useful for ordering things by name when showing a list to users.
A non-ordinal string comparison may take into account other things such as iterating by actual characters and comparing them in language and culture-aware ways. This is useful for ordering things by name when showing a list to users.
Ordinal is plain binary comparison. The default comparison takes language specifics into account. For instance, in German there is a letter called Eszett (ß) that stands for "ss". IndexOf("ss") will find that.
In Germany's German "ss" and "ß" are two different things, ß is its own letter and its transliteration is "ss" or "sz". But it really is its own thing and is not equivalent to "ss". In the past "SS" was the capitalized version of "ß", but that's not officially the case anymore, you now have a capitalized ẞ [0], even if it isn't used in practice (or if it is, really not often).
It's not the same for all versions of German though. For example in Swiss German ß is not used and is replaced by "ss".
I do not know about Austrian German but I would not be surprised if they have some specificities around the letter ß.
In short: it's complicated :)
[0]: https://de.wikipedia.org/wiki/Gro%C3%9Fes_%C3%9F
It's not the same for all versions of German though. For example in Swiss German ß is not used and is replaced by "ss".
I do not know about Austrian German but I would not be surprised if they have some specificities around the letter ß.
In short: it's complicated :)
[0]: https://de.wikipedia.org/wiki/Gro%C3%9Fes_%C3%9F
[deleted]
Ordinal compares the literal bytes. The other comparison variants have additional features, e.g. case-insensitivity.
Such a Anglo centrist view. Rest of the world be damned? Luckily a not all the .Net creators were English speakers.
The default comparison should be a culture neutral comparison. Just like the default number formatting unless specified should default to "NumberFormatInfo.InvariantInfo" rather than "Thread.CurrentThread.CurrentCulture".
If I want to compare or print in my own language or the system language (I very rarely do) then I'm happy to specify that in code. And I wish the API forced me to, because I some times forget and I make code that breaks when it's run on a different machine. Which is almost never what I want.
If I want to compare or print in my own language or the system language (I very rarely do) then I'm happy to specify that in code. And I wish the API forced me to, because I some times forget and I make code that breaks when it's run on a different machine. Which is almost never what I want.
If there's only a single string type, there should be no default comparison at all. There are many cases where ordinal or culture-invariant comparison is wrong (almost any string that can be potentially displayed in UI). There are also many cases where ordinal is the only thing that is correct. The only way to prevent sneaky bugs is to force the dev to think it through every time they have to compare strings.
(It should also be easy to compare strings in different ways. StringComparison.Ordinal is an overly long incantation for the frequency with which it's needed.)
Alternatively, we need two distinct string types - one for "displayed text", and one for internal stuff like an HTTP header - with no implicit conversions between the two, and with comparisons defined differently for either.
(It should also be easy to compare strings in different ways. StringComparison.Ordinal is an overly long incantation for the frequency with which it's needed.)
Alternatively, we need two distinct string types - one for "displayed text", and one for internal stuff like an HTTP header - with no implicit conversions between the two, and with comparisons defined differently for either.
For comparison I’d be happy to force a comparer and never assume anything.
But the problem can also be flipped around and generalized to include formatting. To seem well designed I think it should be symmetric in formatting/parsing wrt what must be provided. In formatting it’s more clear that the system must assume assume format, or some operations become unergonomic (once one wants to be sloppy and allow concatenation of string and int for example). But perhaps one could compromise and just allow ints (assume invariant) but not floats (require formatter).
But the problem can also be flipped around and generalized to include formatting. To seem well designed I think it should be symmetric in formatting/parsing wrt what must be provided. In formatting it’s more clear that the system must assume assume format, or some operations become unergonomic (once one wants to be sloppy and allow concatenation of string and int for example). But perhaps one could compromise and just allow ints (assume invariant) but not floats (require formatter).
How is defaulting to byte-comparing strings Anglocentrist?
The idea that you can byte-compare strings is ascii-centrist. Others will ask "are they even using the same encoding", "are they normalised the same way" first.
.NET strings are backed by two-byte UTF-16 codepoints, not bytes in an unknown encoding.
But ordinal comparison means ignoring equivalence classes, like U+006E (n) + U+0303 (combining tilde) being considered the same as U+00F1 (ñ). But - perhaps more surprisingly - .net's non-ordinal match also matches things like "ß" and "ss".
That leads to some weird things like even if two strings compare as equal in the invariant culture, if you uppercase them in the invariant culture they may no longer be considered equal.
And that's all before you start looking at culture-variant behaviors like different cultures having different casing rules (see Turkish dotless i) or approaches to diacritic equivalence for sorting.
But ordinal comparison means ignoring equivalence classes, like U+006E (n) + U+0303 (combining tilde) being considered the same as U+00F1 (ñ). But - perhaps more surprisingly - .net's non-ordinal match also matches things like "ß" and "ss".
That leads to some weird things like even if two strings compare as equal in the invariant culture, if you uppercase them in the invariant culture they may no longer be considered equal.
And that's all before you start looking at culture-variant behaviors like different cultures having different casing rules (see Turkish dotless i) or approaches to diacritic equivalence for sorting.
Those things only matter when your strings contain human-oriented text, but that's not the only (and dare I say not even most common) usage of strings. Obviously it's best to be explicit about how you want the contents of your strings to be treated, but absent that, I don't see how defaulting to ordinal string comparison is Anglo-centric. The English culture doesn't use ordinal comparison. Defaulting to ordinal comparison can actually _prevent_ breakage for people using non-English cultures, because strings suddenly behave differently in ways the developer didn't anticipate or test.
(Also, I should've said codeunit-compare instead of byte-compare, since C# strings are always UTF-16 encoded).
(Also, I should've said codeunit-compare instead of byte-compare, since C# strings are always UTF-16 encoded).
Not an Anglo. Still think it's dumb. Most of the strings I manipulate are either english, or not even natural languages. Having to write Ordinal for Regex and string comparisons everywhere sucks. Especially considering that if you don't, it will depend on the current thread's Culture setting, which can lead to odd bugs when you call code from different contexts.
It's probably an unfortunate decision either way: For interacting with things the user types the ordinal approach is wrong, but for low-level handling of text the ordinal approach is faster. In both cases you basically have to know your exact needs and choose the correct variant. You could have the parameter not being optional and thus force every user of that API to make that decision, but that is probably fairly quickly perceived as annoying.
Ordinal is the default comparison for most .NET string methods. Most linters will force you to make an active choice. And it is not only a performance thing since you open up for all these Unicode attacks.
The default and recommended way of comparing strings in .NET is with ordinal comparison. It is just some functions that use CurrentCulture instead for some reason. We are also talking about Unicode strings here so you can compare strings in any language.
The .Net analyzers have a feature to check for StringComparison use when available. I tuned it on for my team after a few bugs occurred from forgetting it.
Is it faster than Boyer Moore?
I guess the answer is ... complex. As explained in the linked source for the algorithm (http://0x80.pl/articles/simd-strfind.html#introduction):
The main problem with these standard algorithms is a silent assumption that comparing a pair of characters, looking up in an extra table and conditions are cheap, while comparing two substrings is expansive.
But current desktop CPUs do not meet this assumption, in particular:
• There is no difference in comparing one, two, four or 8 bytes on a 64-bit CPU. When a processor supports SIMD instructions, then comparing vectors (it means 16, 32 or even 64 bytes) is as cheap as comparing a single byte.
• Thus comparing short sequences of chars can be faster than fancy algorithms which avoids such comparison.
• Looking up in a table costs one memory fetch, so at least a L1 cache round (~3 cycles). Reading char-by-char also cost as much cycles.
• Mispredicted jumps cost several cycles of penalty (~10-20 cycles).
• There is a short chain of dependencies: read char, compare it, conditionally jump, which make hard to utilize out-of-order execution capabilities present in a CPU.
There probably is a trade-off to be made. The more complex algorithms may make sense when the initial setup cost can be amortized and perhaps more things are known about the input and search strings. The dead-simple approach of simply running linearly through the string has no setup cost, can be trivially vectorized and may perform very well for most haystack/needle pairs and thus is probably a good idea for the general algorithm in the library. And in fact, the information that's required to decide whether the more complex algorithms are worth it is perhaps not known to string.IndexOf, so that's probably something that application developers have to decide.
The main problem with these standard algorithms is a silent assumption that comparing a pair of characters, looking up in an extra table and conditions are cheap, while comparing two substrings is expansive.
But current desktop CPUs do not meet this assumption, in particular:
• There is no difference in comparing one, two, four or 8 bytes on a 64-bit CPU. When a processor supports SIMD instructions, then comparing vectors (it means 16, 32 or even 64 bytes) is as cheap as comparing a single byte.
• Thus comparing short sequences of chars can be faster than fancy algorithms which avoids such comparison.
• Looking up in a table costs one memory fetch, so at least a L1 cache round (~3 cycles). Reading char-by-char also cost as much cycles.
• Mispredicted jumps cost several cycles of penalty (~10-20 cycles).
• There is a short chain of dependencies: read char, compare it, conditionally jump, which make hard to utilize out-of-order execution capabilities present in a CPU.
There probably is a trade-off to be made. The more complex algorithms may make sense when the initial setup cost can be amortized and perhaps more things are known about the input and search strings. The dead-simple approach of simply running linearly through the string has no setup cost, can be trivially vectorized and may perform very well for most haystack/needle pairs and thus is probably a good idea for the general algorithm in the library. And in fact, the information that's required to decide whether the more complex algorithms are worth it is perhaps not known to string.IndexOf, so that's probably something that application developers have to decide.
> And in fact, the information that's required to decide whether the more complex algorithms are worth it is perhaps not known to string.IndexOf, so that's probably something that application developers have to decide.
It might not even be known to the application developers or, potentially worse, they might think they know but the program usage evolves and it becomes wrong knowledge.
For a JIT'ed language though one could imagine more smartness. In theory the runtime could use a sampling profiler in the background to determine any eligible library functions that are taking a lot of time based on caller.
For example, this specific call to IndexOf is taking a lot of time. The runtime could then replace that call to IndexOf with a variant that does some instrumentation, to for example build crude histograms of input lengths and hit locations. Based on this the runtime could replace that call to IndexOf with a version more optimized to the expected parameters.
At least this is possible for a JIT'ed language, though surely would be a non-trivial amount of work.
It might not even be known to the application developers or, potentially worse, they might think they know but the program usage evolves and it becomes wrong knowledge.
For a JIT'ed language though one could imagine more smartness. In theory the runtime could use a sampling profiler in the background to determine any eligible library functions that are taking a lot of time based on caller.
For example, this specific call to IndexOf is taking a lot of time. The runtime could then replace that call to IndexOf with a variant that does some instrumentation, to for example build crude histograms of input lengths and hit locations. Based on this the runtime could replace that call to IndexOf with a version more optimized to the expected parameters.
At least this is possible for a JIT'ed language, though surely would be a non-trivial amount of work.
One of the most interesting things about the emphasis on algorithms in both CS education and in tech interviews to me is that when you start to look at how people really make high performance software, it rarely comes down to figuring out how to jump from O(n) to O(logn), more often than not it has to do with thinking about memory locality and caching or avoiding branches or fitting the problem into something can be vectorized. Picking the correct algorithm with minimal algorithmic complexity tends to be the easy part. But outside of roles where performance actually matters, you’re probably not going to get asked about these things. And that’s totally reasonable, but why do we ask people about algorithms, then?
I totally agree. I haven’t actually needed to use Boyer Moore in like 15 years. On another project I got around a 10x speed up by reusing a buffer rather than allocating a new buffer. Cache locality makes a lot more difference than people give it credit for.
[deleted]
the c# code is looking a lot like C with the goto’s. Great to see this style in c#.
If you want high performance C# code, it needs to look like this. Very much like C, rather unreadable.
But form my experience, only a very tiny fraction of your code needs to be like that, as in most of the code maintainability and readability is much more important than performance.
But form my experience, only a very tiny fraction of your code needs to be like that, as in most of the code maintainability and readability is much more important than performance.
3 gotos replacing while(true) loops, and one... just reducing nesting?
I'm guessing the reason is because of code gen issues, there's a lot of workarounds throughout the BCL code base.
Seems like every .NET optimization I see is revolved around getting the JIT to generate the right assembly.
There's a lot more that doesn't have to do with the JIT. Yes, in some cases it's about providing hints to the JIT to generate better code. Things like casting to unsigned types for example. But the weird ones (one I came across recently was something like condition ? true : false) are fairly rare. Which makes sense in a way: Not all code is that performance-critical that you have to save two instructions. But for things where the baseline performance is a few nanoseconds in many cases, it probably makes sense taking whatever measures you can to ensure that the machine code looks like you'd expect (and make a note to improve the JIT, which also happens regularly).
Technically you could count vectorization in the category of codegen issues, but since the JIT won't output vector instructions on its own I don't think that's really fair (and you have the same issues in languages like C or C++ that do auto-vectorize, but not reliably or good enough).
What is also frequently optimized, is allocation behavior by ensuring that the code doesn't allocate more memory than needed and in a lot of cases no memory at all. And C# has a lot of tools for that kind of optimization that don't really veer into code that looks atypical.
Technically you could count vectorization in the category of codegen issues, but since the JIT won't output vector instructions on its own I don't think that's really fair (and you have the same issues in languages like C or C++ that do auto-vectorize, but not reliably or good enough).
What is also frequently optimized, is allocation behavior by ensuring that the code doesn't allocate more memory than needed and in a lot of cases no memory at all. And C# has a lot of tools for that kind of optimization that don't really veer into code that looks atypical.
[deleted]
SMART (fastest substring search algorithms) https://smart-tool.github.io/smart/ is up for several years. EPSM, by S. Faro and O. M. Kulekci still the fastest known strstr method, and they still come up with their own.
.NET turning more and more into Linux.
.NET turning more and more into Linux.
Various links on that page (e.g. https://www.dmi.unict.it/~faro/smart/howto.php) are dead for me, and browsing the source isn’t easy because they release .zip/.tar.gz. files (https://github.com/smart-tool/smart/releases), so I didn’t make that effort, but theoretical algorithms often count character or byte comparisons, not nanoseconds. For the latter, code size and cache-friendliness matter, and the best code almost always must be tuned for one specific CPU, nowadays one specific state of a CPU (do you assume the SIMD hardware is powered up? If it isn’t, is using SIMD for short strings worth it?)
There probably also is a choice to be made as to what cases to optimize most for: length of search string, length of to-be-searched for string, case-sensitivity, diacritics-sensitivity, distribution of results (if, most of the time, the string is found close to the start, decreasing algorithm set up time at the cost of some speed may be worth it). ¿Are there corner cases where locale matters?
There probably also is a choice to be made as to what cases to optimize most for: length of search string, length of to-be-searched for string, case-sensitivity, diacritics-sensitivity, distribution of results (if, most of the time, the string is found close to the start, decreasing algorithm set up time at the cost of some speed may be worth it). ¿Are there corner cases where locale matters?
> the best code almost always must be tuned for one specific CPU
There’re very few relevant differences between CPUs of the same instruction set. The author of that PR implemented fast paths for SSE2, AVX2, and NEON. Combined, they cover like 90% of CPUs; the only notable missing one is the 32-bit ARMv7, C# doesn’t support vector intrinsics for that architecture.
> do you assume the SIMD hardware is powered up?
Modern AMD64 CPUs never power off just the SIMD. For AMD64 ISA, SSE1 and SSE2 are included in the base instruction set. Modern C++ compilers compile FP32 and FP64 math into SSE1 and SSE2 respectively, e.g. double y=x*3.0 compiles into MULSD instruction from SSE2 SIMD subset. Powering down that hardware would be too expensive for many programs.
Some early Intel’s AVX CPUs, like Sandy Bridge from 2011, powered down half of their SIMD hardware. On these CPUs, first time a program uses AVX instructions which process 32-byte vectors, the instructions run at half the throughput and +1 cycle of latency. The performance penalty lasts until the state transition is complete, like ~100 nanoseconds or something. AFAIK, for 32-byte AVX vectors, that got fixed years ago in the newer processors.
There’re very few relevant differences between CPUs of the same instruction set. The author of that PR implemented fast paths for SSE2, AVX2, and NEON. Combined, they cover like 90% of CPUs; the only notable missing one is the 32-bit ARMv7, C# doesn’t support vector intrinsics for that architecture.
> do you assume the SIMD hardware is powered up?
Modern AMD64 CPUs never power off just the SIMD. For AMD64 ISA, SSE1 and SSE2 are included in the base instruction set. Modern C++ compilers compile FP32 and FP64 math into SSE1 and SSE2 respectively, e.g. double y=x*3.0 compiles into MULSD instruction from SSE2 SIMD subset. Powering down that hardware would be too expensive for many programs.
Some early Intel’s AVX CPUs, like Sandy Bridge from 2011, powered down half of their SIMD hardware. On these CPUs, first time a program uses AVX instructions which process 32-byte vectors, the instructions run at half the throughput and +1 cycle of latency. The performance penalty lasts until the state transition is complete, like ~100 nanoseconds or something. AFAIK, for 32-byte AVX vectors, that got fixed years ago in the newer processors.
> double y=x*3.0 compiles into MULSD instruction from SSE2 SIMD subset
Why is this? Isn't there a scalar instruction for handling just one float? Or does it have different precision characteristics or something?
Why is this? Isn't there a scalar instruction for handling just one float? Or does it have different precision characteristics or something?
That is the instruction for multiplying just one double (the SD suffix stands for scalar double); the respective instructions for handling more than one number at the same time have a PD suffix (for packed double).
The alternative would be to use the x87 FPU registers and instructions, which are a lot slower these days (but yes, also with different precision characteristics). So they're usually not used at all in code targeting x64.
The alternative would be to use the x87 FPU registers and instructions, which are a lot slower these days (but yes, also with different precision characteristics). So they're usually not used at all in code targeting x64.
Thanks, didn't realise SSE included non-SIMD instructions.
Technically, that instruction is a scalar one. It multiplies just one number in the lowest lane of the vectors, and copies the second lane from the first vector register without changing it. BTW, on modern processors, the performance of such scalar instructions is exactly the same as their vector equivalents which handle all lanes of the registers.
Before AMD64 took off, that C++ code compiled into x87 instructions https://en.wikipedia.org/wiki/X87 That thing is ancient with first implementation from 1980, and some architectural features make it borderline impossible to be performant. For instance, internally it operates on 80-bit floats. Both FP64 and FP32 IEEE floats are being emulated based on bits in the control register.
Before AMD64 took off, that C++ code compiled into x87 instructions https://en.wikipedia.org/wiki/X87 That thing is ancient with first implementation from 1980, and some architectural features make it borderline impossible to be performant. For instance, internally it operates on 80-bit floats. Both FP64 and FP32 IEEE floats are being emulated based on bits in the control register.
You can of course browse the source on GitHub: https://github.com/smart-tool/smart/tree/master/source
The tarballs are just a feature of GitHub, not something they specifically release.
The tarballs are just a feature of GitHub, not something they specifically release.
But they chose to point to them and not to the source. That made me think that’s how they intend to release the code.
Certainly, but I don’t think it’s unreasonable of them to assume a prior basic knowledge of GitHub.
The releases page is the prebuilt binaries they publish, and there are several links you can click to view the source at the tag, commit or main-branch level.
The releases page is the prebuilt binaries they publish, and there are several links you can click to view the source at the tag, commit or main-branch level.
Their site broke recently. Before it had nice benchmarks included. Apparently string backend researchers are not that good in maintaining website frontends.
Having a search algorithm implemented in C has nothing to do with Linux.
I am not deep into the topic. Is that maybe because of a SIMD variant is possible in one algorithm and not the other. .NET is doing a lot of processor specific optimization right now and getting from that it's current speed. On pure paper approach, SIMD is not a thing but on processors it is.
Just waking up. Maybe I am completely off.
Just waking up. Maybe I am completely off.
That project includes implementations which use simd. I don't know if those are the fastest or how it compares to this proposed one.
What does algorithm (approach) has to SIMD / Hardware intrinsics?
Some algorithms are amenable to SIMD, others are not. To utilize SIMD, you need the same set of operations on big chunks of data stored one next to to the other in memory. This fits for example with algorithms which use arrays to store data, and doesn't work at all for alogrithms which rely on linked lists.
As a user of .NET since version 2.0 though, I'm impressed and excited by how the platform has evolved and how much performance has become a focus.