StringBuffer and amortization

Question

In ArrayList the add operation is amortized operation. So while reading StringBuffer it came to my mind why the StringBuffer is not amortized. Suppose I use append operation on a string buffer object then it should be able to add those many no of characters in it's underlying array implementation. But instead I found in source code that we have

System.arraycopy(chars, 0, value, count, chars.length);

in append operation of string buffer. So my question is can't the StringBuffer be amortized so it can give us less that O(N) complexity?

Answer 1

At the end of the day, you're still moving N references from some memory location A to some other memory location B. However, I'm confident that System.arraycopy does it fast enough such that there's amoritized performance coming from StringBuffer. But, that depends on if you do append or insert.

Recall that there are two ways that ArrayList can perform add: either with a single object, or by shifting elements from a particular index spot down. Both have differing performances.

To get this out of the way, (eventually) StringBuffer will make a call to System.arraycopy(). This implementation is actually JVM-dependent (it's a native call), but the likelihood is that it's extremely fast. Outside of that, there's not much that could really slow down the performance of StringBuffer.append(), save for very large non-contiguous memory areas to copy.

ArrayList.add(E element) will take an amoritized O(1) time, but could change to O(N) due to the possibility that it has to grow the backing array to fit more elements in it; if it doesn't have to do that, though, then insertion time is on the order of O(1) (it's adding elements to the end of the array).

ArrayList.add(int index, E element) is likely O(1) in the best case, but O(N - index) in the average and worst cases, due to the amount of elements it has to shift down to place E in.

To sum up:

• The code for StringBuffer.append() can be seen as amoritized O(N), since it does copy over the array. However, this operation is still quick and is only really dependent on how large the data you're moving around is.

• The code for StringBuffer.insert() is different, and could easily be an amoritized O(1) in the best case, and O(N) in the worst (since it makes two calls to System.arraycopy()). Inserting elements at a given point means you have to shift everything else down, and that's not a cheap operation, no matter how fast your code is.

I believe then, depending on the method you use, you do have amoritized performance. You just have to be sure of the operation you're doing to tell what the performance is going to be.

Answer 2

Actually StringBuffer and ArrayList works the same way and as you pointed out, add operation in ArrayList is O(1) amortized.

In an ArrayList you also have an ensureCapacity method when you add an element such that if the capacity is not enough, a new array is allocated and the data is copied in it. Yet, this operation of reallocation occurs rarely enough so you can consider that adding takes O(1) even though 1 time over K, it takes O(n).

Answer 3

If you look further into source code:

public AbstractStringBuilder append(char[] str) {
    int len = str.length;
    ensureCapacityInternal(count + len);  // expand array if needed
    System.arraycopy(str, 0, value, count, len); 
    count += len;
    return this;
}

That's exactly how arraylist works.

    System.arraycopy(str, 0, value, count, len);

Tells us to copy from str to value starting from count (current end position in stringBuffer). Only the len which is length of appended str is copied.

Answer 4

You are mixing complexity depending on the size of the datastructure (ArrayList / StringBuilder length) and complexity depending on the size of the input.

ArrayList's O(1) refers to adding a single element to the list's content and is amortized O(1). Obviously adding n elements to the list will be n * O(1). The same is true for the StringBuilder. In most cases adding a single character is O(1) (unless the internal array has to be expanded. But adding a char array necessites copying the array's values (In reality bulk copying of arrays should be quite fast, certainly faster than appending single chars).

O(1) for list concatenation can be achieved - when appending - using linked lists. But the result would be vulnerable to changes in each of the concatenated sublists, sth. a StringBuilder would always want to avoid. Furthermore linked lists of characters as String implementation would be horribly inefficient.