Why is string creation so slow in Julia?

My preference would be to use a generic one-liner solution, even if it is a bit slower than what Przemysław proposes (I have optimized it for simplicity not speed):

chop_and_join(s::Union{String,SubString{String}}; nc::Integer=80) =
    join((SubString(s, r) for r in findall(Regex(".{1,$nc}"), s)), '\n')

The benefit is that it correctly handles all Unicode characters and will also work with SubString{String}.

How the solution works

How does the given solution work:

• findall(Regex(".{1,$nc}") returns a vector of ranges eagerly matching up to nc characters;
• next I create a SubString(s, r) which avoids allocation, using the returned ranges that are iterated by r.
• finally all is joined with \n as separator.

What is wrong in the OP solutions

First attempt:

• the function name you choose chop is not recommended to be used as it overshadows the function from Base Julia with the same name;
• length(s) is called many times and it is an expensive function; it should be called only once and stored as a variable;
• in general using length is incorrect as Julia uses byte indexing not character indexing (see here for an explanation)
• String(s[l(i):r(i)]) is inefficient as it allocates String twice (actually the outer String is not needed)

Second attempt:

• doing s = collect(s) resolves the issue of calling length many times and incorrect use of byte indexing, but is inefficient as it unnecessarily allocates Vector{Char} and also it makes your code type-unstable (as you assign to variable s value of different type than it originally stored);
• doing String(s[l(i):r(i)]) first allocates a small Vector{Char} and next allocates String

What would be a fast solution

If you want something faster than regex and correct you can use this code:

function chop4(s::Union{String, SubString{String}}; nc::Integer=80)
    @assert nc > 0
    isempty(s) && return s
    sz = sizeof(s)
    cu = codeunits(s)
    buf_sz = sz + div(sz, nc)
    buf = Vector{UInt8}(undef, buf_sz)
    start = 1
    buf_loc = 1
    while true
        stop = min(nextind(s, start, nc), sz + 1)
        copyto!(buf, buf_loc, cu, start, stop - start)
        buf_loc += stop - start
        if stop == sz + 1
            resize!(buf, buf_loc - 1)
            break
        else
            start = stop
            buf[buf_loc] = UInt8('\n')
            buf_loc += 1
        end
    end
    return String(buf)
end

String is immutable in Julia. If you need to work with a string in this way, it's much better to make a Vector{Char} first, to avoid repeatedly allocating new, big strings.

You could operate on bytes

function chop2(s; nc=80)
    b = transcode(UInt8, s)
    nr   = ceil(Int64, length(b)/nc)
    l(i) = 1+(nc*(i-1)) 
    r(i) = min(nc*i, length(b))
    dat = UInt8[]
    for i in 1:nr
        append!(dat, @view(b[l(i):r(i)]))
        i < nr && push!(dat, UInt8('\n'))
    end
    String(dat)
end

and the benchmarks (around 5000x faster):

 @btime chop($s);
  1.531 s (6267 allocations: 1.28 MiB)

julia> @btime chop2($s);
  334.100 μs (13 allocations: 1.57 MiB)

Notes:

• this code could be still made slightly faster by pre-allocating dat but I tried to bi similar to the original.
• when having unicode characters neither yours nor this approach will not work as you cannot cut a unicode character in the middle

With the help of a colleage we figured out the main reason that makes the provided implementation so slow.

It turns out length(::String) has time complexity O(n) in Julia, and the results are not cached, so the longer the string, the more calls to length which itself takes longer the longer the input. See this Reddit post for a good discussion of the phenomenon:

Collecting the string into a vector resolves the bottleneck, because length of a vector is O(1) instead of O(n).

This is of course by no means the best way to solve the general problem, but it's a one line change that speeds up the code as provided.

This has similar performance to the version by @PrzemyslawSzufel, but is much simpler.

function chop3(s; nc=80)
    L = length(s)
    join((@view s[i:min(i+nc-1,L)] for i=1:nc:L), '\n')
end

I didn't choose firstindex(s), lastindex(s) as strings may not have arbitrary indices, but it makes no difference anyway.

@btime chop3(s) setup=(s=randstring(10^6))  # 1.625 ms (18 allocations: 1.13 MiB)
@btime chop2(s) setup=(s=randstring(10^6))  # 1.599 ms (14 allocations: 3.19 MiB)

Update: Based on suggestions by @BogumiłKamiński, working with ASCII strings, this version with sizeof is even 60% faster.

function chop3(s; nc=80)
    L = sizeof(s)
    join((@view s[i:min(i+nc-1,L)] for i=1:nc:L), '\n')
end