> On Tue, Apr 22, 2014 at 01:47:32PM +0900, YAMAMOTO Takashi wrote:
>> Improve random distribution for an hmap with a small number of nodes
>> with the expense of the increased cpu cost.
>> It would be a fair trade-off because the situation is rather common
>> for bond, which is currently the only consumer of this API in tree.
>
> I do not understand why this improves the distribution. Can you
> explain?
consider 2 items, 4 buckets, no collision.
bucket 0 item 0
bucket 1
bucket 2
bucket 3 item 1
the current algorithm picks item 0 if rand % 4 == 0. (25%)
otherwise it picks item 1. (75%)
my change makes them 50%.
YAMAMOTO Takashi
>
>> Signed-off-by: YAMAMOTO Takashi <yamam...@valinux.co.jp>
>> ---
>> lib/hmap.c | 4 ++--
>> 1 file changed, 2 insertions(+), 2 deletions(-)
>>
>> diff --git a/lib/hmap.c b/lib/hmap.c
>> index ec1de67..542d8b5 100644
>> --- a/lib/hmap.c
>> +++ b/lib/hmap.c
>> @@ -214,8 +214,8 @@ hmap_random_node(const struct hmap *hmap)
>> size_t n, i;
>>
>> /* Choose a random non-empty bucket. */
>> - for (i = random_uint32(); ; i++) {
>> - bucket = hmap->buckets[i & hmap->mask];
>> + for (;;) {
>> + bucket = hmap->buckets[random_uint32() & hmap->mask];
>> if (bucket) {
>> break;
>> }
>> --
>> 1.8.3.1
>>
>> _______________________________________________
>> dev mailing list
>> dev@openvswitch.org
>> http://openvswitch.org/mailman/listinfo/dev
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
