Testing performance of new short-circuiting any and all

shortcircuiting-any-all-test.jl

#============================================================#
# detailed()
#   prints expanded tests with average time,
#   minimum time, maximum time, and result.
#
#------------------------------------------------------------
# summarized()
#   prints average times.
#
#============================================================#

## Definitions of the new `any` and `all`

include("shortcircuiting-any-v1.jl")
include("shortcircuiting-any-v2.jl")
include("shortcircuiting-any-v3.jl")
include("shortcircuiting-any-v4.jl")

## Test functions

function print_section(name::AbstractString)
    println("#$("-"^64)")
    println("# $name")
    println("#$("-"^64)")
end

macro section(name, ex)
    quote
        $print_section($name)
        $(esc(ex))
    end
end

function timeof(f)
    st = time_ns()
    f()
    time_ns() - st
end

function timestring(x)
    for (t,name) in [
        (10^9, "seconds")
        (10^6, "milliseconds")
        (10^3, "microseconds")
        (1,    "nanoseconds")]
        if x >= t
            indent = (3-Int(trunc(log10(x / t))))
            string = balance_string("$(x / t)", name, 8-indent, "0")
            return (" "^indent)*string
        end
    end
    return "--"
end

function balance_string(a,b,len,fill)
    length(a) > len? "$(a[1:end-(length(a)-len)]) $b" :
    length(a) < len? "$(a*(fill^(len-length(a)))) $b" :
    "$a $b"
end

function benchmark(f)
    times   = Float64[]
    mintime = Inf
    maxtime = -1.0
    for i=1:200
        t = timeof(f)
        push!(times, t)
        if t != 0
            mintime = min(t, mintime)
            maxtime = max(t, maxtime)
        end
    end
    average = sum(times) / length(times)
    
    average, mintime, maxtime
end
    
    
function times_and_result(ex)
    quote
        average, mintime, maxtime = benchmark(()->$ex)
        println(
        """
            result = $($ex)
            average time = $(timestring(average))
            
            maximum time = $(timestring(maxtime))
            minimum time = $(timestring(mintime))
        """
        )
    end
end

function average_time(name, ex)
    quote
        average,_,_ = benchmark(()->$ex)
        println("    $($name) = $(timestring(average))")
    end
end
            

printcall(fun, args) = printcall(STDOUT, fun, args)

function printcall(io, fun, args)
    print_with_color(:yellow, io, string(fun))
    print(io, "(")
    map(x->print(io, clear(x),", "), args[1:end-1])
    print(io, clear(args[end]), ")")
end

clear(ex) = ex
clear(ex::Expr) =
    ex.head == :tuple?
        :($(ex.args[1:8]...), $(ex.args[9])...,) :
        Expr(ex.head, map(clear, ex.args)...)

oldf(fun,args)   = :($fun($args...))
newf(fun,args,x) = :($(getfield(eval(parse("V$x")), fun))($args...))

const VN = 4

macro forcode(i_in_A, code)
    i,A = i_in_A.args
    :(quote
        $([:($($code)) for $i in $A]...)
    end)
end
            

macro testtime(fun, xs...)
    quote
        printcall($fun, $xs)
        println()
        let args = ($(xs...),)
            @section "old $($fun)" begin
                $(times_and_result(oldf(fun,:args)))
            end
            
            $(@forcode n in 1:VN quote
                @section "new $($fun) V$($n)" begin
                    $(times_and_result(newf(fun,:args,n)))
                end
            end)
            
        end
        println()
    end
end

macro comparetime(fun, xs...)
    quote
        let args = ($(xs...),)
            @section $(sprint(printcall, fun, xs)) begin
                $(average_time("old $(fun)   ", oldf(fun,:args)))
                
                $(@forcode n in 1:VN quote
                    $(average_time("new $(fun) V$n", newf(fun,:args,n)))
                 end)
            end
        end
        println()
    end
end

lessthan0(x)    = x < 0
greaterthan0(x) = x > 0
equalsto1000(x) = x == 1000
diffthan5000(x) = x != 5000

