Skip to content

Instantly share code, notes, and snippets.

@JeffreySarnoff

JeffreySarnoff/firstindex_study.jl

Last active February 15, 2021 12:46
Show Gist options
  • Save JeffreySarnoff/919f92029ff7355d1340ae6683469ec7 to your computer and use it in GitHub Desktop.
Save JeffreySarnoff/919f92029ff7355d1340ae6683469ec7 to your computer and use it in GitHub Desktop.
Download ZIP
benchmarking firstindex
Raw
firstindex_study.jl
using BenchmarkTools
const BT=BenchmarkTools.DEFAULT_PARAMETERS;
BT.samples=60_000; BT.time_tolerance=1/8192;
#=
IS{Int64} == Union{Int64, Symbol}
IS{Int32} == Union{Int32, Symbol}
=#
const IS = Union{I,Symbol} where {I<:Integer}
# test vars, length(chrs) == 96
seqlen = (8, Tuple((16 * i for i=1:6))...,);
middles = (4, 12, Tuple(collect(8+(16 * i) for i=1:5))...,);
finals = deepcopy(seqlen)
chrs = Char.(Int('a'):Int('p'));
syms = Tuple(collect(Iterators.flatten(map(x->Symbol(x,i), chrs) for i=1:6)));
strs = string.(syms);
ints = Tuple(collect(1:length(syms)));
symseqs = collect(syms[1:n] for n in seqlen);
intseqs = collect(ints[1:n] for n in seqlen);
strseqs = collect(strs[1:n] for n in seqlen);
nt_ints = map((symseq,intseq)->NamedTuple{symseq}(intseq), symseqs, intseqs);
nt_strs = map((symseq,strseq)->NamedTuple{symseq}(strseq), symseqs, strseqs);
function indexof(item::T, seq::NTuple{N, T}) where {N,T}
if N < 33
indexof_recur(item, seq)
else
indexof_iter(item, seq)
end
end
function indexof_recur(item::T, seq::NTuple{N, T}, idx=1) where {N,T}
item === first(seq) ? idx : indexof_recur(item, Base.tail(seq), idx+1)
end
indexof_recur(item::T, seq::Tuple{}, idx=1) where {T} = 0
@inline function indexof_iter(item::T, seq::NTuple{N, T}) where {N,T}
equalsx = Base.Fix2(===, item)
idx = 1
for x in seq
equalsx(x) && break
idx = idx + 1
end
return idx > N ? 0 : idx
end
function indexof(item::T, seq::Vector{T}) where {T}
equalsx = Base.Fix2(===, item)
idx = 1
for x in seq
equalsx(x) && break
idx = idx + 1
end
return idx > length(seq) ? 0 : idx
end
#=
v1.7
indexof(item, seq) best times
| seqlen | item | tuple ns | vector ns |
|--------|------|----------|-----------|
| 8 | 4 | 1.9 | 3.5 |
| 8 | 8 | 2.4 | 4.3 |
| 16 | 12 | 3.1 | 5.7 |
| 16 | 16 | 3.8 | 7.1 |
| 32 | 24 | 6.3 | 10.0 |
| 32 | 32 | 7.8 | 12.8 |
| 48 | 40 | 17.9 | 15.8 |
| 48 | 48 | 20.9 | 18.6 |
| 64 | 56 | 24.1 | 21.5 |
| 64 | 64 | 27.7 | 24.3 |
| 80 | 72 | 32.0 | 27.3 |
| 80 | 80 | 41.0 | 35.0 |
| 96 | 88 | 45.0 | 38.3 |
| 96 | 96 | 42.3 | 35.8 |
=#
#=
function indexfirst(x::T, seq::NTuple{N,T}) where {N,T}
if N < 33
return indexfirst_rec(x, seq, 1)
else
return index_first(N, x, seq)
end
end
v1.7
indexfirst(item, seq)
| seqlen | item | tuple ns | vector ns |
|--------|------|----------|-----------|
| 8 | 4 | 1.8 | 2.4 |
| 8 | 8 | 2.4 | 4.3 |
| 16 | 12 | 3.0 | 5.6 |
| 16 | 16 | 3.7 | 7.0 |
| 32 | 24 | 6.4 | 10.0 |
| 32 | 32 | 7.6 | 12.8 |
| 48 | 40 | 18.1 | 15.7 |
| 48 | 48 | 20.3 | 18.2 |
| 64 | 56 | 25.0 | 21.4 |
| 64 | 64 | 27.8 | 24.3 |
| 80 | 72 | 32.0 | 27.3 |
| 80 | 80 | 41.0 | 35.0 |
| 96 | 88 | 45.0 | 38.3 |
| 96 | 96 | 42.3 | 35.8 |
=#
#=
function btime(f, refarg1, refarg2; mulby=1.0e9, digits=2)
t1 = @belapsed $f($refarg1[], $refarg2[])
t2 = @belapsed $f($refarg1[], $refarg2[])
t3 = @belapsed $f($refarg1[], $refarg2[])
t4 = @belapsed $f($refarg1[], $refarg2[])
result = minimum((t1,t2,t3,t4))
result = result * mulby
result = round(result, digits=digits, base=10)
return result
end
function testvals(i)
miditem = Ref(middles[i])
finalitem = Ref(finals[i])
tupl = Ref(intseqs[i])
vect = Ref([intseqs[i]...])
return (miditem, finalitem), (tupl, vect)
end
julia> fn = indexfirst;
julia> (miditem, finalitem), (tupl, vect) = testvals(1); (length=finalitem[],)
(length = 8,)
julia> (n= finalitem[],
tupl= (btime(fn, miditem, tupl), btime(fn, finalitem, tupl)),
vect=(btime(fn, miditem, vect), btime(fn, finalitem, vect)))
(n=8, tupl = (2.7, 3.4), vect = (4.1, 6.0))
julia> btime(fn, miditem, tupl), btime(fn, finalitem, tupl)
3.3, 6.2
julia> btime(fn, miditem, vect), btime(fn, finalitem, vect)
=#
function indexfirst(x::T, seq::NTuple{N,T}) where {N,T}
N < 17 && return indexfirst(Val(N), x, seq)
index_first(N, x, seq)
end
function indexfirst(x::T, seq::V) where {T,V<:AbstractVector{T}}
N = length(seq)
index_first(N, x, seq)
end
@inline function index_first(N, x, seq)
equalsx = Base.Fix2(===, x)
idx = 1
for item in seq
equalsx(item) && break
idx = idx + 1
end
return idx > N ? 0 : idx
end
function indexfirst(x::T, seq::NTuple{N,T}) where {N,T}
if N < 17
return indexfirst(Val(N), x, seq)
elseif N < 33
return indexfirst(x, seq, 1)
elseif N < 65
result = indexfirst(x, seq[1:32], 1)
!iszero(result) && return result
result = indexfirst(x, seq[33:end], 1)
return iszero(result) ? 0 : result + 32
elseif N < 129
result = indexfirst(x, seq[1:64], 1)
!iszero(result) && return result
result = indexfirst(x, seq[65:end], 1)
return iszero(result) ? 0 : result + 64
else
error("seqlen of $N is not supported")
end
end
# recursive
# fast with no allocation until N>32, then 1000x slower
function indexfirst(x::T, seq::NTuple{N,T}, i=1) where {N,T}
x === first(seq) ? i : indexfirst(x, Base.tail(seq), i+1)
end
indexfirst(x::T, seq::Tuple{}) where {T} = 0
indexfirst(x::T, seq::Tuple{}, i) where {T} = 0
# unrolled
# fastest, limit N == 16
function indexfirst(::Val{1}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
(
x === tup[1] && return 1)
return 0
end
function indexfirst(::Val{2}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
((
x === tup[1] && return 1) ||
x === tup[2] && return 2)
return 0
end
function indexfirst(::Val{3}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
(((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3)
return 0
end
function indexfirst(::Val{4}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4)
return 0
end
function indexfirst(::Val{5}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
(((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5)
return 0
end
function indexfirst(::Val{6}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6)
return 0
end
function indexfirst(::Val{7}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
(((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7)
return 0
end
function indexfirst(::Val{8}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
((((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7) ||
x === tup[8] && return 8)
return 0
end
function indexfirst(::Val{9}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
(((((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7) ||
x === tup[8] && return 8) ||
x === tup[9] && return 9)
return 0
end
function indexfirst(::Val{10}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
((((((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7) ||
x === tup[8] && return 8) ||
x === tup[9] && return 9) ||
x === tup[10] && return 10)
return 0
end
function indexfirst(::Val{11}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
(((((((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7) ||
x === tup[8] && return 8) ||
x === tup[9] && return 9) ||
x === tup[10] && return 10) ||
x === tup[11] && return 11)
return 0
end
function indexfirst(::Val{12}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
((((((((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7) ||
x === tup[8] && return 8) ||
x === tup[9] && return 9) ||
x === tup[10] && return 10) ||
x === tup[11] && return 11) ||
x === tup[12] && return 12)
return 0
end
function indexfirst(::Val{13}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
(((((((((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7) ||
x === tup[8] && return 8) ||
x === tup[9] && return 9) ||
x === tup[10] && return 10) ||
x === tup[11] && return 11) ||
x === tup[12] && return 12) ||
x === tup[13] && return 13)
return 0
end
function indexfirst(::Val{14}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
((((((((((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7) ||
x === tup[8] && return 8) ||
x === tup[9] && return 9) ||
x === tup[10] && return 10) ||
x === tup[11] && return 11) ||
x === tup[12] && return 12) ||
x === tup[13] && return 13) ||
x === tup[14] && return 14)
return 0
end
function indexfirst(::Val{15}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
(((((((((((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7) ||
x === tup[8] && return 8) ||
x === tup[9] && return 9) ||
x === tup[10] && return 10) ||
x === tup[11] && return 11) ||
x === tup[12] && return 12) ||
x === tup[13] && return 13) ||
x === tup[14] && return 14) ||
x === tup[15] && return 15)
return 0
end
function indexfirst(::Val{16}, x::T, tup::NTuple{N, T}) where {N, T<:IS{Int}}
((((((((((((((((
x === tup[1] && return 1) ||
x === tup[2] && return 2) ||
x === tup[3] && return 3) ||
x === tup[4] && return 4) ||
x === tup[5] && return 5) ||
x === tup[6] && return 6) ||
x === tup[7] && return 7) ||
x === tup[8] && return 8) ||
x === tup[9] && return 9) ||
x === tup[10] && return 10) ||
x === tup[11] && return 11) ||
x === tup[12] && return 12) ||
x === tup[13] && return 13) ||
x === tup[14] && return 14) ||
x === tup[15] && return 15) ||
x === tup[16] && return 16)
return 0
end
# unrolled k+
function indexfirst(::Val{1}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
(
x === tup[k+1] && return 1)
return 0
end
function indexfirst(::Val{2}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2)
return 0
end
function indexfirst(::Val{3}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
(((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3)
return 0
end
function indexfirst(::Val{4}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4)
return 0
end
function indexfirst(::Val{5}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
(((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5)
return 0
end
function indexfirst(::Val{6}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6)
return 0
end
function indexfirst(::Val{7}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
(((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7)
return 0
end
function indexfirst(::Val{8}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
((((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7) ||
x === tup[k+8] && return 8)
return 0
end
function indexfirst(::Val{9}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
(((((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7) ||
x === tup[k+8] && return 8) ||
x === tup[k+9] && return 9)
return 0
end
function indexfirst(::Val{10}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
((((((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7) ||
x === tup[k+8] && return 8) ||
x === tup[k+9] && return 9) ||
x === tup[k+10] && return 10)
return 0
end
function indexfirst(::Val{11}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
(((((((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7) ||
x === tup[k+8] && return 8) ||
x === tup[k+9] && return 9) ||
x === tup[k+10] && return 10) ||
x === tup[k+11] && return 11)
return 0
end
function indexfirst(::Val{12}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
((((((((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7) ||
x === tup[k+8] && return 8) ||
x === tup[k+9] && return 9) ||
x === tup[k+10] && return 10) ||
x === tup[k+11] && return 11) ||
x === tup[k+12] && return 12)
return 0
end
function indexfirst(::Val{13}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
(((((((((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7) ||
x === tup[k+8] && return 8) ||
x === tup[k+9] && return 9) ||
x === tup[k+10] && return 10) ||
x === tup[k+11] && return 11) ||
x === tup[k+12] && return 12) ||
x === tup[k+13] && return 13)
return 0
end
function indexfirst(::Val{14}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
((((((((((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7) ||
x === tup[k+8] && return 8) ||
x === tup[k+9] && return 9) ||
x === tup[k+10] && return 10) ||
x === tup[k+11] && return 11) ||
x === tup[k+12] && return 12) ||
x === tup[k+13] && return 13) ||
x === tup[k+14] && return 14)
return 0
end
function indexfirst(::Val{15}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
(((((((((((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7) ||
x === tup[k+8] && return 8) ||
x === tup[k+9] && return 9) ||
x === tup[k+10] && return 10) ||
x === tup[k+11] && return 11) ||
x === tup[k+12] && return 12) ||
x === tup[k+13] && return 13) ||
x === tup[k+14] && return 14) ||
x === tup[k+15] && return 15)
return 0
end
function indexfirst(::Val{16}, x::T, k::I, tup::NTuple{N, T}) where {N, I<:Integer, T<:IS{I}}
((((((((((((((((
x === tup[k+1] && return 1) ||
x === tup[k+2] && return 2) ||
x === tup[k+3] && return 3) ||
x === tup[k+4] && return 4) ||
x === tup[k+5] && return 5) ||
x === tup[k+6] && return 6) ||
x === tup[k+7] && return 7) ||
x === tup[k+8] && return 8) ||
x === tup[k+9] && return 9) ||
x === tup[k+10] && return 10) ||
x === tup[k+11] && return 11) ||
x === tup[k+12] && return 12) ||
x === tup[k+13] && return 13) ||
x === tup[k+14] && return 14) ||
x === tup[k+15] && return 15) ||
x === tup[k+16] && return 16)
return 0
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment