Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #46063 > unrolled thread

Solving the problem of mutual recursion

Back to article view | Back to comp.lang.python

Contents

  Solving the problem of mutual recursion Peter Brooks <peter.h.m.brooks@gmail.com> - 2013-05-26 04:49 -0700
    Re: Solving the problem of mutual recursion Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-05-26 18:09 +0300
      Re: Solving the problem of mutual recursion Roy Smith <roy@panix.com> - 2013-05-26 11:23 -0400
      Re: Solving the problem of mutual recursion Peter Brooks <peter.h.m.brooks@gmail.com> - 2013-05-26 10:21 -0700
        RE: Solving the problem of mutual recursion Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-26 21:09 +0300
          Re: Solving the problem of mutual recursion Peter Brooks <peter.h.m.brooks@gmail.com> - 2013-05-26 11:13 -0700
            RE: Solving the problem of mutual recursion Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-26 21:22 +0300
              Re: Solving the problem of mutual recursion Peter Brooks <peter.h.m.brooks@gmail.com> - 2013-05-26 12:05 -0700
            Re: Solving the problem of mutual recursion Ian Kelly <ian.g.kelly@gmail.com> - 2013-05-26 13:35 -0600
            Re: Solving the problem of mutual recursion Chris Angelico <rosuav@gmail.com> - 2013-05-27 08:16 +1000
              Re: Solving the problem of mutual recursion Peter Brooks <peter.h.m.brooks@gmail.com> - 2013-05-26 21:36 -0700
                Re: Solving the problem of mutual recursion Ian Kelly <ian.g.kelly@gmail.com> - 2013-05-27 00:07 -0600
                Re: Solving the problem of mutual recursion Chris Angelico <rosuav@gmail.com> - 2013-05-27 17:37 +1000
            Re: Solving the problem of mutual recursion Ian Kelly <ian.g.kelly@gmail.com> - 2013-05-27 00:19 -0600
            Re: Solving the problem of mutual recursion Ian Kelly <ian.g.kelly@gmail.com> - 2013-05-27 01:04 -0600

#46063 — Solving the problem of mutual recursion

I'm not sure if this'll interest anybody, but I expect that I'm going
to get some mutual recursion in my simulation, so I needed to see how
python handled it. Unfortunately, it falls over once it detects a
certain level of recursion. This is reasonable as, otherwise, the
stack eventually over-fills.

Mostly the recommendation, when this happens, is to re-write the code
as loops. Of course, that's not as satisfactory as using recursion.

The problem really is that the methods or functions called recursively
never exit because they're waiting for the return of the function
they've called. Now, if your recursion relies upon knowing what's
returned, then this solution won't help you. Often, though, you're not
interested in what's returned and would just like the routine to exit
once it's called itself, or another process, recursively.

If that's the case, this solution, using threads, allows you to have
functions call themselves, or each other, indefinitely. It works OK on
a macbook pro and the thread count varies from 2-3, so it handles the
thread queuing well. I'm not sure how well this will work on other
architecture - it'd be interesting to know if anybody tries it.

#!/usr/bin/python
# Two functions, Jim and Fred, call each other recursively and
indefinitely, while the main program continues to execute as well
import threading, time

def jim(arg,count):
        print "Running jim:", arg,count," Thread Count
",threading.active_count()
        thread = threading.Thread(target=fred, args=(" From Jim ",count
+1))
        thread.start()
        print count," Jim complete. Thread
Count",threading.active_count()

def fred(arg,counter):
        print "Running fred:", arg,counter
        thread = threading.Thread(target=jim, args=(" From Fred
",counter+1))
        thread.start()
        print counter,"Fred complete",threading.currentThread()


thread = threading.Thread(target=jim, args=(" From Main",0))
thread.start()
print "Jim run from main"
count = 0
while True:
        count += 1
        print 'In main program',count

[toc] | [next] | [standalone]

#46074

Peter Brooks writes:

> I'm not sure if this'll interest anybody, but I expect that I'm
> going to get some mutual recursion in my simulation, so I needed to
...
> returned, then this solution won't help you. Often, though, you're
> not interested in what's returned and would just like the routine to
> exit once it's called itself, or another process, recursively.
> 
> If that's the case, this solution, using threads, allows you to have
> functions call themselves, or each other, indefinitely. It works OK
> on a macbook pro and the thread count varies from 2-3, so it handles

... hard to resist ... but somehow I manage ... whew ...

A light-weighter way is to have each task end by assigning the next
task and returning, instead of calling the next task directly. When a
task returns, a driver loop will call the assigned task, which again
does a bounded amount of work, assigns the next task, and returns.
Tasks can even pass parameters in the same way.

Like so, Dr. Fred keeps adding to a pile as long as there is a pile,
and Mr. Jim keeps taking from it as long as it's there to take from:

from random import choice

def fred():
    global fun, arg
    print('Fred adds 1')
    fun, arg = choice((fred, jim)), arg + 1

def jim():
    global fun, arg
    print('Jim takes 1')
    fun, arg = choice((fred, jim)), arg - 1

if __name__ == '__main__':
    fun, arg = choice((fred, jim)), 3
    while arg:
        print('Pile is', arg, end = '\t')
        fun()
    else:
        print('Pile is gone')

[toc] | [prev] | [next] | [standalone]

#46076

In article <qota9nhu6ag.fsf@ruuvi.it.helsinki.fi>,
 Jussi Piitulainen <jpiitula@ling.helsinki.fi> wrote:

> A light-weighter way is to have each task end by assigning the next
> task and returning, instead of calling the next task directly. When a
> task returns, a driver loop will call the assigned task, which again
> does a bounded amount of work, assigns the next task, and returns.
> Tasks can even pass parameters in the same way.

Yup.  I've used this pattern for building state machines.  Each state is 
a function which returns the next state (or, sometimes, a (next_state, 
output) tuple).  The top level loop ends up looking very much like yours:

state = start
while state != end:
   state, output = state(get_next_input())
   print output


> 
> Like so, Dr. Fred keeps adding to a pile as long as there is a pile,
> and Mr. Jim keeps taking from it as long as it's there to take from:
> 
> from random import choice
> 
> def fred():
>     global fun, arg
>     print('Fred adds 1')
>     fun, arg = choice((fred, jim)), arg + 1
> 
> def jim():
>     global fun, arg
>     print('Jim takes 1')
>     fun, arg = choice((fred, jim)), arg - 1
> 
> if __name__ == '__main__':
>     fun, arg = choice((fred, jim)), 3
>     while arg:
>         print('Pile is', arg, end = '\t')
>         fun()
>     else:
>         print('Pile is gone')

[toc] | [prev] | [next] | [standalone]

#46086

On May 26, 5:09 pm, Jussi Piitulainen <jpiit...@ling.helsinki.fi>
wrote:
>
> A light-weighter way is to have each task end by assigning the next
> task and returning, instead of calling the next task directly. When a
> task returns, a driver loop will call the assigned task, which again
> does a bounded amount of work, assigns the next task, and returns.
> Tasks can even pass parameters in the same way.
>
Yes, that's true - there are a number of ways of making it linear.

What I'm particularly pleased about with my method is the parallelism
that it achieves - with so little effort! The simulation is going to
be computationally intense and this is going to make sure that the
CPUs are all giving it their best shot. When I run this on my macbook,
the python interpreter takes over 140% of CPU - with a bit of fine-
tuning, it should be possible to have more concurrent threads and to
use the four cores optimally.

Naturally I'll need to be careful with the concurrency, but this is so
simple and clean that it should be easy to avoid the main problems
with accessing the same variables.

[toc] | [prev] | [next] | [standalone]

#46091

----------------------------------------
> Date: Sun, 26 May 2013 10:21:05 -0700
> Subject: Re: Solving the problem of mutual recursion
> From: peter.h.m.brooks@gmail.com
> To: python-list@python.org
>
> On May 26, 5:09 pm, Jussi Piitulainen <jpiit...@ling.helsinki.fi>
> wrote:
>>
>> A light-weighter way is to have each task end by assigning the next
>> task and returning, instead of calling the next task directly. When a
>> task returns, a driver loop will call the assigned task, which again
>> does a bounded amount of work, assigns the next task, and returns.
>> Tasks can even pass parameters in the same way.
>>
> Yes, that's true - there are a number of ways of making it linear.
>
> What I'm particularly pleased about with my method is the parallelism
> that it achieves - with so little effort! The simulation is going to
> be computationally intense and this is going to make sure that the
> CPUs are all giving it their best shot. When I run this on my macbook,
> the python interpreter takes over 140% of CPU - with a bit of fine-
> tuning, it should be possible to have more concurrent threads and to
> use the four cores optimally.
>
> Naturally I'll need to be careful with the concurrency, but this is so
> simple and clean that it should be easy to avoid the main problems
> with accessing the same variables.
> --
> http://mail.python.org/mailman/listinfo/python-list

Python threads run in the same process and won't run concurrently:

"CPython implementation detail: In CPython, due to the Global Interpreter Lock, only one thread can execute Python code at once (even though certain performance-oriented libraries might overcome this limitation). If you want your application to make better use of the computational resources of multi-core machines, you are advised to use multiprocessing. However, threading is still an appropriate model if you want to run multiple I/O-bound tasks simultaneously."[1]

How can you get 140% of CPU? IS that a typo??

[1] http://docs.python.org/2/library/threading.html 		 	   		  

[toc] | [prev] | [next] | [standalone]

#46092

On 26 May, 20:09, Carlos Nepomuceno <carlosnepomuc...@outlook.com>
wrote:
> ----------------------------------------
>
>
>
>
>
>
>
>
>
> > Date: Sun, 26 May 2013 10:21:05 -0700
> > Subject: Re: Solving the problem of mutual recursion
> > From: peter.h.m.bro...@gmail.com
> > To: python-l...@python.org
>
> > On May 26, 5:09 pm, Jussi Piitulainen <jpiit...@ling.helsinki.fi>
> > wrote:
>
> >> A light-weighter way is to have each task end by assigning the next
> >> task and returning, instead of calling the next task directly. When a
> >> task returns, a driver loop will call the assigned task, which again
> >> does a bounded amount of work, assigns the next task, and returns.
> >> Tasks can even pass parameters in the same way.
>
> > Yes, that's true - there are a number of ways of making it linear.
>
> > What I'm particularly pleased about with my method is the parallelism
> > that it achieves - with so little effort! The simulation is going to
> > be computationally intense and this is going to make sure that the
> > CPUs are all giving it their best shot. When I run this on my macbook,
> > the python interpreter takes over 140% of CPU - with a bit of fine-
> > tuning, it should be possible to have more concurrent threads and to
> > use the four cores optimally.
>
> > Naturally I'll need to be careful with the concurrency, but this is so
> > simple and clean that it should be easy to avoid the main problems
> > with accessing the same variables.
> > --
> >http://mail.python.org/mailman/listinfo/python-list
>
> Python threads run in the same process and won't run concurrently:
>
> "CPython implementation detail: In CPython, due to the Global Interpreter Lock, only one thread can execute Python code at once (even though certain performance-oriented libraries might overcome this limitation). If you want your application to make better use of the computational resources of multi-core machines, you are advised to use multiprocessing. However, threading is still an appropriate model if you want to run multiple I/O-bound tasks simultaneously."[1]
>
> How can you get 140% of CPU? IS that a typo??
>
No, on a multi-core machine it's normal. The machine shows python
running multiple threads - and the number of threads change as the
program runs. Perhaps the OS/X implementation of python does allow
concurrency when others don't. It certainly looks like it!

[toc] | [prev] | [next] | [standalone]

#46098

----------------------------------------
> Date: Sun, 26 May 2013 11:13:12 -0700
> Subject: Re: Solving the problem of mutual recursion
> From: peter.h.m.brooks@gmail.com
> To: python-list@python.org
[...]
>> How can you get 140% of CPU? IS that a typo??
>>
> No, on a multi-core machine it's normal. The machine shows python
> running multiple threads - and the number of threads change as the
> program runs. Perhaps the OS/X implementation of python does allow
> concurrency when others don't. It certainly looks like it!


I pretty sure it doesn't run on multiple cores on Linux and Windows.

I've tested it and have been trying to find a better way achieve concurrency in Python. One of the ways is the multiprocessing module[1].

Do Mac OS shows "140%" CPU load when more than a single core is been used? lol Apple sucks!!! lol


[1] http://docs.python.org/2/library/multiprocessing.html 		 	   		  

[toc] | [prev] | [next] | [standalone]

#46102

On 26 May, 20:22, Carlos Nepomuceno <carlosnepomuc...@outlook.com>
wrote:
> ----------------------------------------
>
> > Date: Sun, 26 May 2013 11:13:12 -0700
> > Subject: Re: Solving the problem of mutual recursion
> > From: peter.h.m.bro...@gmail.com
> > To: python-l...@python.org
> [...]
> >> How can you get 140% of CPU? IS that a typo??
>
> > No, on a multi-core machine it's normal. The machine shows python
> > running multiple threads - and the number of threads change as the
> > program runs. Perhaps the OS/X implementation of python does allow
> > concurrency when others don't. It certainly looks like it!
>
> I pretty sure it doesn't run on multiple cores on Linux and Windows.
>
> I've tested it and have been trying to find a better way achieve concurrency in Python. One of the ways is the multiprocessing module[1].
>
> Do Mac OS shows "140%" CPU load when more than a single core is been used? lol Apple sucks!!! lol
>
It's not uncommon - HP-UX does exactly the same thing.

[toc] | [prev] | [next] | [standalone]

#46104

On Sun, May 26, 2013 at 12:13 PM, Peter Brooks
<peter.h.m.brooks@gmail.com> wrote:
> No, on a multi-core machine it's normal. The machine shows python
> running multiple threads - and the number of threads change as the
> program runs. Perhaps the OS/X implementation of python does allow
> concurrency when others don't. It certainly looks like it!

I'm pretty sure that CPython uses the GIL regardless of platform.  And
yes you can have multiple OS-level threads, but because of the GIL
only one will actually be running at a time.  Other possibilities
include:

1) You're using a different implementation of Python that does not
have a GIL, e.g. Jython or IronPython (well, probably not the latter).
 I believe PyPy also has a GIL-less version, although I don't think
this is in the current release yet.

2) You're using a fork of CPython that removes the GIL.  There are a
number of these, but none to my knowledge that are able to maintain
the performance of CPython for a single thread.

