Avoiding double lookup

General Usage Performance
1

Is it possible to cache the location so I don’t need to look it up twice (once in get and once in setindex!)?

"Increment the count by 1, starting from 0."
function bump!(d::Dict{K,Int}, k::K) where K
    v = get(d, k, 0)
    setindex!(d, v+1, k)
    d
end

let
    d = Dict{Int,Int}(10 => 1)
    bump!(d, 10)
end
2

There is get! :wink:

  get!(collection, key, default)

  Return the value stored for the given key, or if no mapping for the key is present, store key => default, and return default.

and

  get!(f::Function, collection, key)

  Return the value stored for the given key, or if no mapping for the key is present, store key => f(), and return f().

  This is intended to be called using do block syntax.
1 Like
4

You can use Base.ht_keyindex like get does internally:

function get(h::Dict{K,V}, key, default) where V where K
    index = ht_keyindex(h, key)
    @inbounds return (index < 0) ? default : h.vals[index]::V
end

In your case, if index < 0 you would set d[k] = 1

5

ht_keyindex is not documented and, therefore, not part of the public interface. It should be avoided if possible, as it can disappear between any Julia versions. Does get! (the version with a bang) not cover your case?

2 Likes
6

I think not. @jar1 is asking if you can increment the value of a key in a dictionary with a single lookup. get! can set a default value if the key isn’t found, but to increment the value (if it was found) requires a second lookup in the form of d[k] += 1

7

I.e.:

julia> function bump!(d, k)
           index = Base.ht_keyindex(d, k)
           if index < 0
               d[k] = 1
           else
               d.vals[index] += 1
           end
           d
       end
bump! (generic function with 1 method)

julia> function bump2!(d, k)
           d[k] = get(d, k, 0) + 1
           d
       end

julia> @btime bump!(d, 's') setup = (d = Dict('a':'f' .=> 1:6))
  11.624 ns (0 allocations: 0 bytes)
Dict{Char, Int64} with 7 entries:
  'f' => 6
  'a' => 1
  'c' => 3
  'd' => 4
  'e' => 5
  's' => 999
  'b' => 2

julia> @btime bump2!(d, 's') setup = (d = Dict('a':'f' .=> 1:6))
  22.042 ns (0 allocations: 0 bytes)
Dict{Char, Int64} with 7 entries:
  'f' => 6
  'a' => 1
  'c' => 3
  'd' => 4
  'e' => 5
  's' => 996
  'b' => 2
8

The interface in Dictionaries.jl provides a tokens API as an abstraction for the equivalent of ht_keyindex:

julia> d = Dictionary(["a","b"], [1,2])
2-element Dictionary{String, Int64}
 "a" │ 1
 "b" │ 2

julia> hadtoken, tok = gettoken!(d, "c")
       settokenvalue!(d, tok, hadtoken ? gettokenvalue(d, tok) + 1 : 0)
3-element Dictionary{String, Int64}
 "a" │ 1
 "b" │ 2
 "c" │ 0

julia> hadtoken, tok = gettoken!(d, "c")
       settokenvalue!(d, tok, hadtoken ? gettokenvalue(d, tok) + 1 : 0)
3-element Dictionary{String, Int64}
 "a" │ 1
 "b" │ 2
 "c" │ 1

However Dict predates Dictionaries.jl so the interfaces aren’t compatible.

2 Likes
9

Sincerely, this should be addressed by a PR to support a get! which takes a function argument that has the found value as a parameter (or default if there is nothing).

2 Likes
10

If the values in your dictionary are mutable, then you can just mutate the value that you get back from get!, like this:

julia> function foo!(d, k)
           v = get!(d, k, Int[])
           push!(v, 0)
       end
foo! (generic function with 1 method)

julia> d = Dict{Int, Vector{Int}}()
Dict{Int64, Vector{Int64}}()

julia> foo!(d, 1)
1-element Vector{Int64}:
 0

julia> foo!(d, 1)
2-element Vector{Int64}:
 0
 0

julia> foo!(d, 2)
1-element Vector{Int64}:
 0

julia> d
Dict{Int64, Vector{Int64}} with 2 entries:
  2 => [0]
  1 => [0, 0]
1 Like
11

I pushed for it, lets see if the core developers have some interest: https://github.com/JuliaLang/julia/issues/13055#issuecomment-1081317599

It is very easy to implement, so I may end up doing it if they like the idea.

1 Like
12

Note also the related: Add modify! function for lookup/update/insert/delete in one go by tkf · Pull Request #33758 · JuliaLang/julia · GitHub

13

Good to know but, sincerely, I really do not like the design that is going there and it overcomplicates for the specific case discussed here, where there is a default value (and messing with nothing and Some is not needed).

1 Like