I understand now. Thank you. This patch looks good, then.
Please add your explanation to the commit message.
On Apr 22, 2014 5:28 PM, "YAMAMOTO Takashi" <yamam...@valinux.co.jp> wrote:
> > 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
