key64_t? ino64_t?
Robert Collins
rbcollins@cygwin.com
Wed May 14 23:42:00 GMT 2003
On Thu, 2003-05-15 at 09:25, Charles Wilson wrote:
> (Naturally,
> there are different mechanisms for key lookup if the keys are stored in a
> tree structure, which don't involve '<', but that's another topic)
Hmm. Trees depend on '<'. Its the minimum needed to build a tree
structure. Tries don't depend on '<', but they do depend on a bit-string
as a key.
> > > But that kills packing (e.g. a key_t object is no longer '72 bits of id
> > > data') because key_t now has vtables, ctor, dtor, etc etc.
> >
> > No, none of the above apply.
>
> Correct. Unless I'm right about '<'
No - vtables, ctor and dtor don't apply *at all* unless we deliberately
use those features. And operator < doesn't require any of vtables, ctor
or dtor.
> > Aliasing isn't bad. However: we *must* prevent clashes. Probability has
> > nothing to do with it. I can't comment on the Linux implementation: I
> > haven't reviewed it.
>
> Why "must" we?
Because if we have a conflict, and we don't resolve it do deliver a
unique key to the client, then a client may ask for a shm segment X, and
get Y instead. Limits to the number of keys are less destructive than
having a shm area that *cannot* be accessed because of a collision.
> I agree that clashes are bad -- but "guaranteed unique
> keys"? Does SuS2 really require that? Because, if you give me a finite
> key bitlength, I can always create a scenario that breaks the
> "guarantee". I do not think it is possible to always eliminate the
> possibility of clashing -- ALL you can ever do is make it as unlikely an
> event as possible.
You can make it impossible for a collision to occur. My psuedo code does
exactly that.
> I don't like this. Without the full implementation, I'm just whistling
> in the dark here -- but there are a lot of gotchas in this code. All of
> them can be coded around, within the Tree/Trie implementation. But more
> code == more complexity.
What gotchas? Limits to number of keys - sure. What other ones?
> * very low: you make an extremely unlikely event even more unlikely --
> but still not impossible. I *can* construct a scenario in which this
> tree-based thing fails.
Please, do so. AFAIK such a scenario doesn't exist within the bounds of
valid (according to SuSv2) parameters to ftok().
> Is the value worth the cost (complexity)?
>
> I don't think so, but that's just my opinion.
Well, I've also put forward my opinion. Until I get time to dig up
SUSv2's reference...
> > Should give a reasonably performing implementation with space for
> > 16.7Million ftok() calls on unique paths. It will use space linear to
> > the path length of each unique path presented to ftok().
> >
> > This is what I meant by a lookaside table.
>
> See, to me this is a tree-based name hash. You say 'lookaside' and I
> think L2 cache... <g>
Firstly, neither a trie or a tree is a hash. hash's have collisions and
approaches to resolving that. Storing a hash in a user-visible value
means that the user has to resolve collisions: but they can't, a key is
opaque to the user.
Secondly, this is one implementation of a lookaside table. It's not the
only possible one - you can do a lookaside table using a hash if you
want to. The point is that the key handed out is *not* dependent on the
node in in the table, but on data within that node.
Finally, it's different from a cache: We're not optimising performance
for data available elsewhere, we're creating and storing unique
associations.
Rob
--
GPG key available at: <http://users.bigpond.net.au/robertc/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
URL: <http://cygwin.com/pipermail/cygwin-developers/attachments/20030514/979f8793/attachment.sig>
More information about the Cygwin-developers
mailing list