From: YAMAMOTO Takashi <yamamoto@valinux.co.jp>
Date: Tue, 22 Apr 2014 04:34:36 +0000 (+0900)
Subject: hmap_random_node: Improve distribution
X-Git-Tag: sliver-openvswitch-2.2.90-1~3^2~84
X-Git-Url: http://git.onelab.eu/?p=sliver-openvswitch.git;a=commitdiff_plain;h=e58f91a15a38ad2d26d77b77b2f1c84f6c6b06dc

hmap_random_node: Improve distribution

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.

Consider 2 items, 4 buckets, no collision.

    bucket 0   item 0
    bucket 1
    bucket 2
    bucket 3   item 1

The old algorithm picks item 0 if rand % 4 == 0.  (25%)
Otherwise it picks item 1.  (75%)

This change makes them 50%.

Acked-by: Ben Pfaff <blp@nicira.com>
Signed-off-by: YAMAMOTO Takashi <yamamoto@valinux.co.jp>
---

diff --git a/lib/hmap.c b/lib/hmap.c
index ec1de67da..542d8b5a8 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;
         }