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.
