defect: sqrt memory leak

[gh-ph4r05]

I've noticed a memory-leak when computing sqrt in a loop. The total memory consumption depends on the number of iterations, thus I think there is a leak somewhere.

I attached the PoC I used to reproduce the bug. For simplicity and verification, I compute integer square root via int(sqrt()) vs isqrt(). isqrt does not seem to have a leak.

Such a leak is problematic as I need to run Sage with PBSPro. The job is created with a certain amount of memory I provide. The leak causes my jobs to consume all allocated memory by the job scheduler. As a result, my job is killed.

The experiment results. "Mem" field shows maximum memory consumption (PBSpro is watching the same value). isqrt method shows constant memory consumption, independent on the number of iterations, sqrt version depends on the number of iterations.

# int(sqrt())
$sage sqrt_memleak.sage -m 0 -c 1
Computed, time: 29.2342960835, mem: 258696, res: fba7460
$sage sqrt_memleak.sage -m 0 -c 2  # 2-times more iterations
Computed, time: 55.098608017,  mem: 334764, res: 2d7a5d2c
$sage sqrt_memleak.sage -m 0 -c 5  # 5-times more iterations
Computed, time: 139.213714838, mem: 561376, res: 149ea29f

# isqrt()
$sage sqrt_memleak.sage -m 1 -c 1
Computed, time: 1.52270507812, mem: 183112, res: fba7460
$sage sqrt_memleak.sage -m 1 -c 2  # 2-times more iterations
Computed, time: 2.30124402046, mem: 183084, res: 2d7a5d2c
$sage sqrt_memleak.sage -m 1 -c 5  # 5-times more iterations
Computed, time: 7.22719287872, mem: 183648, res: 149ea29f

PoC sqrt_memleak.sage:

import argparse
import resource
import time
from sage.misc.randstate import current_randstate

set_random_seed(0)
randrange = current_randstate().python_random().randrange

parser = argparse.ArgumentParser(description='SQRT memleak PoC')
parser.add_argument('--method', '-m', dest='method', default=0, type=int)
parser.add_argument('--cnt', '-c', dest='count', default=1, type=int)
args = parser.parse_args()

large_prime = 982451653
sqrt_fnc = sqrt if args.method == 0 else isqrt
tl, th = 1 << 127, (1 << 128) - 1

set_random_seed(0)
ts = time.time()
res = 0

for i in xrange(100000 * args.count):
    x = randrange(tl, th)
    r = int(sqrt_fnc((4 * x - 1) / 19))
    res = (res + r) % large_prime

print('Computed, time: %s, mem: %s, res: %x'
      % (time.time() - ts, resource.getrusage(resource.RUSAGE_SELF).ru_maxrss, res))

[nbruin]

The memory leak seems real: if one runs

import gc
import objgraph
from collections import Counter

large_prime = 982451653
sqrt_fnc = sqrt
tl, th = 1 << 127, (1 << 128) - 1

set_random_seed(0)
res = 0

gc.collect()
pre={id(a) for a in gc.get_objects()}

for i in xrange(10000 * 1):
    x = randrange(tl, th)
    r = int(sqrt_fnc((4 * x - 1) / 19))
    res = (res + r) % large_prime

gc.collect()
gc.collect()
gc.collect()

T=Counter(str(type(a)) for a in gc.get_objects() if id(a) not in pre)

then one sees an immense number of RealIntervalFieldElement objects. However, looking at their backrefs, there do not seem to be any! So it almost seems like there is an incref/decref disparity somewhere.

Concerning the particular example:

sage: sqrt(95/13)
sqrt(95/13)

so using the standard sqrt function will get you a symbolic expression. Trying to turn that into an integer probably leads to some complicated interval arithmetic do this in such a way that all the integer digits are correct. isqrt should be much more suitable for that.

[gh-ph4r05]

@nbruin thanks for verification! I am using isqrt now and it works fine. I just wanted to report this peculiar memory leak as it took a while to locate it.

[embray]

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)