Appender is ... slow

[Jonathan M Davis via Digitalmars-d-learn]

On Thursday, 14 August 2014 at 21:00:55 UTC, Jonathan M Davis 
wrote:
> On Thursday, 14 August 2014 at 19:47:33 UTC, Brad Anderson 
> wrote:
>> On Thursday, 14 August 2014 at 19:10:18 UTC, Jonathan M Davis 
>> wrote:
>>> I've never really tried to benchmark it, but it was my 
>>> understanding that the idea behind Appender was to use it to 
>>> create the array when you do that via a lot of appending, and 
>>> then you use it as a normal array and stop using Appender. It 
>>> sounds like you're trying to use it as a way to manage 
>>> reusing the array, and I have no idea how it works for that. 
>>> But then again, I've never actually benchmarked it for just 
>>> creating arrays via appending. I'd just assumed that it was 
>>> faster than just using ~=, because that's what it's 
>>> supposedly for. But maybe I just completely misunderstood 
>>> what the point of Appender was.
>>>
>>> - Jonathan M Davis
>>
>> I too have trouble understanding what Appender does that 
>> supposedly makes it faster (at least from the documentation). 
>> My old, naive thought was that it was something like a linked 
>> list of fixed size arrays so that appends didn't have to move 
>> existing elements until you were done appending, at which 
>> point it would bake it into a regular dynamic array moving 
>> each element only once looking at the code it appeared to be 
>> nothing like that (an std::deque with a copy into a vector in 
>> c++ terms).
>>
>> Skimming the code it appears to be more focused on the much 
>> more basic "~= always reallocates" performance problem. It 
>> seems it boils down to doing essentially this (someone feel 
>> free to correct me) in the form of an output range:
>>
>> auto a = /* some array */;
>> auto b = a;
>> a = a.array();
>> for(...)
>>  b.assumeSafeAppend() ~= /* element */;
>
> It was my understanding that that was essentially what it did, 
> but I've never really studied its code, and I don't know if 
> there are any other tricks that it's able to pull. It may be 
> that it really doesn't do anything more than be  wrapper which 
> handles assumeSafeAppend for you correctly. But if that's the 
> case, I wouldn't expect operating on arrays directly to be any 
> faster. Maybe it would be _slightly_ faster, because there are 
> no wrapper functions to inline away, but it wouldn't be much 
> faster, it would ensure that you used assumeSafeAppend 
> correctly. If it's really as much slower as Phillippe is 
> finding, then I have no idea what's going on. Certainly, it 
> merits a bug report and further investigation.

Okay. This makes no sense actually. You call assumeSafeAppend 
after you _shrink_ an array and then want to append to it, not 
when you're just appending to it. So, assumeSafeAppend wouldn't 
help with something like

auto app = appender!string();
// Append a bunch of stuff to app
auto str = app.data;

So, it must be doing something else (though it may be using 
assumeSafeAppend in other functions). I'll clearly have to look 
over the actual code to have any clue about what it's actually 
doing.

Though in reference to your idea of using a linked list of 
arrays, IIRC, someone was looking at changing it to do something 
like that at some point, but it would drastically change what 
Appender's data property would do, so I don't know if it would be 
a good idea to update Appender that way rather than creating a 
new type. But I don't recall what became of that proposal.

- Jonathan M Davis