A C Extension Type String Stack






A C Extension Type String Stack

So far in this chapter, we've been dealing with C extension modulesflat function libraries. To implement multiple-instance objects in C, you need to code a C extension type, not a module. Like Python classes, C types generate multiple-instance objects and can overload (i.e., intercept and implement) Python expression operators and type operations. In recent Python releases, C types can also support subclassing just like Python classes.

One of the biggest drawbacks of types, though, is their sizeto implement a realistically equipped C type, you need to code lots of not-very-pretty C code and fill out type descriptor tables with pointers to link up operation handlers. In fact, C extension types are so complex that I'm going to cut some details here. To give you a feel for the overall structure, Figure presents a C string stack type implementation, but with the bodies of all its functions stripped out. For the complete implementation, see this file in the book's examples distribution.

This C type roughly implements the same interface as the stack classes we met in Chapter 20, but it imposes a few limits on the stack itself. The stripped parts use the same algorithms as the C module in Figure, but they operate on the passed-in self object, which now refers to the particular type instance object being processed, just as the first argument does in class methods. In types, self is a pointer to an allocated C struct that represents a type instance object.

Please note that the C API is prone to frequent changes, especially for C extension types. Although the code of this book's stack type example has been updated and retested for each edition, it may in fact not completely reflect current practice by the time you read these words.

Even as is, although it works as shown, this example does not support new, advanced C type concepts such as support for subclassing. Because this is such a volatile topic, the example was almost cut from this edition completely, but was retained in abbreviated form just to give you a sampling of the general flavor of C types. To code types of your own, you will want to explore additional resources.

For more up-to-date details on C types, consult Python's now thorough Extending and Embedding manual. And for more complete examples, see the Objects directory in the Python source distribution treeall of Python's own datatypes are merely precoded C extension types that utilize the same interfaces and demonstrate best practice usage better than the static nature of books allows.

Of special interest, see Python 2.4's Objects/xxmodule.c for example C type code. Type descriptor layouts, described shortly, are perhaps the most prone to change over time; consult the file Include/object.h in the Python distribution for an up-to-date list of fields. Some new Python releases may also require that C types written to work with earlier releases be recompiled to pick up descriptor changes.

Finally, if it seems like C types are complex, transitory, and error prone, it's because they are. Because many developers will find higher-level tools such as SWIG to be more reasonable alternatives to handcoded C types anyhow, this section is not designed to be complete.


Having said all that, the C extension type in Figure does work, and it demonstrates the basics of the model. Let's take a quick look.

PP3E\Integrate\Extend\Stacks\stacktyp.c

/****************************************************
 * stacktyp.c: a character-string stack datatype;
 * a C extension type, for use in Python programs;
 * stacktype module clients can make multiple stacks;
 * similar to stackmod, but 'self' is the instance,
 * and we can overload sequence operators here;
 ****************************************************/

#include "Python.h"

static PyObject *ErrorObject;      /* local exception */
#define onError(message) \
       { PyErr_SetString(ErrorObject, message); return NULL; }

/*****************************************************************************
 * STACK-TYPE INFORMATION
 *****************************************************************************/
#define MAXCHARS 2048
#define MAXSTACK MAXCHARS

typedef struct {                 /* stack instance object format */
    PyObject_HEAD                /* Python header: ref-count + &typeobject */
    int top, len;
    char *stack[MAXSTACK];       /* per-instance state info */
    char strings[MAXCHARS];      /* same as stackmod, but multiple copies */
} stackobject;

/*****************************************************************************
 * INSTANCE METHODS
 *****************************************************************************/

