Runtime: Optimize int parsing

[danmosemsft]

Int64.Parse was too slow for Kestrel. They wrote their own:

https://github.com/aspnet/KestrelHttpServer/commit/fff0adeaaf55b23f2173be25c59202a322f8eda6

Their code only handles the simple case nevertheless we should examine whether we can optimize the general case, or consider a new API like Int64.ParseFast that they can call instead.

https://github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/Number.cs#L709

/cc @davidfowl

[hughbe]

I created a PR for this reason - I.e. The invariant/NumberStyles.Integer case.
It never picked up a review from msft but Unfortunately I found adding an extra branch to
The product code affected other use cases of int64.Parse negatively

[danmosemsft]

Ah I see it https://github.com/dotnet/coreclr/pull/3995
Literally the extra branch was a problem? One would think it's doing enough work that wouldn't be measurable.
@stephentoub

[hughbe]

I'm planning to come back to it at some point with more thorough investigation (work's getting in the way :D)

[AlexGhiondea]

It looks like there was some progress made here and we ran into a perf regression.

@hughbe are you still interested in working on this? Is there anything we can do to help investigate the perf regression?

[hughbe]

I'm really busy at the mo, feel free to take this or reassign (you can use my code too if you want)

[varocarbas]

I have submitted an issue precisely to optimise ParseNumber, which is called by the Parse/TryParse methods of all the numeric types (in the specific case of long: ParseInt64 -> StringToNumber -> ParseNumber). This is where all the string-analysis actions are performed (= big impact on performance).

Although this is a virtually non-improvable method, most of its contents are focused on decimal types (mainly on decimal); that's why there is an easy and safe way to improve integer type performance: creating another method (e.g., ParseNumberInteger), only including the ParseNumber contents used by integers, which the integer Parse/TryParse methods will call. The functionalities would remain identical, but the performance is likely to become notably better (I guess so; note that I haven't yet done any tests on this front).

May I work on this? (Not sure how is the proceeding with up-for-grabs issues. Calling dibs?) I can have ready a proper version relatively quickly (i.e., new code + tests & performance gains per type within the next 2 weeks).

[varocarbas]

After doing some quick tests and confirming what the integer types can parse (i.e., virtually everything except decimal points; including currencies, hex numbers, parenthesis, etc.) and looking at the quite simplistic proposed improvement (i.e., only accounting for numbers), perhaps new faster methods for integer types (even for all the other types; only considering numbers and basic symbols) might also be an option. In any case, some bits of ParseNumber might definitively be ignored with integer types, what would certainly be reflected on performance (not sure about the impact though).

[AlexGhiondea]

@varocarbas please feel free to work on this. I will assign the issue to you!

Thanks for your interest in this! :)

[AlexGhiondea]

I seem to be unable to assign the issue over to you. However, I removed the up for grabs label. Consider the issue yours! 😄

[varocarbas]

@AlexGhiondea Thanks. I will come back with code, impressions and test results ASAP.

[AlexGhiondea]

Awesome! Looking forward to it @varocarbas !

[varocarbas]

I have finished my analysis before than planned and also with a different output than expected. It seems that no relevant improvement as intended is possible (although there might still be some alternatives, as explained at the end of this post).

First thing to bear in mind is that the in-built Parse/TryParse methods of all the numeric .NET types (integer or not) support other-than-just-digits-characters (i.e., currencies, parenthesis, hexadecimal, etc.). This is the case, at least, with some of their overloads; the simplest ones expect a much more restricted format, more similar to the intuitive understanding of a number. For example, long.Parse(string s) doesn't support all the aforementioned fanciness, but only what is associated with NumberStyles.Integer (i.e., "indicates that the AllowLeadingWhite, AllowTrailingWhite, and AllowLeadingSign styles are used"). Thus, this specific overload only supports strings which are very similar to the just-digits idea, but still a bit different than that. long.Parse("1,2") and long.Parse("1.2") and long.Parse("$1") trigger an error, but long.Parse(" 1") and long.Parse("1 ") and long.Parse("-1") work fine.

The code which is referred at the start of this thread (ParseContentLength) is certainly faster than the aforementioned simplest Parse native overload, but for a different reason than ideal: its applicability is more restricted. It only accounts for digits, what means that ParseContentLength(" 1") and ParseContentLength("1 ") and ParseContentLength("-1") trigger errors. Accounting for all these scenarios isn't precisely straightforward (I mean by keeping the exactly same approach) and, in any case, would increase the algorithm complexity provoking its performance to become similar to the long.Parse one.
Note that this method basically joins together Number.cs's ParseNumber (string analysis) and NumberToInt64 (converting the numeric string into a long variable). Would reducing the quite complex Number.cs structure improve the performance of the parsing methods? I don't think so. This would be a not-precisely-simple task not even likely to provoke an (appreciable) improvement on any front. Also note that the current complex structure accounts for many different types (to not mention all the additional information being accounted by the most complex Parse/TryParse overloads). Changing the existing approach (e.g., moving from first-string-analysis-then-string-to-numeric to everything in one go) here would provoke relevant modifications to reach unclear (performance or readability) benefits.

