julep/rfc: proposal for unified Dict get/insert/has interface

[vtjnash]

problem statement:

a common idiom when working with Associative objects is to do a set of has / insert / lookup operations:

d = Dict()
if !(key in keys(d))
  d[key] = initial_value
end
value = d[key]

this syntax has the advantage of only using basic operations, for clarity, but it's also 3x slower than necessary since the dict lookup gets repeated three times. that concern has lead to the introduction of a get! method that accepts either an object or function, to insert a value if the lookup fails, so that the above code can be rewritten as:

d = Dict()
value = get!(d, key, initial_value)

or

d = Dict()
value = get!(d, key, () -> initial_value)

however, this implementation is still not necessarily faster, since it involves precomputing initial_value (fine it it's just a constant, but bad if it expensive to compute or creates unnecessary garbage) or invoking a lambda.

the code to support this one code pattern isn't exactly short, requires a fair amount of code duplication, and even a macro definition is provided (https://github.com/JuliaLang/julia/blob/master/base/dict.jl#L632-L690)

proposal

define the Ref operation on a Dict to return an intelligent indexer object. the above code pattern could then be written as:

d = Dict()
bp = Ref(d, key)
if isempty(bp)
  bp[] = initial_value
end
value = bp[]

implementation sketch

type RefDict{K, V, D <: Dict} <: Ref{V}
  d::D
  k::K
  last_htindex::Int
  last_state::Int
end
function RefDict{K,V}(d::Dict{K,V}, k)
  key = convert(K, k)
  isequal(key, k) || throw(ArgumentError("k is not a usable key"))
  return RefDict{K,V,typeof(d)}(d, k, 0, 0)
end
function isempty(r::RefDict)
  if (d.last_state != d.changecounter)
    r.last_htindex = ht_keyindex2(d, key)
    r.last_state = d.changecounter
  end
  return r.last_htindex > 0
end

ref #12035 (comment)

[yuyichao]

Is this the one you briefly mentioned on saturday night during the JuliaCon?

[carnaval]

Yep. And yes please (again) !

(btw s/in/haskey/ in your first example)

[yuyichao]

Also would this still has benefit over the get! version if we have fast anonymous function?

[vtjnash]

Is this the one you briefly mentioned on saturday night during the JuliaCon?

yes. i figured i should finally try to see what it would look like

[carnaval]

Also would this still has benefit over the get! version if we have fast anonymous function?

It is more general since you can use the hash table before the insertion. Like

if isempty(bp)
    println("Inserting into ", d)
    bp[] = x
end

We could also still have the lambda version for compactness I guess.

[carnaval]

(well in this example I guess you could capture d in the lambda, but my point is you can carry the ref around for some time before committing to the insertion)

[JeffBezanson]

Good idea!

I think my main concern would be allocating an extra object for each dictionary operation. It could get quite expensive. Also unfortunately the code for the common idiom is not shorter.

[yuyichao]

(well in this example I guess you could capture d in the lambda,

Was just going to say that.

but my point is you can carry the ref around for some time before committing to the insertion)

I see. (not sure if it is good to bring up but I guess it should be as useful as c++ reference.....)

[JeffBezanson]

Related: #2108

[kmsquire]

I'll point out that @StephenVavasis implemented a Token interface for SortedDicts in DataStructures.jl, which plays a similar roll. This one sounds better, however.

(He even started to use Ref in a similar way, before I discouraged him because it wasn't used yet in Base (sorry, Stephen).)

[kmsquire]

my point is you can carry the ref around for some time before committing to the insertion

We might need to be careful about asynchronous updates to the hash table causing it to be resized, especially if we ever get threading.

[yuyichao]

We might need to be careful about asynchronous updates to the hash table causing it to be resized, especially if we ever get threading.

I think in the example above ref[] = value basically fall back to ref.dict[ref.key] = value if it detects that the dictionary have changed so we should just be as careful as doing regular dict assignment?

There might be one additional race possibility but IMHO it shouldn't need more care than the dict itself.

[carnaval]

Yes, Jameson's proposal handles the single thread rehash case by graceful performance degradation. Multi threaded modification of the same data structure will likely be defined as a race condition => undefined behavior. We'll have to implement a family of concurrent data structures. (the java std lib has state of the art implementation of those things, probably good inspiration).

[StephenVavasis]

Since Kevin pinged me on this topic, I guess I can add my two cents about tokens and Ref.

(1) The primary purpose of tokens in my code is to provide a mechanism for stepping through a SortedDict (or SortedSet or SortedMultiSet) in the sort-order of the keys. Obviously, this is not an issue for Dict.

(2) A second purpose of a token is to provide a handle to an entry that can be dereferenced in O(1) time. Again, this is not so much an issue for Dict because the hash-lookup is already supposed to be O(1).

(3) Using a Ref object to point to a spot in the structure where an item would go if it would be inserted later seems like a reasonable idea; as mentioned earlier, there is a performance hit because the Ref object is heap-allocated. However, I am thinking of changing my balanced-tree implementation so that the most recent look-up is cached because often the next lookup is nearby. Couldn't Dict do the same with caching?

(4) Going off on a tangent, I have an issue with the equivalence between haskey(d,k) and in(k, keys(d)) ... see my recent posting here:

JuliaCollections/DataStructures.jl#103

(5) Finally, with regard to the problem of the awkward if-block versus the need to evaluate 'initial_value' in a get! function, wouldn't it be OK to use a macro and to ask anyone who writes an Associative type to support a macro version of get! that solves this problem?

[StefanKarpinski]

I don't really like the syntax much. I've proposed adding a syntax for get! like d[k] ?= v. However, that begs the question of what we should lower that to. If we lower it to the form that uses a closure, then we haven't solved the performance issue (although I'm not entirely convinced that this matters since it will be fast eventually, right?), so maybe it could lower to something like what you're proposing. There certainly are cases within the implementation of Dict where having a more usable "intelligent index" type would be helpful in implementing higher level operations.