4 ms·
> Reduce branching & branch misprediction I wrote a parser for a "formalized" URI (it looked somewhat like OData). This parser was being invoked millions of ti
by zamalek 8y ago
> Reduce branching & branch misprediction
I wrote a parser for a "formalized" URI (it looked somewhat like OData). This parser was being invoked millions of times and was adding minutes to an operation - it dominated the profile at something like 30% CPU time. It started off something like this:
int state = State_Start;
for (var i = 0; i < str.Length; i++)
{
var c = str[i];
switch (state)
{
case State_Start:
/* Handle c for this state. */
/* Update state if a new state is reached. */
}
}
Hardly rocket science, a clear-as-day miniature state machine. VTune was screaming about the switch, so I changed it to this:
for (var i = 0; i < str.Length; i++)
{
for (; i < str.Length; i++)
{
var c = str[i];
/* Handle c for this state. */
/* Break if a new state is reached. */
}
for (; i < str.Length; i++)
{
var c = str[i];
/* Handle c for this state. */
/* Break if a new state is reached. */
}
}
The new profile put the function at < 0.1% of CPU time. This is something that the "premature optimization crowd" (who tend to partially quote Knuth concerning optimization) get wrong: death by a thousand cuts. A single branch in the source (it ends up being more in machine code) was costing 30% performance.
- chrisseaton 8y ago> This is something that the "premature optimization crowd" (who tend to partially quote Knuth concerning optimization) get wrong But this wasn't premature optimisation. - you found performance was actually a problem in practice - you used a tool to profile the application for a real workload - you isolated something to optimise - you came up with a way to optimise based on the data and your tools - you tested that the optimisation worked That isn't premature optimisation. Premature optimisation would have been writing this in the first place without checking anything first.
- deleted 8y ago[deleted]
- pierrebai 8y agoI failed to see how your anecdote relate to your ax-grindy assertion that premature optimization is bad. You wrote your code, you profiled it, you found one function taking 30% of the time, you optimized that function.
- gameswithgo 8y agoWe can always end up with a tautology interpretation of premature optimization, in which case it cannot be bad, if it was bad, it wasn't premature! While this may no include you, a great many forums and advise areas on the internet, and elsewhere, would discourage you from even worrying about a detail like this. Asking questions about this will just get you a knuth quote. I sometimes wonder if the reason so much software today is inexplicably slow is because for 30 years so many young kids curious about how computers and compilers work were told not to worry about it. I think it is useful to build up some intuition about these things, so your default implementation can be the fast one when it isn't especially messy to do so. People don't always get the opportunity to come back and change things later, and some design choices don't just affect a single function that you can easily fix later in the development processes.
- int_19h 8y agoIt's because most of the time, people asking questions like these don't actually have a perf issue. This is very evident on StackOverflow. So when you do have such an issue, and you want to make it clear that it's not a premature optimization, you should mention that it's a hot path as determined by profiling (or whatever other technique). Then you won't get the Knuth quote.
- neetdeth 8y agoOn the other hand, it’s highly annoying to have to anticipate and ward off a whole range of uncharitable and/or unimaginative assumptions about why one would want to do such a thing before there is even an attempt made at a straight answer. If nobody knows the answer, I’d rather have no replies than yet another soliloquy on why nobody actually needs to optimize anything.