const tests = [
    :(any([false for x in 1:100000]))
    :(any(($([false for x in 1:1000]...),)))
    :(any([[false for x in 1:50000]; [true]; [false for x in 1:50000]]))
    :(any($lessthan0,  1:10000))
    :(any($equalsto1000, 1:10000))
    :(any($equalsto1000, Set(1:10000)))
    :(any(1:100000 .< -1))
    :(any(1:100000 .== 50000))
    :(all([true for x in 1:100000]))
    :(all(($([true for x in 1:1000]...),)))
    :(all([[true for x in 1:50000]; [false]; [true for x in 1:50000]]))
    :(all($greaterthan0,  1:10000))
    :(all($diffthan5000, 1:10000))
    :(all($diffthan5000, Set(1:10000)))
    :(all(1:100000 .> -1))
]

@eval function detailed()
    $([:(@testtime $(test.args...)) for test in tests]...)
end

@eval function summarized()
    $([:(@comparetime $(test.args...)) for test in tests]...)
end

shortcircuiting-any-all-v1.jl

module V1

import Base: IdFun, Func, specialized_unary, _msk64, _msk_end

function any(itr)
    for x in itr
        x && return true
    end
    return false
end

function any(f, itr)
    for x in itr
        f(x) && return true
    end
    return false
end

function all(itr)
    for x in itr
        !x && return false
    end
    return true
end

function all(f, itr)
    for x in itr
        !f(x) && return false
    end
    return true
end

# BitArray methods (unmodified)

function all(B::BitArray)
    length(B) == 0 && return true
    Bc = B.chunks
    @inbounds begin
        for i = 1:length(Bc)-1
            Bc[i] == _msk64 || return false
        end
        Bc[end] == _msk_end(B) || return false
    end
    return true
end

function any(B::BitArray)
    length(B) == 0 && return false
    Bc = B.chunks
    @inbounds begin
        for i = 1:length(Bc)
            Bc[i] == 0 || return true
        end
    end
    return false
end

end

shortcircuiting-any-all-v2.jl

module V2

import Base: IdFun, Func, specialized_unary, _msk64, _msk_end

any(itr)    = any(IdFun(), itr)
any(f, itr) = any(specialized_unary(f), itr)

function any(f::IdFun, itr)
    for x in itr
        x && return true
    end
    return false
end

function any(f::Func{1}, itr)
    for x in itr
        f(x) && return true
    end
    return false
end

function any(f::IdFun, itr::Array{Bool, 1})
    i   = 1
    len = length(itr)
    while i <= len
       @inbounds x = itr[i]
       x && return true
       i += 1
    end
    return false
end

function any(f::IdFun, itr::Array)
    error("any(itr) expects the elements of itr to be booleans.")
end

function any{T}(f::Func{1}, itr::Array{T})
    i   = 1
    len = length(itr)
    while i <= len
       @inbounds x = itr[i]
       f(x) && return true
       i += 1
    end
    return false
end

all(itr)    = all(IdFun(), itr)
all(f, itr) = all(specialized_unary(f), itr)

function all(f::IdFun, itr)
    for x in itr
        !x && return false
    end
    return true
end

function all(f::Func{1}, itr)
    for x in itr
        !f(x) && return false
    end
    return true
end

function all(f::IdFun, itr::Array{Bool})
    i   = 1
    len = length(itr)
    while i <= len
       @inbounds x = itr[i]
       !x && return false
       i += 1
    end
    return true
end

function all(f::IdFun, itr::Array)
    error("all(itr) expects the elements of itr to be booleans.")
end

function all{T}(f::Func{1}, itr::Array{T})
    i   = 1
    len = length(itr)
    while i <= len
       @inbounds x = itr[i]
       !f(x) && return false
       i += 1
    end
    return true
end


# BitArray methods (unmodified)

