Add RandomNumberGenerator adapter to base/rand_util.h

Add RandomNumberGenerator adapter to base/rand_util.h

BUG=46679
TEST=none

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=57904

[isherman_google.com, 2010-08-05 19:54:44]

Pretty sure I added more TODOs than code :P  I intend to address those in the
next revision -- they're mostly requests for feedback.

http://codereview.chromium.org/3053050/diff/1/6
File net/websockets/websocket_handshake.cc (right):

http://codereview.chromium.org/3053050/diff/1/6#newcode74
net/websockets/websocket_handshake.cc:74: std::random_shuffle(fields.begin(),
fields.end(), base::RandGenerator);
git blame suggests ukai -- pinging him to make sure this is o.k.

[Paweł Hajdan Jr., 2010-08-05 22:11:49]

How about adding a Shuffle function to the rand util with an interface similar
to the STL shuffle? That would seem a better public interface to me.

[brettw, 2010-08-06 00:02:44]

http://codereview.chromium.org/3053050/diff/1/3
File base/rand_util.h (right):

http://codereview.chromium.org/3053050/diff/1/3#newcode23
base/rand_util.h:23: ptrdiff_t RandGenerator(ptrdiff_t max);
It's confusing and potentially dangerous that this returns a signed ptrdiff_t
(possibly 64-bits) but is limited to a range of a int (32 bits since you
implement this via RandInt). Somebody could call this in a case outside of
random_shuffle and not get the randomness they wanted.

I might call this RandForRandomShuffle instead to guard against this confusion.
It doesn't seem worth doing actual 64-bit here since I presume it will just give
us the size of the vector, where 32 bits is fine and we will just waste time
generating more randomness. Instead, I would mention in the comment that the max
is limited to the range of an int, and DCHECK in the implementation that the max
is < numeric_limits<int>::max().

It would also be nice to give an explicit example of usage in the comment for
how to randomize a container, which would make it much more clear, rather than
the current sentence about an adapter.

[isherman_google.com, 2010-08-19 08:44:23]

http://codereview.chromium.org/3053050/diff/7001/8003
File base/rand_util_unittest.cc (right):

http://codereview.chromium.org/3053050/diff/7001/8003#newcode33
base/rand_util_unittest.cc:33: ::testing::FLAGS_gtest_death_test_style = "fast";
This makes the test print out warnings.  Also, even with "fast", it takes 55ms
to run.  Is there something better I could be doing?  Otherwise, maybe it's not
worth the trouble to have this test at all?

[brettw, 2010-08-19 15:59:06]

http://codereview.chromium.org/3053050/diff/7001/8003
File base/rand_util_unittest.cc (right):

http://codereview.chromium.org/3053050/diff/7001/8003#newcode33
base/rand_util_unittest.cc:33: ::testing::FLAGS_gtest_death_test_style = "fast";
If verifying it DCHECKs is causing problems, I'm OK just removing the test for
that particular feature.

[Paweł Hajdan Jr., 2010-08-19 16:50:31]

http://codereview.chromium.org/3053050/diff/7001/8002
File base/rand_util.h (right):

http://codereview.chromium.org/3053050/diff/7001/8002#newcode26
base/rand_util.h:26: ptrdiff_t RandGeneratorForRandomShuffle(ptrdiff_t max);
I'd prefer this to be hidden, possibly in rand_util_internal.h, or in some other
way. People should be using RandShuffle, and should never use
RandGeneratorForRandomShuffle directly.

[brettw, 2010-08-19 16:54:13]

On Thu, Aug 19, 2010 at 9:50 AM,  <phajdan.jr@chromium.org> wrote:
>
> http://codereview.chromium.org/3053050/diff/7001/8002
> File base/rand_util.h (right):
>
> http://codereview.chromium.org/3053050/diff/7001/8002#newcode26
> base/rand_util.h:26: ptrdiff_t RandGeneratorForRandomShuffle(ptrdiff_t
> max);
> I'd prefer this to be hidden, possibly in rand_util_internal.h, or in
> some other way. People should be using RandShuffle, and should never use
> RandGeneratorForRandomShuffle directly.

I'm not sure that's possible given that the STL random shuffle
algorithm this is used for is a template. The only thing I can think
of is that we write our own template in rand_util.h that just wraps
the STL one and specifies the function to use, and then we put that
function in some subtle namespace. But this requires that then
rand_util brings in <algorithm>. I'm not sure all of this is any
better than what the patch has now.

