best option to shuffle based on seed

[Victor Tan]

Hi, 

As the STL random number engines and generators are banned, and helpers in base/rand_util.h seems don't support seeded random generators.  What would be the best option to randomly shuffle a container (e.g. std::vector) based on the provided seed?  Basically, we would like to shuffle the list of elements to keep them identical throughout the lifetime of the Chromium major version (it's also the seed), and changes for the new Chromium release major version.  This function will be frequently called during requests, it's not just a one-time call. 

Thanks,

Victor

[Peter Kasting]

Good question. I wonder if there's something domain-specific somewhere in the codebase. Even if we allowed the STL engines and generators, I don't think we guarantee they will be consistent across platforms or between versions, which might risk some unintentional behavior. 

PK

--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAJh4P7EMOBRSHN8G_wN%2BibKDrBDB8ASkV%3Dqt_xVMbQnpMN9xZQ%40mail.gmail.com.

[Marijn Kruisselbrink]

Unfortunately there is at least one test in the code base already that rely on STL based seeded random number generators to be consistent across platforms and versions. But that's of course no reason to add more code using banned constructs... (I'm not sure how that usage got in in the first place).

To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAAHOzFDUjmsv%2BmPZ2gdaep-ZoORrhXnQP2VTbxFVf0Vyf2Ct-Q%40mail.gmail.com.

[Joe Mason]

You should probably do the shuffle at build time, writing the list to a generated file. That way you can add a compile-time test that the same list is generated in every build for the life of the version. (And that it's the same on every platform, if needed.)

> This function will be frequently called during requests, it's not just a one-time call. 

I assume you mean a function that should return the same list, in the same order, is called frequently?

To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAAHOzFDUjmsv%2BmPZ2gdaep-ZoORrhXnQP2VTbxFVf0Vyf2Ct-Q%40mail.gmail.com.

[Victor Tan]

> I assume you mean a function that should return the same list, in the same order, is called frequently?

Yes, we expected the function to return the same list element if the Chromium major version is the same. 

[Daniel Cheng]

Does it need to be a consistent ordering across all users of a Chrome major version? Or does it just need to have a stable ordering per user per major revision?

Daniel

To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAJh4P7GhPsQP0jDOE%3Dwqq%2Bz3pBgETDuJBjjpoF_Y%3DS6HA6GOJw%40mail.gmail.com.

[Victor Tan]

> Does it need to be a consistent ordering across all users of a Chrome major version? Or does it just need to have a stable ordering per user per major revision?

To keep compat and  minimize caching variance, I think we would like to keep a consistent ordering across all users of a chrome major version.

For the current implementation, we only support at most three elements in the list, we used a stable permutation table: all permutations of {0,1,2} , which are 3!=6, using major version % 6 to get the order. 

We would like to support 3+ elements in the list to achieve the same effect.  

With the STL library, It seems we can't guarantee to get the same sequence when shuffling a list with the same seed across all platforms.

[David Benjamin]

A user-stable, but otherwise randomized, ordering would probably also have privacy implications.

To view this discussion visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAJh4P7FdWkHySQi72aUfB-8Fyv7O4wmf3rPwPArhRc%3Dkma0F9w%40mail.gmail.com.