Patchwork [3,of,3] test-pathencode: randomize length of each path component

login
register
mail settings
Submitter Siddharth Agarwal
Date June 20, 2013, 5:47 p.m.
Message ID <33db99344b5c851de53d.1371750423@dev1091.prn1.facebook.com>
Download mbox | patch
Permalink /patch/1741/
State Accepted, archived
Delegated to: Matt Mackall
Headers show

Comments

Siddharth Agarwal - June 20, 2013, 5:47 p.m.
# HG changeset patch
# User Siddharth Agarwal <sid0@fb.com>
# Date 1371708340 25200
#      Wed Jun 19 23:05:40 2013 -0700
# Node ID 33db99344b5c851de53d4a020ed78e1c134417a3
# Parent  0388beba5bfc4d02de6d0adcefc8c59f23e19b24
test-pathencode: randomize length of each path component

This makes it possible for long and short components to exist in the same path.
This also makes shorter path components more likely. For
randint(1, randint(1, n)), the likelihood that one sees a number k
(1 <= k <= n) is 1/n * (\sum_{k=i}^n 1/i). This decreases with k, much like in
the real world where shorter paths are more common than longer ones.

The previous fix and this one together cause issue3958 to be detected by this
test with reasonable frequency. When this test was run 100 times in a loop, the
issue was detected 30 of those times.
Giovanni Gherdovich - June 21, 2013, 1:02 a.m.
2013/6/20 Siddharth Agarwal <sid0@fb.com>
>
> the likelihood that one sees a number k
> (1 <= k <= n) is 1/n * (\sum_{k=i}^n 1/i).

shouldn't this be "1/n * (\sum_{i=k}^n 1/i)" ?

I switched k and i inside the { }

I didn't check the math, just basing on what makes sense in plain english
(the sum must be a function of k) and i must be a "free variable".

Giovanni
ggherdov

Patch

diff --git a/tests/test-pathencode.py b/tests/test-pathencode.py
--- a/tests/test-pathencode.py
+++ b/tests/test-pathencode.py
@@ -125,7 +125,8 @@ 
     p = pickfrom(rng, firsttable)(rng)
     l = len(p)
     ps = [p]
-    while l < k:
+    maxl = rng.randint(1, k)
+    while l < maxl:
         p = pickfrom(rng, resttable)(rng)
         l += len(p)
         ps.append(p)