Optimization fun

[H. S. Teoh via Digitalmars-d]

On Sat, Nov 08, 2014 at 01:58:31AM +0300, Dmitry Olshansky via Digitalmars-d wrote:
> 07-Nov-2014 09:05, H. S. Teoh via Digitalmars-d пишет:
[...]
> >Yet more GC drama unfolded tonight: while testing my new GC-disabling
> >option on several other puzzles, one instance ate up my PC's RAM at
> >an astonishing rate, causing the system to almost freeze up from the
> >ensuing thrashing. A little investigation revealed that there are
> >several instances of excessive GC load caused by unnecessary
> >(re)allocations.
> 
> That's the problem with profilers:
> 	they say what takes time but not why :)

True! But it's better than the stereotypical C veteran's approach of "I
know from 50 years' experience (aka personal bias) that X is faster than
Y because it's more terse, so I'm gonna optimize all my code into
unreadable code from the get-go even if 99% of it isn't the real hotspot
anyway."


> Often I find myself looking at memcpy at the top of the list, so
> obvious the "textbook" answer is to optimize memcpy ;) In contrast it
> should be read as "you seem to do excessive copying of data".
[...]

Well, when I saw countUntil at the top of the list, it wasn't
immediately obvious *why* it was at the top of the list. In the grand
scheme of things, it's just a "small cog" in a large machinery filled
with many other things that could easily be considered far better
candidates for performance bottlenecks. And while optimizing countUntil
itself did yield significant improvement, a deeper investigation led to
the realization that the underlying logic of the code was causing it to
call countUntil more often than it needs to. Fixing this issue
drastically reduced the number of calls to countUntil, which yielded no
small overall improvement.

In any case, the old optimization adage applies: you should optimize the
underlying algorithms (i.e., the big-O's) before you spend time
optimizing the low-level primitives (the scalar factors).  No matter how
much you optimize the heck out of the scalar factor, an O(N^2) algorithm
is still an O(N^2) algorithm.  As long as the algorithm remains O(N^2),
you aren't going to get much further.


T

-- 
Life is unfair. Ask too much from it, and it may decide you don't deserve what you have now either.