# Would a search directly calling memchr have disadvantages?

**URL:** <https://discourse.julialang.org/t/would-a-search-directly-calling-memchr-have-disadvantages/92592>\
**Category:** Performance\
**Created:** [January 6, 2023, 7:49am UTC](https://discourse.julialang.org/t/would-a-search-directly-calling-memchr-have-disadvantages/92592 "2023-01-06T07:49:02Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![CodeGodz](https://avatars.discourse-cdn.com/v4/letter/c/aeb1de/32.png) [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)\
**Post date:** [January 6, 2023, 7:49am UTC](https://discourse.julialang.org/t/would-a-search-directly-calling-memchr-have-disadvantages/92592/1 "2023-01-06T07:49:02Z")

</div>

Just looking at the [ScanByte](https://github.com/jakobnissen/ScanByte.jl) package by @jakobnissen (thanks for giving me ideas! 🙂 ). It’s written to find the first occurrence of a given byte in a byte array. Just as a test I thought I can also call `memchr` iteratively to find all matches in an array like so:

(P.s. never used `ccall` before this so let me know if I messed something up)

```julia
@inline function byte_scan(mem::Vector{UInt8}, byte::UInt8)
    c = 0
    @GC.preserve begin
        mem_start::Ptr{UInt8} = pointer(mem)
        mem_length = length(mem)
        actual_index::Int64 = 0
        while mem_length > 1
            pos = @ccall memchr(mem_start::Ptr{UInt8}, byte::Cint, mem_length::Csize_t)::Ptr{Cchar}
            if pos == C_NULL
                return c
            else
                mem_start = pos + 1 # not sure how to fix this type instability)
                actual_index = ((pos - pointer(mem)) + 1) % Int64
                mem_length = length(mem) - actual_index 
                c += actual_index
            end
        end
    end
    return c
end

```

(_Summing them doesn’t make much sense but just to do something with the returned indexes_)

Which would be similar to searching it with a loop in base julia:

```julia
@inline function base_scan(mem::Vector{UInt8}, byte::UInt8)
    c = 0
    @inbounds for i in eachindex(mem)
        if mem[i] == byte
            c += i
        end 
    end 
    return c
end

```

Using `memchr` is much faster on my PC:

```julia
function test()
    target = 0x41
    Random.seed!(3)
    arr = rand(UInt8, 10_000_000)
    # Search 'A' in the random char array
    @btime byte_scan($arr, $target)
    @btime base_scan($arr, $target)
    @assert byte_scan(arr, target) == base_scan(arr, target)
end

  1.161 ms (0 allocations: 0 bytes)
  13.498 ms (0 allocations: 0 bytes)

```

Will this have any major drawbacks that I’m missing or could I just swap this `memchr` in?

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [January 6, 2023, 8:04am UTC](https://discourse.julialang.org/t/would-a-search-directly-calling-memchr-have-disadvantages/92592/2 "2023-01-06T08:04:31Z")

</div>

You could swap memchr in. But you might want to check out Base.findnext, which I believe is also very fast because it calls memchr under the hood.

---

<div class="post-metadata">

**Author:** ![CodeGodz](https://avatars.discourse-cdn.com/v4/letter/c/aeb1de/32.png) [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)\
**Post date:** [January 6, 2023, 8:32am UTC](https://discourse.julialang.org/t/would-a-search-directly-calling-memchr-have-disadvantages/92592/3 "2023-01-06T08:32:29Z")

</div>

Is this what you mean:

```julia
@inline function next_scan(mem::Vector{UInt8}, byte::UInt8)
    c = 0
    index = 1
    @inbounds while index < length(mem)
        index = findnext(x -> x == byte , mem, index+1)
        if isnothing(index)
            return c 
        else
            c += index 
        end
    end
    return c
end

```

That times at:

```julia
8.706 ms (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![CodeGodz](https://avatars.discourse-cdn.com/v4/letter/c/aeb1de/32.png) [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)\
**Post date:** [January 6, 2023, 8:35am UTC](https://discourse.julialang.org/t/would-a-search-directly-calling-memchr-have-disadvantages/92592/4 "2023-01-06T08:35:41Z")

</div>

Looks like base uses `memchr` in [`_search`](https://github.com/JuliaLang/julia/blob/84e9989bee4ca9dce57ebe7b2a6d4e074c55b3b3/base/strings/search.jl#L41) and that indeed gets called by [`findnext`](https://github.com/JuliaLang/julia/blob/84e9989bee4ca9dce57ebe7b2a6d4e074c55b3b3/base/strings/search.jl#L35). Maybe I’m missing something here 🤔

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [January 6, 2023, 11:56am UTC](https://discourse.julialang.org/t/would-a-search-directly-calling-memchr-have-disadvantages/92592/5 "2023-01-06T11:56:40Z")

</div>

It needs to be `findnext(isequal(my_byte), my_arr, my_ind)`. If you use an anoymous function, it will not dispatch to `memchr`.

---

<div class="post-metadata">

**Author:** ![CodeGodz](https://avatars.discourse-cdn.com/v4/letter/c/aeb1de/32.png) [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)\
**Post date:** [January 6, 2023, 12:07pm UTC](https://discourse.julialang.org/t/would-a-search-directly-calling-memchr-have-disadvantages/92592/6 "2023-01-06T12:07:38Z")

</div>

Aaah that comes much closer indeed:

```julia
  1.115 ms (0 allocations: 0 bytes) # Direct
  1.622 ms (0 allocations: 0 bytes) # findnext
  4.140 ms (0 allocations: 0 bytes) # loop

```

Thanks 🙂