# Super slow string performance

**URL:** <https://discourse.julialang.org/t/super-slow-string-performance/78156>\
**Category:** Performance\
**Tags:** performance\
**Created:** [March 20, 2022, 7:39am UTC](https://discourse.julialang.org/t/super-slow-string-performance/78156 "2022-03-20T07:39:38Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![peteole](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/peteole/32/209790_2.png) [@peteole](https://discourse.julialang.org/u/peteole)\
**Post date:** [March 20, 2022, 7:39am UTC](https://discourse.julialang.org/t/super-slow-string-performance/78156/1 "2022-03-20T07:39:38Z")

</div>

Hi,  
while solving a [coding competition problem](https://codingcompetitions.withgoogle.com/kickstart/round/00000000008cb33e/00000000009e7021#problem) with julia I experienced extreme performance issues with the String type.  
This program:

```julia
function deleteCount(target::String, input::String)
    if length(target) > length(input)
        return "IMPOSSIBLE"
    end
    offset::Int = 0
    for i = 1:length(target)
        while target[i] != input[i+offset]
            offset += 1
            if length(target) > length(input) - offset
                return "IMPOSSIBLE"
            end
        end
    end
    return length(input) - length(target)
end

function processTest(io::IO=stdin)
    numCases = parse(Int, readline(io))
    for i = 1:numCases
        target = readline(io)
        actual = readline(io)
        println("Case #", i, ": ", deleteCount(target, actual))
    end
end
processTest()

```

gets a timeout on the test set with over 20s execution time,  
while the following seemingly similar version of it

```julia
function deleteCount(target::Vector{Char}, input::Vector{Char})
    if length(target) > length(input)
        return "IMPOSSIBLE"
    end
    offset::Int = 0
    for i = 1:length(target)
        while target[i] != input[i+offset]
            offset += 1
            if length(target) > length(input) - offset
                return "IMPOSSIBLE"
            end
        end
    end
    return length(input) - length(target)
end

function processTest(io::IO=stdin)
    numCases = parse(Int, readline(io))
    for i = 1:numCases
        target = readline(io)
        actual = readline(io)
        println("Case #", i, ": ", deleteCount(collect(target), collect(actual)))
    end
end
processTest()

```

finishes in next to no time.

Why are Strings so slow compared to char arrays?

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [March 20, 2022, 7:57am UTC](https://discourse.julialang.org/t/super-slow-string-performance/78156/2 "2022-03-20T07:57:40Z")

</div>

The main difference is that strings are UTF-8-encoded, which is a variable-length encoding. This means that `length` of a string is actually an O(n) operation. Since you’re calling `length` twice in each loop iteration, that means your code is suddenly O(n^2) instead of O(n).

From the way you are indexing the strings, you also seem to assume that all characters you are reading in are ASCII, since you always increase your offset by 1. This will error if the input contains any non-ASCII characters, typically you’ll want to use `nextind` or just a for loop over `eachindex(::String)` instead.

Julia does allow you to index strings by single-byte code units, which might be what you want. You can use `codeunit(s, i)` to get the ith code unit and `codeunits(s)` to get the total number of code units. Those will both be O(1) operations.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [March 31, 2022, 8:59am UTC](https://discourse.julialang.org/t/super-slow-string-performance/78156/3 "2022-03-31T08:59:46Z")

</div>

Since your strings are not changed in the loop, and thus the lengths constant, then it seems you can change to:

```julia
    len_target = length(target); len_input = length(input)
    for i = 1:len_target
        while target[i] != input[i+offset]
            offset += 1
            if len_target > len_input - offset
                return "IMPOSSIBLE"
            end
        end
    end

```

I would like the Julia compiler to be able to make that transformation, but it’s probably too non-obvious for compilers (and sometimes humans!). Not sure what they do for other languages, e.g. C++.