package memprof-limits

  1. Overview
  2. Docs
Memory limits, allocation limits, and thread cancellation

Install 

dune-project
 Dependency

gitlab.com Readme Changelog Edit opam file Versions (4)

Authors

  1. G
    Guillaume Munch-Maccagnoni <Guillaume.Munch-Maccagnoni@inria.fr>

Maintainers

  1. G
    Guillaume Munch-Maccagnoni <Guillaume.Munch-Maccagnoni@inria.fr>

Sources

memprof-limits-v0.3.0.tar.gz
md5=39c73e7f96b5e5a01cf74937e2a5a1ae
sha512=a0049fec23c054eef19a924e5be810ecf9de4f697bd09b133e64c244b7ea09f416cec627ccce412ae793c265043894a878f0d822bcc47a2e622526f96d14af25

doc/statistical.html

Statistical analysis of Memprof-limits

  • p: sampling rate
  • S: expected trigger allocation

By default, p=10^{-4} samples per word.

We have S = \frac{1}{p} = 10\,\textrm{kw} (by default). That is, S is about 39.0 kiB of allocations on 32-bit and 78.1 kiB on 64-bit.

Global memory limits

P_{\mathrm{t}}(n): probability of triggering a callback after n allocated words.

One has:

P_{\mathrm{t}}(n) \geq 1-e^{-\frac{n}{S}}

Thus, once the memory limit is reached, on 64-bit:

  • there is more than 64% probability that the function has been interrupted after 80 kiB of allocations,
  • there is a probability less than 10^{-9} that the function has not been interrupted after 1.62 MiB of allocations
  • there is a probability less than 10^{-14} that the function has not been interrupted after 2.5 MiB of allocations
  • there is a probability less than 10^{-50} that the function has not been interrupted after 8.8 MiB of allocations

Allocation limits

  • l: limit chosen by the user
  • k: number of memprof callback runs needed to interrupt the function

We have k = \frac{l}{S}.

Probability of being interrupted

P_{\mathrm{a}}(n): probability of being interrupted after n allocations. It is given by the cumulative binomial distribution, that is, one has in terms of the regularized incomplete beta function I:

P_{\mathrm{a}}(n) = I_p(k,n-k+1)
[Graph entitled 'Cumulative probability of being interrupted relative to the chosen limit', reproduced as a table right below.]
Cumulative probability of being interrupted relative to the chosen limit (table)

n/l for p=10^{-4}

P_{\mathrm{a}} (for l=200\,\mathrm{kw}; k=20)

P_{\mathrm{a}} (for l=10\,000\,\mathrm{kw}; k=1000)

0.00

0

0

0.20

1.017 \cdot 10^{-8}

\varepsilon

0.40

2.527 \cdot 10^{-4}

8.900 \cdot 10^{-140}

0.60

2.127 \cdot 10^{-2}

2.329 \cdot 10^{-50}

0.80

1.877 \cdot 10^{-1}

5.531 \cdot 10^{-12}

1.00

5.297 \cdot 10^{-1}

5.047 \cdot 10^{-1}

1.20

1 - 1.802 \cdot 10^{-1}

1 - 1.276 \cdot 10^{-9}

1.40

1 - 4.780 \cdot 10^{-2}

1 - 7.872 \cdot 10^{-30}

1.60

1 - 9.339 \cdot 10^{-3}

1 - 7.065 \cdot 10^{-59}

1.80

1 - 1.421 \cdot 10^{-3}

1 - 1.029 \cdot 10^{-94}

2.00

1 - 1.762 \cdot 10^{-4}

1 - 6.426 \cdot 10^{-136}

\varepsilon: too small for the precision of calculations in 64-bit floating point.

Accuracy of limit

  • t: target safe probability
  • N: maximum number of safe allocations, that is, allocations that can be performed while the cumulative probability of being interrupted remains less than t.