3) You're mistakenly looking at multiple Python processes that are
running simultaneously and adding their usages together.

4) The utility you're using is reporting the process CPU usage incorrectly.

5) Maybe for some reason the Mac OS X build of CPython is using
spin-locks in the GIL.  I can't imagine why this would be the case.

[toc] | [prev] | [next] | [standalone]

#46130

On Mon, May 27, 2013 at 5:35 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> I'm pretty sure that CPython uses the GIL regardless of platform.  And
> yes you can have multiple OS-level threads, but because of the GIL
> only one will actually be running at a time.  Other possibilities
> include:

6) It's spinning in a function that has released the GIL. Python
threads can certainly execute concurrently; they just can't be
manipulating Python objects. Most of the I/O functions will release
the GIL before doing a potentially-blocking operation, and some
CPU-heavy functions can do the same (I'm given to understand that
numpy does this) - just depends on having a long job that involves no
refcounted objects.

ChrisA

[toc] | [prev] | [next] | [standalone]

#46158

On May 27, 12:16 am, Chris Angelico <ros...@gmail.com> wrote:
> On Mon, May 27, 2013 at 5:35 AM, Ian Kelly <ian.g.ke...@gmail.com> wrote:
> > I'm pretty sure that CPython uses the GIL regardless of platform.  And
> > yes you can have multiple OS-level threads, but because of the GIL
> > only one will actually be running at a time.  Other possibilities
> > include:
>
> 6) It's spinning in a function that has released the GIL. Python
> threads can certainly execute concurrently; they just can't be
> manipulating Python objects. Most of the I/O functions will release
> the GIL before doing a potentially-blocking operation, and some
> CPU-heavy functions can do the same (I'm given to understand that
> numpy does this) - just depends on having a long job that involves no
> refcounted objects.
>
This makes complete sense - any atomic action should be atomic, so two
threads can't be doing it at the same time. They can be doing anything
else though.

If two threads create a new object at the same time, for example,
there's potentially the problem that they'll get the same space, so
the object will be owned by both. To prevent this, the new object call
should be run in only one thread.

If you have two objects running their methods on their own local
variables, then there's no potential for conflict, so there's no need
for them to be blocked.

This is an interesting subject.. There's nothing wrong with the tool
I'm using to report threads - 'Activity Monitor' is the standard
process monitor. It counts cores as 'CPUs', which seems perfectly
reasonable to me. As I said, other Unixes, such as HP-UX, do the same
thing.

I'm not quite sure of the best way to examine the exact behaviour.
Since the blocking works at the level of atomic operations, it's
difficult to detect - a call to an atomic operation may block all
other threads, but any snapshot of the number of active threads won't
be running at this time, so will only report when there are multiple
threads active.

[toc] | [prev] | [next] | [standalone]

#46170

On Sun, May 26, 2013 at 10:36 PM, Peter Brooks
<peter.h.m.brooks@gmail.com> wrote:
> This makes complete sense - any atomic action should be atomic, so two
> threads can't be doing it at the same time. They can be doing anything
> else though.
>
> If two threads create a new object at the same time, for example,
> there's potentially the problem that they'll get the same space, so
> the object will be owned by both. To prevent this, the new object call
> should be run in only one thread.
>
> If you have two objects running their methods on their own local
> variables, then there's no potential for conflict, so there's no need
> for them to be blocked.

