473,288 Members | 1,750 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,288 software developers and data experts.

GMPY: divm() memory leak revisited


Since the following discussion took place (unresolved),

<http://groups.google.com/group/comp.lang.python/browse_frm/thread/c3bd08ef3e4c478a/2b54deb522c9b9d9?lnk=st&q=divm()+memory+leak+group :comp.lang.python+author:mensanator&rnum=1&hl=en#2 b54deb522c9b9d9>

I've kept it in the back of my mind as I've been
learning to use the base gmp library in c. Now I believe
I know what the problem is.

First, divm() is not a gmp function. It is a derived
function created in gmpy. It is derived from the
gmp invert() function (which I know from my testing
does not leak memory). So it's a gmpy specific bug.

Second, I learned from the gmp c library that temporary
mpz objects must be freed to prevent memory leak. Aha!
The gmpy source code is probably not freeing some temporary
mpz it created.

Third, we have the smoking gun:

divm(a,b,m): returns x such that b*x==a modulo m,
or else raises a ZeroDivisionError
exception if no such value x exists
(a, b and m must be mpz objects,
or else get coerced to mpz)

Of course, to "coerce" means to create temporary variables
to pass to the gmp library. It would appear that these
temporary variables are not being freed. Now if I'm right,
then I can prove this by eliminating the need to coerce
the operands by passing mpz's to the divm() function.

#
# if the parameters are already mpz's...
#
z = gmpy.mpz(81287570543)
x = gmpy.mpz(8589934592)
y = gmpy.mpz(3486784401)
tot = 0
while True:
n = input('How many more divm: ')
if n<=0: break
print '%d more...' % n,
#
# ...then they won't need to be coerced
#
for i in xrange(n): gmpy.divm(z,x,y)
tot += n
print '...total %d' % tot
With coercing, I get

C:\Python23\user\the_full_monty>python gmpytest.py
How many more divm: 10000000
10000000 more...Fatal Python error: mp_allocate failure
abnormal program termination
peak Commit Charge (K): 792556

Without needing to coerce, the test ran to completion with
flat memory usage.

Unfortunately, c is still somewhat greek to me, but even so,
the problem appears obvious.

static PyObject *
Pygmpy_divm(PyObject *self, PyObject *args)
{
PympzObject *num, *den, *mod, *res;
if(!PyArg_ParseTuple(args, "O&O&O&",
Pympz_convert_arg, &num,
Pympz_convert_arg, &den,
Pympz_convert_arg, &mod))
{
return last_try("divm", 3, 3, args);
}
if(!(res = Pympz_new()))
return NULL;
if(mpz_invert(res->z, den->z, mod->z)) { /* inverse exists */
mpz_mul(res->z, res->z, num->z);
mpz_mod(res->z, res->z, mod->z);
if(options.ZM_cb && mpz_sgn(res->z)==0) {
PyObject* result;
if(options.debug)
fprintf(stderr, "calling %p from %s for %p %p %p %p\n",
options.ZM_cb, "divm", res, num, den, mod);
result = PyObject_CallFunction(options.ZM_cb, "sOOOO",
"divm",
res, num, den, mod);
if(result != Py_None) {
Py_DECREF((PyObject*)res);
return result;
}
}
return (PyObject*)res;
} else {
PyObject* result = 0;
if(options.ZD_cb) {
result = PyObject_CallFunction(options.ZD_cb,
"sOOO", "divm", num, den, mod);
} else {
PyErr_SetString(PyExc_ZeroDivisionError, "not invertible");
}
Py_DECREF((PyObject*)res);
return result;
}
}

Note that 4 PympzObjects get created but only res gets passed to
Py_DECREF (which seems to be the method by which it's freed, not
100% sure about this). But I notice that other functions that
coerce variables call Py_DECREF on each of the coerced variables:

static PyObject *
Pygmpy_gcd(PyObject *self, PyObject *args)
{
PympzObject *a, *b, *c;
TWO_ARG_CONVERTED("gcd", Pympz_convert_arg,&a,&b);
assert(Pympz_Check((PyObject*)a));
assert(Pympz_Check((PyObject*)b));
if(!(c = Pympz_new())) {
Py_DECREF((PyObject*)a); Py_DECREF((PyObject*)b);
return NULL;
}
mpz_gcd(c->z, a->z, b->z);
Py_DECREF((PyObject*)a); Py_DECREF((PyObject*)b);
return (PyObject*)c;
}

Here the PympzObject c is not freed because it is returned
as the result of the function, but the coerced variables a and b
are.

So the fix may be to simply add

Py_DECREF((PyObject*)num);
Py_DECREF((PyObject*)den);
Py_DECREF((PyObject*)mod);

to divm(). (Assuming it's that simple, I could have overlooked
something.)

Unfortunately, I don't have any means of testing this theory.

I did see the reference to

<http://www.vrplumber.com/programming/mstoolkit>

which I will be trying eventually, but in case I can't get that
to work I wanted to have this posted in case someone else wants
to take a crack at it.

Nov 5 '05 #1
3 2404
me********@aol.com wrote:
Since the following discussion took place (unresolved),