static PyObject *             /* on "instance.push(arg)" */
stack_push(self, args)        /* 'self' is the stack instance object */
    stackobject *self;        /* 'args' are args passed to self.push method */
    PyObject    *args;
{    ...
}
static PyObject *
stack_pop(self, args)
    stackobject *self;
    PyObject    *args;        /* on "instance.pop( )" */
{    ...
}
static PyObject *
stack_top(self, args)
    stackobject *self;
    PyObject    *args;
{    ...
}
static PyObject *
stack_empty(self, args)
    stackobject *self;
    PyObject    *args;
{    ...
}
static struct PyMethodDef stack_methods[] = {     /* instance methods */
 {"push",       stack_push,     1},               /* name/address table */
 {"pop",        stack_pop,      1},               /* like list append,sort */
 {"top",        stack_top,      1},
 {"empty",      stack_empty,    1},               /* extra ops besides optrs */
 {NULL,         NULL}                             /* end, for getattr here */
};

/*****************************************************************************
 * BASIC TYPE-OPERATIONS
 *****************************************************************************/

static stackobject *             /* on "x = stacktype.Stack( )" */
newstackobject( )                 /* instance constructor function */
{   ...                            /* these don't get an 'args' input */
}
static void                      /* instance destructor function */
stack_dealloc(self)              /* when reference-count reaches zero */
    stackobject *self;
{   ...                            /* do cleanup activity */
}
static int
stack_print(self, fp, flags)
    stackobject *self;
    FILE *fp;
    int flags;                   /* print self to file */
{   ...
}
static PyObject *
stack_getattr(self, name)        /* on "instance.attr" reference  */
    stackobject *self;           /* make a bound-method or member */
    char *name;
{   ...
}
static int
stack_compare(v, w)              /* on all comparisons */
    stackobject *v, *w;
{   ...
}

/*****************************************************************************
 * SEQUENCE TYPE-OPERATIONS
 *****************************************************************************/

static int
stack_length(self)
    stackobject *self;               /* called on "len(instance)" */
{   ...
}
static PyObject *
stack_concat(self, other)
    stackobject *self;               /* on "instance + other" */
    PyObject    *other;              /* 'self' is the instance */
{   ...
}
static PyObject *
stack_repeat(self, n)                /* on "instance * N" */
    stackobject *self;               /* new stack = repeat self n times */
    int n;
{   ...
}
static PyObject *
stack_item(self, index)              /* on "instance[offset]", "in/for" */
    stackobject *self;               /* return the i-th item of self */
    int index;                       /* negative index pre-adjusted */
{   ...
}
static PyObject *
stack_slice(self, ilow, ihigh)
    stackobject *self;               /* on "instance[ilow:ihigh]" */
    int ilow, ihigh;                 /* negative-adjusted, not scaled */
{   ...
}

/*****************************************************************************
 * TYPE DESCRIPTORS
 *****************************************************************************/

static PySequenceMethods stack_as_sequence = {  /* sequence supplement     */
      (inquiry)       stack_length,             /* sq_length    "len(x)"   */
      (binaryfunc)    stack_concat,             /* sq_concat    "x + y"    */
      (intargfunc)    stack_repeat,             /* sq_repeat    "x * n"    */
      (intargfunc)    stack_item,               /* sq_item      "x[i], in" */
      (intintargfunc) stack_slice,              /* sq_slice     "x[i:j]"   */
      (intobjargproc)     0,                    /* sq_ass_item  "x[i] = v" */
      (intintobjargproc)  0,                    /* sq_ass_slice "x[i:j]=v" */
};


/* The ob_type field must be initialized in the module init
   function to be portable to Windows without using C++. */

static PyTypeObject Stacktype = {      /* main Python type-descriptor */
  /* type header */                    /* shared by all instances */
      PyObject_HEAD_INIT(NULL)         /* was PyObject_HEAD_INIT(&PyType_Type)*/
      0,                               /* ob_size */
      "stack",                         /* tp_name */
      sizeof(stackobject),             /* tp_basicsize */
      0,                               /* tp_itemsize */

  /* standard methods */
      (destructor)  stack_dealloc,     /* tp_dealloc  ref-count==0  */
      (printfunc)   stack_print,       /* tp_print    "print x"     */
      (getattrfunc) stack_getattr,     /* tp_getattr  "x.attr"      */
      (setattrfunc) 0,                 /* tp_setattr  "x.attr=v"    */
      (cmpfunc)     stack_compare,     /* tp_compare  "x > y"       */
      (reprfunc)    0,                 /* tp_repr     'x',repr,print */

  /* type categories */
      0,                               /* tp_as_number   +,-,*,/,%,&,>>,...*/
      &stack_as_sequence,              /* tp_as_sequence +,[i],[i:j],len, ...*/
      0,                               /* tp_as_mapping  [key], len, ...*/

  /* more methods */
      (hashfunc)     0,                /* tp_hash    "dict[x]" */
      (ternaryfunc)  0,                /* tp_call    "x( )"     */
      (reprfunc)     0,                /* tp_str     "str(x)"  */

};  /* plus others: see Python's Include/object.h, Modules/xxmodule.c */

/*****************************************************************************
 * MODULE LOGIC
 *****************************************************************************/

static PyObject *
stacktype_new(self, args)                 /* on "x = stacktype.Stack( )" */
    PyObject *self;                       /* self not used */
    PyObject *args;                       /* constructor args */
{
    if (!PyArg_ParseTuple(args, ""))      /* Module-method function */
        return NULL;
    return (PyObject *)newstackobject( );  /* make a new type-instance object */
}                                         /* the hook from module to type... */

static struct PyMethodDef stacktype_methods[] = {
    {"Stack",  stacktype_new,  1},             /* one function: make a stack */
    {NULL,     NULL}                           /* end marker, for initmodule */
};

void
initstacktype( )                 /* on first "import stacktype" */
{
    PyObject *m, *d;

    /* finalize type object, setting type of new type object
       here for portability to Windows without requiring C++ */
    if (PyType_Ready(&Stacktype) < 0)
        return;

    m = Py_InitModule("stacktype", stacktype_methods);   /* make the module, */
    d = PyModule_GetDict(m);                             /* with 'Stack' func */
    ErrorObject = Py_BuildValue("s", "stacktype.error");
    PyDict_SetItemString(d, "error", ErrorObject);       /* export exception */
    if (PyErr_Occurred( ))
        Py_FatalError("can't initialize module stacktype");

}

Anatomy of a C Extension Type

Although most of the file stacktyp.c is missing, there is enough here to illustrate the global structure common to C type implementations:


Instance struct

The file starts off by defining a C struct called stackobject that will be used to hold per-instance state informationeach generated instance object gets a newly malloc'd copy of the struct. It serves the same function as class instance attribute dictionaries, and it contains data that was saved in global variables by the C stack module of the preceding section (Figure).


Instance methods

As in the module, a set of instance methods follows next; they implement method calls such as push and pop. But here, method functions process the implied instance object, passed in to the self argument. This is similar in spirit to class methods. Type instance methods are looked up in the registration table of the code listing (Figure) when accessed.


Basic type operations

Next, the file defines functions to handle basic operations common to all types: creation, printing, qualification, and so on. These functions have more specific type signatures than instance method handlers. The object creation handler allocates a new stack struct and initializes its header fields; the reference count is set to 1, and its type object pointer is set to the Stacktype type descriptor that appears later in the file.


Sequence operations

Functions for handling sequence type operations come next. Stacks respond to most sequence operators: len, +, *, and [i]. Much like the _ _getitem_ _ class method, the stack_item indexing handler performs indexing, but also in membership tests and for iterator loops. These latter two work by indexing an object until an IndexError exception is caught by Python.


Type descriptors

The type descriptor tables (really, structs) that appear near the end of the file are the crux of the matter for typesPython uses these tables to dispatch an operation performed on an instance object to the corresponding C handler function in this file. In fact, everything is routed through these tables; even method attribute lookups start by running a C stack_getattr function listed in the table (which in turn looks up the attribute name in a name/function-pointer table). The main Stacktype table includes a link to the supplemental stack_as_sequence table in which sequence operation handlers are registered; types can provide such tables to register handlers for mapping, number, and sequence operation sets.