[isherman_google.com, 2010-08-19 22:54:26]

On 2010/08/19 16:54:13, brettw wrote:
> On Thu, Aug 19, 2010 at 9:50 AM,  <mailto:phajdan.jr@chromium.org> wrote:
> >
> > http://codereview.chromium.org/3053050/diff/7001/8002
> > File base/rand_util.h (right):
> >
> > http://codereview.chromium.org/3053050/diff/7001/8002#newcode26
> > base/rand_util.h:26: ptrdiff_t RandGeneratorForRandomShuffle(ptrdiff_t
> > max);
> > I'd prefer this to be hidden, possibly in rand_util_internal.h, or in
> > some other way. People should be using RandShuffle, and should never use
> > RandGeneratorForRandomShuffle directly.
> 
> I'm not sure that's possible given that the STL random shuffle
> algorithm this is used for is a template. The only thing I can think
> of is that we write our own template in rand_util.h that just wraps
> the STL one and specifies the function to use, and then we put that
> function in some subtle namespace. But this requires that then
> rand_util brings in <algorithm>. I'm not sure all of this is any
> better than what the patch has now.
> 

The previous version of the patch had both the adapter
RandGeneratorForRandomShuffle() and the wrapper template RandShuffle() exposed. 
This version hides the adapter in "rand_util_internal.h', per Paweł's
suggestion, as I agree with him that this seems to be a cleaner API to expose. 
You're right that this has the unfortunate consequence that rand_util brings in
<algorithm> -- how big of an issue is that?

I think if we want to leave just the adapter function in the API, then we should
make it properly 64-bit (given that the implementation of RandInt actually
coerces everything to be 64-bit anyway), and make it more generally usable than
with std::random_shuffle.  "RandGeneratorForRandomShuffle" just feels a little
too yucky for the rand_util interface :)

[brettw, 2010-08-20 23:51:19]

Sorry to drag this out. I really preferred patch set 2, except I would not
include the template for actually doing the shuffle. I'm fine with telling
people to use std::shuffle and to use this function. I think we should provide
and example in the comment above this function, but I would prefer to avoid
include <algorithm> here.

In patch set 3, you don't actually reduce header file dependencies (it includes
<algorithm> in just as many places, nor does it make it obvious at the callsite
that you shouldn't be using it, it just makes the function harder to find.

[isherman_google.com, 2010-08-24 05:10:31]

On 2010/08/20 23:51:19, brettw wrote:
> Sorry to drag this out.

No worries -- I'm pretty much just occasionally flitting back to this patch when
I have random downtime with my other stuff.

> In patch set 3, you don't actually reduce header file dependencies (it
includes
> <algorithm> in just as many places, nor does it make it obvious at the
callsite
> that you shouldn't be using it, it just makes the function harder to find.

These are fair objections :)

[isherman_google.com, 2010-08-26 21:56:38]

ping :)

[brettw, 2010-08-27 19:50:40]

LGTM

[isherman_google.com, 2010-08-27 21:58:04]

phajdan.jr: wdyt?

[Paweł Hajdan Jr., 2010-08-30 18:09:02]

http://codereview.chromium.org/3053050/diff/28001/29002
File base/rand_util.h (right):

http://codereview.chromium.org/3053050/diff/28001/29002#newcode24
base/rand_util.h:24: uint64 RandGenerator(uint64 max);
I think I'd prefer a RandomShuffle thing. The implementation seems to be small
enough to fit inline in case we need this for template reasons. However, if
Brett wouldn't like it, I'm fine with the current solution.

[isherman_google.com, 2010-08-30 21:05:16]

On 2010/08/30 18:09:02, Paweł Hajdan Jr. wrote:
> I think I'd prefer a RandomShuffle thing. The implementation seems to be small
> enough to fit inline in case we need this for template reasons. However, if
> Brett wouldn't like it, I'm fine with the current solution.

I think the main objection to RandomShuffle as an API here is that introduces
dependencies (e.g. pulling in <algorithm>) into various files that use rand_util
but don't need to shuffle anything.  Since it seems that everyone's more or less
ok with the current implementation, I'm going to go ahead and commit it -- if we
come up with a lightweight way to provide RandomShuffle in the API, we can
revisit the decision :)