Findfirst for Dicts with `nothing` keys

[Liso]

Thanks for clarification!

true + true == 2

Oh my dream about consistency!

[jeff.bezanson]

This is work in progress — there is already a PR up to change find functions to return nothing consistently for not-found. In the case of regexes, a regex can match the empty string so an empty range is in any case not sufficient to mean not-found. searchsorted is different, as you observe.

One possibility is to add an option

findfirst(f, xs, wrap=Some)

to wrap found indices when you might have nothing keys.

[foobar_lv2]

Are we all in agreement about the following?

1. the desired API (if it had somehow no performance overhead) for search methods should be something like Tuple{Bool, Union{ret_type, Nothing}}, and the desired ABI / machine-code would return the bool (found yes/no) via register and would return the return value (found key) via the usual way (which depends on its type), such that the alloc is always elided if I write is_found, key = findstuff(...)?

2. The only problem is that we are currently incapable of cleanly obtaining this desired combination of API and ABI / machine-code, and hence decided for a suboptimal API (sentinel-value nothing) in order to get acceptable (allocation-free) machine-code.

3. In other words, the 0.7 and planned 1.0 API is a work-around for the compiler-limitation that multiple return-values are not supported in a zero-cost way.

4. According to current plans this compiler-limitation won’t go away soon, so it is better to fix the bad API / good performance now and get a good API (truly supporting Any-keys in dicts) in julia 2.

I guess if this was in the official documentation for the API then nobody would be confused, and there would be no need for people to argue.

Or is the general position that a nothing sentinel value that makes Dict with nothing-keys behave weirdly is a better API than returning a tuple with a bool isfound?

edit: Jeff and Stefan corrected me here. This is not the state of the discussion but rather me jumping to wrong conclusions.

[jeff.bezanson]

This is incorrect. We optimize away tuples all the time. I don’t recall seeing a proposal to return a tuple with a found flag — did I miss it? If we’re going to “wrap” the result in some way, we could use Some(x). For many people, the primary API concern is that they do not want to have to manually unwrap values to use them. But I agree found, val = findfirst(...) doesn’t seem so bad.

[ScottPJones]

I had proposed that, as well as found and find_result functions to unwrap the result of a find call for generic code (but the most common case of dealing with strings could continue to simply use a “in-band” sentinel value of 0, since it has been decided that 0 is not a valid index for any AbstractString).

[foobar_lv2]

Thanks, then I misunderstood the discussion.

@jeff.bezanson

We optimize away tuples all the time.

Not really. This is a huge pain-point for me and forces a lot of questionable API decisions. Except if I just failed at coding; in this case I would be extremely grateful to be enlightened.

Let’s do an minimal slowly-working example of the tuple-API that either returns nothing or a non-bitstype, as well as a bool whether the look-up was successful. I was under the impression that the compiler currently does not allow a fast version of this.

@noinline function foo(A::Vector{Vector{Int}},i::Int)::Tuple{Bool, Union{Vector{Int}, Nothing}}
    if 0<i<=length(A)
        return (true,A[i])::Tuple{Bool, Vector{Int}}
    else
        return (false,nothing)::Tuple{Bool, Nothing}
    end
    assert(false)
end

function foosum(A::Vector{Vector{Int}}, indices_::Vector{Int})
    s::Int=0
    for i in indices_
        found, val = foo(A,i)
        if found
            val::Vector{Int}
            s+= val[1]
        end
    end
    s
end

A= [[rand(1:100)] for i=1:1000];

indices_ = rand(1:200, 10^6);
foosum(A,indices_);

@time foosum(A,indices_);
#0.244705 seconds (4.00 M allocations: 76.303 MiB, 19.78% gc time)

versioninfo()
#Julia Version 0.7.0-DEV.3961
#Commit 12964e839e* (2018-02-13 10:42 UTC)

Edit: The pain-point is not the find-API for dicts but the problem of multiple return values.

[StefanKarpinski]

You marked the called function as @noinline so you are explicitly disallowing the compiler from optimizing anything.

[foobar_lv2]

@StefanKarpinski

You marked the called function as @noinline so you are explicitly disallowing the compiler from optimizing anything.

Sure; otherwise it would take quite some time to code up an example that the inliner decides not to inline, and whether it does would be kinda unpredictable. I just remark that findfirst(Base.EqualTo{String}, Dict{Any,Any}) is typically not inlined (in my short experiments on 0.7).

