Using Python for programming algorithms

[Vicent Giner]

On May 19, 7:03 am, Bruno Desthuilliers <bruno.

I'm pretty sure about that: when the algorithms take 4 hours to test
a single execution, you value processor time.

Yes, of course, but that should mean that I have to do it better, in
the programming step (I would have to re-program or re-implement my
algorithm). And I think the problem would be the same in any other
language, wouldn't it?

The situation would be simpler if there were good well-known toolkits
for optimization in python (like numpy for matrix operations), but
that's not the case.

Are there such toolkits in other languages? I am not sure they exist
in C, for example.

By the way, is it possible (and easy) to call a C function from a
Python program??

 

[Lou Pecora]

Bruno Desthuilliers schreef:

You keep saying that, and in theory you're right. But I'm still inclined
to disagree with it, since the practical reality is different. Python is
indeed compiled to byte code, but if you compare that byte code with
assembly code you'll see that there's a whole world of difference
between the two, largely because of the dynamical nature of Python. Fact
is that Python was designed from the start to run on a virtual machine,
not on the native hardware.

C OTOH was designed to be compiled to assembly code (or directly to
machine code) and as a result there are no (or virtually) no
implementations that interpret C or compile it to bytecode.

But how about this C/C++ interpreter. Dr. Dobbs article:
http://www.ddj.com/cpp/184402054. Title and first two paragraphs:

Ch: A C/C++ Interpreter for Script Computing
Interactive computing in C

Ch is a complete C interpreter that supports all language features and
standard libraries of the ISO C90 Standard, but extends C with many
high-level features such as string type and computational arrays as
first-class objects.

For some tasks, C and its compile/ link/execute/debug process are not
productive. As computer hardware becomes cheaper and faster, to be
productive and cost effective, script computing in C/C++ can be an
appealing solution. To this end, we have developed Ch, an embeddable
C/C++ interpreter for cross-platform scripting, shell programming, 2D/3D
plotting, numerical computing, and embedded scripting [1].

 

[Jaap Spies]

Thank you very much for all the answers I've got.

As far as I have understood, Python can be a good alternative, or, at
least, a reasonable choice.

I intend to design new algorithms for a kind of Optimization problems,
and then I have to implement them and show/prove that they are good
enough, in terms of effectiveness (quality of the solution that the
algorithm is able to find, for some given "difficult" problems), and
not mainly in terms of efficiency (time to find the solution).

I mean, in order to prove that my algorithms are "good", I have to
compare them with the results given by other algorithms, in terms of
how much better is the solution given by my proposal, in front of the
previous ones. Only comparatives in terms of "number of iterations",
and not "time to find the solution", can be done (I think).

Here you find good company in the Sage developers community!

Jaap

 

[bruno.desthuilliers]

Bruno Desthuilliers schreef:



You keep saying that, and in theory you're right.

"In theory" ??? Heck, both points above are mere facts. Well, I may
accept that the 2nd one is a bit overgeneralized, since IIRC there's
an experimental Python to javascript "compiler" in Pypy, but...

But I'm still inclined to disagree with it, since the practical reality is different.

Do you mean that how source code written in a language (that is : a
grammar + a syntax) finally become a set of instructions executed by
a CPU depends on the language (I repeat : a grammer + a syntax), and
not on a piece of software turning the source code into something that
can actually be executed by the CPU ? Or that there exists a (working
and usable) implementation of the Python language that does not use an
intermediate byte-code compilation ? If the latest, I'd happly
recognize my error if proven wrong. But on the first point, I'm afraid
that, well, a fact is a fact is a fact.

Python is
indeed compiled to byte code, but if you compare that byte code with
assembly code you'll see that there's a whole world of difference
between the two,

Obviously, yes - at least for all assembly language I've seen so far.
But whoever said otherwise ?

largely because of the dynamical nature of Python. Fact
is that Python was designed from the start to run on a virtual machine,
not on the native hardware.

Nope. The facts are that
1/ Python (the language) has *not* been designed with ease of
implementation of an optimizing native-code compiler in mind, and
2/ CPython (the first and reference implementation) has been designed
to use a byte-code + VM scheme

C OTOH was designed to be compiled to assembly code (or directly to
machine code)

Note quite. C has been designed to make it as easy as possible to
write either a C to assembly or C to native binary code compiler.

and as a result there are no (or virtually) no
implementations that interpret C or compile it to bytecode.

There's at least one (possibly incomplete) C interpreter. FWIW, it
would not be harder (and possibly simpler) to write a byte-code+VM
based C implementation than it is to write CPython, Jython or
IronPython. The point is that it's just useless - C is a (very) low-
level language, and the only reason to use C is that you'll find a
pretty good optimizing native-code compiler on almost any platform -
sometimes even before the CPU physically exists.

I love Python, but IMHO it's a bit silly to maintain that the fact that
Python compiles to byte code instead of assembly code/machine code is
purely a matter of implementation; on the contrary, I believe it's a
result of its design.

There's a very naive belief we saw every here and then here, which is
that "Python would be faster if it was compiled to native code". The
point is that, given Python's (as a language) extrem dynamism,
compiling it to native code wouldn't buy you much in terms of raw
performances. The problem is not with writing a native-code
compiler[1}, but with writing an *optimising* native-code compiler.
FWIW, even Java with it's brain-dead static type-system gained more
from JIT compilation in the VM than from being directly compiled to
native code.

[1] not that I would personnaly be able to do so in a reasonable
amount of time, but given how many talented programmers have been and
are still working on making as fast as possible Python implementions,
it seems obvious that such a thing would already exists if there was
any point working on it.

I also think that there's a large difference
between byte code and machine code

(in Python's case; I haven't looked
at other languages), and that it's a bit silly to try to trivialize that
difference.

I'm not trying to "trivialize" anything. I'm just getting fed up with
this "Python is an interpreted and therefore slow language" non-
sense. Python is a language, and as such is neither slow nor fast nor
interpreted nor compiled nor <insert any implementation related stuff
here>. And while CPython is not blazingly fast for computation-heavy
stuff, it's not because it is "interpreted" - which it is not for a
strict definition of "interpreted", but anyway... - but because
*optimizing* execution of an highly dynamic language is nothing,
well, err, trivial.

 

[bruno.desthuilliers]

I agree with what most people here said, that the language doesn't
really matter, etc., but that simply does not apply to the specific
case of optimization research.

The little I know about optimization, even trivial problems may be
hairy problems. Naïve implementations simply don't finish and the
performance bottlenecks are not necessarily in the numeric computation
algorithms (so numpy doesn't help much here). If the guy is doing
research on that, it possible that he will work with thousands (or
millions) of weird constraints.

I'm pretty sure about that: when the algorithms take 4 hours to test
a single execution, you value processor time.

I'm no expert here, but this sounds like a sensible argument to me.

OTHO, if the OP ends up spending more time writing boilerplate code
and fighting with gory implementation details than working on the
algorithm themselves, he might find than relative difference between
two possible algorithms (like one takes 4 hours and the second take 2
1/2 hours, but each took less than one hour to implement) is much more
important than having the first one taking 4 minutes, the second 2 1/2
minutes, and each having take 15 days to write and debug...

The situation would be simpler if there were good well-known toolkits
for optimization in python (like numpy for matrix operations), but
that's not the case.

There's at least Psyco (if you're willing and able to restrict
yourself from using some of the most dynamic parts of Python - which
might not be a problem here). One could also mention stuff like Pyrex
and Cython.

 

[bruno.desthuilliers]

On May 19, 6:11 pm, Henrique Dante de Almeida <[email protected]>
wrote:
(snip)

Are there such toolkits in other languages? I am not sure they exist
in C, for example.

Well... They do - they are called 'C compilers' !-) As Roel Schroven
mentioned - and he is at least partially right on this point - C has
been designed to make optimizing C compiler not to hairy to write.

By the way, is it possible (and easy) to call a C function from a
Python program??

Possible, yes, indeed. Easy depends on your definition of easiness,
but going down to C for computation-heavy performance-critical parts
of a program or library is not that uncommon.

 

[bruno.desthuilliers]

(snip)

Yes, I was actually referring to statically typed JIT-compiled
languages. Sorry about that, blame the beers that entered my digestive
system that night.

for beer in beers:
if beer.entered_henrique_digestive_system_last_night:
beer.blame()

!-)

 

[Henrique Dante de Almeida]

Yes, of course, but that should mean that I have to do it better, in
the programming step (I would have to re-program or re-implement my
algorithm). And I think the problem would be the same in any other
language, wouldn't it?

The idea is that a C version of the same program could take, eg. 0,4
hours. But I think we have an authoritative answer here, see Robin
Becker's post (even though he programmed the problem, not the
algorithm).

Are there such toolkits in other languages? I am not sure they exist
in C, for example.

I'm sure there are a lot of toolkits for linear programming (can't
tell about other solvers). glpk is the GNU implementation. It even has
its own built-in language (Mathprog). Someone posted an interesting
link of a python wrapper: "OpenOpt"

http://scipy.org/scipy/scikits/wiki/OpenOpt

It supports many solvers. It may be interesting for you, since there
are some non-linear and "global" problem solvers:

http://scipy.org/scipy/scikits/wiki/OOClasses

By the way, is it possible (and easy) to call a C function from a
Python program??

Yes. The easiest way I know of is using SWIG. People will recommend
you Cython too.

 

[Henrique Dante de Almeida]

There's at least one (possibly incomplete) C interpreter. FWIW, it
would not be harder (and possibly simpler) to write a byte-code+VM
based C implementation than it is to write CPython, Jython or

You may (right now, readily, without experimental software) compile C
to, for example, llvm bytecode, interpret it in the VM, JIT-compile
it, native-compile it, etc. There's also experimental support for
compiling C to the JVM.

Notice that you usually want to optimize C code, so it will be harder
than writing a python interpreter.

IronPython. The point is that it's just useless - C is a (very) low-

It's not useless. Consider that you may distribute your C application
in byte-code instead of native code and during the installation
process, it is native compiled and optimized exactly to your
architecture (like a better "Gentoo", with the compilation split
between you and the user).

point is that, given Python's (as a language) extrem dynamism,
compiling it to native code wouldn't buy you much in terms of raw
performances. The problem is not with writing a native-code
compiler[1}, but with writing an *optimising* native-code compiler.

That's the job of pypy folks. And they are getting there. They use a
python subset, called RPython:

http://morepypy.blogspot.com/2008/01/rpython-can-be-faster-than-c.html
(note: the test in the site compares garbage collection speed)

BTW, here's how to compile RPython to (optimized) native code:
http://codespeak.net/pypy/dist/pypy/doc/standalone-howto.html

And here is the document that talks about all that:
http://codespeak.net/pypy/dist/pypy/doc/dynamic-language-translation.html

I'm not trying to "trivialize" anything. I'm just getting fed up with
this "Python is an interpreted and therefore slow language" non-
sense.  Python is a language, and as such is neither slow nor fast nor

I'm sorry for creating all those offtopic posts. I feel so ashamed :-
(. Well, not really.

My suggestion was to use code suitable for optimization (not
considering things that you'd need to worry about the way you write
code, like RPython, or psyco). That's all.

 

[Henrique Dante de Almeida]

There's at least Psyco (if you're willing and able to restrict
yourself from using some of the most dynamic parts of Python - which
might not be a problem here).  One could also mention stuff like Pyrex
and Cython.

I meant toolkits for "optimization problems", not "code
optimization".

 

[Henrique Dante de Almeida]

(snip)


for beer in beers:
  if beer.entered_henrique_digestive_system_last_night:
    beer.blame()

!-)

???

beers += [Beer.random()]

 

[Bruno Desthuilliers]

Henrique Dante de Almeida a écrit :

I meant toolkits for "optimization problems", not "code
optimization".

oops, sorry.

 

[Ivan Illarionov]

Yes, I was actually referring to statically typed JIT-compiled
languages. Sorry about that, blame the beers that entered my digestive
system that night.

[beer.blame() for beer in beers]

if len(beers) > 2:
news_reader.stop_working()

 

[Ivan Illarionov]

]

By the way, is it possible (and easy) to call a C function from a Python
program??

Yes.

http://groups.google.com/group/comp.lang.python/msg/9d47913a265c348a

-- Ivan

 

[brad]

The usual answer is that development time is more important than running time.

This depends. Run time is not important until you are asked to scale to
millions or billions of users or computations or large data sets. I've
seen this first hand. Getting results back the same day or sooner may be
important. In cases such as this, I use C or C++... nothing else will
do. Nothing else is as fast. Although I always keep a py version around
for testing and for smaller tasks. Don't get me wrong, I love Python,
but there are times when nothing, but pure, hard speed will do.

 

[Arnaud Delobelle]

This depends. Run time is not important until you are asked to scale
to millions or billions of users or computations or large data
sets. I've seen this first hand. Getting results back the same day or
sooner may be important. In cases such as this, I use C or
C++... nothing else will do. Nothing else is as fast. Although I
always keep a py version around for testing and for smaller
tasks. Don't get me wrong, I love Python, but there are times when
nothing, but pure, hard speed will do.

Sure. Be careful not to overdose on it though.

 

[sturlamolden]

By the way, is it possible (and easy) to call a C function from a
Python program??

Yes it is. You can e.g. use ctypes for that.

 

[sturlamolden]

Well... They do - they are called 'C compilers' !-) As Roel Schroven
mentioned - and he is at least partially right on this point - C has
been designed to make optimizing C compiler not to hairy to write.

C has proven very difficult to optimize, particularly because pointer
aliasing prevents efficient register allocation.

Fortran was designed with ease of optimization in mind. Not many years
ago, it was not uncommon for Fortran code to run twice as fast as
equivalent C. C compilers have recently closed on on the gap by
becoming extremely good at what they do. But that is not because C is
easy to optimize. On the contrary.

