[interfacekit] Re: BHandler::fToken

Cheers - that does indeed explain it :)

John

On Tue, Mar 11, 2003 at 04:52:40PM -0800, Erik Jaesler wrote:
> 
> The issue isn't how hard it is to find a known token value; the issue is 
> the speed with which we can find the first available *unused* token 
> value.  As BHandler-derived instances are destroyed, they return their 
> token to BTokenSpace; that token can now be reused.  BTokenSpace keeps 
> an internal counter which simultaneously tracks how many tokens have 
> been handed out in the life of the app *and* provides the token values 
> themselves.
> 
> In the *extremely* unlikely event that an application actually manages 
> to request 32 bits worth of tokens in a given execution, the counter 
> will max out and BTokenSpace will have to start using returned tokens. 
> The obvious solution is to walk the token-to-handler map beginning with 
> 0 until you reach a value which is not contained in the map -- that 
> token is not being used currently.  In order to save the overhead of 
> walking the map, BTokenSpace has a queue (actually a stack currently) in 
> which returned tokens are placed so that once the internal counter is 
> maxed out, you don't have to walk the map to try and find a token that 
> isn't being used.
> 
> This discussion is almost entirely separate from the server token 
> discussion, aside from the fact that one of the proposals was that the 
> handler token be used as the server token for BViews.
> 
> Hope that clears the air a bit. ;)
> 
> e
> 
> John Hedditch wrote:
> > <lurk mode off>
> > 
> > I think I must be missing something. I don't see why you need a token
> > queue at all.
> > 
> >>From what I can recall from old CS lectures, the hash table is just a way 
> >>of 
> > providing a way of sorting unpredictable
> > input data into relatively even piles. If we have as many, or more, buckets
> > than inputs, then generally we get no collision, (providing we have a good
> > hash function), and we have either one or zero entities per bucket. 
> > 
> > If we have a 32 bit id as the hash key, and we insert more than 4 billion
> > entries, we will get collision, but so what. In the case of 40 billion
> > entries it takes 10 lookups to find an entity. That sounds pretty good to
> > me.
> > 
> > Cheers,
> > John
> > 
> > On Tue, Mar 11, 2003 at 04:15:52PM -0800, Erik Jaesler wrote:
> > 
> >>Axel Dörfler wrote:
> >>
> >>>Erik Jaesler <erik@xxxxxxxxxxxxxx> wrote:
> >>>OTOH looking up a token should be very fast, since we have to do that 
> >>>all the time, even more often than creating/deleting them.
> >>
> >>It's not looking up *one* token that concerns me; even with just a 
> >>regular map that's plenty fast.  The case that the token queue is 
> >>supposed to deal with is when you've maxed out the token counter.  Once 
> >>that's happened, without the queue, you have to start at zero and check, 
> >>iteratively, whether a given token is currently being used.  With the 
> >>token queue, we have a cache of tokens we *know* aren't being used, so 
> >>we don't have to hunt through the token space trying to find a free one. 
> >>  With the queue, the only time that would happen is when an app has 
> >>maxed the token counter *and* used up everything in the queue.  Maybe 
> >>this is an unnecessary concern; perhaps walking the map looking for a 
> >>free token will be fast enough even under the worst case.
> >>
> >>e
> >>
> >>
> > 
> > 
> 
> 
>

Other related posts: