• Dmitriy (8/8) Nov 05 2014 Hello, I'm in the middle of learning D. I can't find any
• Jonathan M Davis via Digitalmars-d-learn (13/21) Nov 05 2014 They should both be an amortized O(1). As I understand it, the problem w...
• Steven Schveighoffer (10/18) Nov 06 2014 As Jonathan said, it's because array append needs to look up information...

"Dmitriy" <123 123.com> writes:

Hello, I'm in the middle of learning D. I can't find any 
definitive information about what is the complexity of operator 
~= when used for adding an element to an array. Is it amortized 
O(1) or is it implementation defined? (I hope it at worst O(n) 
though I haven't seen any information about that either).

Also documentation to std.array.Appender says that "it is more 
efficient" to use Appender "when appending many elements". Does 
it imply that Appender.put has amortized O(1)?

Jonathan M Davis via Digitalmars-d-learn writes:

On Thursday, November 06, 2014 03:48:26 Dmitriy via Digitalmars-d-learn wrote:
 Hello, I'm in the middle of learning D. I can't find any
 definitive information about what is the complexity of operator
 ~= when used for adding an element to an array. Is it amortized
 O(1) or is it implementation defined? (I hope it at worst O(n)
 though I haven't seen any information about that either).

 Also documentation to std.array.Appender says that "it is more
 efficient" to use Appender "when appending many elements". Does
 it imply that Appender.put has amortized O(1)?

They should both be an amortized O(1). As I understand it, the problem with
~= over using Appender is the extra checks that the runtime has to do with
~= to see whether there's room to append anything without reallocating, and
because Appender is free to assume that the whole block of memory is for its
personal use rather than having to worry about other dynamic arrays which
are backed by slices of the same block of memory extending into that memory
first, it's able to check for available capacity much faster. So, it's the
coefficient that changes, not the overall complexity. For the complexity to
change, you'd have to get behavior like ~= _always_ reallocating (and thus
having to copy all of the elements every time) rather than just when there
isn't any extra capacity, and that's not the case at all.

- Jonathan M Davis

Steven Schveighoffer <schveiguy yahoo.com> writes:

On 11/5/14 10:48 PM, Dmitriy wrote:
 Hello, I'm in the middle of learning D. I can't find any definitive
 information about what is the complexity of operator ~= when used for
 adding an element to an array. Is it amortized O(1) or is it
 implementation defined? (I hope it at worst O(n) though I haven't seen
 any information about that either).

It's amortized O(1).

 Also documentation to std.array.Appender says that "it is more
 efficient" to use Appender "when appending many elements". Does it imply
 that Appender.put has amortized O(1)?

As Jonathan said, it's because array append needs to look up information 
in the GC, which can be costly (we have mechanisms to mitigate this 
somewhat, but it can't be inlined). The Appender has all the information 
it needs handy, and can be inlined. The disadvantage is that the 
Appender may have higher up-front costs, and does not have some of the 
same properties as a builtin array.

You may find this article helpful: http://dlang.org/d-array-article.html

-Steve