I also noticed that the prim_concatStringSep is very optimistic, assuming that each list element is 32 chars long:

If a nix language user uses builtins.concatStringsSep on a long list of long strings (e.g. to construct some big file), this will also be O(n²).

Could we use the same approach there, computing state.coerceToString(pos, *args[1]->listElems()[n], context); for each element ahead of time, of alternatively res.reserve()ing the buffer size exponentially to avoid that from happening?

Edit: See PR #3942.

Doesn't std::string grow the capacity by a constant factor when it exceeds the current capacity, thereby amortizing the cost to O(1) per character?

Doesn't std::string grow the capacity by a constant factor when it exceeds the current capacity, thereby amortizing the cost to O(1) per character?

Many implementations do, but the standard doesn't guarantee it, see full answer in #3942 (comment).

I marked this as stale due to inactivity. → More info

I closed this issue due to inactivity. → More info