Optimization fun

[H. S. Teoh via Digitalmars-d]

On Thu, Nov 06, 2014 at 02:58:16PM -0800, H. S. Teoh via Digitalmars-d wrote:
[...]
> 1) The GC could use some serious improvement: it just so happens that
> the solver's algorithm only ever needs to allocate memory, never
> release it (it keeps a hash of visited states that only grows, never
> shrinks).  The profiler indicated that one of the hotspots is the GC.
> So I added an option to the program to call GC.disable() if a command
> line option is given. The result is a 40%-50% reduction in running
> time.
[...]

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.

One case was a function that constructs and returns a new array each
call -- unnecessary because after the resulting array is traversed, it
is discarded. Perfect candidate for a reusable buffer. After
implementing this, the rate of memory consumption is far less
frightening, but still far too rapid compared to when the GC is enabled,
so clearly, *something* else is still doing way more allocations than
necessary.

A little more investigation revealed the culprit: a queue object
implemented with subarrays, and subarrays were being used as stacks by
appending with ~= and popping by decrementing .length. A dangerous
combination that causes excessive reallocations! After inserting
assumeSafeAppend() in the right place, the memory consumption rate
dropped to more reasonable levels. It's still visibly faster than when
GC is enabled, so probably there are other places with excessive
allocations, but this particular change stood out because after adding
assumeSafeAppend() to the code, the solver's performance *even with GC
enabled* improved by about 40%-50%. So this explains why calling
GC.disable() had such a pronounced effect before: the GC is too busy
cleaning up after unnecessarily allocation-hungry code!

The moral of the story, is that code like the following should raise big
red warning flags:

	struct MyData(T) {
		T[] data;
		T pop() {
			...
			data.length--; // <--- yikes
			...
		}
		void push(T t) {
			...
			data ~= t; // <--- yikes
			...
		}
	}

The easy fix (though not a complete one) is to insert a call to
assumeSafeAppend before `data ~= t`. That suppresses the majority of the
unnecessary reallocations, while leaving the necessary ones intact (e.g.
when the GC block runs out of space to store the array).

A more complete fix, of course, is to use a linked-list of presized
blocks, so that the arrays don't keep getting moved around in memory
needlessly.

So while the GC does need to be improved, in this particular case a big
part of the problem is poorly-written user code (by yours truly :-P),
not so much the GC itself. ;-)


T

-- 
Skill without imagination is craftsmanship and gives us many useful objects such as wickerwork picnic baskets.  Imagination without skill gives us modern art. -- Tom Stoppard