Do not retain lock during `default()` call in `get(!)`

[Jutho]

The point of this PR is to release the lock while calling default() in get or get!. In particular, this allows for the default() function to itself depend on the lru cache. Previously, this would have resulted in a deadlock.

[Jutho]

Not sure if there is a nice way to implement this behaviour with the lock(...) do ... syntax.

[codecov-commenter]

Codecov Report

Merging #19 into master will increase coverage by 0.52%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master      #19      +/-   ##
==========================================
+ Coverage   72.28%   72.81%   +0.52%     
==========================================
  Files           2        2              
  Lines         184      217      +33     
==========================================
+ Hits          133      158      +25     
- Misses         51       59       +8     

Impacted Files	Coverage Δ
src/LRUCache.jl	95.72% <100.00%> (-0.02%)	:arrow_down:
src/cyclicorderedset.jl	46.00% <0.00%> (-1.78%)	:arrow_down:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 6cff52b...ef66298. Read the comment docs.

[Jutho]

The added test would hang (deadlock) on master. There is an issue though: in get!, as the lock is released while default() is called, another thread might add a result for this key. If that happens, the return value of default() is discarded and this other value is used instead. Another strategy might be to compare that both values match.

Care for a review @kmsquire , and maybe also cc @maartenvd ?

[maartenvd]

It's subtle, because on the one hand you have cases where you'd really only want the value to be calculated exactly once, but on the other hand - without this pr - it's very easy to get deadlocks, especially when using multiple memoized functions.

[Jutho]

Would there be a relevant use case for the old behaviour, where get! is being called from multiple threads, but nonetheless you want to ensure that default() is being called at most once, and the other threads, if they want to access the same value, just wait. I guess with the new threading infrastructure, it is possible though, that the other get! calls, waiting for the lock to be released, are paused, thus freeing the corresponding threads do useful work, e.g. that default() is itself multithreaded and uses those threads.

[Jutho]

I think I will merge this PR unless there are objections. If I am correct, the new behaviour is more robust and cannot lead to deadlocks. The only downside is the potential that default() is computed more often than necessary, but I think valuing safety and correctness over absolute (but potentially unsafe) efficiency is in line with Julia's general philosophy.