Unless I’m mistaken, filterInPlace on a TrieMap relies on the default implementation from MapOps, which loops over the pairs and removes some using this code:
if (!p(k, v)) {
this -= k
}
That doesn’t seem right, as this could remove a value other than v, added concurrently, that does satisfy the predicate. Shouldn’t the pair be removed using this.remove(k,v)?
In case more convincing is needed, here’s a little program that shows the incorrect behavior:
val exec = Executors.newCachedThreadPool()
def slowPositive(x: Int): Boolean =
SECONDS.sleep(2)
x > 0
val map = TrieMap("K" -> 0)
exec.execute(() => map.filterInPlace((_, v) => slowPositive(v)))
exec.execute { () =>
SECONDS.sleep(1)
map += "K" -> 1
}
exec.shutdown()
exec.awaitTermination(10, SECONDS)
assert(map.get("K").contains(1)) // should be true
The map should contain a single pair "K" -> 1 after both tasks are finished; instead, it is empty.
Should I file a bug report or will someone from this group take care of it?
It’s always best to file a bug report (with minimal reproducing code, as you’ve posted here). Thanks for noticing this!
Why not just send a PR? Seems like it would only be a few lines.
The quickest solution would be to replace -= with remove(k,v) in MapOps, but this would have an unnecessary performance cost on all the non-concurrent maps. The next quickest is to copy the implementation of filterInPlace from MapOps into TrieMap and replace -= with remove(k,v) there. But this code copies the entire map into an array in order to avoid ConcurrentModificationException. This is overkill in a concurrent map that, presumably, can handle modifications during iterations. So, the best approach is probably to rewrite the method directly in terms of the TrieMap implementation. It looks like using iterator and remove(k,v) should work, but may not be the best approach. There’s nothing trickier than non-blocking concurrent code! Whoever wrote TrieMap would know best.
I’ve been wanting to participate in library code for a while—I’ve seen several things over the years that I think could be improved—but never found the time to get started. Is there is step-by-step guide on how to proceed?
In the meantime, I’ll file a bug report, and include my suggestion for implementation in it.