A good lower bound for N is estimated for various values of k, and the error (l-N)/N is given below for t = 10^{-9}, t = 4\cdot10^{-15}, and t = 10^{-50}. (10^{-9} is the probability of winning the lottery, 10^{-50} is considered implausible by physicists' standards.)

[Graph entitled 'Inaccuracy of limit for a target safe allocation', reproduced as a table right below.]
Inaccuracy of limit for a target safe allocation (table, rounded up)

Values for p=10^{-4}.

N (in kw)

l/N-1 (for t<10^{-50})

l/N-1 (for t<4\cdot 10^{-15})

l/N-1 (for t<10^{-9})

1

3\cdot 10^{2}*

9\cdot 10^{1}*

6\cdot 10^{1}*

10

4\cdot 10^{1}*

2\cdot 10^{1}*

2\cdot 10^{1}*

10^{2}

8\cdot 10^{0}

4\cdot 10^{0}

3\cdot 10^{0}

10^{3}

2\cdot 10^{0}

9\cdot 10^{-1}

7\cdot 10^{-1}

10^{4}

5\cdot 10^{-1}

3\cdot 10^{-1}

2\cdot 10^{-1}

10^{5}

2\cdot 10^{-1}

8\cdot 10^{-2}

6\cdot 10^{-2}

10^{6}

5\cdot 10^{-2}

3\cdot 10^{-2}

2\cdot 10^{-2}

10^{7}

2\cdot 10^{-2}

8\cdot 10^{-3}

6\cdot 10^{-3}

*: l/N is higher than 10 (accuracy too low for practical purposes).

The same data gives us an indicative value for l for a given N.

[Graph entitled 'Allocation limit for a target safe allocation', reproduced as a table right below.]
Allocation limit for a target safe allocation (table)

Values for p=10^{-4}.

N (in kw)

l (for t<10^{-50})

l (for t<4\cdot 10^{-15})

l (for t<10^{-9})

1

3\cdot 10^{2}*

9\cdot 10^{1}*

6\cdot 10^{1}*

10

4\cdot 10^{2}*

2\cdot 10^{2}*

2\cdot 10^{2}*

10^{2}

9\cdot 10^{2}

5\cdot 10^{2}

4\cdot 10^{2}

10^{3}

3\cdot 10^{3}

1.9\cdot 10^{3}

1.7\cdot 10^{3}

10^{4}

1.5\cdot 10^{4}

1.3\cdot 10^{4}

1.2\cdot 10^{4}

10^{5}

1.2\cdot 10^{5}

1.08\cdot 10^{5}

1.06\cdot 10^{5}

10^{6}

1.05\cdot 10^{6}

1.03\cdot 10^{6}

1.02\cdot 10^{6}

10^{7}

1.02\cdot 10^{7}

1.008\cdot 10^{7}

1.006\cdot 10^{7}

*: l/N is higher than 10 (N too small for practical purposes).

The allocation limit is reasonably accurate (i.e. l is less than an order of magnitude greater than N) starting at around N = 20\,\textrm{kw}, that is, for a target safe probability of 4\cdot10^{-15}, around a limit of l = 200\,\textrm{kw}. Allocation limits l \leq 60\,\textrm{kw} on the other hand are probably too inaccurate to be useful.

Impact of the sampling value

This data is given for the default sampling rate. When memprof is used for profiling via the provided Memprof module, the user's sampling rate is used instead. But, memprof-limits will refuse to run with sampling rates less than the default one. As a consequence, the limits can only get more accurate, not less, such that the chosen N remains a safe allocation number.

From a theoretical point of view, one can wonder whether it is useful to increase the default rate. Below is the minimal sampling rate for a target safe allocation assuming l is chosen an order of magnitude greater than N.

[Graph entitled 'Minimal sampling rate for a target safe allocation (l/N = 10)', reproduced as a table right below.]
Minimal sampling rate for a target safe allocation (table)

k chosen such that l/N is around 10 for the specified value of t.

N (in kw)

p (for t<10^{-50})

p (for t<4\cdot 10^{-15})

p (for t<10^{-9})

1

7.8\cdot 10^{-3}*

2.1\cdot 10^{-3}*

1.4\cdot 10^{-3}*

10

7.8\cdot 10^{-4}*

2.1\cdot 10^{-4}*

1.4\cdot 10^{-4}*

10^{2}

7.8\cdot 10^{-5}

2.1\cdot 10^{-5}

1.4\cdot 10^{-5}

10^{3}

7.8\cdot 10^{-6}

2.1\cdot 10^{-6}

1.4\cdot 10^{-6}

10^{4}

7.8\cdot 10^{-7}

2.1\cdot 10^{-7}

1.4\cdot 10^{-7}

10^{5}

7.8\cdot 10^{-8}

2.1\cdot 10^{-8}

1.4\cdot 10^{-8}

10^{6}

7.8\cdot 10^{-9}

2.1\cdot 10^{-9}

1.4\cdot 10^{-9}

10^{7}

7.8\cdot 10^{-10}

2.1\cdot 10^{-10}

1.4\cdot 10^{-10}

*: The minimal sampling rate is higher than 10^{-4}, the value chosen by Memprof-limits.

The default sampling rate (10^{-4}) is one among many possible choices that provide reasonable accuracy without affecting performance. Nevertheless, feedback regarding the need of being able to select greater or lower sampling rates is welcome.