Optimization fun

[Steven Schveighoffer via Digitalmars-d]

On 11/7/14 8:43 AM, Steven Schveighoffer wrote:
> On 11/7/14 1:05 AM, H. S. Teoh via Digitalmars-d wrote:
>>
>> 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!
>
> In D1 this would have worked fine. A "queue array" wrapper may be a good
> candidate for Phobos that works just like a normal array but calls
> assume safe append whenever decrementing length.

Also to note -- even with this, you will create garbage. As the array 
grows, it may have to relocate to a new block. The old block would be 
garbage.

Once you get large enough, there is a chance that it will just extend 
into new pages. But if it ever has to reallocate a very large array, 
then you just created a very large piece of garbage that will not be 
cleaned up.

I'm wondering if said "queue array" should have an option to forcefully 
delete the old array. In which case, we'd have to make sure the data 
cannot be accessed directly, or mark it as unsafe.

-Steve