<http://groups.google.com/group/comp.lang.python/browse_frm/thread/c3bd08ef3e4c478a/2b54deb522c9b9d9?lnk=st&q=divm()+memory+leak+group :comp.lang.python+author:mensanator&rnum=1&hl=en#2 b54deb522c9b9d9>

I've kept it in the back of my mind as I've been
learning to use the base gmp library in c. Now I believe
I know what the problem is.

First, divm() is not a gmp function. It is a derived
function created in gmpy. It is derived from the
gmp invert() function (which I know from my testing
does not leak memory). So it's a gmpy specific bug.

Second, I learned from the gmp c library that temporary
mpz objects must be freed to prevent memory leak. Aha!
The gmpy source code is probably not freeing some temporary
mpz it created.

Third, we have the smoking gun:

divm(a,b,m): returns x such that b*x==a modulo m,
or else raises a ZeroDivisionError
exception if no such value x exists
(a, b and m must be mpz objects,
or else get coerced to mpz)

Of course, to "coerce" means to create temporary variables
to pass to the gmp library. It would appear that these
temporary variables are not being freed. Now if I'm right,
then I can prove this by eliminating the need to coerce
the operands by passing mpz's to the divm() function.

#
# if the parameters are already mpz's...
#
z = gmpy.mpz(81287570543)
x = gmpy.mpz(8589934592)
y = gmpy.mpz(3486784401)
tot = 0
while True:
n = input('How many more divm: ')
if n<=0: break
print '%d more...' % n,
#
# ...then they won't need to be coerced
#
for i in xrange(n): gmpy.divm(z,x,y)
tot += n
print '...total %d' % tot
With coercing, I get

C:\Python23\user\the_full_monty>python gmpytest.py
How many more divm: 10000000
10000000 more...Fatal Python error: mp_allocate failure
abnormal program termination
peak Commit Charge (K): 792556

Without needing to coerce, the test ran to completion with
flat memory usage.

Unfortunately, c is still somewhat greek to me, but even so,
the problem appears obvious.

static PyObject *
Pygmpy_divm(PyObject *self, PyObject *args)
{
PympzObject *num, *den, *mod, *res;
if(!PyArg_ParseTuple(args, "O&O&O&",
Pympz_convert_arg, &num,
Pympz_convert_arg, &den,
Pympz_convert_arg, &mod))
{
return last_try("divm", 3, 3, args);
}
if(!(res = Pympz_new()))
return NULL;
if(mpz_invert(res->z, den->z, mod->z)) { /* inverse exists */
mpz_mul(res->z, res->z, num->z);
mpz_mod(res->z, res->z, mod->z);
if(options.ZM_cb && mpz_sgn(res->z)==0) {
PyObject* result;
if(options.debug)
fprintf(stderr, "calling %p from %s for %p %p %p %p\n",
options.ZM_cb, "divm", res, num, den, mod);
result = PyObject_CallFunction(options.ZM_cb, "sOOOO",
"divm",
res, num, den, mod);
if(result != Py_None) {
Py_DECREF((PyObject*)res);
return result;
}
}
return (PyObject*)res;
} else {
PyObject* result = 0;
if(options.ZD_cb) {
result = PyObject_CallFunction(options.ZD_cb,
"sOOO", "divm", num, den, mod);
} else {
PyErr_SetString(PyExc_ZeroDivisionError, "not invertible");
}
Py_DECREF((PyObject*)res);
return result;
}
}

Note that 4 PympzObjects get created but only res gets passed to
Py_DECREF (which seems to be the method by which it's freed, not
100% sure about this). But I notice that other functions that
coerce variables call Py_DECREF on each of the coerced variables:

static PyObject *
Pygmpy_gcd(PyObject *self, PyObject *args)
{
PympzObject *a, *b, *c;
TWO_ARG_CONVERTED("gcd", Pympz_convert_arg,&a,&b);
assert(Pympz_Check((PyObject*)a));
assert(Pympz_Check((PyObject*)b));
if(!(c = Pympz_new())) {
Py_DECREF((PyObject*)a); Py_DECREF((PyObject*)b);
return NULL;
}
mpz_gcd(c->z, a->z, b->z);
Py_DECREF((PyObject*)a); Py_DECREF((PyObject*)b);
return (PyObject*)c;
}

Here the PympzObject c is not freed because it is returned
as the result of the function, but the coerced variables a and b
are.

So the fix may be to simply add

Py_DECREF((PyObject*)num);
Py_DECREF((PyObject*)den);
Py_DECREF((PyObject*)mod);

to divm(). (Assuming it's that simple, I could have overlooked
something.)

Unfortunately, I don't have any means of testing this theory.

I did see the reference to

<http://www.vrplumber.com/programming/mstoolkit>

which I will be trying eventually, but in case I can't get that
to work I wanted to have this posted in case someone else wants
to take a crack at it.

I completely forgot to mention the fourth thing I discovered.

The linear congruence algorithm used in divm() is wrong. To wit:
divm(6,12,14)
Traceback (most recent call last):
File "<pyshell#4>", line 1, in -toplevel-
divm(6,12,14)
ZeroDivisionError: not invertible

