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))

Component: basic arithmetic

Keywords: sqrt

Issue created by migration from https://trac.sagemath.org/ticket/27185