Showing an `AnnotatedString` is `O(length_string * num_annotations)`

[KristofferC]

There are many cases where the function at https://github.com/JuliaLang/julia/blob/c6732a79494f604e0f320ea451856a1c10511659/base/strings/annotated.jl#L396-L401 gets called a number of times proportional to the length of the string (leading to quadratic behavior).

StyledStrings.jl/src/regioniterator.jl

Line 52 in f7af623

push!(annots, map(last, annotations(s, start)))

is one such place.

When you iterate an AnnotatedString character by character (as e.g. escape_string does in Base) it also shows up.

I think it would be good to:

• do some pre processing of the annotations so that there is no need to do this type of random access lookup of them
• provide a better iterator over an AnnotatedString that uses something similar to eachregion instead of having to do everything from scratch for every character.

Printing a somewhat long string to stdout is noticeably quite slow.

Some code to generate a long string:

using Random

function generate_annot_string(n)
    colors = [:yellow, :green, :blue, :red]
    offset = 1
    annotations = Tuple{UnitRange{Int64}, Pair{Symbol, Any}}[]
    while true
        col = rand(1:length(colors))
        l = rand(1:10)
        offset + l > n && break
        push!(annotations, (offset:(offset+l), :face => colors[col]))
        offset += l
    end
    s = randstring(n)
    return Base.AnnotatedString(s, annotations)
end

str = generate_annot_string(100000)

[tecosaur]

Yea, @LilithHafner and I talked about this a while ago that resulted in JuliaLang/julia#54289. It used to be a sorted list so searchsortedfirst could be used and came to the conclusion that this made the semantics worse and we should remove ordering assumptions, with sorting being something that could be done on-demand as a preprocessing step when needed.

Using the example you provided, @time show(stdout, MIME("text/plain"), str) gives a whopping 2.2s on my machine. The current (unoptimised) eachregion-backed @time println(str) gives a better but still unimpressive time of 0.4s.

I've just had a go at optimising eachregion by pre-sorting the annotations. With my changes, @time println(str) is O(n log n) and takes 0.015s. Much better!

That doesn't help with show being char-by-char and still O(n m), but I think it shows a path to acceptable performance.

[tecosaur]

I wonder why the string limiting doesn't apply?

julia> show(IOContext(stdout, :limit => true), MIME("text/plain"), String(str))
"XE0ooPvnGBs4ubRE2c8UdJki4UpbI3t2SGnqaAgVLPUba8ZJHjJe4PRfu6x1Z1OnMQcTI95jhn8DMSe507ei272QIsAnBLV5dFGzgb390kkd9ywVQ6z0PXPtIT1s685CeqkHqnIMLzQKhQjEoCcvNQXXydm16VMRmiaW5e3JkkjiJkALdpRj74eq7yHPZgueh88h3yJkxxM8mfEx61iKs5kKdLf3MyfCYZcmRs8EuQV2aGjrAazmMKevtDIf5Cp4tYeGMEBuwC1zZ0Pn7pL8TSKsZTRL73ed9gt9BIf7t2Njf8HxeerwtBZwZTMpa3oFCWRIoov2s7470AlR" ⋯ 99328 bytes ⋯ "9i3zXHswaDfMcXuZExW7dxsXPJj75Mz3ymckh3USUj84YDg3QBiFMLCFQaGJMXAzIrHBA8B0nK3eegTXHBWsJTVuN4KRo3bPjqoLSD103T8MXgncZbt9AdqctEYCtKbHgVLg7Gig3n4r14E8iYYE0wV1EmD43IOLqzKCtKZCu3xdKLMvrG9Ri22TfZMtKJeGQMFfCea9OMa5908TJQ9knjmd68MWN11pxkCAKJgTba3BT6wNBOkSg1gxkm1nlAzx44lPARaWnI14Wkw0wgk8a4XkANjKQkFfrK9BHSrdSMvqLy4215Xc6PZz7S7y1WqnWOxkbS6Az5AW4trX"
julia> show(IOContext(stdout, :limit => true), MIME("text/plain"), str)
# The entire string shows, with no truncation

[tecosaur]

Ok, that deserves it's own investigation, but I've just discovered why show is so much slower than print: While an optimized escape_string is defined, Base.escape_string isn't imported 🤦 (I suppose this is another argument for #69).

With an added Base., I now see:

juila> @time show(stdout, MIME("text/plain"), str)
"... lots of output..."
 0.037248 seconds (552.72 k allocations: 26.695 MiB, 35.34% gc time)

So, as of #74 original issue raised here will be fixed.