But even without emulating ParseContentLength, there was an alternative which seemed promising too: creating a restricted version of ParseNumber to be called by the simplest overloads. Note that this same method is called by long.Parse("1") and by long.Parse("$1", NumberStyles.AllowCurrencySymbol, new CultureInfo("en-US"));, when the requirements in both cases are very different. In the simplest scenario, NumberStyles.Integer is always used what means that a big proportion of the ParseNumber code is being plainly ignored (i.e., many conditions never hold). So, why not creating a new method (ParseNumberInteger) including only the parts of the algorithm which are used in these cases? I did that and the code reduction was certainly important, but this didn't provoked the expected performance improvement (almost right the contrary).

I didn't spend too much time on this, but I certainly did it while working on the aforementioned CoreCLR issue to improve ParseNumber and I know what to expect here: this is a highly-optimised code where even a small improvement requires a relevant amount of effort. Perhaps the aforementioned proceeding might provoke a slight performance improvement; perhaps I have even reached that stage already, despite my tests saying other thing (in the original CoreCLR thread, there are various references to the big influence of the hardware where the tests are performed and that mine isn't precisely too powerful/good to see improvements). In any case and despite the huge variability of the tests in my aforementioned PR, I always saw something which didn't see here: consistency. The differences old-new might vary a lot, but under good enough testing conditions, the quickest option always remained as such.

In any case and despite the conclusion of the previous paragraph, someone particularly interested in improving this part might find something worthy. Note that, additionally to the mentioned perhaps-improving-a-bit-the-performance suggestions, there might be some parts which are obsolete (if not for all the types/conditions, perhaps for specific cases). Putting all this together (+ some persistence and work) is likely to output some improvements on the performance and readability/clarity fronts.

Although this isn't exactly what I had in mind (= submitting a new PR with an improved version of the code), I hope that someone will find useful these ideas.

[AlexGhiondea]

@varocarbas thank you very much for the extremely detailed analysis and all the work that went into coming up to this conclusion.

What I think it comes down to is how you are actually using the Parse method for. If you are using it for a specific scenario where you can narrow down the requirement of the input to a small subset, then you can really optimize for that scenario and get really good performance in that case.

In the framework we have to handle a larger set of number formats, with various degrees of complexity which means that optimizing for one format will most likely come with a downside - either making something else slower or increasing the complexity of the existing code.

At this point, we could consider coming up with a very fast and simple parser that would only handle the very simple cases, but I am not sure that it really makes sense for the framework to do that.
@danmosemsft @hughbe what do you think?

[varocarbas]

@AlexGhiondea No problem.

using the Parse method for. If you are using it for a specific scenario where you can narrow down the requirement of the input

Yes. For example, long.Parse(string) accounts for a very restricted scenario (it only accepts digits, the minus/plus sign and heading/trailing blank spaces) and I did modify the standard NumberParser algorithm to only care about this scenario (I am not sharing the code because didn't get any worthy result). The resulting code was much smaller, but the measured performance was similar to the default one. Bear in mind that the algorithm of ParseNumber is formed by various consecutive loops performing pointer/bitwise operations which are extremely quick; the only thing you can do is removing some of the conditions inside these loops. On the other hand, someone might want to spend some time by doing more tests on this line (and measure the differences properly; bear in mind that the differences will always be very small/variable and the more powerful the computer, the better) and might get some improvement, but certainly not a relevant one.

At this point, we could consider coming up with a very fast and simple parser that would only handle the very simple cases

You have this already in place, because the current algorithm is really fast. As said in my previous comment, the new method proposed here isn't faster, but accounts for less scenarios than the simplest Parse overload by relying on an approach with a much simpler structure (very difficult to be replicated in Number.cs for all the cases or driving to a very messy code and, in any case, very unlikely to deliver a better performance). The first step to even start considering a modification of the algorithm (which I insist is currently very fast) should be having in place an alternative delivering the same functionalities. The proposed code cannot even deal with the simplest long.Parse scenario; it would have also to account for heading +/- and heading/trailing spaces.

[danmosemsft]

Seconding our thanks to @varocarbas for this work.

Generally I don't want to make optimizations here (or anywhere else) that are specialized or increase complexity without real world motivation eg some benchmark or important workload that has identified that work here is necessary to help them achieve performance goals. That would also help prove we are optimizing usefully.

We do know ASP.NET was such a workload but they already "solved" their problem (we might consider whether we want to move their code into CoreFX as a new API of course)

[varocarbas]

@danmosemsft No problem. Actually, I am slightly disappointed because of not finding the improvable-worthy situation I was expecting.

In any case, I insist in what I said in my comments above: not sure about what kind of problem these people wanted to address, but their code doesn't deliver what the simplest long.Parse overload does. It cannot understand negative numbers (neither positive ones with a heading plus sign) or strings including heading/trailing blank spaces. So, this code could never be used to replace the current long.Parse unless being improved (what would provoke its performance to certainly become worse).

[danmosemsft]

I agree it could not replace the existing parse. That was my bad (didn't pay attention)

[joperezr]

From the discussion above, this seems to be resolved as a no-op for us for now so I'll go ahead and close this issue. @danmosemsft feel free to reopen if that is not the case.