Potential memory leak when calling binomial

[Stephen Hartke]

The following code ends up using a lot of memory:

print get_memory_usage()
for i in range(100000):
    b=binomial(5,2)
print get_memory_usage()

Output:
133.48828125
135.015625

So 1.5 extra megabytes is used after the 100,000 calls of binomial.  If repeated calls to binomial are made, eventually Sage runs out of memory and bombs out.  This is a problem for the Combinations.rank() code, which makes many repeated calls to binomial.

Might this be related to how binomial is evaluated using GiNaC?  Similar problems occur when replacing binomial with log.

Weirdly, the code above with fixed parameters for binomial does not create a problem when run in the notebook.  However, if different random values are used in the binomial code for each iteration, then the same memory usage occurs.  Perhaps there's some sort of caching going on?

I've tried this code on both Sage 4.0.1 and Sage 4.1, and the behavior is the same.

Thanks for any insights!
Stephen

[Justin C. Walker]

On Jul 25, 2009, at 08:08 , Stephen Hartke wrote:

> The following code ends up using a lot of memory:
>
> print get_memory_usage()
> for i in range(100000):
> b=binomial(5,2)
> print get_memory_usage()
>
> Output:
> 133.48828125
> 135.015625

I just tried this on 4.0.2 and 4.1 (on Mac OS X, 10.5.7), and got the
same values before and after the loop, so something else must be
involved.

HTH

Justin

--
Justin C. Walker, Curmudgeon at Large
Institute for the Absorption of Federal Funds
-----------
I'm beginning to like the cut of his jibberish.
-----------

[Stephen Hartke]

On Sat, Jul 25, 2009 at 1:54 PM, Justin C. Walker <jus...@mac.com> wrote:

I just tried this on 4.0.2 and 4.1 (on Mac OS X, 10.5.7), and got the
same values before and after the loop, so something else must be
involved.

Justin,

Thanks for your response!  Did you run it from the command line or the notebook?  I noticed that in the notebook, the code does create a problem, but random values do.

Can you try the following code?

import random
print get_memory_usage()
for i in xrange(100000):
    x=random.randint(10,100)
    y=random.randint(0,x)
    r=binomial(x,y)
print get_memory_usage()

I tried the above code on sagenb.org, and get this output:

730.6328125
736.5625

I have Sage 4.1 on a Fedora 9 32-bit machine, and Sage 4.0.1 on a Fedora 8 64-bit machine.  I wonder if that's creating a problem.

Thanks for your help!
Stephen

[Justin C. Walker]

On Jul 25, 2009, at 15:08 , Stephen Hartke wrote:

> On Sat, Jul 25, 2009 at 1:54 PM, Justin C. Walker <jus...@mac.com>
> wrote:
>
>> I just tried this on 4.0.2 and 4.1 (on Mac OS X, 10.5.7), and got the
>> same values before and after the loop, so something else must be
>> involved.
>>
>
> Justin,
>
> Thanks for your response! Did you run it from the command line or the
> notebook?

I used the command-line interface.

> I noticed that in the notebook, the code does create a problem,

^ not??

> but random values do.
>
> Can you try the following code?

Yup. I now see what you see: memory usage increases after executing
the loop using random values. Go ahead and write up a trac/bug
report, and thanks for reporting this.

Justin

--
Justin C. Walker, Curmudgeon at Large
Institute for the Absorption of Federal Funds
--

Democracy is two wolves and a lamb
voting on what to have for lunch.
Liberty is a well-armed lamb contesting
the vote.

[Stephen Hartke]

On Sat, Jul 25, 2009 at 6:04 PM, Justin C. Walker <jus...@mac.com> wrote:

> I noticed that in the notebook, the code does create a problem,

                                               ^ not??

> but random values do.

Yes, I missed a "not".
 

Yup.  I now see what you see: memory usage increases after executing
the loop using random values.  Go ahead and write up a trac/bug
report, and thanks for reporting this.

This is now trac #6623.

Thanks,
Stephen

[Carlo Hamalainen]

