[interfacekit] Re: BHandler::fToken

On Wed, 12 Mar 2003, Adi Oanca wrote:

> Before I begin!
>
> PEOPLE! We need to make a decision! There are many alternatives, but we need
> one!

Before Marc's last mail I would have said, just implement one solution.
Switching from numerical tokens to BView pointers would require only very
local changes and thus could be done easily. But according to Marc things
seem to work a bit differently, so one should make sure, that the concepts
are well understood before start hacking. In particular it wouldn't make
sense to think about a token->BView* mapping (be it view cast or hash
table), if it wouldn't be necessary to ever to that
(BWindow::find_token_and_handler() seems to suggest, that it is
necessary, though).

> > There is still the alternative to use a hash map on client side to map
> > server tokens (or reuse the handler tokens and use the already existing
> > BTokenSpace) to BViews.
>
> No, no, most of the messages came from app_server, so on the client side
> is more efficient to cast pointers!

I don't say, that a pointer cast isn't more efficient, but I suspect
in comparison with the real task to be done also the time for a hash table
lookup is negligible.

> > > You must be kidding. It's complexity is O(n).
> >
> > If you have a very bad hash function, i.e. one that maps all elements to
> > the same hash value, then you're right. Otherwise -- and when using
> > consecutive numbers as tokens this is hard to avoid :-) -- you have O(1)
> > complexity.
>
> I think I'm confusing them with hash maps!

As to my knowledge hash maps are simply hash table based map
implementations.

> > > > If you have a hash table for each window I think the hash
> > > > table is more of an overhead than a speed-up.
> > >
> > > Excuse me??? where is the extra overhead???
> >
> > When using small hash tables, it is more likely that you'll need to
> > rehash, which costs time. In fact a global hash table needs to be rehashed
> > sometimes too, and that may actually be quite an effort, but on the other
> > hand this could also be done asynchronously. :-P
> >
> > BTW, as a compromise one could use a hash table per application. Then the
> > object pointer is still a unique key and can also be used as hash value
> > directly. This does, of course, only work, if the tokens doesn't need to
> > be unique in the whole server.
>
> Yes, but only for BViews (not BWindows) and perhaps BBitmaps!

Yes, I thought, we were talking about BViews.

> And Ingo! Are you sure that hash tables are better than linked lists??

Regarding searching I have no doubt.

> What
> I mean, is, there aren't so many views in a window! A linked list would
> handle them just fine!

But, and that's the crucial point, if you have a window with a lot of
views, then performance drops significantly. O(n) lookup time means, that
a task to be done for every view (each time with a lookup) has O(n^2)
complexity, which might quickly become inacceptable.

> We're talking about 1K of additional memory if we
> have 256 views in a window, and that's a lot of views...

Mmh, I don't get, what memory has to do with that.

CU, Ingo

Other related posts: