=====================
 Weave Documentation
=====================

By Eric Jones eric@enthought.com


Outline
=======

.. contents::


==============
 Introduction
==============

The ``weave`` package provides tools for including C/C++ code within in
Python code. This offers both another level of optimization to those who need
it, and an easy way to modify and extend any supported extension libraries
such as wxPython and hopefully VTK soon. Inlining C/C++ code within Python
generally results in speed ups of 1.5x to 30x speed-up over algorithms
written in pure Python (However, it is also possible to slow things down...).
Generally algorithms that require a large number of calls to the Python API
don't benefit as much from the conversion to C/C++ as algorithms that have
inner loops completely convertable to C.

There are three basic ways to use ``weave``. The ``weave.inline()`` function
executes C code directly within Python, and ``weave.blitz()`` translates
Python NumPy expressions to C++ for fast execution. ``blitz()`` was the
original reason ``weave`` was built. For those interested in building
extension libraries, the ``ext_tools`` module provides classes for building
extension modules within Python.

Most of ``weave's`` functionality should work on Windows and Unix, although
some of its functionality requires ``gcc`` or a similarly modern C++ compiler
that handles templates well. Up to now, most testing has been done on Windows
2000 with Microsoft's C++ compiler (MSVC) and with gcc (mingw32 2.95.2 and
2.95.3-6). All tests also pass on Linux (RH 7.1 with gcc 2.96), and I've had
reports that it works on Debian also (thanks Pearu).

The ``inline`` and ``blitz`` provide new functionality to Python (although
I've recently learned about the `PyInline`_ project which may offer similar
functionality to ``inline``). On the other hand, tools for building Python
extension modules already exists (SWIG, SIP, pycpp, CXX, and others). As of
yet, I'm not sure where ``weave`` fits in this spectrum. It is closest in
flavor to CXX in that it makes creating new C/C++ extension modules pretty
easy. However, if you're wrapping a gaggle of legacy functions or classes,
SWIG and friends are definitely the better choice. ``weave`` is set up so
that you can customize how Python types are converted to C types in
``weave``. This is great for ``inline()``, but, for wrapping legacy code, it
is more flexible to specify things the other way around -- that is how C
types map to Python types. This ``weave`` does not do. I guess it would be
possible to build such a tool on top of ``weave``, but with good tools like
SWIG around, I'm not sure the effort produces any new capabilities. Things
like function overloading are probably easily implemented in ``weave`` and it
might be easier to mix Python/C code in function calls, but nothing beyond
this comes to mind. So, if you're developing new extension modules or
optimizing Python functions in C, ``weave.ext_tools()`` might be the tool for
you. If you're wrapping legacy code, stick with SWIG.

The next several sections give the basics of how to use ``weave``. We'll
discuss what's happening under the covers in more detail later on. Serious
users will need to at least look at the type conversion section to understand
how Python variables map to C/C++ types and how to customize this behavior.
One other note. If you don't know C or C++ then these docs are probably of
very little help to you. Further, it'd be helpful if you know something about
writing Python extensions. ``weave`` does quite a bit for you, but for
anything complex, you'll need to do some conversions, reference counting,
etc.

.. note::
  ``weave`` is actually part of the `SciPy`_ package. However, it
  also works fine as a standalone package (you can check out the sources using
  ``svn co http://svn.scipy.org/svn/scipy/trunk/Lib/weave weave`` and install as
  python setup.py install). The examples here are given as if it is used as a
  stand alone package. If you are using from within scipy, you can use `` from
  scipy import weave`` and the examples will work identically.


==============
 Requirements
==============

-   Python

    I use 2.1.1. Probably 2.0 or higher should work.

-   C++ compiler

    ``weave`` uses ``distutils`` to actually build extension modules, so
    it uses whatever compiler was originally used to build Python. ``weave``
    itself requires a C++ compiler. If you used a C++ compiler to build
    Python, your probably fine.

    On Unix gcc is the preferred choice because I've done a little
    testing with it. All testing has been done with gcc, but I expect the
    majority of compilers should work for ``inline`` and ``ext_tools``. The
    one issue I'm not sure about is that I've hard coded things so that
    compilations are linked with the ``stdc++`` library. *Is this standard
    across Unix compilers, or is this a gcc-ism?*

    For ``blitz()``, you'll need a reasonably recent version of gcc.
    2.95.2 works on windows and 2.96 looks fine on Linux. Other versions are
    likely to work. Its likely that KAI's C++ compiler and maybe some others
    will work, but I haven't tried. My advice is to use gcc for now unless
    your willing to tinker with the code some.

    On Windows, either MSVC or gcc (`mingw32`_) should work. Again,
    you'll need gcc for ``blitz()`` as the MSVC compiler doesn't handle
    templates well.

    I have not tried Cygwin, so please report success if it works for
    you.

-   NumPy

    The python `NumPy`_ module is required for ``blitz()`` to
    work and for numpy.distutils which is used by weave.


==============
 Installation
==============

There are currently two ways to get ``weave``. First, ``weave`` is part of
SciPy and installed automatically (as a sub- package) whenever SciPy is
installed. Second, since ``weave`` is useful outside of the scientific
community, it has been setup so that it can be used as a stand-alone module.

The stand-alone version can be downloaded from `here`_.  Instructions for
installing should be found there as well.  setup.py file to simplify
installation.


=========
 Testing
=========

Once ``weave`` is installed, fire up python and run its unit tests.

::

    >>> import weave
    >>> weave.test()
    runs long time... spews tons of output and a few warnings
    .
    .
    .
    ..............................................................
    ................................................................
    ..................................................
    ----------------------------------------------------------------------
    Ran 184 tests in 158.418s
    OK
    >>>


This takes a while, usually several minutes. On Unix with remote file
systems, I've had it take 15 or so minutes. In the end, it should run about
180 tests and spew some speed results along the way. If you get errors,
they'll be reported at the end of the output. Please report errors that you
find. Some tests are known to fail at this point.


If you only want to test a single module of the package, you can do this by
running test() for that specific module.

::

        >>> import weave.scalar_spec
        >>> weave.scalar_spec.test()
        .......
         ----------------------------------------------------------------------
        Ran 7 tests in 23.284s


Testing Notes:
==============


-   Windows 1

    I've had some test fail on windows machines where I have msvc,
    gcc-2.95.2 (in c:\gcc-2.95.2), and gcc-2.95.3-6 (in c:\gcc) all
    installed. My environment has c:\gcc in the path and does not have
    c:\gcc-2.95.2 in the path. The test process runs very smoothly until the
    end where several test using gcc fail with cpp0 not found by g++. If I
    check os.system('gcc -v') before running tests, I get gcc-2.95.3-6. If I
    check after running tests (and after failure), I get gcc-2.95.2. ??huh??.
    The os.environ['PATH'] still has c:\gcc first in it and is not corrupted
    (msvc/distutils messes with the environment variables, so we have to undo
    its work in some places). If anyone else sees this, let me know - - it
    may just be an quirk on my machine (unlikely). Testing with the gcc-
    2.95.2 installation always works.

-   Windows 2

    If you run the tests from PythonWin or some other GUI tool, you'll
    get a ton of DOS windows popping up periodically as ``weave`` spawns the
    compiler multiple times. Very annoying. Anyone know how to fix this?

-   wxPython

    wxPython tests are not enabled by default because importing wxPython
    on a Unix machine without access to a X-term will cause the program to
    exit. Anyone know of a safe way to detect whether wxPython can be
    imported and whether a display exists on a machine?

============
 Benchmarks
============

This section has not been updated from old scipy weave and Numeric....

This section has a few benchmarks  -- thats all people want to see anyway
right? These are mostly taken from running files in the ``weave/example``
directory and also from the test scripts. Without more information about what
the test actually do, their value is limited. Still, their here for the
curious. Look at the example scripts for more specifics about what problem
was actually solved by each run. These examples are run under windows 2000
using Microsoft Visual C++ and python2.1 on a 850 MHz PIII laptop with 320 MB
of RAM. Speed up is the improvement (degredation) factor of ``weave``
compared to conventional Python functions. ``The blitz()`` comparisons are
shown compared to NumPy.

inline and ext_tools

Algorithm

Speed up

binary search   1.50
fibonacci (recursive)  82.10
fibonacci (loop)   9.17
return None   0.14
map   1.20
dictionary sort   2.54
vector quantization  37.40

blitz -- double precision

Algorithm

Speed up

a = b + c 512x512   3.05
a = b + c + d 512x512   4.59
5 pt avg. filter, 2D Image 512x512   9.01
Electromagnetics (FDTD) 100x100x100   8.61

The benchmarks shown ``blitz`` in the best possible light. NumPy (at least on
my machine) is significantly worse for double precision than it is for single
precision calculations. If your interested in single precision results, you
can pretty much divide the double precision speed up by 3 and you'll be
close.


========
 Inline
========

``inline()`` compiles and executes C/C++ code on the fly. Variables in the
local and global Python scope are also available in the C/C++ code. Values
are passed to the C/C++ code by assignment much like variables are passed
into a standard Python function. Values are returned from the C/C++ code
through a special argument called return_val. Also, the contents of mutable
objects can be changed within the C/C++ code and the changes remain after the
C code exits and returns to Python. (more on this later)

Here's a trivial ``printf`` example using ``inline()``::

        >>> import weave
        >>> a  = 1
        >>> weave.inline('printf("%d\\n",a);',['a'])
        1

In this, its most basic form, ``inline(c_code, var_list)`` requires two
arguments. ``c_code`` is a string of valid C/C++ code. ``var_list`` is a list
of variable names that are passed from Python into C/C++. Here we have a
simple ``printf`` statement that writes the Python variable ``a`` to the
screen. The first time you run this, there will be a pause while the code is
written to a .cpp file, compiled into an extension module, loaded into
Python, cataloged for future use, and executed. On windows (850 MHz PIII),
this takes about 1.5 seconds when using Microsoft's C++ compiler (MSVC) and
6-12 seconds using gcc (mingw32 2.95.2). All subsequent executions of the
code will happen very quickly because the code only needs to be compiled
once. If you kill and restart the interpreter and then execute the same code
fragment again, there will be a much shorter delay in the fractions of
seconds range. This is because ``weave`` stores a catalog of all previously
compiled functions in an on disk cache. When it sees a string that has been
compiled, it loads the already compiled module and executes the appropriate
function.

.. note::
  If you try the ``printf`` example in a GUI shell such as IDLE,
  PythonWin, PyShell, etc., you're unlikely to see the output. This is because
  the C code is writing to stdout, instead of to the GUI window. This doesn't
  mean that inline doesn't work in these environments -- it only means that
  standard out in C is not the same as the standard out for Python in these
  cases. Non input/output functions will work as expected.

Although effort has been made to reduce the overhead associated with calling
inline, it is still less efficient for simple code snippets than using
equivalent Python code. The simple ``printf`` example is actually slower by
30% or so than using Python ``print`` statement. And, it is not difficult to
create code fragments that are 8-10 times slower using inline than equivalent
Python. However, for more complicated algorithms, the speed up can be worth
while -- anywhwere from 1.5- 30 times faster. Algorithms that have to
manipulate Python objects (sorting a list) usually only see a factor of 2 or
so improvement. Algorithms that are highly computational or manipulate NumPy
arrays can see much larger improvements. The examples/vq.py file shows a
factor of 30 or more improvement on the vector quantization algorithm that is
used heavily in information theory and classification problems.


More with printf
================

MSVC users will actually see a bit of compiler output that distutils does not
supress the first time the code executes::

        >>> weave.inline(r'printf("%d\n",a);',['a'])
        sc_e013937dbc8c647ac62438874e5795131.cpp
           Creating library C:\DOCUME~1\eric\LOCALS~1\Temp\python21_compiled\temp
           \Release\sc_e013937dbc8c647ac62438874e5795131.lib and
           object C:\DOCUME~1\eric\LOCALS~1\Temp\python21_compiled\temp\Release\sc_e013937dbc8c647ac62438874e5795131.exp
        1

Nothing bad is happening, its just a bit annoying. * Anyone know how to turn
this off?*

This example also demonstrates using 'raw strings'. The ``r`` preceeding the
code string in the last example denotes that this is a 'raw string'. In raw
strings, the backslash character is not interpreted as an escape character,
and so it isn't necessary to use a double backslash to indicate that the '\n'
is meant to be interpreted in the C ``printf`` statement instead of by
Python. If your C code contains a lot of strings and control characters, raw
strings might make things easier. Most of the time, however, standard strings
work just as well.

The ``printf`` statement in these examples is formatted to print out
integers. What happens if ``a`` is a string? ``inline`` will happily, compile
a new version of the code to accept strings as input, and execute the code.
The result?

::

        >>> a = 'string'
        >>> weave.inline(r'printf("%d\n",a);',['a'])
        32956972


In this case, the result is non-sensical, but also non-fatal. In other
situations, it might produce a compile time error because ``a`` is required
to be an integer at some point in the code, or it could produce a
segmentation fault. Its possible to protect against passing ``inline``
arguments of the wrong data type by using asserts in Python.

::

         >>> a = 'string'
         >>> def protected_printf(a):
         ...     assert(type(a) == type(1))
         ...     weave.inline(r'printf("%d\n",a);',['a'])
         >>> protected_printf(1)
          1
         >>> protected_printf('string')
         AssertError...


For printing strings, the format statement needs to be changed. Also, weave
doesn't convert strings to char*. Instead it uses CXX Py::String type, so you
have to do a little more work. Here we convert it to a C++ std::string and
then ask cor the char* version.

::

         >>> a = 'string'
         >>> weave.inline(r'printf("%s\n",std::string(a).c_str());',['a'])
         string

.. admonition:: XXX

  This is a little convoluted. Perhaps strings should convert to ``std::string``
  objects instead of CXX objects. Or maybe to ``char*``.

As in this case, C/C++ code fragments often have to change to accept
different types. For the given printing task, however, C++ streams provide a
way of a single statement that works for integers and strings. By default,
the stream objects live in the std (standard) namespace and thus require the
use of ``std::``.

::

        >>> weave.inline('std::cout << a << std::endl;',['a'])
        1
        >>> a = 'string'
        >>> weave.inline('std::cout << a << std::endl;',['a'])
        string


Examples using ``printf`` and ``cout`` are included in
examples/print_example.py.


More examples
=============

This section shows several more advanced uses of ``inline``. It includes a
few algorithms from the `Python Cookbook`_ that have been re-written in
inline C to improve speed as well as a couple examples using NumPy and
wxPython.

Binary search
-------------

Lets look at the example of searching a sorted list of integers for a value.
For inspiration, we'll use Kalle Svensson's `binary_search()`_ algorithm
from the Python Cookbook. His recipe follows::

        def binary_search(seq, t):
            min = 0; max = len(seq) - 1
            while 1:
                if max < min:
                    return -1
                m = (min  + max)  / 2
                if seq[m] < t:
                    min = m  + 1
                elif seq[m] > t:
                    max = m  - 1
                else:
                    return m


This Python version works for arbitrary Python data types. The C version
below is specialized to handle integer values. There is a little type
checking done in Python to assure that we're working with the correct data
types before heading into C. The variables ``seq`` and ``t`` don't need to be
declared beacuse ``weave`` handles converting and declaring them in the C
code. All other temporary variables such as ``min, max``, etc. must be
declared -- it is C after all. Here's the new mixed Python/C function::

        def c_int_binary_search(seq,t):
            # do a little type checking in Python
            assert(type(t) == type(1))
            assert(type(seq) == type([]))

            # now the C code
            code = """
                   #line 29 "binary_search.py"
                   int val, m, min = 0;
                   int max = seq.length() - 1;
                   PyObject *py_val;
                   for(;;)
                   {
                       if (max < min  )
                       {
                           return_val =  Py::new_reference_to(Py::Int(-1));
                           break;
                       }
                       m =  (min + max) /2;
                       val = py_to_int(PyList_GetItem(seq.ptr(),m),"val");
                       if (val  < t)
                           min = m  + 1;
                       else if (val >  t)
                           max = m - 1;
                       else
                       {
                           return_val = Py::new_reference_to(Py::Int(m));
                           break;
                       }
                   }
                   """
            return inline(code,['seq','t'])

We have two variables ``seq`` and ``t`` passed in. ``t`` is guaranteed (by
the ``assert``) to be an integer. Python integers are converted to C int
types in the transition from Python to C. ``seq`` is a Python list. By
default, it is translated to a CXX list object. Full documentation for the
CXX library can be found at its `website`_. The basics are that the CXX
provides C++ class equivalents for Python objects that simplify, or at least
object orientify, working with Python objects in C/C++. For example,
``seq.length()`` returns the length of the list. A little more about CXX and
its class methods, etc. is in the ** type conversions ** section.

.. note::
  CXX uses templates and therefore may be a little less portable than
  another alternative by Gordan McMillan called SCXX which was
  inspired by CXX. It doesn't use templates so it should compile
  faster and be more portable. SCXX has a few less features, but it
  appears to me that it would mesh with the needs of weave quite well.
  Hopefully xxx_spec files will be written for SCXX in the future, and
  we'll be able to compare on a more empirical basis. Both sets of
  spec files will probably stick around, it just a question of which
  becomes the default.

Most of the algorithm above looks similar in C to the original Python code.
There are two main differences. The first is the setting of ``return_val``
instead of directly returning from the C code with a ``return`` statement.
``return_val`` is an automatically defined variable of type ``PyObject*``
that is returned from the C code back to Python. You'll have to handle
reference counting issues when setting this variable. In this example, CXX
classes and functions handle the dirty work. All CXX functions and classes
live in the namespace ``Py::``. The following code converts the integer ``m``
to a CXX ``Int()`` object and then to a ``PyObject*`` with an incremented
reference count using ``Py::new_reference_to()``.

::
        return_val = Py::new_reference_to(Py::Int(m));


The second big differences shows up in the retrieval of integer values from
the Python list. The simple Python ``seq[i]`` call balloons into a C Python
API call to grab the value out of the list and then a separate call to
``py_to_int()`` that converts the PyObject* to an integer. ``py_to_int()``
includes both a NULL cheack and a ``PyInt_Check()`` call as well as the
conversion call. If either of the checks fail, an exception is raised. The
entire C++ code block is executed with in a ``try/catch`` block that handles
exceptions much like Python does. This removes the need for most error
checking code.

It is worth note that CXX lists do have indexing operators that result in
code that looks much like Python. However, the overhead in using them appears
to be relatively high, so the standard Python API was used on the
``seq.ptr()`` which is the underlying ``PyObject*`` of the List object.

The ``#line`` directive that is the first line of the C code block isn't
necessary, but it's nice for debugging. If the compilation fails because of
the syntax error in the code, the error will be reported as an error in the
Python file "binary_search.py" with an offset from the given line number (29
here).

So what was all our effort worth in terms of efficiency? Well not a lot in
this case. The examples/binary_search.py file runs both Python and C versions
of the functions As well as using the standard ``bisect`` module. If we run
it on a 1 million element list and run the search 3000 times (for 0- 2999),
here are the results we get::

        C:\home\ej\wrk\scipy\weave\examples> python binary_search.py
        Binary search for 3000 items in 1000000 length list of integers:
        speed in python: 0.159999966621
        speed of bisect: 0.121000051498
        speed up: 1.32
        speed in c: 0.110000014305
        speed up: 1.45
        speed in c(no asserts): 0.0900000333786
        speed up: 1.78


So, we get roughly a 50-75% improvement depending on whether we use the
Python asserts in our C version. If we move down to searching a 10000 element
list, the advantage evaporates. Even smaller lists might result in the Python
version being faster. I'd like to say that moving to NumPy lists (and getting
rid of the GetItem() call) offers a substantial speed up, but my preliminary
efforts didn't produce one. I think the log(N) algorithm is to blame. Because
the algorithm is nice, there just isn't much time spent computing things, so
moving to C isn't that big of a win. If there are ways to reduce conversion
overhead of values, this may improve the C/Python speed up. Anyone have other
explanations or faster code, please let me know.


Dictionary Sort
---------------

The demo in examples/dict_sort.py is another example from the Python
CookBook. `This submission`_, by Alex Martelli, demonstrates how to return
the values from a dictionary sorted by their keys:

::
        def sortedDictValues3(adict):
            keys = adict.keys()
            keys.sort()
            return map(adict.get, keys)


Alex provides 3 algorithms and this is the 3rd and fastest of the set. The C
version of this same algorithm follows::

        def c_sort(adict):
            assert(type(adict) == type({}))
            code = """
            #line 21 "dict_sort.py"
            Py::List keys = adict.keys();
            Py::List items(keys.length()); keys.sort();
            PyObject* item = NULL;
            for(int i = 0;  i < keys.length();i++)
            {
                item = PyList_GET_ITEM(keys.ptr(),i);
                item = PyDict_GetItem(adict.ptr(),item);
                Py_XINCREF(item);
                PyList_SetItem(items.ptr(),i,item);
            }
            return_val = Py::new_reference_to(items);
            """
            return inline_tools.inline(code,['adict'],verbose=1)


Like the original Python function, the C++ version can handle any Python
dictionary regardless of the key/value pair types. It uses CXX objects for
the most part to declare python types in C++, but uses Python API calls to
manipulate their contents. Again, this choice is made for speed. The C++
version, while more complicated, is about a factor of 2 faster than Python.

::

        C:\home\ej\wrk\scipy\weave\examples> python dict_sort.py
        Dict sort of 1000 items for 300 iterations:
         speed in python: 0.319999933243
        [0, 1, 2, 3, 4]
         speed in c: 0.151000022888
         speed up: 2.12
        [0, 1, 2, 3, 4]



NumPy -- cast/copy/transpose
----------------------------

CastCopyTranspose is a function called quite heavily by Linear Algebra
routines in the NumPy library. Its needed in part because of the row-major
memory layout of multi-demensional Python (and C) arrays vs. the col-major
order of the underlying Fortran algorithms. For small matrices (say 100x100
or less), a significant portion of the common routines such as LU
decompisition or singular value decompostion are spent in this setup routine.
This shouldn't happen. Here is the Python version of the function using
standard NumPy operations.

::

        def _castCopyAndTranspose(type, array):
            if a.typecode() == type:
                cast_array = copy.copy(NumPy.transpose(a))
            else:
                cast_array = copy.copy(NumPy.transpose(a).astype(type))
            return cast_array


And the following is a inline C version of the same function::

        from weave.blitz_tools import blitz_type_factories
        from weave import scalar_spec
        from weave import inline
        def _cast_copy_transpose(type,a_2d):
            assert(len(shape(a_2d)) == 2)
            new_array = zeros(shape(a_2d),type)
            NumPy_type = scalar_spec.NumPy_to_blitz_type_mapping[type]
            code = \
            """
            for(int i = 0;i < _Na_2d[0]; i++)
                for(int j = 0;  j < _Na_2d[1]; j++)
                    new_array(i,j) = (%s) a_2d(j,i);
            """ % NumPy_type
            inline(code,['new_array','a_2d'],
                   type_factories = blitz_type_factories,compiler='gcc')
            return new_array


This example uses blitz++ arrays instead of the standard representation of
NumPy arrays so that indexing is simplier to write. This is accomplished by
passing in the blitz++ "type factories" to override the standard Python to
C++ type conversions. Blitz++ arrays allow you to write clean, fast code, but
they also are sloooow to compile (20 seconds or more for this snippet). This
is why they aren't the default type used for Numeric arrays (and also because
most compilers can't compile blitz arrays...). ``inline()`` is also forced to
use 'gcc' as the compiler because the default compiler on Windows (MSVC) will
not compile blitz code. ('gcc' I think will use the standard compiler on
Unix machine instead of explicitly forcing gcc (check this)) Comparisons of
the Python vs inline C++ code show a factor of 3 speed up. Also shown are the
results of an "inplace" transpose routine that can be used if the output of
the linear algebra routine can overwrite the original matrix (this is often
appropriate). This provides another factor of 2 improvement.

::

        #C:\home\ej\wrk\scipy\weave\examples> python cast_copy_transpose.py
        # Cast/Copy/Transposing (150,150)array 1 times
        #  speed in python: 0.870999932289
        #  speed in c: 0.25
        #  speed up: 3.48
        #  inplace transpose c: 0.129999995232
        #  speed up: 6.70

wxPython
--------

``inline`` knows how to handle wxPython objects. Thats nice in and of itself,
but it also demonstrates that the type conversion mechanism is reasonably
flexible. Chances are, it won't take a ton of effort to support special types
you might have. The examples/wx_example.py borrows the scrolled window
example from the wxPython demo, accept that it mixes inline C code in the
middle of the drawing function.

::

        def DoDrawing(self, dc):

            red = wxNamedColour("RED");
            blue = wxNamedColour("BLUE");
            grey_brush = wxLIGHT_GREY_BRUSH;
            code = \
            """
            #line 108 "wx_example.py"
            dc->BeginDrawing();
            dc->SetPen(wxPen(*red,4,wxSOLID));
            dc->DrawRectangle(5,5,50,50);
            dc->SetBrush(*grey_brush);
            dc->SetPen(wxPen(*blue,4,wxSOLID));
            dc->DrawRectangle(15, 15, 50, 50);
            """
            inline(code,['dc','red','blue','grey_brush'])

            dc.SetFont(wxFont(14, wxSWISS, wxNORMAL, wxNORMAL))
            dc.SetTextForeground(wxColour(0xFF, 0x20, 0xFF))
            te = dc.GetTextExtent("Hello World")
            dc.DrawText("Hello World", 60, 65)

            dc.SetPen(wxPen(wxNamedColour('VIOLET'), 4))
            dc.DrawLine(5, 65+te[1], 60+te[0], 65+te[1])
            ...

Here, some of the Python calls to wx objects were just converted to C++
calls. There isn't any benefit, it just demonstrates the capabilities. You
might want to use this if you have a computationally intensive loop in your
drawing code that you want to speed up. On windows, you'll have to use the
MSVC compiler if you use the standard wxPython DLLs distributed by Robin
Dunn. Thats because MSVC and gcc, while binary compatible in C, are not
binary compatible for C++. In fact, its probably best, no matter what
platform you're on, to specify that ``inline`` use the same compiler that was
used to build wxPython to be on the safe side. There isn't currently a way to
learn this info from the library -- you just have to know. Also, at least on
the windows platform, you'll need to install the wxWindows libraries and link
to them. I think there is a way around this, but I haven't found it yet -- I
get some linking errors dealing with wxString. One final note. You'll
probably have to tweak weave/wx_spec.py or weave/wx_info.py for your
machine's configuration to point at the correct directories etc. There. That
should sufficiently scare people into not even looking at this... :)

Keyword Option
==============

The basic definition of the ``inline()`` function has a slew of optional
variables. It also takes keyword arguments that are passed to ``distutils``
as compiler options. The following is a formatted cut/paste of the argument
section of ``inline's`` doc-string. It explains all of the variables. Some
examples using various options will follow.

::

        def inline(code,arg_names,local_dict = None, global_dict = None,
                   force = 0,
                   compiler='',
                   verbose = 0,
                   support_code = None,
                   customize=None,
                   type_factories = None,
                   auto_downcast=1,
                   **kw):


``inline`` has quite a few options as listed below. Also, the keyword
arguments for distutils extension modules are accepted to specify extra
information needed for compiling.

Inline Arguments
================

code  string. A string of valid C++ code. It should not specify a return
statement. Instead it should assign results that need to be returned to
Python in the return_val.  arg_names  list of strings. A list of Python
variable names that should be transferred from Python into the C/C++ code.
local_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the local scope for the C/C++ code. If local_dict is
not specified the local dictionary of the calling function is used.
global_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the global scope for the C/C++ code. If global_dict is
not specified the global dictionary of the calling function is used.  force
optional. 0 or 1. default 0. If 1, the C++ code is compiled every time inline
is called. This is really only useful for debugging, and probably only useful
if you're editing support_code a lot.  compiler  optional. string. The name
of compiler to use when compiling. On windows, it understands 'msvc' and
'gcc' as well as all the compiler names understood by distutils. On Unix,
it'll only understand the values understoof by distutils. (I should add 'gcc'
though to this).

On windows, the compiler defaults to the Microsoft C++ compiler. If this
isn't available, it looks for mingw32 (the gcc compiler).

On Unix, it'll probably use the same compiler that was used when compiling
Python. Cygwin's behavior should be similar.

verbose  optional. 0,1, or 2. defualt 0. Speficies how much much
information is printed during the compile phase of inlining code. 0 is silent
(except on windows with msvc where it still prints some garbage). 1 informs
you when compiling starts, finishes, and how long it took. 2 prints out the
command lines for the compilation process and can be useful if you're having
problems getting code to work. Its handy for finding the name of the .cpp
file if you need to examine it. verbose has no affect if the compilation
isn't necessary.  support_code  optional. string. A string of valid C++ code
declaring extra code that might be needed by your compiled function. This
could be declarations of functions, classes, or structures.  customize
optional. base_info.custom_info object. An alternative way to specifiy
support_code, headers, etc. needed by the function see the weave.base_info
module for more details. (not sure this'll be used much).  type_factories
optional. list of type specification factories. These guys are what convert
Python data types to C/C++ data types. If you'd like to use a different set
of type conversions than the default, specify them here. Look in the type
conversions section of the main documentation for examples.  auto_downcast
optional. 0 or 1. default 1. This only affects functions that have Numeric
arrays as input variables. Setting this to 1 will cause all floating point
values to be cast as float instead of double if all the NumPy arrays are of
type float. If even one of the arrays has type double or double complex, all
variables maintain there standard types.


Distutils keywords
==================

``inline()`` also accepts a number of ``distutils`` keywords for
controlling how the code is compiled. The following descriptions have been
copied from Greg Ward's ``distutils.extension.Extension`` class doc- strings
for convenience:  sources  [string] list of source filenames, relative to the
distribution root (where the setup script lives), in Unix form (slash-
separated) for portability. Source files may be C, C++, SWIG (.i), platform-
specific resource files, or whatever else is recognized by the "build_ext"
command as source for a Python extension. Note: The module_path file is
always appended to the front of this list  include_dirs  [string] list of
directories to search for C/C++ header files (in Unix form for portability)
define_macros  [(name : string, value : string|None)] list of macros to
define; each macro is defined using a 2-tuple, where 'value' is either the
string to define it to or None to define it without a particular value
(equivalent of "#define FOO" in source or -DFOO on Unix C compiler command
line)  undef_macros  [string] list of macros to undefine explicitly
library_dirs  [string] list of directories to search for C/C++ libraries at
link time  libraries  [string] list of library names (not filenames or paths)
to link against  runtime_library_dirs  [string] list of directories to search
for C/C++ libraries at run time (for shared extensions, this is when the
extension is loaded)  extra_objects  [string] list of extra files to link
with (eg. object files not implied by 'sources', static library that must be
explicitly specified, binary resource files, etc.)  extra_compile_args
[string] any extra platform- and compiler-specific information to use when
compiling the source files in 'sources'. For platforms and compilers where
"command line" makes sense, this is typically a list of command-line
arguments, but for other platforms it could be anything.  extra_link_args
[string] any extra platform- and compiler-specific information to use when
linking object files together to create the extension (or to create a new
static Python inte are 8-ng code converts the integer ``m``
to a CXX ``Int()`` object and then to a ``PyObject*`` with an incremented
reference count using ``Py::new_reference_to()``.

::
        return_val = Py::new_reference_to(Py::Int(m));


The second big differences shows up in the retrieval of integer values from
the Python list. The simple Python ``seq[i]`` call balloons into a C Python
API call to grab the value out of the list and then a separate call to
``py_to_int()`` that converts the PyObject* to an integer. ``py_to_int()``
includes both a NULL cheack and a ``PyInt_Check()`` call as well as the
conversion call. If either of the checks fail, an exception is raised. The
entire C++ code block is executed with in a ``try/catch`` block that handles
exceptions much like Python does. This removes the need for most error
checking code.

It is worth note that CXX lists do have indexing operators that result in
code that looks much like Python. However, the overhead in using them appears
to be relatively high, so the standard Python API was used on the
``seq.ptr()`` which is the underlying ``PyObject*`` of the List object.

The ``#line`` directive that is the first line of the C code block isn't
necessary, but it's nice for debugging. If the compilation fails because of
the syntax error in the code, the error will be reported as an error in the
Python file "binary_search.py" with an offset from the given line number (29
here).

So what was all our effort worth in terms of efficiency? Well not a lot in
this case. The examples/binary_search.py file runs both Python and C versions
of the functions As well as using the standard ``bisect`` module. If we run
it on a 1 million element list and run the search 3000 times (for 0- 2999),
here are the results we get::

        C:\home\ej\wrk\scipy\weave\examples> python binary_search.py
        Binary search for 3000 items in 1000000 length list of integers:
        speed in python: 0.159999966621
        speed of bisect: 0.121000051498
        speed up: 1.32
        speed in c: 0.110000014305
        speed up: 1.45
        speed in c(no asserts): 0.0900000333786
        speed up: 1.78


So, we get roughly a 50-75% improvement depending on whether we use the
Python asserts in our C version. If we move down to searching a 10000 element
list, the advantage evaporates. Even smaller lists might result in the Python
version being faster. I'd like to say that moving to NumPy lists (and getting
rid of the GetItem() call) offers a substantial speed up, but my preliminary
efforts didn't produce one. I think the log(N) algorithm is to blame. Because
the algorithm is nice, there just isn't much time spent computing things, so
moving to C isn't that big of a win. If there are ways to reduce conversion
overhead of values, this may improve the C/Python speed up. Anyone have other
explanations or faster code, please let me know.


Dictionary Sort
---------------

The demo in examples/dict_sort.py is another example from the Python
CookBook. `This submission`_, by Alex Martelli, demonstrates how to return
the values from a dictionary sorted by their keys:

::
        def sortedDictValues3(adict):
            keys = adict.keys()
            keys.sort()
            return map(adict.get, keys)


Alex provides 3 algorithms and this is the 3rd and fastest of the set. The C
version of this same algorithm follows::

        def c_sort(adict):
            assert(type(adict) == type({}))
            code = """
            #line 21 "dict_sort.py"
            Py::List keys = adict.keys();
            Py::List items(keys.length()); keys.sort();
            PyObject* item = NULL;
            for(int i = 0;  i < keys.length();i++)
            {
                item = PyList_GET_ITEM(keys.ptr(),i);
                item = PyDict_GetItem(adict.ptr(),item);
                Py_XINCREF(item);
                PyList_SetItem(items.ptr(),i,item);
            }
            return_val = Py::new_reference_to(items);
            """
            return inline_tools.inline(code,['adict'],verbose=1)


Like the original Python function, the C++ version can handle any Python
dictionary regardless of the key/value pair types. It uses CXX objects for
the most part to declare python types in C++, but uses Python API calls to
manipulate their contents. Again, this choice is made for speed. The C++
version, while more complicated, is about a factor of 2 faster than Python.

::

        C:\home\ej\wrk\scipy\weave\examples> python dict_sort.py
        Dict sort of 1000 items for 300 iterations:
         speed in python: 0.319999933243
        [0, 1, 2, 3, 4]
         speed in c: 0.151000022888
         speed up: 2.12
        [0, 1, 2, 3, 4]



NumPy -- cast/copy/transpose
----------------------------

CastCopyTranspose is a function called quite heavily by Linear Algebra
routines in the NumPy library. Its needed in part because of the row-major
memory layout of multi-demensional Python (and C) arrays vs. the col-major
order of the underlying Fortran algorithms. For small matrices (say 100x100
or less), a significant portion of the common routines such as LU
decompisition or singular value decompostion are spent in this setup routine.
This shouldn't happen. Here is the Python version of the function using
standard NumPy operations.

::

        def _castCopyAndTranspose(type, array):
            if a.typecode() == type:
                cast_array = copy.copy(NumPy.transpose(a))
            else:
                cast_array = copy.copy(NumPy.transpose(a).astype(type))
            return cast_array


And the following is a inline C version of the same function::

        from weave.blitz_tools import blitz_type_factories
        from weave import scalar_spec
        from weave import inline
        def _cast_copy_transpose(type,a_2d):
            assert(len(shape(a_2d)) == 2)
            new_array = zeros(shape(a_2d),type)
            NumPy_type = scalar_spec.NumPy_to_blitz_type_mapping[type]
            code = \
            """
            for(int i = 0;i < _Na_2d[0]; i++)
                for(int j = 0;  j < _Na_2d[1]; j++)
                    new_array(i,j) = (%s) a_2d(j,i);
            """ % NumPy_type
            inline(code,['new_array','a_2d'],
                   type_factories = blitz_type_factories,compiler='gcc')
            return new_array


This example uses blitz++ arrays instead of the standard representation of
NumPy arrays so that indexing is simplier to write. This is accomplished by
passing in the blitz++ "type factories" to override the standard Python to
C++ type conversions. Blitz++ arrays allow you to write clean, fast code, but
they also are sloooow to compile (20 seconds or more for this snippet). This
is why they aren't the default type used for Numeric arrays (and also because
most compilers can't compile blitz arrays...). ``inline()`` is also forced to
use 'gcc' as the compiler because the default compiler on Windows (MSVC) will
not compile blitz code. ('gcc' I think will use the standard compiler on
Unix machine instead of explicitly forcing gcc (check this)) Comparisons of
the Python vs inline C++ code show a factor of 3 speed up. Also shown are the
results of an "inplace" transpose routine that can be used if the output of
the linear algebra routine can overwrite the original matrix (this is often
appropriate). This provides another factor of 2 improvement.

::

        #C:\home\ej\wrk\scipy\weave\examples> python cast_copy_transpose.py
        # Cast/Copy/Transposing (150,150)array 1 times
        #  speed in python: 0.870999932289
        #  speed in c: 0.25
        #  speed up: 3.48
        #  inplace transpose c: 0.129999995232
        #  speed up: 6.70

wxPython
--------

``inline`` knows how to handle wxPython objects. Thats nice in and of itself,
but it also demonstrates that the type conversion mechanism is reasonably
flexible. Chances are, it won't take a ton of effort to support special types
you might have. The examples/wx_example.py borrows the scrolled window
example from the wxPython demo, accept that it mixes inline C code in the
middle of the drawing function.

::

        def DoDrawing(self, dc):

            red = wxNamedColour("RED");
            blue = wxNamedColour("BLUE");
            grey_brush = wxLIGHT_GREY_BRUSH;
            code = \
            """
            #line 108 "wx_example.py"
            dc->BeginDrawing();
            dc->SetPen(wxPen(*red,4,wxSOLID));
            dc->DrawRectangle(5,5,50,50);
            dc->SetBrush(*grey_brush);
            dc->SetPen(wxPen(*blue,4,wxSOLID));
            dc->DrawRectangle(15, 15, 50, 50);
            """
            inline(code,['dc','red','blue','grey_brush'])

            dc.SetFont(wxFont(14, wxSWISS, wxNORMAL, wxNORMAL))
            dc.SetTextForeground(wxColour(0xFF, 0x20, 0xFF))
            te = dc.GetTextExtent("Hello World")
            dc.DrawText("Hello World", 60, 65)

            dc.SetPen(wxPen(wxNamedColour('VIOLET'), 4))
            dc.DrawLine(5, 65+te[1], 60+te[0], 65+te[1])
            ...

Here, some of the Python calls to wx objects were just converted to C++
calls. There isn't any benefit, it just demonstrates the capabilities. You
might want to use this if you have a computationally intensive loop in your
drawing code that you want to speed up. On windows, you'll have to use the
MSVC compiler if you use the standard wxPython DLLs distributed by Robin
Dunn. Thats because MSVC and gcc, while binary compatible in C, are not
binary compatible for C++. In fact, its probably best, no matter what
platform you're on, to specify that ``inline`` use the same compiler that was
used to build wxPython to be on the safe side. There isn't currently a way to
learn this info from the library -- you just have to know. Also, at least on
the windows platform, you'll need to install the wxWindows libraries and link
to them. I think there is a way around this, but I haven't found it yet -- I
get some linking errors dealing with wxString. One final note. You'll
probably have to tweak weave/wx_spec.py or weave/wx_info.py for your
machine's configuration to point at the correct directories etc. There. That
should sufficiently scare people into not even looking at this... :)

Keyword Option
==============

The basic definition of the ``inline()`` function has a slew of optional
variables. It also takes keyword arguments that are passed to ``distutils``
as compiler options. The following is a formatted cut/paste of the argument
section of ``inline's`` doc-string. It explains all of the variables. Some
examples using various options will follow.

::

        def inline(code,arg_names,local_dict = None, global_dict = None,
                   force = 0,
                   compiler='',
                   verbose = 0,
                   support_code = None,
                   customize=None,
                   type_factories = None,
                   auto_downcast=1,
                   **kw):


``inline`` has quite a few options as listed below. Also, the keyword
arguments for distutils extension modules are accepted to specify extra
information needed for compiling.

Inline Arguments
================

code  string. A string of valid C++ code. It should not specify a return
statement. Instead it should assign results that need to be returned to
Python in the return_val.  arg_names  list of strings. A list of Python
variable names that should be transferred from Python into the C/C++ code.
local_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the local scope for the C/C++ code. If local_dict is
not specified the local dictionary of the calling function is used.
global_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the global scope for the C/C++ code. If global_dict is
not specified the global dictionary of the calling function is used.  force
optional. 0 or 1. default 0. If 1, the C++ code is compiled every time inline
is called. This is really only useful for debugging, and probably only useful
if you're editing support_code a lot.  compiler  optional. string. The name
of compiler to use when compiling. On windows, it understands 'msvc' and
'gcc' as well as all the compiler names understood by distutils. On Unix,
it'll only understand the values understoof by distutils. (I should add 'gcc'
though to this).

On windows, the compiler defaults to the Microsoft C++ compiler. If this
isn't available, it looks for mingw32 (the gcc compiler).

On Unix, it'll probably use the same compiler that was used when compiling
Python. Cygwin's behavior should be similar.

verbose  optional. 0,1, or 2. defualt 0. Speficies how much much
information is printed during the compile phase of inlining code. 0 is silent
(except on windows with msvc where it still prints some garbage). 1 informs
you when compiling starts, finishes, and how long it took. 2 prints out the
command lines for the compilation process and can be useful if you're having
problems getting code to work. Its handy for finding the name of the .cpp
file if you need to examine it. verbose has no affect if the compilation
isn't necessary.  support_code  optional. string. A string of valid C++ code
declaring extra code that might be needed by your compiled function. This
could be declarations of functions, classes, or structures.  customize
optional. base_info.custom_info object. An alternative way to specifiy
support_code, headers, etc. needed by the function see the weave.base_info
module for more details. (not sure this'll be used much).  type_factories
optional. list of type specification factories. These guys are what convert
Python data types to C/C++ data types. If you'd like to use a different set
of type conversions than the default, specify them here. Look in the type
conversions section of the main documentation for examples.  auto_downcast
optional. 0 or 1. default 1. This only affects functions that have Numeric
arrays as input variables. Setting this to 1 will cause all floating point
values to be cast as float instead of double if all the NumPy arrays are of
type float. If even one of the arrays has type double or double complex, all
variables maintain there standard types.


Distutils keywords
==================

``inline()`` also accepts a number of ``distutils`` keywords for
controlling how the code is compiled. The following descriptions have been
copied from Greg Ward's ``distutils.extension.Extension`` class doc- strings
for convenience:  sources  [string] list of source filenames, relative to the
distribution root (where the setup script lives), in Unix form (slash-
separated) for portability. Source files may be C, C++, SWIG (.i), platform-
specific resource files, or whatever else is recognized by the "build_ext"
command as source for a Python extension. Note: The module_path file is
always appended to the front of this list  include_dirs  [string] list of
directories to search for C/C++ header files (in Unix form for portability)
define_macros  [(name : string, value : string|None)] list of macros to
define; each macro is defined using a 2-tuple, where 'value' is either the
string to define it to or None to define it without a particular value
(equivalent of "#define FOO" in source or -DFOO on Unix C compiler command
line)  undef_macros  [string] list of macros to undefine explicitly
library_dirs  [string] list of directories to search for C/C++ libraries at
link time  libraries  [string] list of library names (not filenames or paths)
to link against  runtime_library_dirs  [string] list of directories to search
for C/C++ libraries at run time (for shared extensions, this is when the
extension is loaded)  extra_objects  [string] list of extra files to link
with (eg. object files not implied by 'sources', static library that must be
explicitly specified, binary resource files, etc.)  extra_compile_args
[string] any extra platform- and compiler-specific information to use when
compiling the source files in 'sources'. For platforms and compilers where
"command line" makes sense, this is typically a list of command-line
arguments, but for other platforms it could be anything.  extra_link_args
[string] any extra platform- and compiler-specific information to use when
linking object files together to create the extension (or to create a new
static Python inte are 8-ng code converts the integer ``m``
to a CXX ``Int()`` object and then to a ``PyObject*`` with an incremented
reference count using ``Py::new_reference_to()``.

::
        return_val = Py::new_reference_to(Py::Int(m));


The second big differences shows up in the retrieval of integer values from
the Python list. The simple Python ``seq[i]`` call balloons into a C Python
API call to grab the value out of the list and then a separate call to
``py_to_int()`` that converts the PyObject* to an integer. ``py_to_int()``
includes both a NULL cheack and a ``PyInt_Check()`` call as well as the
conversion call. If either of the checks fail, an exception is raised. The
entire C++ code block is executed with in a ``try/catch`` block that handles
exceptions much like Python does. This removes the need for most error
checking code.

It is worth note that CXX lists do have indexing operators that result in
code that looks much like Python. However, the overhead in using them appears
to be relatively high, so the standard Python API was used on the
``seq.ptr()`` which is the underlying ``PyObject*`` of the List object.

The ``#line`` directive that is the first line of the C code block isn't
necessary, but it's nice for debugging. If the compilation fails because of
the syntax error in the code, the error will be reported as an error in the
Python file "binary_search.py" with an offset from the given line number (29
here).

So what was all our effort worth in terms of efficiency? Well not a lot in
this case. The examples/binary_search.py file runs both Python and C versions
of the functions As well as using the standard ``bisect`` module. If we run
it on a 1 million element list and run the search 3000 times (for 0- 2999),
here are the results we get::

        C:\home\ej\wrk\scipy\weave\examples> python binary_search.py
        Binary search for 3000 items in 1000000 length list of integers:
        speed in python: 0.159999966621
        speed of bisect: 0.121000051498
        speed up: 1.32
        speed in c: 0.110000014305
        speed up: 1.45
        speed in c(no asserts): 0.0900000333786
        speed up: 1.78


So, we get roughly a 50-75% improvement depending on whether we use the
Python asserts in our C version. If we move down to searching a 10000 element
list, the advantage evaporates. Even smaller lists might result in the Python
version being faster. I'd like to say that moving to NumPy lists (and getting
rid of the GetItem() call) offers a substantial speed up, but my preliminary
efforts didn't produce one. I think the log(N) algorithm is to blame. Because
the algorithm is nice, there just isn't much time spent computing things, so
moving to C isn't that big of a win. If there are ways to reduce conversion
overhead of values, this may improve the C/Python speed up. Anyone have other
explanations or faster code, please let me know.


Dictionary Sort
---------------

The demo in examples/dict_sort.py is another example from the Python
CookBook. `This submission`_, by Alex Martelli, demonstrates how to return
the values from a dictionary sorted by their keys:

::
        def sortedDictValues3(adict):
            keys = adict.keys()
            keys.sort()
            return map(adict.get, keys)


Alex provides 3 algorithms and this is the 3rd and fastest of the set. The C
version of this same algorithm follows::

        def c_sort(adict):
            assert(type(adict) == type({}))
            code = """
            #line 21 "dict_sort.py"
            Py::List keys = adict.keys();
            Py::List items(keys.length()); keys.sort();
            PyObject* item = NULL;
            for(int i = 0;  i < keys.length();i++)
            {
                item = PyList_GET_ITEM(keys.ptr(),i);
                item = PyDict_GetItem(adict.ptr(),item);
                Py_XINCREF(item);
                PyList_SetItem(items.ptr(),i,item);
            }
            return_val = Py::new_reference_to(items);
            """
            return inline_tools.inline(code,['adict'],verbose=1)


Like the original Python function, the C++ version can handle any Python
dictionary regardless of the key/value pair types. It uses CXX objects for
the most part to declare python types in C++, but uses Python API calls to
manipulate their contents. Again, this choice is made for speed. The C++
version, while more complicated, is about a factor of 2 faster than Python.

::

        C:\home\ej\wrk\scipy\weave\examples> python dict_sort.py
        Dict sort of 1000 items for 300 iterations:
         speed in python: 0.319999933243
        [0, 1, 2, 3, 4]
         speed in c: 0.151000022888
         speed up: 2.12
        [0, 1, 2, 3, 4]



NumPy -- cast/copy/transpose
----------------------------

CastCopyTranspose is a function called quite heavily by Linear Algebra
routines in the NumPy library. Its needed in part because of the row-major
memory layout of multi-demensional Python (and C) arrays vs. the col-major
order of the underlying Fortran algorithms. For small matrices (say 100x100
or less), a significant portion of the common routines such as LU
decompisition or singular value decompostion are spent in this setup routine.
This shouldn't happen. Here is the Python version of the function using
standard NumPy operations.

::

        def _castCopyAndTranspose(type, array):
            if a.typecode() == type:
                cast_array = copy.copy(NumPy.transpose(a))
            else:
                cast_array = copy.copy(NumPy.transpose(a).astype(type))
            return cast_array


And the following is a inline C version of the same function::

        from weave.blitz_tools import blitz_type_factories
        from weave import scalar_spec
        from weave import inline
        def _cast_copy_transpose(type,a_2d):
            assert(len(shape(a_2d)) == 2)
            new_array = zeros(shape(a_2d),type)
            NumPy_type = scalar_spec.NumPy_to_blitz_type_mapping[type]
            code = \
            """
            for(int i = 0;i < _Na_2d[0]; i++)
                for(int j = 0;  j < _Na_2d[1]; j++)
                    new_array(i,j) = (%s) a_2d(j,i);
            """ % NumPy_type
            inline(code,['new_array','a_2d'],
                   type_factories = blitz_type_factories,compiler='gcc')
            return new_array


This example uses blitz++ arrays instead of the standard representation of
NumPy arrays so that indexing is simplier to write. This is accomplished by
passing in the blitz++ "type factories" to override the standard Python to
C++ type conversions. Blitz++ arrays allow you to write clean, fast code, but
they also are sloooow to compile (20 seconds or more for this snippet). This
is why they aren't the default type used for Numeric arrays (and also because
most compilers can't compile blitz arrays...). ``inline()`` is also forced to
use 'gcc' as the compiler because the default compiler on Windows (MSVC) will
not compile blitz code. ('gcc' I think will use the standard compiler on
Unix machine instead of explicitly forcing gcc (check this)) Comparisons of
the Python vs inline C++ code show a factor of 3 speed up. Also shown are the
results of an "inplace" transpose routine that can be used if the output of
the linear algebra routine can overwrite the original matrix (this is often
appropriate). This provides another factor of 2 improvement.

::

        #C:\home\ej\wrk\scipy\weave\examples> python cast_copy_transpose.py
        # Cast/Copy/Transposing (150,150)array 1 times
        #  speed in python: 0.870999932289
        #  speed in c: 0.25
        #  speed up: 3.48
        #  inplace transpose c: 0.129999995232
        #  speed up: 6.70

wxPython
--------

``inline`` knows how to handle wxPython objects. Thats nice in and of itself,
but it also demonstrates that the type conversion mechanism is reasonably
flexible. Chances are, it won't take a ton of effort to support special types
you might have. The examples/wx_example.py borrows the scrolled window
example from the wxPython demo, accept that it mixes inline C code in the
middle of the drawing function.

::

        def DoDrawing(self, dc):

            red = wxNamedColour("RED");
            blue = wxNamedColour("BLUE");
            grey_brush = wxLIGHT_GREY_BRUSH;
            code = \
            """
            #line 108 "wx_example.py"
            dc->BeginDrawing();
            dc->SetPen(wxPen(*red,4,wxSOLID));
            dc->DrawRectangle(5,5,50,50);
            dc->SetBrush(*grey_brush);
            dc->SetPen(wxPen(*blue,4,wxSOLID));
            dc->DrawRectangle(15, 15, 50, 50);
            """
            inline(code,['dc','red','blue','grey_brush'])

            dc.SetFont(wxFont(14, wxSWISS, wxNORMAL, wxNORMAL))
            dc.SetTextForeground(wxColour(0xFF, 0x20, 0xFF))
            te = dc.GetTextExtent("Hello World")
            dc.DrawText("Hello World", 60, 65)

            dc.SetPen(wxPen(wxNamedColour('VIOLET'), 4))
            dc.DrawLine(5, 65+te[1], 60+te[0], 65+te[1])
            ...

Here, some of the Python calls to wx objects were just converted to C++
calls. There isn't any benefit, it just demonstrates the capabilities. You
might want to use this if you have a computationally intensive loop in your
drawing code that you want to speed up. On windows, you'll have to use the
MSVC compiler if you use the standard wxPython DLLs distributed by Robin
Dunn. Thats because MSVC and gcc, while binary compatible in C, are not
binary compatible for C++. In fact, its probably best, no matter what
platform you're on, to specify that ``inline`` use the same compiler that was
used to build wxPython to be on the safe side. There isn't currently a way to
learn this info from the library -- you just have to know. Also, at least on
the windows platform, you'll need to install the wxWindows libraries and link
to them. I think there is a way around this, but I haven't found it yet -- I
get some linking errors dealing with wxString. One final note. You'll
probably have to tweak weave/wx_spec.py or weave/wx_info.py for your
machine's configuration to point at the correct directories etc. There. That
should sufficiently scare people into not even looking at this... :)

Keyword Option
==============

The basic definition of the ``inline()`` function has a slew of optional
variables. It also takes keyword arguments that are passed to ``distutils``
as compiler options. The following is a formatted cut/paste of the argument
section of ``inline's`` doc-string. It explains all of the variables. Some
examples using various options will follow.

::

        def inline(code,arg_names,local_dict = None, global_dict = None,
                   force = 0,
                   compiler='',
                   verbose = 0,
                   support_code = None,
                   customize=None,
                   type_factories = None,
                   auto_downcast=1,
                   **kw):


``inline`` has quite a few options as listed below. Also, the keyword
arguments for distutils extension modules are accepted to specify extra
information needed for compiling.

Inline Arguments
================

code  string. A string of valid C++ code. It should not specify a return
statement. Instead it should assign results that need to be returned to
Python in the return_val.  arg_names  list of strings. A list of Python
variable names that should be transferred from Python into the C/C++ code.
local_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the local scope for the C/C++ code. If local_dict is
not specified the local dictionary of the calling function is used.
global_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the global scope for the C/C++ code. If global_dict is
not specified the global dictionary of the calling function is used.  force
optional. 0 or 1. default 0. If 1, the C++ code is compiled every time inline
is called. This is really only useful for debugging, and probably only useful
if you're editing support_code a lot.  compiler  optional. string. The name
of compiler to use when compiling. On windows, it understands 'msvc' and
'gcc' as well as all the compiler names understood by distutils. On Unix,
it'll only understand the values understoof by distutils. (I should add 'gcc'
though to this).

On windows, the compiler defaults to the Microsoft C++ compiler. If this
isn't available, it looks for mingw32 (the gcc compiler).

On Unix, it'll probably use the same compiler that was used when compiling
Python. Cygwin's behavior should be similar.

verbose  optional. 0,1, or 2. defualt 0. Speficies how much much
information is printed during the compile phase of inlining code. 0 is silent
(except on windows with msvc where it still prints some garbage). 1 informs
you when compiling starts, finishes, and how long it took. 2 prints out the
command lines for the compilation process and can be useful if you're having
problems getting code to work. Its handy for finding the name of the .cpp
file if you need to examine it. verbose has no affect if the compilation
isn't necessary.  support_code  optional. string. A string of valid C++ code
declaring extra code that might be needed by your compiled function. This
could be declarations of functions, classes, or structures.  customize
optional. base_info.custom_info object. An alternative way to specifiy
support_code, headers, etc. needed by the function see the weave.base_info
module for more details. (not sure this'll be used much).  type_factories
optional. list of type specification factories. These guys are what convert
Python data types to C/C++ data types. If you'd like to use a different set
of type conversions than the default, specify them here. Look in the type
conversions section of the main documentation for examples.  auto_downcast
optional. 0 or 1. default 1. This only affects functions that have Numeric
arrays as input variables. Setting this to 1 will cause all floating point
values to be cast as float instead of double if all the NumPy arrays are of
type float. If even one of the arrays has type double or double complex, all
variables maintain there standard types.


Distutils keywords
==================

``inline()`` also accepts a number of ``distutils`` keywords for
controlling how the code is compiled. The following descriptions have been
copied from Greg Ward's ``distutils.extension.Extension`` class doc- strings
for convenience:  sources  [string] list of source filenames, relative to the
distribution root (where the setup script lives), in Unix form (slash-
separated) for portability. Source files may be C, C++, SWIG (.i), platform-
specific resource files, or whatever else is recognized by the "build_ext"
command as source for a Python extension. Note: The module_path file is
always appended to the front of this list  include_dirs  [string] list of
directories to search for C/C++ header files (in Unix form for portability)
define_macros  [(name : string, value : string|None)] list of macros to
define; each macro is defined using a 2-tuple, where 'value' is either the
string to define it to or None to define it without a particular value
(equivalent of "#define FOO" in source or -DFOO on Unix C compiler command
line)  undef_macros  [string] list of macros to undefine explicitly
library_dirs  [string] list of directories to search for C/C++ libraries at
link time  libraries  [string] list of library names (not filenames or paths)
to link against  runtime_library_dirs  [string] list of directories to search
for C/C++ libraries at run time (for shared extensions, this is when the
extension is loaded)  extra_objects  [string] list of extra files to link
with (eg. object files not implied by 'sources', static library that must be
explicitly specified, binary resource files, etc.)  extra_compile_args
[string] any extra platform- and compiler-specific information to use when
compiling the source files in 'sources'. For platforms and compilers where
"command line" makes sense, this is typically a list of command-line
arguments, but for other platforms it could be anything.  extra_link_args
[string] any extra platform- and compiler-specific information to use when
linking object files together to create the extension (or to create a new
static Python inte are 8-ng code converts the integer ``m``
to a CXX ``Int()`` object and then to a ``PyObject*`` with an incremented
reference count using ``Py::new_reference_to()``.

::
        return_val = Py::new_reference_to(Py::Int(m));


The second big differences shows up in the retrieval of integer values from
the Python list. The simple Python ``seq[i]`` call balloons into a C Python
API call to grab the value out of the list and then a separate call to
``py_to_int()`` that converts the PyObject* to an integer. ``py_to_int()``
includes both a NULL cheack and a ``PyInt_Check()`` call as well as the
conversion call. If either of the checks fail, an exception is raised. The
entire C++ code block is executed with in a ``try/catch`` block that handles
exceptions much like Python does. This removes the need for most error
checking code.

It is worth note that CXX lists do have indexing operators that result in
code that looks much like Python. However, the overhead in using them appears
to be relatively high, so the standard Python API was used on the
``seq.ptr()`` which is the underlying ``PyObject*`` of the List object.

The ``#line`` directive that is the first line of the C code block isn't
necessary, but it's nice for debugging. If the compilation fails because of
the syntax error in the code, the error will be reported as an error in the
Python file "binary_search.py" with an offset from the given line number (29
here).

So what was all our effort worth in terms of efficiency? Well not a lot in
this case. The examples/binary_search.py file runs both Python and C versions
of the functions As well as using the standard ``bisect`` module. If we run
it on a 1 million element list and run the search 3000 times (for 0- 2999),
here are the results we get::

        C:\home\ej\wrk\scipy\weave\examples> python binary_search.py
        Binary search for 3000 items in 1000000 length list of integers:
        speed in python: 0.159999966621
        speed of bisect: 0.121000051498
        speed up: 1.32
        speed in c: 0.110000014305
        speed up: 1.45
        speed in c(no asserts): 0.0900000333786
        speed up: 1.78


So, we get roughly a 50-75% improvement depending on whether we use the
Python asserts in our C version. If we move down to searching a 10000 element
list, the advantage evaporates. Even smaller lists might result in the Python
version being faster. I'd like to say that moving to NumPy lists (and getting
rid of the GetItem() call) offers a substantial speed up, but my preliminary
efforts didn't produce one. I think the log(N) algorithm is to blame. Because
the algorithm is nice, there just isn't much time spent computing things, so
moving to C isn't that big of a win. If there are ways to reduce conversion
overhead of values, this may improve the C/Python speed up. Anyone have other
explanations or faster code, please let me know.


Dictionary Sort
---------------

The demo in examples/dict_sort.py is another example from the Python
CookBook. `This submission`_, by Alex Martelli, demonstrates how to return
the values from a dictionary sorted by their keys:

::
        def sortedDictValues3(adict):
            keys = adict.keys()
            keys.sort()
            return map(adict.get, keys)


Alex provides 3 algorithms and this is the 3rd and fastest of the set. The C
version of this same algorithm follows::

        def c_sort(adict):
            assert(type(adict) == type({}))
            code = """
            #line 21 "dict_sort.py"
            Py::List keys = adict.keys();
            Py::List items(keys.length()); keys.sort();
            PyObject* item = NULL;
            for(int i = 0;  i < keys.length();i++)
            {
                item = PyList_GET_ITEM(keys.ptr(),i);
                item = PyDict_GetItem(adict.ptr(),item);
                Py_XINCREF(item);
                PyList_SetItem(items.ptr(),i,item);
            }
            return_val = Py::new_reference_to(items);
            """
            return inline_tools.inline(code,['adict'],verbose=1)


Like the original Python function, the C++ version can handle any Python
dictionary regardless of the key/value pair types. It uses CXX objects for
the most part to declare python types in C++, but uses Python API calls to
manipulate their contents. Again, this choice is made for speed. The C++
version, while more complicated, is about a factor of 2 faster than Python.

::

        C:\home\ej\wrk\scipy\weave\examples> python dict_sort.py
        Dict sort of 1000 items for 300 iterations:
         speed in python: 0.319999933243
        [0, 1, 2, 3, 4]
         speed in c: 0.151000022888
         speed up: 2.12
        [0, 1, 2, 3, 4]



NumPy -- cast/copy/transpose
----------------------------

CastCopyTranspose is a function called quite heavily by Linear Algebra
routines in the NumPy library. Its needed in part because of the row-major
memory layout of multi-demensional Python (and C) arrays vs. the col-major
order of the underlying Fortran algorithms. For small matrices (say 100x100
or less), a significant portion of the common routines such as LU
decompisition or singular value decompostion are spent in this setup routine.
This shouldn't happen. Here is the Python version of the function using
standard NumPy operations.

::

        def _castCopyAndTranspose(type, array):
            if a.typecode() == type:
                cast_array = copy.copy(NumPy.transpose(a))
            else:
                cast_array = copy.copy(NumPy.transpose(a).astype(type))
            return cast_array


And the following is a inline C version of the same function::

        from weave.blitz_tools import blitz_type_factories
        from weave import scalar_spec
        from weave import inline
        def _cast_copy_transpose(type,a_2d):
            assert(len(shape(a_2d)) == 2)
            new_array = zeros(shape(a_2d),type)
            NumPy_type = scalar_spec.NumPy_to_blitz_type_mapping[type]
            code = \
            """
            for(int i = 0;i < _Na_2d[0]; i++)
                for(int j = 0;  j < _Na_2d[1]; j++)
                    new_array(i,j) = (%s) a_2d(j,i);
            """ % NumPy_type
            inline(code,['new_array','a_2d'],
                   type_factories = blitz_type_factories,compiler='gcc')
            return new_array


This example uses blitz++ arrays instead of the standard representation of
NumPy arrays so that indexing is simplier to write. This is accomplished by
passing in the blitz++ "type factories" to override the standard Python to
C++ type conversions. Blitz++ arrays allow you to write clean, fast code, but
they also are sloooow to compile (20 seconds or more for this snippet). This
is why they aren't the default type used for Numeric arrays (and also because
most compilers can't compile blitz arrays...). ``inline()`` is also forced to
use 'gcc' as the compiler because the default compiler on Windows (MSVC) will
not compile blitz code. ('gcc' I think will use the standard compiler on
Unix machine instead of explicitly forcing gcc (check this)) Comparisons of
the Python vs inline C++ code show a factor of 3 speed up. Also shown are the
results of an "inplace" transpose routine that can be used if the output of
the linear algebra routine can overwrite the original matrix (this is often
appropriate). This provides another factor of 2 improvement.

::

        #C:\home\ej\wrk\scipy\weave\examples> python cast_copy_transpose.py
        # Cast/Copy/Transposing (150,150)array 1 times
        #  speed in python: 0.870999932289
        #  speed in c: 0.25
        #  speed up: 3.48
        #  inplace transpose c: 0.129999995232
        #  speed up: 6.70

wxPython
--------

``inline`` knows how to handle wxPython objects. Thats nice in and of itself,
but it also demonstrates that the type conversion mechanism is reasonably
flexible. Chances are, it won't take a ton of effort to support special types
you might have. The examples/wx_example.py borrows the scrolled window
example from the wxPython demo, accept that it mixes inline C code in the
middle of the drawing function.

::

        def DoDrawing(self, dc):

            red = wxNamedColour("RED");
            blue = wxNamedColour("BLUE");
            grey_brush = wxLIGHT_GREY_BRUSH;
            code = \
            """
            #line 108 "wx_example.py"
            dc->BeginDrawing();
            dc->SetPen(wxPen(*red,4,wxSOLID));
            dc->DrawRectangle(5,5,50,50);
            dc->SetBrush(*grey_brush);
            dc->SetPen(wxPen(*blue,4,wxSOLID));
            dc->DrawRectangle(15, 15, 50, 50);
            """
            inline(code,['dc','red','blue','grey_brush'])

            dc.SetFont(wxFont(14, wxSWISS, wxNORMAL, wxNORMAL))
            dc.SetTextForeground(wxColour(0xFF, 0x20, 0xFF))
            te = dc.GetTextExtent("Hello World")
            dc.DrawText("Hello World", 60, 65)

            dc.SetPen(wxPen(wxNamedColour('VIOLET'), 4))
            dc.DrawLine(5, 65+te[1], 60+te[0], 65+te[1])
            ...

Here, some of the Python calls to wx objects were just converted to C++
calls. There isn't any benefit, it just demonstrates the capabilities. You
might want to use this if you have a computationally intensive loop in your
drawing code that you want to speed up. On windows, you'll have to use the
MSVC compiler if you use the standard wxPython DLLs distributed by Robin
Dunn. Thats because MSVC and gcc, while binary compatible in C, are not
binary compatible for C++. In fact, its probably best, no matter what
platform you're on, to specify that ``inline`` use the same compiler that was
used to build wxPython to be on the safe side. There isn't currently a way to
learn this info from the library -- you just have to know. Also, at least on
the windows platform, you'll need to install the wxWindows libraries and link
to them. I think there is a way around this, but I haven't found it yet -- I
get some linking errors dealing with wxString. One final note. You'll
probably have to tweak weave/wx_spec.py or weave/wx_info.py for your
machine's configuration to point at the correct directories etc. There. That
should sufficiently scare people into not even looking at this... :)

Keyword Option
==============

The basic definition of the ``inline()`` function has a slew of optional
variables. It also takes keyword arguments that are passed to ``distutils``
as compiler options. The following is a formatted cut/paste of the argument
section of ``inline's`` doc-string. It explains all of the variables. Some
examples using various options will follow.

::

        def inline(code,arg_names,local_dict = None, global_dict = None,
                   force = 0,
                   compiler='',
                   verbose = 0,
                   support_code = None,
                   customize=None,
                   type_factories = None,
                   auto_downcast=1,
                   **kw):


``inline`` has quite a few options as listed below. Also, the keyword
arguments for distutils extension modules are accepted to specify extra
information needed for compiling.

Inline Arguments
================

code  string. A string of valid C++ code. It should not specify a return
statement. Instead it should assign results that need to be returned to
Python in the return_val.  arg_names  list of strings. A list of Python
variable names that should be transferred from Python into the C/C++ code.
local_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the local scope for the C/C++ code. If local_dict is
not specified the local dictionary of the calling function is used.
global_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the global scope for the C/C++ code. If global_dict is
not specified the global dictionary of the calling function is used.  force
optional. 0 or 1. default 0. If 1, the C++ code is compiled every time inline
is called. This is really only useful for debugging, and probably only useful
if you're editing support_code a lot.  compiler  optional. string. The name
of compiler to use when compiling. On windows, it understands 'msvc' and
'gcc' as well as all the compiler names understood by distutils. On Unix,
it'll only understand the values understoof by distutils. (I should add 'gcc'
though to this).

On windows, the compiler defaults to the Microsoft C++ compiler. If this
isn't available, it looks for mingw32 (the gcc compiler).

On Unix, it'll probably use the same compiler that was used when compiling
Python. Cygwin's behavior should be similar.

verbose  optional. 0,1, or 2. defualt 0. Speficies how much much
information is printed during the compile phase of inlining code. 0 is silent
(except on windows with msvc where it still prints some garbage). 1 informs
you when compiling starts, finishes, and how long it took. 2 prints out the
command lines for the compilation process and can be useful if you're having
problems getting code to work. Its handy for finding the name of the .cpp
file if you need to examine it. verbose has no affect if the compilation
isn't necessary.  support_code  optional. string. A string of valid C++ code
declaring extra code that might be needed by your compiled function. This
could be declarations of functions, classes, or structures.  customize
optional. base_info.custom_info object. An alternative way to specifiy
support_code, headers, etc. needed by the function see the weave.base_info
module for more details. (not sure this'll be used much).  type_factories
optional. list of type specification factories. These guys are what convert
Python data types to C/C++ data types. If you'd like to use a different set
of type conversions than the default, specify them here. Look in the type
conversions section of the main documentation for examples.  auto_downcast
optional. 0 or 1. default 1. This only affects functions that have Numeric
arrays as input variables. Setting this to 1 will cause all floating point
values to be cast as float instead of double if all the NumPy arrays are of
type float. If even one of the arrays has type double or double complex, all
variables maintain there standard types.


Distutils keywords
==================

``inline()`` also accepts a number of ``distutils`` keywords for
controlling how the code is compiled. The following descriptions have been
copied from Greg Ward's ``distutils.extension.Extension`` class doc- strings
for convenience:  sources  [string] list of source filenames, relative to the
distribution root (where the setup script lives), in Unix form (slash-
separated) for portability. Source files may be C, C++, SWIG (.i), platform-
specific resource files, or whatever else is recognized by the "build_ext"
command as source for a Python extension. Note: The module_path file is
always appended to the front of this list  include_dirs  [string] list of
directories to search for C/C++ header files (in Unix form for portability)
define_macros  [(name : string, value : string|None)] list of macros to
define; each macro is defined using a 2-tuple, where 'value' is either the
string to define it to or None to define it without a particular value
(equivalent of "#define FOO" in source or -DFOO on Unix C compiler command
line)  undef_macros  [string] list of macros to undefine explicitly
library_dirs  [string] list of directories to search for C/C++ libraries at
link time  libraries  [string] list of library names (not filenames or paths)
to link against  runtime_library_dirs  [string] list of directories to search
for C/C++ libraries at run time (for shared extensions, this is when the
extension is loaded)  extra_objects  [string] list of extra files to link
with (eg. object files not implied by 'sources', static library that must be
explicitly specified, binary resource files, etc.)  extra_compile_args
[string] any extra platform- and compiler-specific information to use when
compiling the source files in 'sources'. For platforms and compilers where
"command line" makes sense, this is typically a list of command-line
arguments, but for other platforms it could be anything.  extra_link_args
[string] any extra platform- and compiler-specific information to use when
linking object files together to create the extension (or to create a new
static Python inte are 8-ng code converts the integer ``m``
to a CXX ``Int()`` object and then to a ``PyObject*`` with an incremented
reference count using ``Py::new_reference_to()``.

::
        return_val = Py::new_reference_to(Py::Int(m));


The second big differences shows up in the retrieval of integer values from
the Python list. The simple Python ``seq[i]`` call balloons into a C Python
API call to grab the value out of the list and then a separate call to
``py_to_int()`` that converts the PyObject* to an integer. ``py_to_int()``
includes both a NULL cheack and a ``PyInt_Check()`` call as well as the
conversion call. If either of the checks fail, an exception is raised. The
entire C++ code block is executed with in a ``try/catch`` block that handles
exceptions much like Python does. This removes the need for most error
checking code.

It is worth note that CXX lists do have indexing operators that result in
code that looks much like Python. However, the overhead in using them appears
to be relatively high, so the standard Python API was used on the
``seq.ptr()`` which is the underlying ``PyObject*`` of the List object.

The ``#line`` directive that is the first line of the C code block isn't
necessary, but it's nice for debugging. If the compilation fails because of
the syntax error in the code, the error will be reported as an error in the
Python file "binary_search.py" with an offset from the given line number (29
here).

So what was all our effort worth in terms of efficiency? Well not a lot in
this case. The examples/binary_search.py file runs both Python and C versions
of the functions As well as using the standard ``bisect`` module. If we run
it on a 1 million element list and run the search 3000 times (for 0- 2999),
here are the results we get::

        C:\home\ej\wrk\scipy\weave\examples> python binary_search.py
        Binary search for 3000 items in 1000000 length list of integers:
        speed in python: 0.159999966621
        speed of bisect: 0.121000051498
        speed up: 1.32
        speed in c: 0.110000014305
        speed up: 1.45
        speed in c(no asserts): 0.0900000333786
        speed up: 1.78


So, we get roughly a 50-75% improvement depending on whether we use the
Python asserts in our C version. If we move down to searching a 10000 element
list, the advantage evaporates. Even smaller lists might result in the Python
version being faster. I'd like to say that moving to NumPy lists (and getting
rid of the GetItem() call) offers a substantial speed up, but my preliminary
efforts didn't produce one. I think the log(N) algorithm is to blame. Because
the algorithm is nice, there just isn't much time spent computing things, so
moving to C isn't that big of a win. If there are ways to reduce conversion
overhead of values, this may improve the C/Python speed up. Anyone have other
explanations or faster code, please let me know.


Dictionary Sort
---------------

The demo in examples/dict_sort.py is another example from the Python
CookBook. `This submission`_, by Alex Martelli, demonstrates how to return
the values from a dictionary sorted by their keys:

::
        def sortedDictValues3(adict):
            keys = adict.keys()
            keys.sort()
            return map(adict.get, keys)


Alex provides 3 algorithms and this is the 3rd and fastest of the set. The C
version of this same algorithm follows::

        def c_sort(adict):
            assert(type(adict) == type({}))
            code = """
            #line 21 "dict_sort.py"
            Py::List keys = adict.keys();
            Py::List items(keys.length()); keys.sort();
            PyObject* item = NULL;
            for(int i = 0;  i < keys.length();i++)
            {
                item = PyList_GET_ITEM(keys.ptr(),i);
                item = PyDict_GetItem(adict.ptr(),item);
                Py_XINCREF(item);
                PyList_SetItem(items.ptr(),i,item);
            }
            return_val = Py::new_reference_to(items);
            """
            return inline_tools.inline(code,['adict'],verbose=1)


Like the original Python function, the C++ version can handle any Python
dictionary regardless of the key/value pair types. It uses CXX objects for
the most part to declare python types in C++, but uses Python API calls to
manipulate their contents. Again, this choice is made for speed. The C++
version, while more complicated, is about a factor of 2 faster than Python.

::

        C:\home\ej\wrk\scipy\weave\examples> python dict_sort.py
        Dict sort of 1000 items for 300 iterations:
         speed in python: 0.319999933243
        [0, 1, 2, 3, 4]
         speed in c: 0.151000022888
         speed up: 2.12
        [0, 1, 2, 3, 4]



NumPy -- cast/copy/transpose
----------------------------

CastCopyTranspose is a function called quite heavily by Linear Algebra
routines in the NumPy library. Its needed in part because of the row-major
memory layout of multi-demensional Python (and C) arrays vs. the col-major
order of the underlying Fortran algorithms. For small matrices (say 100x100
or less), a significant portion of the common routines such as LU
decompisition or singular value decompostion are spent in this setup routine.
This shouldn't happen. Here is the Python version of the function using
standard NumPy operations.

::

        def _castCopyAndTranspose(type, array):
            if a.typecode() == type:
                cast_array = copy.copy(NumPy.transpose(a))
            else:
                cast_array = copy.copy(NumPy.transpose(a).astype(type))
            return cast_array


And the following is a inline C version of the same function::

        from weave.blitz_tools import blitz_type_factories
        from weave import scalar_spec
        from weave import inline
        def _cast_copy_transpose(type,a_2d):
            assert(len(shape(a_2d)) == 2)
            new_array = zeros(shape(a_2d),type)
            NumPy_type = scalar_spec.NumPy_to_blitz_type_mapping[type]
            code = \
            """
            for(int i = 0;i < _Na_2d[0]; i++)
                for(int j = 0;  j < _Na_2d[1]; j++)
                    new_array(i,j) = (%s) a_2d(j,i);
            """ % NumPy_type
            inline(code,['new_array','a_2d'],
                   type_factories = blitz_type_factories,compiler='gcc')
            return new_array


This example uses blitz++ arrays instead of the standard representation of
NumPy arrays so that indexing is simplier to write. This is accomplished by
passing in the blitz++ "type factories" to override the standard Python to
C++ type conversions. Blitz++ arrays allow you to write clean, fast code, but
they also are sloooow to compile (20 seconds or more for this snippet). This
is why they aren't the default type used for Numeric arrays (and also because
most compilers can't compile blitz arrays...). ``inline()`` is also forced to
use 'gcc' as the compiler because the default compiler on Windows (MSVC) will
not compile blitz code. ('gcc' I think will use the standard compiler on
Unix machine instead of explicitly forcing gcc (check this)) Comparisons of
the Python vs inline C++ code show a factor of 3 speed up. Also shown are the
results of an "inplace" transpose routine that can be used if the output of
the linear algebra routine can overwrite the original matrix (this is often
appropriate). This provides another factor of 2 improvement.

::

        #C:\home\ej\wrk\scipy\weave\examples> python cast_copy_transpose.py
        # Cast/Copy/Transposing (150,150)array 1 times
        #  speed in python: 0.870999932289
        #  speed in c: 0.25
        #  speed up: 3.48
        #  inplace transpose c: 0.129999995232
        #  speed up: 6.70

wxPython
--------

``inline`` knows how to handle wxPython objects. Thats nice in and of itself,
but it also demonstrates that the type conversion mechanism is reasonably
flexible. Chances are, it won't take a ton of effort to support special types
you might have. The examples/wx_example.py borrows the scrolled window
example from the wxPython demo, accept that it mixes inline C code in the
middle of the drawing function.

::

        def DoDrawing(self, dc):

            red = wxNamedColour("RED");
            blue = wxNamedColour("BLUE");
            grey_brush = wxLIGHT_GREY_BRUSH;
            code = \
            """
            #line 108 "wx_example.py"
            dc->BeginDrawing();
            dc->SetPen(wxPen(*red,4,wxSOLID));
            dc->DrawRectangle(5,5,50,50);
            dc->SetBrush(*grey_brush);
            dc->SetPen(wxPen(*blue,4,wxSOLID));
            dc->DrawRectangle(15, 15, 50, 50);
            """
            inline(code,['dc','red','blue','grey_brush'])

            dc.SetFont(wxFont(14, wxSWISS, wxNORMAL, wxNORMAL))
            dc.SetTextForeground(wxColour(0xFF, 0x20, 0xFF))
            te = dc.GetTextExtent("Hello World")
            dc.DrawText("Hello World", 60, 65)

            dc.SetPen(wxPen(wxNamedColour('VIOLET'), 4))
            dc.DrawLine(5, 65+te[1], 60+te[0], 65+te[1])
            ...

Here, some of the Python calls to wx objects were just converted to C++
calls. There isn't any benefit, it just demonstrates the capabilities. You
might want to use this if you have a computationally intensive loop in your
drawing code that you want to speed up. On windows, you'll have to use the
MSVC compiler if you use the standard wxPython DLLs distributed by Robin
Dunn. Thats because MSVC and gcc, while binary compatible in C, are not
binary compatible for C++. In fact, its probably best, no matter what
platform you're on, to specify that ``inline`` use the same compiler that was
used to build wxPython to be on the safe side. There isn't currently a way to
learn this info from the library -- you just have to know. Also, at least on
the windows platform, you'll need to install the wxWindows libraries and link
to them. I think there is a way around this, but I haven't found it yet -- I
get some linking errors dealing with wxString. One final note. You'll
probably have to tweak weave/wx_spec.py or weave/wx_info.py for your
machine's configuration to point at the correct directories etc. There. That
should sufficiently scare people into not even looking at this... :)

