7 ms·
Faster IndexOf for Substrings in .NET
- lifthrasiir 5y agoThe replacement algorithm: http://0x80.pl/articles/simd-strfind.html#algorithm-1-generic-simd 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.
- rurban 5y agoSMART (fastest substring search algorithms) https://smart-tool.github.io/smart/ 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.
- oaiey 5y agoI 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.
- charcircuit 5y agoThat project includes implementations which use simd. I don't know if those are the fastest or how it compares to this proposed one.
- tester34 5y agoWhat does algorithm (approach) has to SIMD / Hardware intrinsics?
- tsimionescu 5y agoSome 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.
- Someone 5y agoVarious links on that page (e.g. https://www.dmi.unict.it/~faro/smart/howto.php 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 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?
- orf 5y agoYou can of course browse the source on GitHub: https://github.com/smart-tool/smart/tree/master/source https://github.com/smart-tool/smart/tree/master/source The tarballs are just a feature of GitHub, not something they specifically release.
- Someone 5y agoBut they chose to point to them and not to the source. That made me think that’s how they intend to release the code.
- rurban 5y agoTheir site broke recently. Before it had nice benchmarks included. Apparently string backend researchers are not that good in maintaining website frontends.
- orf 5y agoCertainly, 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.
- pjmlp 5y agoHaving a search algorithm implemented in C has nothing to do with Linux.
- _3u10 5y agoIs it faster than Boyer Moore?
- ygra 5y agoI guess the answer is ... complex. As explained in the linked source for the algorithm (http://0x80.pl/articles/simd-strfind.html#introduction 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.
- deleted 5y ago[deleted]
- magicalhippo 5y ago> 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.
- ryanmccullagh 5y agothe c# code is looking a lot like C with the goto’s. Great to see this style in c#.
- rawling 5y ago3 gotos replacing while(true) loops, and one... just reducing nesting?
- dubiousconst281 5y agoI'm guessing the reason is because of code gen issues, there's a lot of workarounds throughout the BCL code base.
- vips7L 5y agoSeems like every .NET optimization I see is revolved around getting the JIT to generate the right assembly.
- ygra 5y agoThere'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.
- manigandham 5y agoInteresting submission considering it's still in draft status. 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.
- secondaryacct 5y agoAs 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
- MauroIksem 5y agoWhere are you hiring? I'm primarily a .net dev at a uni in the states. I'm surprised you're having trouble finding someone.
- Beltiras 5y agoI have a clue about C#/.NET. Did it professionally for almost 2 years. That's why I don't like it.
- francisofascii 5y agoCan you elaborate on why?
- Beltiras 5y agoSure. 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.
- deleted 5y ago[deleted]
- AtNightWeCode 5y agoNice 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 |
- afdsafsfasd 5y agoWhat is an "ordinal string comparison"? To contrast, what is a non-ordinal string comparison?
- ChrisSD 5y agoA 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.
- Thiez 5y agoOrdinal compares the literal bytes. The other comparison variants have additional features, e.g. case-insensitivity.