Re: [PATCH] Assoc_array: Drop leaf-type concept

[George Spelvin]

Looks cleaner.

The larger issues that bother me:

1) The fact that the abstract daya type "index key" provides access to
   a byte string "index key" is a bit confusing.  I'd describe it as
   follows:  (Based on my current understanding.)


   Each object has an associated "index key" that is used for lookup.
   The index key is a string of bits which is stored "inside" the object,
   however all access to it is done through method functions, so it is
   not necessary to explicitly store it anywhere.

   For example, it is possible to have the leading portion of the
   index_key be a hash of the remainder.

   Index keys may be variable-length, but must be self-delimiting.
   Specifically, two different index keys must differ at some bit position
   before the end of the shorter of the two.

   Some index key methods take an isolated "const void *index_key"
   argument, while others take an object pointer.

2) The code does not look 32-bit safe.  In particular, keyring_get_key_chunk
   assumes the hash is BITS_PER_LONG long, but keyring_diff_objects 
   assumes it's 8*8 bits...

3) I presume you looked at wider tries like Judy arrays and found that
   a fan-out of 16 was better?

4) There are 3/7 unused bytes in an assoc_array_node, after parent_slot.
   Would it be worth storing 16/48 bits of index key and 3/4 bits of
   number of levels to skip per assoc_array_node?
   Since parent_slot is actually only 4 bits, you could store 4 bits
   of nubmer of levels and 56 bits (up to 14 levels, plus the one
   from the famout) of index key.

   With 32-way fanout, you could fit 5 bits of parent index, 25/55 bits of
   index key, and encode the number of levels to skip (0-5/11) more carefully.

5) The big question: Why not use a hash table?  That's what people
   usually expect when you say "associative array".  It would be simpler
   and faster.

   RCU-safe resizeable hash tables are tricky, but a solved problem,
   There are universal hashing techniques for preventing hash collision
   attacks.  
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/