See Python's integer and dictionary objects ' source code for number and mapping examples; they are analogous to the sequence type here, but their operation tables vary. Descriptor layouts, like most C API tools, are prone to change over time, and you should always consult Include/object.h in the Python distribution for an up-to-date list of fields.


Constructor module

Besides defining a C type, this file also creates a simple C module at the end that exports a stacktype.Stack constructor function, which Python scripts call to generate new stack instance objects. The initialization function for this module is the only C name in this file that is not static (local to the file); everything else is reached by following pointersfrom instance to type descriptor to C handler function.

Again, see this book's examples distribution for the full C stack type implementation. But to give you the general flavor of C type methods, here is what the C type's pop function looks like; compare this with the C module's pop function to see how the self argument is used to access per-instance information in types:

static PyObject *
stack_pop(self, args)
    stackobject *self;
    PyObject *args;                            /* on "instance.pop( )" */
{
    PyObject *pstr;
    if (!PyArg_ParseTuple(args, ""))           /* verify no args passed */
        return NULL;
    if (self->top == 0)
        onError("stack underflow")             /* return NULL = raise */
    else {
        pstr = Py_BuildValue("s", self->stack[--self->top]);
        self->len -= (strlen(self->stack[self->top]) + 1);
        return pstr;
    }
}

Compiling and Running

This C extension file is compiled and dynamically or statically linked like previous examples; the file makefile.stack in the book's examples distribution handles the build like this:

PYLIB = /usr/bin
PYINC = /usr/include/python2.4

stacktype.dll: stacktyp.c
        gcc stacktyp.c -g -I$(PYINC) -shared -L$(PYLIB) -lpython2.4 -o $@

Once compiled, you can import the C module and make and use instances of the C type that it defines much as if it were a Python class. You would normally do this from a Python script, but the interactive prompt is a convenient place to test the basics:

.../PP3E/Integrate/Extend/Stacks$ python
>>> import stacktype                            # import C constructor module
>>> x = stacktype.Stack( )                           # make C type instance object
>>> x.push('new')                               # call C type methods
>>> x                                           # call C type print handler
[Stack:
0: 'new'
]

>>> x[0]                                        # call C type index handler
'new'
>>> y = stacktype.Stack( )                          # make another type instance
>>> for c in 'SPAM': y.push(c)                  # a distinct stack object
...
>>> y
[Stack:
3: 'M'
2: 'A'
1: 'P'
0: 'S'
]

>>> z = x + y                                   # call C type concat handler
>>> z
[Stack:
4: 'M'
3: 'A'
2: 'P'
1: 'S'
0: 'new'
]

>>> y.pop( )
'M'
>>> len(z), z[0], z[-1]                         # for loops work too (indexing)
(5, 'new', 'M')

>>> dir( stacktype)
['Stack', '_ _doc_ _', '_ _file_ _', '_ _name_ _', 'error']
>>> stacktype._ _file_ _
'stacktype.dll'

Timing the C Implementations

So how did we do on the optimization front this time? Let's resurrect that timer module we wrote back in Figure to compare the C stack module and type of this chapter to the Python stack module and classes we coded in Chapter 20. Figure calculates the system time in seconds that it takes to run tests on all of this book's stack implementations.

PP3E\Integrate\Extend\Stacks\exttime.py

#!/usr/local/bin/python
# time the C stack module and type extensions
# versus the object chapter's Python stack implementations

from PP3E.Dstruct.Basic.timer  import test      # second count function
from PP3E.Dstruct.Basic import stack1           # Python stack module
from PP3E.Dstruct.Basic import stack2           # Python stack class: +/slice
from PP3E.Dstruct.Basic import stack3           # Python stack class: tuples
from PP3E.Dstruct.Basic import stack4           # Python stack class: append/pop
import stackmod, stacktype                      # C extension type, module

