On 1/18/16 6:51 PM, Ilya wrote:
On Monday, 18 January 2016 at 23:49:36 UTC, Andrei Alexandrescu wrote:
On 1/18/16 6:44 PM, Ilya wrote:
On Monday, 18 January 2016 at 23:27:19 UTC, Ivan Kazmenko wrote:
On Monday, 18 January 2016 at 23:18:03 UTC, Ilya wrote:
A RNGs don't improve worst case. It only changes an permutation for
worst case. --Ilya
Still, use of RNG makes it impossible to construct the worst case
beforehand, once and for all. In that sense, this is a regression.
No, it is definitely possible, because RNGs are Pseudo-RNGs. --Ilya
unpredictableSeed uses the system clock as a source of randomness, so
we're good there. -- Andrei
Would this work for pure functions? --Ilya
Of course not. I think this back-and-forth takes away from the gist of
things. So let me summarize what has happened:
1. topN was reportedly slow. It was using a random pivot. I made it use
getPivot (deterministic) instead of a random pivot in
https://github.com/D-Programming-Language/phobos/pull/3921. getPivot is
also what sort uses.
2. Now that both functions use getPivot, I set out to improve it in
https://github.com/D-Programming-Language/phobos/pull/3922. The problem
is I couldn't make getPivot impure; pure functions already call sort, so
making it impure would have been a regression.
3. So I made getPivot use just a bit of randomness taken from the length
of the range.
4. sort was and is attackable before all of these changes
5. So now we have pure topN and sort (subject to the range offering pure
primitives) but they are both attackable.
6. PRNGs don't have any other downside than making functions impure.
The way I see it we have these solutions:
(a) make topN still use a random pivot. That way there's no regression.
Then proceed and make sort() avoid quadratic cases in other ways, e.g.
switch to heapsort if performance degrades.
(b) Improve sort() first, then apply a similar strategy to improving
topN. Do not use RNGs at all.
(c) Seek randomness in other places, e.g. address of elements, data
hashes etc. Come with a solution that may still be attacked in narrow
cases but make that unlikely enough to be a real concern.
Andrei
