Optimal String Concatenation in UserTalk

Almost every slow UserTalk system we are asked to look at is slow for the same reason, and it is almost never the reason the team expects. It is not the database, the network or the parser. It is a loop that builds a string by adding to it, and a runtime that, done wrong, copies the entire accumulated string on every single iteration.

The fix is usually four lines. The explanation of why those four lines matter is worth considerably more than the fix, because once you have it you stop writing the slow form anywhere.

The quadratic trap, stated plainly

Consider assembling a report from forty thousand short lines. The obvious code is the one everybody writes first:

on buildReport (adrRows) {
	local (s = "", row);
	for row in adrRows^ {
		s = s + row.name + tab + row.value + cr};
	return (s)}

Read the assignment carefully: s = s + something. The right-hand side is a new string, built by copying the whole of s and then appending. On iteration one you copy nothing; on iteration forty thousand you copy the forty-thousand-line string you have already built. The total work is proportional to the square of the output size.

With an average line of forty bytes, forty thousand lines produce a 1.6 MB result — and move roughly 32 GB through memory to get there. The allocator does the rest of the damage.

Notice the shape rather than the absolute numbers. The naive column roughly quadruples when the input doubles; the in-place column roughly doubles. That is the entire story, and it is why the problem hides successfully in testing: at a thousand rows, both are instant.

The in-place append

The runtime contains an optimisation that makes the fast form possible: when a string has exactly one reference and you append to it in a way the interpreter can recognise, it extends the existing buffer instead of allocating a new one. The trick is writing the append so that the interpreter can see it.

on buildReport (adrRows) {
	local (s = "", row);
	for row in adrRows^ {
		«s is named on the left AND is the first term on the right:
		«the interpreter recognises this as an append, not a copy.
		s = s + row.name + tab + row.value + cr};
	return (s)}

That looks identical to the slow version, and in the simplest case it is — which is exactly why the subject causes so much confusion. The optimisation is real but fragile. It survives only while the accumulator has one reference and the append is recognisable. Four common things break it:

1. Putting the accumulator second. s = prefix + s cannot be an append; it must build a new string. Prepending in a loop is always quadratic. Collect and reverse, or build forward.
2. Passing the accumulator to something that keeps it. Handing s to a verb that stores it, even briefly, creates a second reference. The next append must copy to preserve the other holder's view.
3. Accumulating into a database node. adr^ = adr^ + line reads from the database, builds a new value and writes it back — every iteration, with the persistence machinery running each time. This is the single most expensive version of the mistake.
4. Slicing between appends. Any operation that produces a new string from the accumulator can leave you appending to something the interpreter no longer treats as uniquely owned.

When the buffer approach beats both

For very large outputs, or where pieces arrive out of order, collect into a list and join once. The list holds references to the pieces without copying them, and the final join allocates the result exactly once because the total length can be computed up front.

on buildReport (adrRows) {
	local (parts = {}, row);
	for row in adrRows^ {
		parts = parts + {row.name + tab + row.value}};
	«One allocation of the exact final size.
	return (string.join (parts, cr))}

Rule of thumb from our audits: below roughly 100 KB of output the in-place append wins on simplicity and is fast enough; above about 1 MB, or when the assembly order is not the output order, collect-and-join wins on predictability. Between those, either is fine, and you should pick the one the next reader will understand faster.

Writing straight to the destination

The fastest string is the one you never build. If the result is going to a file, a socket or an HTTP response, stream it. The memory ceiling stops depending on the output size entirely, and the first byte reaches the client while you are still producing the last.

on writeReport (adrRows, path) {
	local (f = file.open (path, true), row);
	try {
		for row in adrRows^ {
			file.write (f, row.name + tab + row.value + cr)};
		file.close (f)}
	else {
		file.close (f);
		scriptError ("writeReport failed: " + tryError)};
	return (file.size (path))}

How to find the problem in code you did not write

You do not need a profiler for the first pass. Search the source for an assignment whose left-hand name also appears on the right, inside a loop. In practice three patterns account for nearly all of it:

• s = s + … where s is not declared local in the enclosing handler — it is a database node and every iteration is a persisted write.
• s = … + s — prepending, unconditionally quadratic.
• An accumulator passed into a helper inside the loop — the extra reference defeats the optimisation invisibly.

Then measure before you change anything. A five-line harness is enough, and having the number lets you prove the fix rather than assert it.

on benchmark (adrScript, iterations = 5) {
	local (times = {}, i, t);
	for i = 1 to iterations {
		t = clock.now ();
		adrScript^ ();
		times = times + {clock.now () - t}};
	return ({
		"median": math.median (times),
		"min": math.min (times),
		"max": math.max (times),
		"runs": iterations})}

The same trap in other places

Once you recognise the shape, you find it outside strings. Appending to a list with list = list + {item} in a loop has the same cost curve. Growing a table by repeatedly copying it does too. So does building an outline node by node from a fresh copy each time. The remedy is always the same: accumulate in something that can grow in place, or collect pieces and combine once.

It is also worth saying what not to do with this knowledge. Do not scatter micro-optimisations through code that runs a hundred times on small inputs; you will make it harder to read for no measurable gain. The quadratic trap matters precisely because it is not a constant-factor problem — it is a different curve. Fix the curve, and leave the constants alone.