[ovs-git] Open vSwitch: hmap_random_node: Improve distribution (master)

dev at openvswitch.org dev at openvswitch.org
Thu Apr 24 06:02:57 UTC 2014

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "Open vSwitch".

The branch, master has been updated
       via  e58f91a15a38ad2d26d77b77b2f1c84f6c6b06dc (commit)
      from  7d1700980b5dcf98003fdceb821d7967fad99786 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit e58f91a15a38ad2d26d77b77b2f1c84f6c6b06dc
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=e58f91a15a38ad2d26d77b77b2f1c84f6c6b06dc
Author: YAMAMOTO Takashi <yamamoto at valinux.co.jp>
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 at nicira.com>
Signed-off-by: YAMAMOTO Takashi <yamamoto at valinux.co.jp>


Summary of changes:
 lib/hmap.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

Open vSwitch

More information about the git mailing list