function all(B::BitArray)
    length(B) == 0 && return true
    Bc = B.chunks
    @inbounds begin
        for i = 1:length(Bc)-1
            Bc[i] == _msk64 || return false
        end
        Bc[end] == _msk_end(B) || return false
    end
    return true
end

function any(B::BitArray)
    length(B) == 0 && return false
    Bc = B.chunks
    @inbounds begin
        for i = 1:length(Bc)
            Bc[i] == 0 || return true
        end
    end
    return false
end

end

shortcircuiting-any-all-v3.jl

module V3

import Base: IdFun, Func, UnspecializedFun, specialized_unary, _msk64, _msk_end

any(itr) = any(IdFun(), itr)
    
any(f, itr) =
    isgeneric(f)? # temporary hack to avoid needing the indentity function early
        any(specialized_unary(f),   itr) :
        any(UnspecializedFun{1}(f), itr)

function any(f::Func{1}, itr)
    for x in itr
        f(x) && return true
    end
    return false
end

function any{T <: Union(Signed,Unsigned)}(f::IdFun, itr::AbstractArray{T})
    # maybe deprecate this?
    reduce(|, itr)
end

function any(f::Func{1}, itr::AbstractArray)
    @inbounds for x in itr
        f(x) && return true
    end
    return false
end

all(itr) = all(IdFun(), itr)
    
all(f, itr) =
    isgeneric(f)? # temporary hack to avoid needing the indentity function early
        all(specialized_unary(f),   itr) :
        all(UnspecializedFun{1}(f), itr)

function all(f::Func{1}, itr)
    for x in itr
        !f(x) && return false
    end
    return true
end

function all(f::Func{1}, itr::AbstractArray)
    @inbounds for x in itr
        !f(x) && return false
    end
    return true
end

function all{T <: Union(Signed,Unsigned)}(f::IdFun, itr::AbstractArray{T})
    # maybe deprecate this?
    reduce(&, itr)
end

# BitArray methods (unmodified)

function all(B::BitArray)
    length(B) == 0 && return true
    Bc = B.chunks
    @inbounds begin
        for i = 1:length(Bc)-1
            Bc[i] == _msk64 || return false
        end
        Bc[end] == _msk_end(B) || return false
    end
    return true
end

function any(B::BitArray)
    length(B) == 0 && return false
    Bc = B.chunks
    @inbounds begin
        for i = 1:length(Bc)
            Bc[i] == 0 || return true
        end
    end
    return false
end

end

shortcircuiting-any-all-v4.jl

module V4

import Base: IdFun, Func, OrFun, AndFun,
       UnspecializedFun, specialized_unary, 
       _msk64, _msk_end,
       call, depwarn, return_types,
       identity, abs, abs2, exp, log, mr_empty,
       _mapreduce

# functors.jl

type Predicate <: Func{1}
    f::Function
end
call(pred::Predicate, x) = pred.f(x)::Bool

returntype(f, types::Tuple)          = return_types(call, (typeof(f), types...))
returntype(f::Predicate, ::Tuple)    = [Bool]
returntype(f::IdFun, types::Tuple)   = collect(types)
returntype(f::Function, types::Type) = return_types(f, types)

returntype(f::UnspecializedFun, types::Tuple) = return_types(f.f, types)


# reduce.jl

const ShortCircuits = Union{AndFun, OrFun}
typealias Iterable{T} Union{Tuple{T}, AbstractArray{T}, Set{T}}

iszero(x::Bool) = !x
iszero{T}(x::T) =  x == zero(T)

ismax(x::Bool) = x
ismax{T}(x::T) = x == typemax(T)

shortcircuits{T <: Integer}(::AndFun, x::T) = iszero(x)
shortcircuits{T <: Integer}(::OrFun,  x::T) = ismax(x)

shortcircuits(::ShortCircuits, x) = false

shorted(::AndFun) = false
shorted(::OrFun)  = true

# temporary support for deprecated the (Char,Char) methods of & and |
shortcircuits(::AndFun, x::Char) = iszero(x)
shortcircuits(::OrFun,  x::Char) = ismax(x)
#---

