Hi Adam,
I plan to have a thorough look at your recent changes during my back
flight from Black Hat; at this point I have just a couple of comments,
see below.
On 07/24/2012 04:58 PM, Adam Hraska wrote:
> 1) I had a look at the current single threaded uspace
> hash table and I extended it so it can now resize
> automatically [1]. It resizes in a way that protects
> against bad hashes.
Nice.
> 2) I got rid of another hash table implementation in
> uspace/*/adt/hash_set and switched its only user
> nic_addr_db to hash_table.
Is networking still working with one of the nic drivers??
> Details:
> (1) required a slight change of the interface, so
> many files were affected by the commit.
The original hash table supported a trick: the compare function could
have been passed fewer keys for a partial match, which has been used in
hash_table_remove() to remove more partially matching keys at once. I
noticed you tried to preserve this behaviour, but just wanted to point
out it was there and that it might have been used.
> (1) I did not know how to thoroughly test the change,
> so I copied ~15000 files back and forth from fatfs
> to tmpfs. I also ran the user tester tests a couple
> of times.
In your tests, you could also include networking involving NIC drivers,
try to mount & unmount some FAT and TMPFS file systems that have some
files on them.
> (1) The single-threaded hash table now uses table sizes
> that are (mostly) prime to protect against suboptimal
> hashes. Its minimum size is 89 buckets. If someone
> wanted to create many small hash tables and the minimum
> table size would waste too much memory, I can switch
> the table from computing its new size to looking it up
> in a static table of primes. That would allow the table
> to have a size less than 89.
I noticed that for each converted hash() function, there would be some
boilerplate code matching the following pattern:
/* Inspired by Effective Java, 2nd edition. */
size_t hash = 17;
hash = 31 * hash + key[0];
...
hash = 31 * hash + key[n];
Could we do better and turn this into some kind of a macro or even a
function (for each reasonably small n) so that we don't have this
comment and code in a dozen of locations?
Jakub
_______________________________________________
HelenOS-devel mailing list
[email protected]
http://lists.modry.cz/cgi-bin/listinfo/helenos-devel
