String search operations needlessly allocate

[jakobnissen]

For example, findfirst("abc", "ab") eventually ends up calling:

function _searchindex(s::String, t::String, i::Integer)
    # Check for fast case of a single byte
    lastindex(t) == 1 && return something(findnext(isequal(t[1]), s, i), 0)
    _searchindex(unsafe_wrap(Vector{UInt8},s), unsafe_wrap(Vector{UInt8},t), i)
end

The unsafe_wrap allocates, which slows down string search.
However, when I tried replacing the unsafe_wrap(Vector{UInt8}, ::String) with codeunits(::String), Julia failed to bootstrap.

There are a number of similar unsafe_wrap calls in the same file.

It would be nice to remove this allocation, somehow.

[Moelf]

I would have thought the easier thing to do is to replace

_searchindex(unsafe_wrap(Vector{UInt8},s), unsafe_wrap(Vector{UInt8},t), i)

with

_searchindex(codeunits(s), codeunits(t), i)

but this didn't remove allocation

[bicycle1885]

Actually, I have noticed and solved this in #40120 by rewriting the code entirely.

[stevengj]

Since #40120 is breaking and is marked as "Julia 2.0", we need another solution here. Why doesn't using codeunits(s) remove the allocation?

[jakobnissen]

That would be a good idea, but Julia fails to build when I try to do that.

[KristofferC]

I tried it and it worked fine and it seemed to remove the allocation... So what error do you get?

diff --git a/base/strings/search.jl b/base/strings/search.jl
index eade1fbe74..6a617dd2a0 100644
--- a/base/strings/search.jl
+++ b/base/strings/search.jl
@@ -55,7 +55,7 @@ function _search(a::ByteArray, b::AbstractChar, i::Integer = 1)
     if isascii(b)
         _search(a,UInt8(b),i)
     else
-        _search(a,unsafe_wrap(Vector{UInt8},string(b)),i).start
+        _search(a,codeunits(string(b)),i).start
     end
 end
 
@@ -98,7 +98,7 @@ function _rsearch(a::ByteArray, b::AbstractChar, i::Integer = length(a))
     if isascii(b)
         _rsearch(a,UInt8(b),i)
     else
-        _rsearch(a,unsafe_wrap(Vector{UInt8},string(b)),i).start
+        _rsearch(a,codeunits(string(b)),i).start
     end
 end
 
@@ -207,7 +207,7 @@ _nthbyte(t::AbstractVector, index) = t[index + (firstindex(t)-1)]
 function _searchindex(s::String, t::String, i::Integer)
     # Check for fast case of a single byte
     lastindex(t) == 1 && return something(findnext(isequal(t[1]), s, i), 0)
-    _searchindex(unsafe_wrap(Vector{UInt8},s), unsafe_wrap(Vector{UInt8},t), i)
+    _searchindex(codeunits(s), codeunits(t), i)
 end
 
 function _searchindex(s::AbstractVector{<:Union{Int8,UInt8}},
@@ -521,7 +521,7 @@ function _rsearchindex(s::String, t::String, i::Integer)
         return something(findprev(isequal(t[1]), s, i), 0)
     elseif lastindex(t) != 0
         j = i ≤ ncodeunits(s) ? nextind(s, i)-1 : i
-        return _rsearchindex(unsafe_wrap(Vector{UInt8}, s), unsafe_wrap(Vector{UInt8}, t), j)
+        return _rsearchindex(codeunits(s), codeunits(t), j)
     elseif i > sizeof(s)
         return 0
     elseif i == 0

[jakobnissen]

It build for me just fine on master (0c3b950) with that diff. Don't know what happened last time. Let me make a PR!