www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Complexity guaranties of array append operator

reply "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)?
Nov 05 2014
next sibling parent 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
Nov 05 2014
prev sibling parent 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
Nov 06 2014