from sys import argv
rept, pushes, pops, items = 200, 200, 200, 200  # default: 200 * (600 ops)
try:
    [rept, pushes, pops, items] = map(int, argv[1:])
except: pass
print 'reps=%d * [push=%d+pop=%d+fetch=%d]' % (rept, pushes, pops, items)

def moduleops(mod):
    for i in range(pushes): mod.push('hello')   # strings only for C
    for i in range(items):  t = mod.item(i)
    for i in range(pops):   mod.pop( )

def objectops(Maker):                           # type has no init args
    x = Maker( )                                     # type or class instance
    for i in range(pushes): x.push('hello')     # strings only for C
    for i in range(items):  t = x[i]
    for i in range(pops):   x.pop( )

# test modules: python/c
print "Python module:", test(rept, moduleops, stack1)
print "C ext module: ", test(rept, moduleops, stackmod), '\n'

# test objects: class/type
print "Python simple Stack:", test(rept, objectops, stack2.Stack)
print "Python tuple  Stack:", test(rept, objectops, stack3.Stack)
print "Python append Stack:", test(rept, objectops, stack4.Stack)
print "C ext type Stack:   ", test(rept, objectops, stacktype.Stack)

Running this script under Cygwin on Windows produces the following results (as usual, these are prone to change over time; these tests were run under Python 2.4 on a 1.2 GHz machine). As we saw before, the Python tuple stack is slightly better than the Python in-place append stack in typical use (when the stack is only pushed and popped), but it is slower when indexed. The first test here runs 200 repetitions of 200 stack pushes and pops, or 80,000 stack operations (200 x 400); times listed are test duration seconds:

.../PP3E/Integrate/Extend/Stacks$ python exttime.py 200 200 200 0
reps=200 * [push=200+pop=200+fetch=0]
Python module: 0.35
C ext module:  0.07

Python simple Stack: 0.381
Python tuple  Stack: 0.11
Python append Stack: 0.13
C ext type Stack:    0.07

.../PP3E/Integrate/Extend/Stacks$ python exttime.py 100 300 300 0
reps=100 * [push=300+pop=300+fetch=0]
Python module: 0.33
C ext module:  0.06

Python simple Stack: 0.321
Python tuple  Stack: 0.08
Python append Stack: 0.09
C ext type Stack:    0.06

At least when there are no indexing operations on the stack, as in these two tests (just pushes and pops), the C type is only slightly faster than the best Python stack (tuples). In fact, the difference seems trivial; it's not exactly the kind of performance issue that would generate a bug report.

The C module comes in at roughly five times faster than the Python module, but these results are flawed. The stack1 Python module tested here uses the same slow stack implementation as the Python "simple" stack (stack2). If it was recoded to use the tuple stack representation used in Chapter 20, its speed would be similar to the "tuple" figures listed here and almost identical to the speed of the C module in the first two tests:

.../PP3E/Integrate/Extend/Stacks$ python exttime.py 200 200 200 50
reps=200 * [push=200+pop=200+fetch=50]
Python module: 0.36
C ext module:  0.08

Python simple Stack: 0.401
Python tuple  Stack: 0.24
Python append Stack: 0.15
C ext type Stack:    0.08

.../PP3E/Integrate/Extend/Stacks$ python exttime.py
reps=200 * [push=200+pop=200+fetch=200]
Python module: 0.44
C ext module:  0.12

Python simple Stack: 0.431
Python tuple  Stack: 1.983
Python append Stack: 0.19
C ext type Stack:    0.1

But under the different usage patterns simulated in these two tests, the C type wins the race. It is about twice as fast as the best Python stack (append) when indexing is added to the test mix, as illustrated by the two preceding test runs that ran with a nonzero fetch count. Similarly, the C module would be twice as fast as the best Python module coding in this case as well.

