What if we made another C++ concatStringsSep that took an iterator (something I wanted anyways, FWIW) and then wrote them both interms of that?

Answering #3941 (comment):

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?

There's no C++ standard guarantee for it: https://en.cppreference.com/w/cpp/string/basic_string/operator%2B%3D:

Complexity
There are no standard complexity guarantees

The amortised-constant guarantee that the standard gives for vector/string is on push_back().

GCC's libstdc++ and LLVM's libc++ currently implement += with exponential growth (see e.g. this, section Growth strategy), but they may change it and other standard library implementations may not do it this way.

So it's more of a "do you want to code against API guarantees or implementation details" choice.

This PR guarantees the complexity relying only on what the standard says. It would also be OK to rely on the implementation but I think that should have a comment then.

(For my memory, and in contrast to what I believed before, stringstream does not provide a complexity guarantee in the standard either, and it can be slower than string's += because it also does locale encoding.)

I don't think we need to worry too much about theoretical implementations not doing the sane thing. Having said that, it would be nice to avoid doing any reallocations, but then we should evaluate each string, sum the sizes and reserve() the entire result string.

BTW another optimization that might be worthwhile is to avoid allocating the temporary strings returned by coerceToString() (which is wasteful if the value is a plain string). Ideally it would return something like Rust's Cow type, i.e. either a string or a string_view.

I don't think we need to worry too much about theoretical implementations not doing the sane thing.

OK, I shall switch it then to just a comment that says why it's not quadratic on the platforms we use.

Having said that, it would be nice to avoid doing any reallocations, but then we should evaluate each string, sum the sizes and reserve() the entire result string.

@edolstra How should that best be done? There seem to be 2 straightforward ways:

• Computing state.coerceToString(pos, *args[1]->listElems()[n], context); twice for each string (the first time just to compute its length, the second time for copying it over). I'm doing that in util: concatStringsSep(): Avoid quadratic string append #3941 but I'm a bit scared of that here because inside coerceToString() the v.type == tPath looks like it'll have to copyPathToStore(), which requires a typedef std::map<Path, StorePath> SrcToStore lookup, which might be slower than what the optimisation provides.
• Computing once it once and storing the returned strings (but this would require ~50% more maximum memory, assuming that at the worst point we'd have to keep around the original nix strings, the output of the corercion, and the final string buffer), unless your Cow idea is also implemented.

The second option should be fine since they're temporary strings anyway and probably not very large.

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

I closed this issue due to inactivity. → More info

Hold up, fine if stale bot is marking things stale, but it should be closing them. We need to actually triage old stuff. We can't just let a bot due our duties for us.

I assume this was just a misconfiguration, as the Nixpkgs stale bot doesn't close things to my knowledge.

It looks like nix's stale bot was configured to close already 14 months ago:

#4526 (review)

It also closed some other PRs that I think really shouldn't be closed: #3208 (comment)