My application involves a graph with a node set, represented as map from
integral node ID to a node structure. Several threads need to look up
these node structures. This graph is constructed lazily, by which I mean
that the structures representing the nodes are only instantiated upon
first visiting of a given node. The per-node structures are like a "color
map" used to guide depth-first-traversal.
If I were building this map in Java, I could write an operation like
this using ConcurrentMap¹:
Node ensureNodeExists(Id id, ConcurrentMap<Id, Node> map)
{
final Node defaultNode = createDefault();
final Node prev = map.putIfAbsent(id, defaultNode);
return null == prev ? defaultNode : prev;
}
If there was no previous entry for the given ID, insert a default node
structure and return it. Otherwise, return the current node.
Given that nodes will never be deleted from the map, we could optimize
this function a little:
Node ensureNodeExists(Id id, ConcurrentMap<Id, Node> map)
{
final Node current = map.get(id);
if (null != current)
return current;
final Node defaultNode = createDefault();
final Node prev = map.putIfAbsent(id, defaultNode);
return null == prev ? defaultNode : prev;
}
That involves an extra lookup in the case that the entry isn't currently
in the map, but saves construction of the default node for cases where
the entry is already in the map.
Suppose we want to write an analogous operation in Clojure. I think the
solution involves `dosync' and either `alter' or `commute', but I'm
having trouble reasoning about the semantics of those operations in the
face of collisions among competing threads.
My first attempt:
(dosync
(or (*id-node-map* id)
(alter *id-node-map*
#(assoc % id (create-default)))))
Ignoring the defect that each branch of the `or' form returns a
different kind of value (in one case, the mapped value, in the other
case, the map itself), I wondered whether it's possible that in between
when I first lookup the value and find it missing and when `alter' runs
that another thread could have jammed a value in there. Feeling
paranoid, next I wrote this:
(dosync
(or (*id-node-map* id)
(alter *id-node-map*
#(update-in % [id]
(fn [cur] (if (nil? cur)
(create-default)
cur))))))
In that case, if the value is already in the map, it looks like we still
wind up "changing" the *id-node-map* ref even if the map didn't need to
change.
Several questions arise:
o What happens if two threads run this operation concurrently? Will one
fail and retry, backing off for finding the value now present in the
map?
o Is there some map updating operation better suited to my goal here?
The lookup ahead of time seems like it might not be necessary.
o Is there some way to capture the new value associated with the key
without looking it up again /outside/ and /after/ the `dosync' form?
The contract is that there's either no value associated with the key
or there is a value, and once there's a value it will not change to be
a different value. (These values are themselves agents.) But it's hard
to tell from within `dosync' whether a proposed update to the map will
be the one than wins.
o Assuming that `alter' is germane to the solution, how would `commute'
behave differently? I understand that `commute' doesn't block writers
and hence can retry. In my case, retrying after losing in the
collision should result in finding that the competing thread already
bound a value to the given key in the map.
It's been very difficult to find a thorough discussion of how `dosync',
`alter', and `commute' behave. In particular, if a transaction touches
several values with several `alter' or `commute' calls, and any one of
those values wind up conflicting with a competing transaction, does the
whole transaction fail and restart? Again, how do `alter' and `commute'
differ in such a case?
Footnotes:
¹ http://java.sun.com/javase/7/docs/api/java/util/concurrent/ConcurrentMap.html
--
Steven E. Harris
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