In other words, the fastest Python stacks are essentially as good as the C stacks if you stick to pushes and pops, but the C stacks are roughly twice as fast if any indexing is performed. Moreover, since you have to pick one representation, if indexing is possible at all you would likely pick the Python append stack; assuming they represent the best case, C stacks would always be twice as fast.

Of course, the measured time differences are so small that in many applications you won't care. Even at one million iterations, the best Python stack is still less than half a second slower than the C stack type:

.../PP3E/Integrate/Extend/Stacks$$ python exttime.py 2000 250 250 0
reps=2000 * [push=250+pop=250+fetch=0]
Python module: 4.686
C ext module:  0.952

Python simple Stack: 4.987
Python tuple  Stack: 1.352
Python append Stack: 1.572
C ext type Stack:    0.941

Further, in many ways, this is not quite an apples-to-apples comparison. The C stacks are much more difficult to program, and they achieve their speed by imposing substantial functional limits (as coded, the C module and type overflow at 342 pushes: 342 * 6 > 2048). But as a rule of thumb, C extensions can not only integrate existing components for use in Python scripts, they can also optimize time-critical components of pure Python programs. In other scenarios, migration to C might yield an even larger speedup.

On the other hand, C extensions should generally be used only as a last resort. As we learned earlier, algorithms and data structures are often bigger influences on program performance than implementation language. The fact that Python-coded tuple stacks are very nearly as fast as the C stacks under common usage patterns speaks volumes about the importance of data structure representation. Installing the Psyco just-in-time compiler for Python code might erase the remaining difference completely, but we'll leave this as a suggested exercise.

Older Timing Results

Interestingly, Python grew much faster between this book's first and second editions, relative to C. In the first edition, the C type was still almost three times faster than the best Python stack (tuples), even when no indexing was performed. Today, as in the second edition, it's almost a draw. One might infer from this that C migrations have become one-third as important as they once were.

For comparison, here were the results of this script in the second edition of this book, run on a 650 MHz machine under Python 1.5.2 and Linux. The results were relatively similar, though typically six or more times slowerowing likely to both Python and machine speedups:

.../PP3E/Integrate/Extend/Stacks$ python exttime.py 200 200 200 0
reps=200 * [push=200+pop=200+fetch=0]
Python module: 2.09
C ext module:  0.68

Python simple Stack: 2.15
Python tuple  Stack: 0.68
Python append Stack: 1.16
C ext type Stack:    0.5

.../PP3E/Integrate/Extend/Stacks$ python exttime.py 100 300 300 0
reps=100 * [push=300+pop=300+fetch=0]
Python module: 1.86
C ext module:  0.52
Python simple Stack: 1.91
Python tuple  Stack: 0.51
Python append Stack: 0.87
C ext type Stack:    0.38

.../PP3E/Integrate/Extend/Stacks$ python exttime.py 200 200 200 50
reps=200 * [push=200+pop=200+fetch=50]
Python module: 2.17
C ext module:  0.79

Python simple Stack: 2.24
Python tuple  Stack: 1.94
Python append Stack: 1.25
C ext type Stack:    0.52

.../PP3E/Integrate/Extend/Stacks$ python exttime.py
reps=200 * [push=200+pop=200+fetch=200]
Python module: 2.42
C ext module:  1.1

Python simple Stack: 2.54
Python tuple  Stack: 19.09
Python append Stack: 1.54
C ext type Stack:    0.63

But Don't Do That EitherSWIG

You can code C types manually like thisand in some applications, this approach may make sense. But you don't necessarily have tobecause SWIG knows how to generate glue code for C++ classes, you can instead automatically generate all the C extension and wrapper class code required to integrate such a stack object, simply by running SWIG over an appropriate class declaration. The wrapped C++ class provides a multiple-instance datatype much like the C extension type presented in this section, but SWIG handles language integration details. The next section shows how.



 Python   SQL   Java   php   Perl 
 game development   web development   internet   *nix   graphics   hardware 
 telecommunications   C++ 
 Flash   Active Directory   Windows