Re: [PATCH 02/16] user_ns: use new hashtable implementation

Sasha Levin [off-list ref] writes:

On 08/15/2012 01:52 AM, Eric W. Biederman wrote:

quoted

Sasha Levin [off-list ref] writes:

quoted

Switch user_ns to use the new hashtable implementation. This reduces the amount of
generic unrelated code in user_ns.

Two concerns here.
1) When adding a new entry you recompute the hash where previously that
   was not done.  I believe that will slow down adding of new entries.

I figured that the price for the extra hashing isn't significant since hash_32
is just a multiplication and a shift.

I'll modify the code to calculate the key just once.

Honestly I don't know either way, but it seemed a shame to give up a
common and trivial optimization.

quoted

2) Using hash_32 for uids is an interesting choice.  hash_32 discards
   the low bits.  Last I checked for uids the low bits were the bits
   that were most likely to be different and had the most entropy.

   I'm not certain how multiplying by the GOLDEN_RATION_PRIME_32 will
   affect things but I would be surprised if it shifted all of the
   randomness from the low bits to the high bits.

"Is hash_* good enough for our purpose?" - I was actually surprised that no one
raised that question during the RFC and assumed it was because everybody agreed
that it's indeed good enough.

I can offer the following: I'll write a small module that will hash 1...10000
into a hashtable which uses 7 bits (just like user_ns) and post the distribution
we'll get.

That won't hurt.  I think 1-100 then 1000-1100 may actually be more
representative.  Not that I would mind seeing the larger range.
Especially since I am in the process of encouraging the use of more
uids.

If the results of the above will be satisfactory we can avoid the discussion
about which hash function we should really be using. If not, I guess now is a
good time for that :)

Yes.  A small emperical test sounds good.

Eric

--
To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On 08/15/2012 03:08 AM, Eric W. Biederman wrote:

quoted

I can offer the following: I'll write a small module that will hash 1...10000

quoted

into a hashtable which uses 7 bits (just like user_ns) and post the distribution
we'll get.

That won't hurt.  I think 1-100 then 1000-1100 may actually be more
representative.  Not that I would mind seeing the larger range.
Especially since I am in the process of encouraging the use of more
uids.

Alrighty, the results are in (numbers are objects in bucket):

For the 0...10000 range:

Average: 78.125
Std dev: 1.4197704151
Min: 75
Max: 80


For the 1...100 range:

Average: 0.78125
Std dev: 0.5164613088
Min: 0
Max: 2


For the 1000...1100 range:

Average: 0.7890625
Std dev: 0.4964812206
Min: 0
Max: 2


Looks like hash_32 is pretty good with small numbers.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>