[ovs-dev] [PATCH] hmap_random_node: Improve distribution

[Ben Pfaff]

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?

> Signed-off-by: YAMAMOTO Takashi <yamamoto at 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 at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev