From e58f91a15a38ad2d26d77b77b2f1c84f6c6b06dc Mon Sep 17 00:00:00 2001 From: YAMAMOTO Takashi Date: Tue, 22 Apr 2014 13:34:36 +0900 Subject: [PATCH] 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 Signed-off-by: YAMAMOTO Takashi --- lib/hmap.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) 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; } -- 2.43.0