On Wednesday 11 March 2009 17:26:29 Evan Daniel wrote: > On Wed, Mar 11, 2009 at 1:22 PM, Oskar Sandberg <[email protected]> wrote: > > On Wed, Mar 11, 2009 at 5:03 PM, Evan Daniel <[email protected]> wrote: > >> > >> There is a technique that would make the store fill more quickly than > >> it currently does without any drawbacks (aside from a small amount of > >> development time ;) ). Right now, there are two hash tables with one > >> slot per location. One hash table is the store, one the cache. > >> (Obviously I'm only considering a single one of CHK/SSK/pubkey.) This > >> is equivalent to a single hash table with two slots per location, with > >> rules that decide which slot to use rather than which hash table. > >> > >> Currently, the rule is that inserts go in the store and fetches in the > >> cache. The change is this: when storing a key in the cache, if the > >> cache slot is already occupied but the store slot is empty, put it in > >> the store instead (and vice versa). Even without the bloom filter, > >> this doesn't add any disk reads -- by treating it as one hash table > >> with two slots per location, you put those two slots adjacent on disk > >> and simply make one larger read to retrieve both keys. > >> > >> This is a technique I first saw in hash tables for chess programs. > >> Evaluation results are cached, with two distinct slots per location. > >> One slot stores the most recent evaluation result, the other stores > >> the most expensive to recompute. There is a noticeable performance > >> improvement in the cache if you are willing to store a result in the > >> wrong slot when only one of the two is full already. > > > > Isn't this just a more complicated way of saying: put anything which you > > cache into the store if the store isn't full yet? > > Basically. And an observation that there doesn't have to be a > performance penalty in doing so.
In which case we would need to have a per-slot tag indicating that a block isn't really a "store" block, and therefore should be preferentially clobbered? (The salted hash store uses quadratic probing, hence it checks four slots for any given key to see if any are free). > > Evan Daniel
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list [email protected] http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