Keyword Option
==============

The basic definition of the ``inline()`` function has a slew of optional
variables. It also takes keyword arguments that are passed to ``distutils``
as compiler options. The following is a formatted cut/paste of the argument
section of ``inline's`` doc-string. It explains all of the variables. Some
examples using various options will follow.

::

        def inline(code,arg_names,local_dict = None, global_dict = None,
                   force = 0,
                   compiler='',
                   verbose = 0,
                   support_code = None,
                   customize=None,
                   type_factories = None,
                   auto_downcast=1,
                   **kw):


``inline`` has quite a few options as listed below. Also, the keyword
arguments for distutils extension modules are accepted to specify extra
information needed for compiling.

Inline Arguments
================

code  string. A string of valid C++ code. It should not specify a return
statement. Instead it should assign results that need to be returned to
Python in the return_val.  arg_names  list of strings. A list of Python
variable names that should be transferred from Python into the C/C++ code.
local_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the local scope for the C/C++ code. If local_dict is
not specified the local dictionary of the calling function is used.
global_dict  optional. dictionary. If specified, it is a dictionary of values
that should be used as the global scope for the C/C++ code. If global_dict is
not specified the global dictionary of the calling function is used.  force
optional. 0 or 1. default 0. If 1, the C++ code is compiled every time inline
is called. This is really only useful for debugging, and probably only useful
if you're editing support_code a lot.  compiler  optional. string. The name
of compiler to use when compiling. On windows, it understands 'msvc' and
'gcc' as well as all the compiler names understood by distutils. On Unix,
it'll only understand the values understoof by distutils. (I should add 'gcc'
though to this).

On windows, the compiler defaults to the Microsoft C++ compiler. If this
isn't available, it looks for mingw32 (the gcc compiler).

On Unix, it'll probably use the same compiler that was used when compiling
Python. Cygwin's behavior should be similar.

verbose  optional. 0,1, or 2. defualt 0. Speficies how much much
information is printed during the compile phase of inlining code. 0 is silent
(except on windows with msvc where it still prints some garbage). 1 informs
you when compiling starts, finishes, and how long it took. 2 prints out the
command lines for the compilation process and can be useful if you're having
problems getting code to work. Its handy for finding the name of the .cpp
file if you need to examine it. verbose has no affect if the compilation
isn't necessary.  support_code  optional. string. A string of valid C++ code
declaring extra code that might be needed by your compiled function. This
could be declarations of functions, classes, or structures.  customize
optional. base_info.custom_info object. An alternative way to specifiy
support_code, headers, etc. needed by the function see the weave.base_info
module for more details. (not sure this'll be used much).  type_factories
optional. list of type specification factories. These guys are what convert
Python data types to C/C++ data types. If you'd like to use a different set
of type conversions than the default, specify them here. Look in the type
conversions section of the main documentation for examples.  auto_downcast
optional. 0 or 1. default 1. This only affects functions that have Numeric
arrays as input variables. Setting this to 1 will cause all floating point
values to be cast as float instead of double if all the NumPy arrays are of
type float. If even one of the arrays has type double or double complex, all
variables maintain there standard types.


Distutils keywords
==================

``inline()`` also accepts a number of ``distutils`` keywords for
controlling how the code is compiled. The following descriptions have been
copied from Greg Ward's ``distutils.extension.Extension`` class doc- strings
for convenience:  sources  [string] list of source filenames, relative to the
distribution root (where the setup script lives), in Unix form (slash-
separated) for portability. Source files may be C, C++, SWIG (.i), platform-
specific resource files, or whatever else is recognized by the "build_ext"
command as source for a Python extension. Note: The module_path file is
always appended to the front of this list  include_dirs  [string] list of
directories to search for C/C++ header files (in Unix form for portability)
define_macros  [(name : string, value : string|None)] list of macros to
define; each macro is defined using a 2-tuple, where 'value' is either the
string to define it to or None to define it without a particular value
(equivalent of "#define FOO" in source or -DFOO on Unix C compiler command
line)  undef_macros  [string] list of macros to undefine explicitly
library_dirs  [string] list of directories to search for C/C++ libraries at
link time  libraries  [string] list of library names (not filenames or paths)
to link against  runtime_library_dirs  [string] list of directories to search
for C/C++ libraries at run time (for shared extensions, this is when the
extension is loaded)  extra_objects  [string] list of extra files to link
with (eg. object files not implied by 'sources', static library that must be
explicitly specified, binary resource files, etc.)  extra_compile_args
[string] any extra platform- and compiler-specific information to use when
compiling the source files in 'sources'. For platforms and compilers where
"command line" makes sense, this is typically a list of command-line
arguments, but for other platforms it could be anything.  extra_link_args
[string] any extra platform- and compiler-specific information to use when
linking object files together to create the extension (or to create a new
static Python inte are 8-ng code converts the integer ``m``
to a CXX ``Int()`` object and then to a ``PyObject*`` with an incremented
reference count using ``Py::new_reference_to()``.

::
        return_val = Py::new_reference_to(Py::Int(m));


The second big differences shows up in the retrieval of integer values from
the Python list. The simple Python ``seq[i]`` call balloons into a C Python
API call to grab the value out of the list and then a separate call to
``py_to_int()`` that converts the PyObject* to an integer. ``py_to_int()``
includes both a NULL cheack and a ``PyInt_Check()`` call as well as the
conversion call. If either of the checks fail, an exception is raised. The
entire C++ code block is executed with in a ``try/catch`` block that handles
exceptions much like Python does. This removes the need for most error
checking code.

It is worth note that CXX lists do have indexing operators that result in
code that looks much like Python. However, the overhead in using them appears
to be relatively high, so the standard Python API was used on the
``seq.ptr()`` which is the underlying ``PyObject*`` of the List object.

The ``#line`` directive that is the first line of the C code block isn't
necessary, but it's nice for debugging. If the compilation fails because of
the syntax error in the code, the error will be reported as an error in the
Python file "binary_search.py" with an offset from the given line number (29
here).

So what was all our effort worth in terms of efficiency? Well not a lot in
this case. The examples/binary_search.py file runs both Python and C versions
of the functions As well as using the standard ``bisect`` module. If we run
it on a 1 million element list and run the search 3000 times (for 0- 2999),
here are the results we get::

        C:\home\ej\wrk\scipy\weave\examples> python binary_search.py
        Binary search for 3000 items in 1000000 length list of integers:
        speed in python: 0.159999966621
        speed of bisect: 0.121000051498
        speed up: 1.32
        speed in c: 0.110000014305
        speed up: 1.45
        speed in c(no asserts): 0.0900000333786
        speed up: 1.78


So, we get roughly a 50-75% improvement depending on whether we use the
Python asserts in our C version. If we move down to searching a 10000 element
list, the advantage evaporates. Even smaller lists might result in the Python
version being faster. I'd like to say that moving to NumPy lists (and getting
rid of the GetItem() call) offers a substantial speed up, but my preliminary
efforts didn't produce one. I think the log(N) algorithm is to blame. Because
the algorithm is nice, there just isn't much time spent computing things, so
moving to C isn't that big of a win. If there are ways to reduce conversion
overhead of values, this may improve the C/Python speed up. Anyone have other
explanations or faster code, please let me know.


Dictionary Sort
---------------

The demo in examples/dict_sort.py is another example from the Python
CookBook. `This submission`_, by Alex Martelli, demonstrates how to return
the values from a dictionary sorted by their keys:

::
        def sortedDictValues3(adict):
            keys = adict.keys()
            keys.sort()
            return map(adict.get, keys)


Alex provides 3 algorithms and this is the 3rd and fastest of the set. The C
version of this same algorithm follows::

        def c_sort(adict):
            assert(type(adict) == type({}))
            code = """
            #line 21 "dict_sort.py"
            Py::List keys = adict.keys();
            Py::List items(keys.length()); keys.sort();
            PyObject* item = NULL;
            for(int i = 0;  i < keys.length();i++)
            {
                item = PyList_GET_ITEM(keys.ptr(),i);
                item = PyDict_GetItem(adict.ptr(),item);
                Py_XINCREF(item);
                PyList_SetItem(items.ptr(),i,item);
            }
            return_val = Py::new_reference_to(items);
            """
            return inline_tools.inline(code,['adict'],verbose=1)


Like the original Python function, the C++ version can handle any Python
dictionary regardless of the key/value pair types. It uses CXX objects for
the most part to declare python types in C++, but uses Python API calls to
manipulate their contents. Again, this choice is made for speed. The C++
version, while more complicated, is about a factor of 2 faster than Python.

::

        C:\home\ej\wrk\scipy\weave\examples> python dict_sort.py
        Dict sort of 1000 items for 300 iterations:
         speed in python: 0.319999933243
        [0, 1, 2, 3, 4]
         speed in c: 0.151000022888
         speed up: 2.12
        [0, 1, 2, 3, 4]



NumPy -- cast/copy/transpose
----------------------------

CastCopyTranspose is a function called quite heavily by Linear Algebra
routines in the NumPy library. Its needed in part because of the row-major
memory layout of multi-demensional Python (and C) a