New find* methods and type stability

General Usage
1

In 0.7 find* methods changed the return value from 0 to nothing for no match. Assuming the following code is in a function:

s = "abc"
pos = findfirst(equalto('b'), s)
println(typeof(pos))
pos = findfirst(equalto('x'), s)
println(typeof(pos))

The type of pos changes from Int to Nothing. Will this type instability cause performance issues? Should I declare pos with type Union{Nothing, Int}?

2

The compiler is pretty good at these types of type instabilities. So benchmark your code and unless you notice a problem, just done worry about it.

3

Hmm. The following looks like it regresses quite severely:

versioninfo()
#Julia Version 0.6.2
using BenchmarkTools

struct equalto_{T} <: Function
       x::T
end
(eq_::equalto_{T})(y) where T = isequal(eq_.x, y)

V=[rand(UInt8, rand(0:255)) for i=1:1000];
Q=rand(UInt8, 1000);

function foolistsearch6(Q, V)
     out = Vector{Int}(length(V))
     for i=1:length(V)
           pos = findfirst(equalto_(Q[i]), V[i])
               if pos===0
                    out[i]=-1
               else
                    out[i]=pos
               end
     end
     out
 end
@btime foolistsearch6(Q,V);
#115.033 ��s (1 allocation: 7.94 KiB)
Q=rand(UInt16, length(Q));
@btime foolistsearch6(Q,V);
#148.848 ��s (1 allocation: 7.94 KiB)

versioninfo()
#Julia Version 0.7.0-DEV.3666
#Commit 0f95988141* (2018-01-31 03:25 UTC)
using BenchmarkTools

V=[rand(UInt8, rand(0:255)) for i=1:1000];
Q=rand(UInt8, 1000);

function foolistsearch7(Q, V)
     out = Vector{Int}(length(V))
     for i=1:length(V)
           pos = findfirst(equalto(Q[i]), V[i])
               if pos===nothing
                    out[i]=-1
               else
                    out[i]=pos
               end
     end
     out
 end

@btime foolistsearch7(Q,V)
154.900 ��s (88 allocations: 19.52 KiB)
Q=rand(UInt16, length(Q));
@btime foolistsearch7(Q,V)
287.831 ��s (88 allocations: 19.52 KiB)

I am not sure whether my example code simply sucks, or my example is badly chosen or whether this is due to the new handling.

4

I’d suggest trying on the latest Julia master. The performance improvements for small unions are new in v0.7.

5

They both are on 0.7. @foobar_lv2 — you have a deprecated method in your version 7 example. Changing Vector{Int}(length(V)) to Vector{Int}(uninitialized, length(V)) gives me nearly a 4x speed up.

Deprecations are slow. Fix that and 0.7 is way faster in my tests.

6 Likes
6

Ok, you’re right. Somehow I naively thought that deprecations would only show warnings and induce slow-down during compilation.

The new timings are:

  21.713 ��s (1 allocation: 7.94 KiB)
 152.476 ��s (1 allocation: 7.94 KiB)

which is indeed way faster than 0.62. I hereby retract all my objections :slight_smile:

PS at rddeits: You see from the versionstring that my 0.7 version was a master less than 48 hours old. I shall continue to post versioninfo() for all timings (master is moving so fast).

7

Ah yes, I missed that, sorry.