This does not change the fact that multiple return-values currently quite expensive when the resulting tuple is not bitstype. This is an ABI limitation, shared with the C-ABI; and this forces a lot of API decisions, like sentinel-values (apparently the choice for findfirst in julia) or the pattern of passing mutables / pointers / references for writing extra output (typical in in C / C++).

The arguments to a function are typically not bundled into a tuple (which would be expensive, since they currently must be heap-allocated when not inlined), except if there are too many arguments. This is good ABI-design and allows good APIs; it is shared among virtually all programming languages.

Similarly, it would be cool to have multiple return-values as a non-tuple (or a compiler change that makes all small tuples stack-allocated), in order to allow an API that returns both a result and meta-data for the result (in this specific case: the maybe-found key/index and a boolean whether the search was successful; more generally, one can fit a lot of error flags into a machine-size word).

AFAIK such an API is currently impossible with the current compiler (if I want small overhead). Again, I would be very grateful to be corrected.

(and I mistakenly believed that there was consensus that out-of-band signaling of the success of the search would be an optimal API, which is regrettably not supported by the compiler. The same applies for the discussion of the iterator protocol)

[jeff.bezanson]

@foobar_lv2

and this forces a lot of API decisions, like sentinel-values (apparently the choice for findfirst in julia)

You keep claiming this, but I don’t remember anybody saying “Yes, returning a tuple is obviously the best API, but because it will sometimes heap allocate we can’t do it”. Allocation of tuples can’t be influencing design too much, seeing that e.g. the iteration protocol uses tuples heavily (both the new one and the old one).

Look, this is a GC’d language. However painful it might be, sometimes we are going to heap allocate things. In your example the GC overhead is 20%, which is significant, but hardly the end of the world. It is also fully possible to optimize this, and I’m sure we will at some point.

In the specific case of find, allocating a tuple is probably cheap compared to the work the function is doing. I’d expect the overhead to be less than in your example. So I would not personally make the argument that tuples are too slow to use in this API.

[foobar_lv2]

@jeff.bezanson

Look, this is a GC’d language. However painful it might be, sometimes we are going to heap allocate things.

Yes, and the allocation of small things is amazingly fast. Count me happy on alloc / gc speed.

But still, the multiple return-values bite. And this is a problem with the iteration protocol as well: See the trouble with enumerate, or the semi-token API in sorted collections. This got marginally better in 0.7, since many allocations are optimized out when inlined.

@jeff.bezanson

You keep claiming this, but I don’t remember anybody saying “Yes, returning a tuple is obviously the best API, but because it will sometimes heap allocate we can’t do it”.

You are correct. I am the only one saying this, and I entirely misread the state of the discussion. Sorry for jumping to wrong conclusions.

That being said, if it did not have the alloc / multiple return-value problem then I would argue for returning a tuple (or more generally, out-of-band signaling of search success). And I am slightly unhappy that this is not a realistic option, currently, and claiming that this constrains many decisions, even though this one would apparently not go for out-of-band signaling anyway.

[garrison]

@Liso

Or maybe we could at least change findfirst to something like findkey(value, dict, sentinel=nothing)?

The option to provide a sentinel was also suggested on github. I would tend to be in favor of a pull request that added an additional sentinel argument to indexin, findfirst, findlast, findprev, and findnext (which should, of course, default to nothing if not specified).

[nalimilan]

@garrison

The option to provide a sentinel was also suggested on github. I would tend to be in favor of a pull request that added an additional sentinel argument to indexin, findfirst, findlast, findprev, and findnext (which should, of course, default to nothing if not specified).

Choosing an arbitrary sentinel doesn’t really fix the problem, as any sentinel could be a valid key in a Dict{Any,Any}, unless you create an unexported type specifically for that in each package (which is quite radical). As @jeff.bezanson said above, it would make more sense to allow requesting that keys be wrapped in a Some object, making it possible to distinguish Some(nothing) from nothing. I had precisely this kind of API in mind when I added this type (which is not frequently used in Base yet, but probably should).

[foobar_lv2]

Cheap variant for in-band signaling is

struct wrap_nothing{N} end
wrap(x)=x
wrap(::Nothing) = wrap_nothing{1}()
wrap(::wrap_nothing{N}) where N = wrap_nothing{N+1}()

unwrap(x)=x
unwrap(::wrap_nothing{N}) where N = wrap_nothing{N-1}()
unwrap(::wrap_nothing{1})=nothing

Is this what you have in mind?

[nalimilan]

Not really. See the Some type in Julia 0.7.