For serious number crunshing, there is nothing that compares to
Fortran, even today. f2py makes it easy to call Fortran subroutines
from Python.

 

[sturlamolden]

http://docs.python.org/lib/module-ctypes.html

Also see Cython (or Pyrex if you prefer the original). With Cython it
is easy to call C functions, but Cython also alleviates the need for C
to a great extent. The advantage of Cython over C + ctypes is of
course the readability of Python and the presence of Python built-in
types like strings, dicts and lists. Unfortunately, it is still a bit
difficult to use NumPy ndarrays with Cython or Pyrex. NumPy ndarrays
work very well with ctypes though.

http://www.cython.org/

 

[Roel Schroeven]

Wow this resulted in far more reactions than I had expected ...

(e-mail address removed) schreef:

"In theory" ??? Heck, both points above are mere facts. Well, I may
accept that the 2nd one is a bit overgeneralized, since IIRC there's
an experimental Python to javascript "compiler" in Pypy, but...


Do you mean that how source code written in a language (that is : a
grammar + a syntax) finally become a set of instructions executed by
a CPU depends on the language (I repeat : a grammer + a syntax), and
not on a piece of software turning the source code into something that
can actually be executed by the CPU ?

No, that's not what I said; what I said is that some languages where
designed with in the back of the head the idea that they were going to
be compiled to native code, others to be interpreted, and others to be
compiled to byte code.

Wikipedia says about C that "its design goals were for it to be compiled
using a relatively straightforward compiler, provide low-level access to
memory, provide language constructs that map efficiently to machine
instructions, and require minimal run-time support". To me, that very
strongly suggests that it was meant to be compiled to native code. It's
called "portable assembly" for a reason. You *can* make it work in
another way, and I suppose that it *is* done, but those implementations
are far in the minority.

As for Python, until the advent of PyPy all implementations I known used
a virtual machine (CPython, Jython, IronPython). And PyPy is still
experimental as far as I know.

So yes, the transformation method from source code to something that the
CPU understands depends on your tools. But if you want to get work done,
the most common method by far for C is to use a toolchain that compiles
to native code and for Python a byte code compiler + virtual machine.
With possibly a JIT compiler, that's true.

Obviously, yes - at least for all assembly language I've seen so far.
But whoever said otherwise ?

Whenever someone says that Python is interpreted, you respond saying
that that's not true, since it's compiled to byte code. Correct of
course, but somehow it appears to me that you imply that that makes
Python closer to a C-like language than to an interpreted language, and
that's not correct (IMO). If that's just a misinterpretation by me, I
apologize.

Nope. The facts are that
1/ Python (the language) has *not* been designed with ease of
implementation of an optimizing native-code compiler in mind, and
2/ CPython (the first and reference implementation) has been designed
to use a byte-code + VM scheme

Isn't that more or less the same as what I said?

Maybe I don't make enough distinction between Python the language and
CPython the implementation, but Python development does happen on the
CPython implementation (Python 3.0 alpha releases are CPython releases,
for example).

Note quite. C has been designed to make it as easy as possible to
write either a C to assembly or C to native binary code compiler.

I find it hard to believe that during the development of C Dennis
Ritchie was considering any other mode of operation than compilation to
assembly or machine code. I might be wrong of course.

There's at least one (possibly incomplete) C interpreter.

I'd like to call that the exception that confirms the rule.

There's a very naive belief we saw every here and then here, which is
that "Python would be faster if it was compiled to native code". The
point is that, given Python's (as a language) extrem dynamism,
compiling it to native code wouldn't buy you much in terms of raw
performances. The problem is not with writing a native-code
compiler[1}, but with writing an *optimising* native-code compiler.

I admit I'm guilty of that belief. I know it's true what you say, but I
do have the more-or-less unconscious reflex 'compiled to native code
== fast'.

I'm just getting fed up with
this "Python is an interpreted and therefore slow language" non-
sense. Python is a language, and as such is neither slow nor fast nor
interpreted nor compiled nor <insert any implementation related stuff
here>. And while CPython is not blazingly fast for computation-heavy
stuff, it's not because it is "interpreted" - which it is not for a
strict definition of "interpreted", but anyway... - but because
*optimizing* execution of an highly dynamic language is nothing,
well, err, trivial.

So you are saying that CPython is relatively slow because Python is a
highly dynamic language. I know that CPython is not Python and Python is
not CPython, but there is a very strong association between the two and
therefore I think it's not really that much wrong to simplify that to
'Python is slow because it is a highly dynamic language (until proven
wrong by PyPy or another fast implementation'.

--
The saddest aspect of life right now is that science gathers knowledge
faster than society gathers wisdom.
-- Isaac Asimov

Roel Schroeven