Re: time complexity of string +=

[Chet Ramey]

On 3/13/21 4:26 AM, Koichi Murase wrote:
> 2021年3月13日(土) 0:17 Peng Yu <pengyu.ut@gmail.com>:
> > It seems that the time complexity of string += is super-linear. Is it
> > so? Should it be made to be linear instead of super-linear?
>
> The time complexity of a single `+=' is not super-linear but linear
> [i.e., O(string-length)]. In your measurement, the entire loop becomes
> super-linear because you repeat it N (=10^2,10^4,10^6) times.

I think you'll find if you profile that as the number of loop iterations
increases, and the variable value's length increases, execution time
becomes dominated by memory allocation and reallocation, as you suspect.

> I guess you meant that the time complexity of a single ``string +=''
> is now linear but could be an amortized constant time. It is in
> principle possible by reallocating the strings with a capacity larger
> than its actual string length and by exponentially increasing the
> capacity on reallocation. 

Bash does optimize this case, especially the case where the value being
appended is a single character, but does not perform exponential capacity
increases upon reallocation. The bash malloc does take care of some of
that with its binary binsize allocation, and its realloc is smart
enough to just modify the allocated size if the chunk is big enough.

--
``The lyf so short, the craft so long to lerne.'' - Chaucer
                 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU    chet@case.edu    http://tiswww.cwru.edu/~chet/