On Sat, Jul 25, 2009 at 5:08 PM, Stephen Hartke<har...@gmail.com> wrote:
> Might this be related to how binomial is evaluated using GiNaC?  Similar
> problems occur when replacing binomial with log.

Valgrind says yes:

==26568== 4 bytes in 1 blocks are definitely lost in loss record 35 of 3,312
==26568== at 0x4026FDE: malloc (vg_replace_malloc.c:207)
==26568== by 0x71A0270: __pyx_f_4sage_5rings_7integer_fast_tp_new
(integer.c:28497)
==26568== by 0x719B3DF:
__pyx_f_4sage_5rings_7integer_8int_to_Z__call_ (integer.c:28008)
==26568== by 0x5AB90AA:
__pyx_pf_4sage_9structure_6parent_6Parent___call__ (parent.c:4130)
==26568== by 0x805D596: PyObject_Call (abstract.c:1861)
==26568== by 0x80CCFB4: PyEval_EvalFrameEx (ceval.c:3823)
==26568== by 0x80D0104: PyEval_EvalCodeEx (ceval.c:2875)
==26568== by 0x8116CF0: function_call (funcobject.c:517)
==26568== by 0x805D596: PyObject_Call (abstract.c:1861)
==26568== by 0x806377E: instancemethod_call (classobject.c:2519)
==26568== by 0x805D596: PyObject_Call (abstract.c:1861)
==26568== by 0x7E681FC:
__pyx_f_4sage_5rings_10polynomial_18polynomial_element_10Polynomial__hash_c
(polynomial_element.c:8163)
==26568== by 0x7DE8301:
__pyx_pf_4sage_5rings_10polynomial_18polynomial_element_10Polynomial___hash__
(polynomial_element.c:8113)
==26568== by 0x949106F:
__pyx_pf_4sage_5rings_12number_field_30number_field_element_quadratic_28NumberFieldElement_quadratic___hash__(_object*)
(number_field_element_quadratic.cpp:7281)
==26568== by 0xAA1F7FA: GiNaC::Number_T::hash() const (numeric.cpp:797)
==26568== by 0xAA1F94F: GiNaC::numeric::calchash() const (numeric.cpp:1788)
==26568== by 0xA919E5A: GiNaC::basic::is_equal(GiNaC::basic const&)
const (basic.h:264)
==26568== by 0xA9ED4B5: GiNaC::mul::eval(int) const (ex.h:348)
==26568== by 0xA947B9C:
GiNaC::ex::construct_from_basic(GiNaC::basic const&) (ex.cpp:312)
==26568== by 0xAA26E21: GiNaC::operator*(GiNaC::ex const&,
GiNaC::ex const&) (ex.h:267)
==26568== by 0xA9A5B38: GiNaC::exp_eval(GiNaC::ex const&)
(inifcns_trans.cpp:83)
==26568== by 0xA96102C: GiNaC::function::eval(int) const (function.cpp:1388)
==26568== by 0xA947B9C:
GiNaC::ex::construct_from_basic(GiNaC::basic const&) (ex.cpp:312)
==26568== by 0xAB09757:
__pyx_pf_4sage_8symbolic_10expression_10Expression_exp(_object*,
_object*) (ex.h:267)
==26568== by 0x80CE962: PyEval_EvalFrameEx (ceval.c:3596)

--
Carlo Hamalainen
http://carlo-hamalainen.net

[Stephen Hartke]

On Sun, Jul 26, 2009 at 12:31 AM, Carlo Hamalainen <carlo.ha...@gmail.com> wrote:

On Sat, Jul 25, 2009 at 5:08 PM, Stephen Hartke<har...@gmail.com> wrote:
> Might this be related to how binomial is evaluated using GiNaC?

Valgrind says yes:

==26568== 4 bytes in 1 blocks are definitely lost in loss record 35 of 3,312

The funny thing is that Valgrind detected _only_ 4 bytes that are definitely lost.  So it doesn't seem that this particular memory leak can account for the large amount of memory usage.

Stephen