sc_finish(::AndFun) = true
sc_finish(::OrFun)  = false

macro inbounds_if_array(itr, block)
    quote
        if isa($itr, $AbstractArray)
            @inbounds $(esc(block))
        else
            $(esc(block))
        end
    end
end

function mapreduce_sc(f::Func{1}, op::ShortCircuits, itr)
    isempty(itr) && return mr_empty(f,op,itr)
    
    x = first(itr)
    r = f(x)
    t = typeof(r)
    
    ftypes = returntype(f, (eltype(itr),))
    
    if ftypes == [t] && t <: Integer && isleaftype(t)
        shortcircuits(op,r) && return r
        mapreduce_sc(f, op, itr, r)
    else
        _mapreduce(f, op, itr)
    end
end

function mapreduce_sc{T}(f::Func{1}, op::ShortCircuits, itr, r::T)
    local v::T = r
    @inbounds_if_array itr begin
        for x in itr
            v = op(v, f(x)::T)
            shortcircuits(op, v) && return v
        end
    end
    return v
end

# optimization for bool results: No need to keep track of previous results
function mapreduce_sc(f::Func{1}, op::ShortCircuits, itr, r::Bool)
    @inbounds_if_array itr begin
        for x in itr
            v::Bool = f(x)::Bool
            shortcircuits(op, v) && return shorted(op)
        end
    end
    return sc_finish(op)
end

mapreduce_sc(f::Function, op::ShortCircuits, itr) =
    mapreduce_sc(specialized_unary(f), op, itr)

    
# resolve ambiguity
mapreduce(f, op::ShortCircuits, itr::AbstractArray) =
    mapreduce_sc(f, op, itr)

# entry method
mapreduce(f, op::ShortCircuits, itr) =
    mapreduce_sc(f, op, itr)


# any & all

# make sure that the specializable unary functions are defined before `any` or `all` are used
for fun in [:identity, :abs, :abs2, :exp, :log]
    eval(Expr(:function, fun))
end

any(itr) = any(IdFun(), itr)
all(itr) = all(IdFun(), itr)

function any(f, itr)
    specf  = isgeneric(f)? specialized_unary(f) : Predicate(f)
    any(specf, itr)
end

function any(f::Func{1}, itr)
    result = mapreduce_sc(f, OrFun(), itr)
    isa(result, Bool)? result : nonboolean_any(result) 
end

function all(f, itr)
    specf  = isgeneric(f)? specialized_unary(f) : Predicate(f)
    all(specf, itr)
end

function all(f::Func{1}, itr)
    result = mapreduce_sc(f, AndFun(), itr)
    isa(result, Bool)? result : nonboolean_all(result)
end


# deprecate.jl
# when removing these deprecations, move them to reduce.jl, remove the depwarns and uncomment the errors.
function nonboolean_any(result)
    depwarn("any(f, itr) where f doesn't return bool is deprecated, use mapreduce(f, |, itr) instead.", :nonboolean_any)
    #throw(ArgumentError("any(f, itr) only accepts functions that return booleans. Use mapreduce(f, |, itr) instead."))
    return result
end

function nonboolean_all(result)
    depwarn("all(f, itr) where f doesn't return bool is deprecated, use mapreduce(f, &, itr) instead.", :nonboolean_all)
    #throw(ArgumentError("all(f, itr) only accepts functions that return booleans. Use mapreduce(f, &, itr) instead."))
    return result
end
#---

# bitarray.jl
# BitArray methods (unmodified)

function all(B::BitArray)
    length(B) == 0 && return true
    Bc = B.chunks
    @inbounds begin
        for i = 1:length(Bc)-1
            Bc[i] == _msk64 || return false
        end
        Bc[end] == _msk_end(B) || return false
    end
    return true
end

function any(B::BitArray)
    length(B) == 0 && return false
    Bc = B.chunks
    @inbounds begin
        for i = 1:length(Bc)
            Bc[i] == 0 || return true
        end
    end
    return false
end

end