Cool link Elias, I read the paper linked in the javadoc and it's very interesting. Netty seems to use scheme 6 (a single array of lists with hashing and without any overflow). I believe in general our timeouts will be much longer so I suspect scheme 5 or scheme 7 should perform better for us. Scheme 5 should be much better than 6 if most of the timeouts use the same value, and I believe we fit right in that use case. On the other hand I think we could save some memory if we implement scheme 7 by not actually storing the higher level wheels and building them on the fly by iterating the data container. The downside is that we'll need periodic sweeps of the data container, but those can be on a separate thread.

One scenario that we should keep in mind is the L1 cache, whose entries I would guess are invalidated much more often than they expire after their 1 hour lifetime. If the user stores only immortal entries + L1 entries in the cache we might end up with a ticker task that never rarely does anything useful so we should minimize its impact. It might also be worth it to implement our own list type to make adding and removing timeouts faster. I see Netty uses IdentityHashMap-backed sets for the bucket lists, but as Sanne found out they aren't the fastest thing around. Using a doubly-linked list and keeping a reference to the Node in the cache entry should make it much faster.

I've experimented with some implementations; since the simplest approach just removes and simplifies code while providing a significant speedup I'm going to send a pull request for that one: I just have to add some additional methods to InternalCacheEntry, and get a good improvement in the eviction "scanning". Since with 10 million entries it's able to scan/check them all in a timewindow close to a single second (~ 1,2 s on my laptop), I'm then proposing as well the second change to remove the "precision check" at all, which means we don't need any clock and I just need to remove some ~40 lines of useless and slow code. It seems we're all agreeing that higher precision is pointless, correct? Especially since the eviction thread can finish a full scan quicker. Cheers, Sanne On 2 November 2011 14:45, Manik Surtani <manik(a)jboss.org&gt; wrote: > > On 30 Oct 2011, at 23:58, Dan Berindei wrote: > >> Cool link Elias, I read the paper linked in the javadoc and it's very >> interesting. >> >> Netty seems to use scheme 6 (a single array of lists with hashing and >> without any overflow). I believe in general our timeouts will be much >> longer so I suspect scheme 5 or scheme 7 should perform better for us. >> >> Scheme 5 should be much better than 6 if most of the timeouts use the >> same value, and I believe we fit right in that use case. >> On the other hand I think we could save some memory if we implement >> scheme 7 by not actually storing the higher level wheels and building >> them on the fly by iterating the data container. The downside is that >> we'll need periodic sweeps of the data container, but those can be on >> a separate thread. > > -1. I'd prefer an approach that does not involve any additional management threads. > >> One scenario that we should keep in mind is the L1 cache, whose >> entries I would guess are invalidated much more often than they expire >> after their 1 hour lifetime. If the user stores only immortal entries >> + L1 entries in the cache we might end up with a ticker task that >> never rarely does anything useful so we should minimize its impact. >> >> It might also be worth it to implement our own list type to make >> adding and removing timeouts faster. I see Netty uses >> IdentityHashMap-backed sets for the bucket lists, but as Sanne found >> out they aren't the fastest thing around. Using a doubly-linked list >> and keeping a reference to the Node in the cache entry should make it >> much faster. > > Yes, I think implementing our own is the way forward as well. No sense in adding dependencies for just a single class, etc. > > Cheers > Manik > -- > Manik Surtani > manik(a)jboss.org > twitter.com/maniksurtani > > Lead, Infinispan > http://www.infinispan.org > > > > > _______________________________________________ > infinispan-dev mailing list > infinispan-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev > _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

Sanne have you integrated this? I would love to see what you have done!