Make `only` use `first` for dictionaries (or other types)?

Internals & Design
1

I’ve noticed that only is not as fast as it could be. I compare it to

function only2(x)
    length(x) == 1 || error("Collection must contain exactly one element")
    @inbounds first(x)   # EDIT: added @inbounds
end

In the following benchmarks (done with master) for various subtypes of AbstractDict, only2 is never slower than only:

x only(x) only2(x)
Dict('x' => 3) 11.930 ns 5.898 ns
IdDict('x' => 3) 16.893 ns 8.153 ns
v = [1,2]; x = WeakKeyDict(v => 3) 410.720 ns 240.881 ns
Base.PersistentDict('x' => 3) 1.409 μs 1.146 μs
pairs((x = 3,)) 12.674 ns 12.672 ns
Base.ImmutableDict('x' => 3) 3.451 ns 3.268 ns

Would you be interest in a PR that uses first for some or all abstract dictionaries? Or maybe also for other types?

Here are some more benchmarks:

x only(x) only2(x)
('x',) 2.673 ns 2.602 ns
['x'] 2.963 ns 2.966 ns
Set([x]) 9.225 ns 4.083 ns
"x" 3.261 ns 6.571 ns

The last example shows that only2 is not automatically faster for types T with Base.haslength(T) == true. If desired, one could make only(x::T) look at haslength(T) be default and add separate methods for types like String where this is not a good idea.

2 
function only3(x)
    r = iterate(x)
    isnothing(r) && error("Collection is empty")
    t,s = r
    isnothing(iterate(x,s)) ? t : error("Collection contains more than one element")
end

is also pretty fast. Doesn’t length(x) which can sometimes take more time.

3

I think that’s basically the current implementation of only.

4

Hmmm… you are right :laughing:. Didn’t bother to check. BTW on my machine the timings are different. I’m using 1.9.4.

5

I should have said that the benchmarks were on master (now added above). For 1.9.4 and 1.10.0-rc1 I get similar patters. Many benchmarks are somewhat faster than on master, but the ratio between only and only2 is roughly the same.

The only exception is ImmutableDict on 1.10.0-rc1 where only suddenly allocates:

julia> x = Base.ImmutableDict('x' => 3);
julia> @btime only($x);
  7.900 ns (1 allocation: 32 bytes)
julia> @btime only2($x);
  3.269 ns (0 allocations: 0 bytes)
6

There a are a few methods for only:


[1] only(x::Ref)                                  
@ iterators.jl:1527                       
[2] only(x::Number)                               
@ iterators.jl:1528
[3] only(x::Tuple{Any})                           
@ iterators.jl:1530                       
[4] only(x::Tuple)                                
@ iterators.jl:1531                       
[5] only(a::AbstractArray{<:Any, 0})              
@ iterators.jl:1534                       
[6] only(x::NamedTuple{<:Any, <:Tuple{Any}})      
@ iterators.jl:1535                       
[7] only(x::NamedTuple)                           
@ iterators.jl:1536                       
[8] only(x::Char)

@ iterators.jl:1529                       
[9] only(x)                                       
@ iterators.jl:1514
7

Yes, and only2 seems to be as good as these dedicated methods:

typeof(x) = Int64
  2.672 ns (0 allocations: 0 bytes)   # only
  2.679 ns (0 allocations: 0 bytes)   # only2
typeof(x) = Char
  2.603 ns (0 allocations: 0 bytes)
  2.879 ns (0 allocations: 0 bytes)
typeof(x) = Tuple{Char}
  2.532 ns (0 allocations: 0 bytes)
  2.522 ns (0 allocations: 0 bytes)
typeof(x) = Vector{Char}
  2.879 ns (0 allocations: 0 bytes)
  2.733 ns (0 allocations: 0 bytes)
typeof(x) = @NamedTuple{x::Int64}
  2.462 ns (0 allocations: 0 bytes)
  2.670 ns (0 allocations: 0 bytes)
typeof(x) = Base.RefValue{Int64}
  2.594 ns (0 allocations: 0 bytes)
  2.522 ns (0 allocations: 0 bytes)
8

seems worth a pr to me

1 Like
9

How can first be faster than iterate? Wouldn’t it usually just call iterate?

10

iterate has to prepare state for the next iteration, while first can just return first element (regardless of the rest of the container).

Perhaps the right way to go, is two versions of only dispatching on the IteratorSize trait. If a container has a HasLength then use length otherwise just use iterate.

11

But e.g. Set([1]) was shown as one of the biggest differences (9ns vs 4ns), but

julia> s = Set([1])
Set{Int64} with 1 element:
  1

julia> @edit first(s)

shows the implementation is just the generic first that calls iterate:

function first(itr)
    x = iterate(itr)
    x === nothing && throw(ArgumentError("collection must be non-empty"))
    x[1]
end

That is to say, I am skeptical of these benchmarks, because the numbers are so tiny (a few ns) that I think they can be overwhelmed by artifacts, and one needs to be very careful to accurately conclude one implementation is faster than another.

2 Likes
12

Wow, I would be extremely unhappy if a stray @inbounds happened to remove the explicitly requested check that there is only a single value.

This is surprising and either warrants a very loud warning in the docs, or it is a bug.

(propagating the inbounds such that we may read out-of-bounds for e.g. malformed views on iterate is fair game and expected, though)

1 Like
13

For data structures based on hash tables it makes sense to me that using first is faster: When iterating through a hash table, Julia doesn’t count the number of elements seen so far, but only scans for more elements until it reaches the end of the table. (Correct me if I’m wrong.) Hence for only (with error checking on) it needs to scan twice instead of only once.

14

I see, so maybe the key piece is that the length call is faster than the second iterate call?

15

Yes, because a hash table keeps track of the number of entries it has.

1 Like
16

PR submitted here.

1 Like