> Well, just do n steps at once in the first phase. In the binary search > phase, make it a n-ary search. Don't split the range you have (the range you > know the last taken slot must be in) in half, but split it in n equal parts. > Then have thread i request the slot at the i-th boundary. > > The first phase is sped up roughly by a factor of n; the second phase only > by ld (n+1) - well, that's better than nothing I'd say.
Cool :) Makes sense. Definitely worth the overhead of a few threads. Now, the real curly problem... Trying to keep some efficiency in there if some idiot spams the crap out of the index, or if several keys in the index fall out of freenet (thus giving request failures on key numbers that are not the max index inserted. For example, an index with 300 keys, and key 301 is the next available. If the guess tries for key 130, and the insert fails, it'll try to find a blank below 130. It'll go through all the motions, and croak because all calculated guesses below 130 succeed. But then in that case, it can simply go with key 130. (excuse me thinking out loud here, but it's late at night :)) Such an approach would make insertion fast, and put the burden onto the poor sucker harvesting and filtering the index. (more thoughts in next post...) ----- Original Message ----- From: "Stefan Reich" <[email protected]> To: <devl at freenetproject.org> Sent: Wednesday, June 06, 2001 01:18 Subject: Re: [freenet-devl] Exponential Key Index Insertion > ----- Original Message ----- > From: "David McNab" <david at rebirthing.co.nz> > > The devil certainly puts your mind to good service ;-) > > Hehe, how did you find out? > > > Perhaps instead of doubling, I could add a random number between 3n/2 and > > 5n/2, where n is the current guess. > > Sounds plausible. > > > In fact, the simulation reveals that the random factor makes the search > > slightly faster on average. > > (code below). > > So that's what your simulation's good for! I retract any previous > criticsm... > > > Now, Stefan or anyone, any thoughts on the n-threads version? > > Well, just do n steps at once in the first phase. In the binary search > phase, make it a n-ary search. Don't split the range you have (the range you > know the last taken slot must be in) in half, but split it in n equal parts. > Then have thread i request the slot at the i-th boundary. > > The first phase is sped up roughly by a factor of n; the second phase only > by ld (n+1) - well, that's better than nothing I'd say. > > -Stefan > > > > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://lists.freenetproject.org/mailman/listinfo/devl > _______________________________________________ Devl mailing list Devl at freenetproject.org http://lists.freenetproject.org/mailman/listinfo/devl
