<div class="gmail_quote">Charles,</div><div class="gmail_quote"><br></div><div class="gmail_quote">See the thread you started &quot;MapMaker listener and removal notification.&quot; Ben is already doing the right thing:</div>
<div class="gmail_quote"><br></div><div class="gmail_quote">&quot;<span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 12.5px; border-collapse: collapse; ">Yep, that&#39;s exactly how my CL implements it, with an internal listener queue per segment, a Receiver passed to makeXXX(), and invokation on the clients thread outside of any locks on a mutate.&quot;</span></div>
<div class="gmail_quote"><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 12.5px; border-collapse: collapse; "><br></span></div><div class="gmail_quote">On Mon, May 10, 2010 at 10:01 PM, Charles Fry <span dir="ltr">&lt;<a href="mailto:fry@google.com">fry@google.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">a) Should eviction notifications be callbacks, or should we simply add<br>
evicted entries to a queue that users could then poll? Callback<br>
notifications definitely seem conceptually simpler from the users<br>
perspective, but they do require the execution of the callback code.<br>
Using a queue makes the job of performing eviction simpler, but then<br>
is more complicated for users to integrate with.<br></blockquote><div><br></div><div>Queue inside segment, call back in client threads, outside of locks. Best of both worlds.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

b) If eviction notifications are made using callbacks, where should<br>
the callback be executed? We could execute them on user threads when<br>
they make other calls on MapMaker maps, but that implies that<br>
exceptions and blocking within callbacks could then impact threads<br>
performing other operations on the map. The other obvious alternative<br>
would be to require users to provide an ExecutorService for executing<br>
callbacks, but that feels a bit overkill when all you really want is<br>
an eviction notification.<br></blockquote><div><br></div><div>A user-provided ExecutorService is not viable. The user could just implement execute() to execute the task in the task immediately in the current thread.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">c) Is it worth doing removal notifications, that include a callback<br>
when remove is called manually, or is it sufficient to limit<br>
notifications to eviction events?<br></blockquote><div><br></div><div>This was also discussed in the thread. The callback should only be invoked for automatic evictions. This enables the user to differentiate between manual and automatic removals. That&#39;s harder if you invoke the callback in both cases.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
d) While there are plenty of algorithms for concurrent<br>
recency/frequency based eviction policies, it is also simple to<br>
maintain a mutation queue that records a memento of each modification<br>
operation, occasionally locking and applying them on a single thread.<br>
The overhead of such a mechanism is trivial, and it allows the exact<br>
application of non-concurrent eviction algorithms. It has the minor<br>
caveat of requiring care to be taken with elements that are removed<br>
from the cache while one of their mutation mementos is still enqueued.<br>
Are there other concerns to be aware of, or is this a reasonable<br>
approach?<br></blockquote><div><br></div><div>I still plan to test the LRU algorithm Josh, Jesse and I came up with. It&#39;s incredibly light on memory, CPU and locking. We can experiment with other algorithms and consider them if they significantly increase retention in real world code without too much overhead.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
e) With respect to size eviction, our initial thought was to put a<br>
hard limit on the size of each segment. This has the advantage of<br>
being very simple conceptually, and the notable disadvantage of<br>
applying the eviction algorithm at the segment level instead of<br>
globally. If a mutation queue is used to manage evictions then it can<br>
very simply be extended to apply them globally instead of per-segment.<br>
Are there other major considerations to be aware of here? Does it<br>
sound reasonable to make global eviction decisions?<br></blockquote><div><br></div><div>We shouldn&#39;t introduce a map-wide lock or CAS. Heavy CAS contention across cores can actually be slower than grabbing a lock.</div>
<div> </div><div>Bob</div></div>