Optimization fun

[H. S. Teoh via Digitalmars-d]

On Fri, Nov 07, 2014 at 09:28:56AM +0000, thedeemon via Digitalmars-d wrote:
> On Thursday, 6 November 2014 at 23:00:19 UTC, 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).
> 
> When you grow a hash table it periodically reallocates bucket arrays
> it uses internally, so some garbage to collect appears anyway even if
> you only add elements.

I realize that, it's just that even after accounting for that, the
memory consumption rate is much higher than expected, and sure enough
further investigation revealed unnecessary GC load caused by
reallocating arrays where (re)using an existing one would suffice.

In the case of the function that used to return an array, which would
allocate a new array every call (and there are hundreds of thousands of
calls for this particular test case), after implementing buffer reuse,
even though it does need to reallocate the buffer sometimes when the
array runs out of space, it only reallocates 3-4 times for the entire
run.

I'm not sure what the overhead for the hash table would be, but I'm
expecting it shouldn't be more than, say, 50-100 reallocations of the
bucket array (I didn't measure this). So it shouldn't add up to *that*
much.


T

-- 
There is no gravity. The earth sucks.