That's not the way it works.  The CPython interpreter always runs with
the GIL held; the alternative would be to have individual mutex locks
on every Python object, which is expensive for performance due to the
reference counting mechanism.  Python functions can't release the GIL.
 C functions that are called from the interpreter *can* release the
GIL to allow concurrency, but are only permitted to do so as long as
they're not working with Python objects, e.g. waiting on I/O or
performing a long calculation on C data.

There are some more detailed slides on how the GIL works at:

http://www.dabeaz.com/python/UnderstandingGIL.pdf

Note that the description in Part 1 describes how the GIL worked prior
to Python 3.2.  The new GIL is described in Part 4, but the basic
underlying concept is the same.

> This is an interesting subject.. There's nothing wrong with the tool
> I'm using to report threads - 'Activity Monitor' is the standard
> process monitor. It counts cores as 'CPUs', which seems perfectly
> reasonable to me. As I said, other Unixes, such as HP-UX, do the same
> thing.

I have no problem with that.  It's also the default in Linux, where I
believe it is called "IRIX mode" (as opposed to "Solaris mode", where
the difference is just a factor equal to the number of cores).  What I
was questioning was whether the actual number being reported was
correct.  If it's the standard tool for the OS, then it probably is.

[toc] | [prev] | [next] | [standalone]

#46178

On Mon, May 27, 2013 at 4:07 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Sun, May 26, 2013 at 10:36 PM, Peter Brooks
> <peter.h.m.brooks@gmail.com> wrote:
>> This makes complete sense - any atomic action should be atomic, so two
>> threads can't be doing it at the same time. They can be doing anything
>> else though.
>>
>> If two threads create a new object at the same time, for example,
>> there's potentially the problem that they'll get the same space, so
>> the object will be owned by both. To prevent this, the new object call
>> should be run in only one thread.
>>
>> If you have two objects running their methods on their own local
>> variables, then there's no potential for conflict, so there's no need
>> for them to be blocked.
>
> That's not the way it works. [snip details]

You're actually both saying the same thing, except that Peter went for
finer granularity than Ian and CPython did. CPython figures that, with
a refcounted heap, there's not a lot of point having separate mutex
locks for different operations. Other language interpreters have made
other choices. But Peter's analysis is still correct; it's just that
guarding it is simplified down to a binary state: either you have the
GIL, or you don't.

ChrisA

[toc] | [prev] | [next] | [standalone]

#46173

On Sun, May 26, 2013 at 4:16 PM, Chris Angelico <rosuav@gmail.com> wrote:
> On Mon, May 27, 2013 at 5:35 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>> I'm pretty sure that CPython uses the GIL regardless of platform.  And
>> yes you can have multiple OS-level threads, but because of the GIL
>> only one will actually be running at a time.  Other possibilities
>> include:
>
> 6) It's spinning in a function that has released the GIL. Python
> threads can certainly execute concurrently; they just can't be
> manipulating Python objects. Most of the I/O functions will release
> the GIL before doing a potentially-blocking operation, and some
> CPU-heavy functions can do the same (I'm given to understand that
> numpy does this) - just depends on having a long job that involves no
> refcounted objects.

7) Since the program being tested does basically nothing except start
and exit threads, the extra 40% probably represents the overhead of
all that starting and stopping, which would be done outside the GIL.

[toc] | [prev] | [next] | [standalone]

#46175

On Mon, May 27, 2013 at 12:19 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> 7) Since the program being tested does basically nothing except start
> and exit threads, the extra 40% probably represents the overhead of
> all that starting and stopping, which would be done outside the GIL.

To test this, I tried running the script in Python 2.7 in Linux with
the print statements removed and verified that it was using about 135%
of the CPU.  However, top also told me that only about 95% of that was
user processes; the other 40% was kernel usage.  The 40% doesn't seem
to be threading overhead though, because I tried adding large xrange
loops to slow down the thread creation process and it had no effect on
the stats.

Then I tried running the same program in Python 3.2, and I got the
more expected 100% CPU usage with minimal kernel time.  So I'm
thinking now that the extra 40% may actually be overhead induced by
the GIL.  If that's the case then wow, the old GIL really did suck.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web