Sure, (12,14) is not invertible, but that is not a requirement for
solving a linear congruence. All that's required is that gcd(12,14)
divides 6, which it obviously does. The divm() function cannot
handle the case when b and m are not coprime. A properly
written linear congruence algorithm will work around the fact
that (12,14) is not invertible. To wit:
linear_congruence(12,14,6)

mpz(4)

The correct algorithm can't solve a problem that's not solvable,
but it shouldn't let non-invertability cause an exception. Here's
the correct algorithm which divm() ought to incorprorate.

from gmpy import *
def linear_congruence(x,y,z):
#
# xa == z (mod y)
#
g = gcd(x,y)
d = divmod(z,g)
if d[1]==0:
#
# gcd(x,y) divides z, solution exists
#
if g==1:
#
# x,y coprime, modular inverse exists
#
a = invert(x,y)*z % y
else:
#
# x,y not coprime, no modular inverse
# ...but wait, if we get here g divides z and also
# by definition, x & y, so divide x,y,z by g to create
# a new congruence with x,y now coprime and invert() valid
#
x = x/g
y = y/g
z = z/g
a = invert(x,y)*z % y
else:
#
# g doesn't divide z, no solution
#
a = -1
return a

Nov 5 '05 #2
me********@aol.com <me********@aol.com> wrote:
...
Unfortunately, I don't have any means of testing this theory.


Yep -- I reproduced the memory leak you mentioned, and easily fixed it
(exactly as you suggest) in the current CVS version of gmpy (meant to be
"1.01 release candidate"). I need to fix some other pending bugs, then
remind myself of how the (expl.del) one makes a release on Sourceforge,
then it shd be fine (except for Windows -- I have no Windows development
system around to do anything... Mac and Linux only).

One of the bugs I must still get around to examining is the algorithmic
one you mention in your next post, btw.

Thanks for your diagnostic and debugging help. BTW, should you wish to
mail me privately, I'm "aleaxit" (my favourite userid, with or w/o the
trailing "it" depending on service -- see www.aleax.com to understand
why that is the case), and the best way to reach me these days is
through "gmail.com" .
Alex
Nov 6 '05 #3

Alex Martelli wrote:
me********@aol.com <me********@aol.com> wrote:
...
Unfortunately, I don't have any means of testing this theory.
Yep -- I reproduced the memory leak you mentioned, and easily fixed it
(exactly as you suggest) in the current CVS version of gmpy (meant to be
"1.01 release candidate"). I need to fix some other pending bugs, then
remind myself of how the (expl.del) one makes a release on Sourceforge,
then it shd be fine


That's great!
(except for Windows -- I have no Windows development
system around to do anything... Mac and Linux only).
Well, I hope someone makes a Windows binary once you publish ver 1.01.
I downloaded all that MSVC command line stuff (over 800 MB!) but am not
looking forward to trying to get it to work.

One of the bugs I must still get around to examining is the algorithmic
one you mention in your next post, btw.

Thanks for your diagnostic and debugging help. BTW, should you wish to
mail me privately, I'm "aleaxit" (my favourite userid, with or w/o the
trailing "it" depending on service -- see www.aleax.com to understand
why that is the case), and the best way to reach me these days is
through "gmail.com" .
Alex


Nov 6 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

22
by: Alex Martelli | last post by:
I have fixed almost all of the outstanding bugreports and feature request for gmpy: divm doesn't leak memory any more, truediv and floordiv are implemented for all types, etc -- in the current CVS...
8
by: ranjeet.gupta | last post by:
Dear All Is the Root Cause of the Memory corruption is the Memory leak, ?? suppose If in the code there is Memory leak, Do this may lead to the Memory Corruption while executing the program ? ...
17
by: José Joye | last post by:
Hi, I have implemented a Service that is responsible for getting messages from a MS MQ located on a remote machine. I'm getting memory leak from time to time (???). In some situation, it is...
20
by: jeevankodali | last post by:
Hi I have an .Net application which processes thousands of Xml nodes each day and for each node I am using around 30-40 Regex matches to see if they satisfy some conditions are not. These Regex...
23
by: James | last post by:
The following code will create memory leaks!!! using System; using System.Diagnostics; using System.Data; using System.Data.SqlClient; namespace MemoryLeak
18
by: diffuser78 | last post by:
I have a python code which is running on a huge data set. After starting the program the computer becomes unstable and gets very diffucult to even open konsole to kill that process. What I am...
3
by: mensanator | last post by:
## Holy Mother of Pearl! ## ## >>> for i in range(10): ## for j in range(10): ## print '%4d' % (gmpy.mpz(i)*gmpy.mpz(j)), ## print ## ## ## ...
3
by: Jim Land | last post by:
Jack Slocum claims here http://www.jackslocum.com/yui/2006/10/02/3-easy-steps-to-avoid-javascript- memory-leaks/ that "almost every site you visit that uses JavaScript is leaking memory". ...
22
by: Peter | last post by:
I am using VS2008. I have a Windows Service application which creates Crystal Reports. This is a multi theaded application which can run several reports at one time. My problem - there is a...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.