Added the cProfile module.

Based on lsprof (patch #1212837) by Brett Rosen and Ted Czotter.
With further editing by Michael Hudson and myself.
History in svn repo: http://codespeak.net/svn/user/arigo/hack/misc/lsprof

* Module/_lsprof.c is the internal C module, Lib/cProfile.py a wrapper.
* pstats.py updated to display cProfile's caller/callee timings if available.
* setup.py and NEWS updated.
* documentation updates in the profiler section:
   - explain the differences between the three profilers that we have now
   - profile and cProfile can use a unified documentation, like (c)Pickle
   - mention that hotshot is "for specialized usage" now
   - removed references to the "old profiler" that no longer exists
* test updates:
   - extended test_profile to cover delicate cases like recursion
   - added tests for the caller/callee displays
   - added test_cProfile, performing the same tests for cProfile
* TO-DO:
   - cProfile gives a nicer name to built-in, particularly built-in methods,
     which could be backported to profile.
   - not tested on Windows recently!

3 files changed, 1015 insertions, 0 deletions

diff --git a/Modules/_lsprof.c b/Modules/_lsprof.c
new file mode 100644
index 0000000..81d88ea
--- /dev/null
+++ b/Modules/_lsprof.c
@@ -0,0 +1,867 @@
+#include "Python.h"
+#include "compile.h"
+#include "frameobject.h"
+#include "structseq.h"
+#include "rotatingtree.h"
+
+#if !defined(HAVE_LONG_LONG)
+#error "This module requires long longs!"
+#endif
+
+/*** Selection of a high-precision timer ***/
+
+#ifdef MS_WINDOWS
+
+#include <windows.h>
+
+static PY_LONG_LONG
+hpTimer(void)
+{
+	LARGE_INTEGER li;
+	QueryPerformanceCounter(&li);
+	return li.QuadPart;
+}
+
+static double
+hpTimerUnit(void)
+{
+	LARGE_INTEGER li;
+	if (QueryPerformanceFrequency(&li))
+		return 1000.0 / li.QuadPart;
+	else
+		return 0.001;  /* unlikely */
+}
+
+#else  /* !MS_WINDOWS */
+
+#ifndef HAVE_GETTIMEOFDAY
+#error "This module requires gettimeofday() on non-Windows platforms!"
+#endif
+
+#if (defined(PYOS_OS2) && defined(PYCC_GCC))
+#include <sys/time.h>
+#else
+#include <sys/resource.h>
+#include <sys/times.h>
+#endif
+
+static PY_LONG_LONG
+hpTimer(void)
+{
+	struct timeval tv;
+	PY_LONG_LONG ret;
+#ifdef GETTIMEOFDAY_NO_TZ
+	gettimeofday(&tv);
+#else
+	gettimeofday(&tv, (struct timezone *)NULL);
+#endif
+	ret = tv.tv_sec;
+	ret = ret * 1000000 + tv.tv_usec;
+	return ret;
+}
+
+static double
+hpTimerUnit(void)
+{
+	return 0.001;
+}
+
+#endif  /* MS_WINDOWS */
+
+/************************************************************/
+/* Written by Brett Rosen and Ted Czotter */
+
+struct _ProfilerEntry;
+
+/* represents a function called from another function */
+typedef struct _ProfilerSubEntry {
+	rotating_node_t header;
+	PY_LONG_LONG tt;
+	PY_LONG_LONG it;
+	long callcount;
+	long recursivecallcount;
+	long recursionLevel;
+} ProfilerSubEntry;
+
+/* represents a function or user defined block */
+typedef struct _ProfilerEntry {
+	rotating_node_t header;
+	PyObject *userObj; /* PyCodeObject, or a descriptive str for builtins */
+	PY_LONG_LONG tt; /* total time in this entry */
+	PY_LONG_LONG it; /* inline time in this entry (not in subcalls) */
+	long callcount; /* how many times this was called */
+	long recursivecallcount; /* how many times called recursively */
+	long recursionLevel;
+	rotating_node_t *calls;
+} ProfilerEntry;
+
+typedef struct _ProfilerContext {
+	PY_LONG_LONG t0;
+	PY_LONG_LONG subt;
+	struct _ProfilerContext *previous;
+	ProfilerEntry *ctxEntry;
+} ProfilerContext;
+
+typedef struct {
+	PyObject_HEAD
+	rotating_node_t *profilerEntries;
+	ProfilerContext *currentProfilerContext;
+	ProfilerContext *freelistProfilerContext;
+	int flags;
+	PyObject *externalTimer;
+	double externalTimerUnit;
+} ProfilerObject;
+
+#define POF_ENABLED     0x001
+#define POF_SUBCALLS    0x002
+#define POF_BUILTINS    0x004
+#define POF_NOMEMORY    0x100
+
+staticforward PyTypeObject PyProfiler_Type;
+
+#define PyProfiler_Check(op) PyObject_TypeCheck(op, &PyProfiler_Type)
+#define PyProfiler_CheckExact(op) ((op)->ob_type == &PyProfiler_Type)
+
+/*** External Timers ***/
+
+#define DOUBLE_TIMER_PRECISION   4294967296.0
+static PyObject *empty_tuple;
+
+static PY_LONG_LONG CallExternalTimer(ProfilerObject *pObj)
+{
+	PY_LONG_LONG result;
+	PyObject *o = PyObject_Call(pObj->externalTimer, empty_tuple, NULL);
+	if (o == NULL) {
+		PyErr_WriteUnraisable(pObj->externalTimer);
+		return 0;
+	}
+	if (pObj->externalTimerUnit > 0.0) {
+		/* interpret the result as an integer that will be scaled
+		   in profiler_getstats() */
+		result = PyLong_AsLongLong(o);
+	}
+	else {
+		/* interpret the result as a double measured in seconds.
+		   As the profiler works with PY_LONG_LONG internally
+		   we convert it to a large integer */
+		double val = PyFloat_AsDouble(o);
+		/* error handling delayed to the code below */
+		result = (PY_LONG_LONG) (val * DOUBLE_TIMER_PRECISION);
+	}
+	Py_DECREF(o);
+	if (PyErr_Occurred()) {
+		PyErr_WriteUnraisable((PyObject *) pObj);
+		return 0;
+	}
+	return result;
+}
+
+#define CALL_TIMER(pObj)	((pObj)->externalTimer ?		\
+					CallExternalTimer(pObj) :	\
+					hpTimer())
+
+/*** ProfilerObject ***/
+
+static PyObject *
+normalizeUserObj(PyObject *obj)
+{
+	PyCFunctionObject *fn;
+	if (!PyCFunction_Check(obj)) {
+		Py_INCREF(obj);
+		return obj;
+	}
+	/* Replace built-in function objects with a descriptive string
+	   because of built-in methods -- keeping a reference to
+	   __self__ is probably not a good idea. */
+	fn = (PyCFunctionObject *)obj;
+
+	if (fn->m_self == NULL) {
+		/* built-in function: look up the module name */
+		PyObject *mod = fn->m_module;
+		char *modname;
+		if (mod && PyString_Check(mod)) {
+			modname = PyString_AS_STRING(mod);
+		}
+		else if (mod && PyModule_Check(mod)) {
+			modname = PyModule_GetName(mod);
+			if (modname == NULL) {
+				PyErr_Clear();
+				modname = "__builtin__";
+			}
+		}
+		else {
+			modname = "__builtin__";
+		}
+		if (strcmp(modname, "__builtin__") != 0)
+			return PyString_FromFormat("<%s.%s>",
+						   modname,
+						   fn->m_ml->ml_name);
+		else
+			return PyString_FromFormat("<%s>",
+						   fn->m_ml->ml_name);
+	}
+	else {
+		/* built-in method: try to return
+			repr(getattr(type(__self__), __name__))
+		*/
+		PyObject *self = fn->m_self;
+		PyObject *name = PyString_FromString(fn->m_ml->ml_name);
+		if (name != NULL) {
+			PyObject *mo = _PyType_Lookup(self->ob_type, name);
+			Py_XINCREF(mo);
+			Py_DECREF(name);
+			if (mo != NULL) {
+				PyObject *res = PyObject_Repr(mo);
+				Py_DECREF(mo);
+				if (res != NULL)
+					return res;
+			}
+		}
+		PyErr_Clear();
+		return PyString_FromFormat("<built-in method %s>",
+					   fn->m_ml->ml_name);
+	}
+}
+
+static ProfilerEntry*
+newProfilerEntry(ProfilerObject *pObj, void *key, PyObject *userObj)
+{
+	ProfilerEntry *self;
+	self = (ProfilerEntry*) malloc(sizeof(ProfilerEntry));
+	if (self == NULL) {
+		pObj->flags |= POF_NOMEMORY;
+		return NULL;
+	}
+	userObj = normalizeUserObj(userObj);
+	if (userObj == NULL) {
+		PyErr_Clear();
+		free(self);
+		pObj->flags |= POF_NOMEMORY;
+		return NULL;
+	}
+	self->header.key = key;
+	self->userObj = userObj;
+	self->tt = 0;
+	self->it = 0;
+	self->callcount = 0;
+	self->recursivecallcount = 0;
+	self->recursionLevel = 0;
+	self->calls = EMPTY_ROTATING_TREE;
+	RotatingTree_Add(&pObj->profilerEntries, &self->header);
+	return self;
+}
+
+static ProfilerEntry*
+getEntry(ProfilerObject *pObj, void *key)
+{
+	return (ProfilerEntry*) RotatingTree_Get(&pObj->profilerEntries, key);
+}
+
+static ProfilerSubEntry * 
+getSubEntry(ProfilerObject *pObj, ProfilerEntry *caller, ProfilerEntry* entry)
+{
+	return (ProfilerSubEntry*) RotatingTree_Get(&caller->calls,
+						    (void *)entry);
+}
+
+static ProfilerSubEntry *
+newSubEntry(ProfilerObject *pObj,  ProfilerEntry *caller, ProfilerEntry* entry)
+{
+	ProfilerSubEntry *self;
+	self = (ProfilerSubEntry*) malloc(sizeof(ProfilerSubEntry));
+	if (self == NULL) {
+		pObj->flags |= POF_NOMEMORY;
+		return NULL;
+	}
+	self->header.key = (void *)entry;
+	self->tt = 0;
+	self->it = 0;
+	self->callcount = 0;
+	self->recursivecallcount = 0;
+	self->recursionLevel = 0;
+	RotatingTree_Add(&caller->calls, &self->header);
+	return self;
+}
+
+static int freeSubEntry(rotating_node_t *header, void *arg)
+{
+	ProfilerSubEntry *subentry = (ProfilerSubEntry*) header;
+	free(subentry);
+	return 0;
+}
+
+static int freeEntry(rotating_node_t *header, void *arg)
+{
+	ProfilerEntry *entry = (ProfilerEntry*) header;
+	RotatingTree_Enum(entry->calls, freeSubEntry, NULL);
+	Py_DECREF(entry->userObj);
+	free(entry);
+	return 0;
+}
+
+static void clearEntries(ProfilerObject *pObj)
+{
+	RotatingTree_Enum(pObj->profilerEntries, freeEntry, NULL);
+	pObj->profilerEntries = EMPTY_ROTATING_TREE;
+	/* release the memory hold by the free list of ProfilerContexts */
+	while (pObj->freelistProfilerContext) {
+		ProfilerContext *c = pObj->freelistProfilerContext;
+		pObj->freelistProfilerContext = c->previous;
+		free(c);
+	}
+}
+
+static void
+initContext(ProfilerObject *pObj, ProfilerContext *self, ProfilerEntry *entry)
+{
+	self->ctxEntry = entry;
+	self->subt = 0;
+	self->previous = pObj->currentProfilerContext;
+	pObj->currentProfilerContext = self;
+	++entry->recursionLevel;
+	if ((pObj->flags & POF_SUBCALLS) && self->previous) {
+		/* find or create an entry for me in my caller's entry */
+		ProfilerEntry *caller = self->previous->ctxEntry;
+		ProfilerSubEntry *subentry = getSubEntry(pObj, caller, entry);
+		if (subentry == NULL)
+			subentry = newSubEntry(pObj, caller, entry);
+		if (subentry)
+			++subentry->recursionLevel;
+	}
+	self->t0 = CALL_TIMER(pObj);
+}
+
+static void
+Stop(ProfilerObject *pObj, ProfilerContext *self, ProfilerEntry *entry)
+{
+	PY_LONG_LONG tt = CALL_TIMER(pObj) - self->t0;
+	PY_LONG_LONG it = tt - self->subt;
+	if (self->previous)
+		self->previous->subt += tt;
+	pObj->currentProfilerContext = self->previous;
+	if (--entry->recursionLevel == 0)
+		entry->tt += tt;
+	else
+		++entry->recursivecallcount;
+	entry->it += it;
+	entry->callcount++;
+	if ((pObj->flags & POF_SUBCALLS) && self->previous) {
+		/* find or create an entry for me in my caller's entry */
+		ProfilerEntry *caller = self->previous->ctxEntry;
+		ProfilerSubEntry *subentry = getSubEntry(pObj, caller, entry);
+		if (subentry) {
+			if (--subentry->recursionLevel == 0)
+				subentry->tt += tt;
+			else
+				++subentry->recursivecallcount;
+			subentry->it += it;
+			++subentry->callcount;
+		}
+	}
+}
+
+static void
+ptrace_enter_call(PyObject *self, void *key, PyObject *userObj)
+{
+	/* entering a call to the function identified by 'key'
+	   (which can be a PyCodeObject or a PyMethodDef pointer) */
+	ProfilerObject *pObj = (ProfilerObject*)self;
+	ProfilerEntry *profEntry;
+	ProfilerContext *pContext;
+
+	profEntry = getEntry(pObj, key);
+	if (profEntry == NULL) {
+		profEntry = newProfilerEntry(pObj, key, userObj);
+		if (profEntry == NULL)
+			return;
+	}
+	/* grab a ProfilerContext out of the free list */
+	pContext = pObj->freelistProfilerContext;
+	if (pContext) {
+		pObj->freelistProfilerContext = pContext->previous;
+	}
+	else {
+		/* free list exhausted, allocate a new one */
+		pContext = (ProfilerContext*)
+			malloc(sizeof(ProfilerContext));
+		if (pContext == NULL) {
+			pObj->flags |= POF_NOMEMORY;
+			return;
+		}
+	}
+	initContext(pObj, pContext, profEntry);
+}
+
+static void
+ptrace_leave_call(PyObject *self, void *key)
+{
+	/* leaving a call to the function identified by 'key' */
+	ProfilerObject *pObj = (ProfilerObject*)self;
+	ProfilerEntry *profEntry;
+	ProfilerContext *pContext;
+
+	pContext = pObj->currentProfilerContext;
+	if (pContext == NULL)
+		return;
+	profEntry = getEntry(pObj, key);
+	if (profEntry) {
+		Stop(pObj, pContext, profEntry);
+	}
+	else {
+		pObj->currentProfilerContext = pContext->previous;
+	}
+	/* put pContext into the free list */
+	pContext->previous = pObj->freelistProfilerContext;
+	pObj->freelistProfilerContext = pContext;
+}
+
+static int
+profiler_callback(PyObject *self, PyFrameObject *frame, int what,
+		  PyObject *arg)
+{
+	switch (what) {
+
+	/* the 'frame' of a called function is about to start its execution */
+	case PyTrace_CALL:
+		ptrace_enter_call(self, (void *)frame->f_code,
+				        (PyObject *)frame->f_code);
+		break;
+
+	/* the 'frame' of a called function is about to finish
+	   (either normally or with an exception) */
+	case PyTrace_RETURN:
+		ptrace_leave_call(self, (void *)frame->f_code);
+		break;
+
+	/* case PyTrace_EXCEPTION:
+		If the exception results in the function exiting, a
+		PyTrace_RETURN event will be generated, so we don't need to
+		handle it. */
+
+#ifdef PyTrace_C_CALL	/* not defined in Python <= 2.3 */
+	/* the Python function 'frame' is issuing a call to the built-in
+	   function 'arg' */
+	case PyTrace_C_CALL:
+		if ((((ProfilerObject *)self)->flags & POF_BUILTINS)
+		    && PyCFunction_Check(arg)) {
+			ptrace_enter_call(self,
+					  ((PyCFunctionObject *)arg)->m_ml,
+					  arg);
+		}
+		break;
+
+	/* the call to the built-in function 'arg' is returning into its
+	   caller 'frame' */
+	case PyTrace_C_RETURN:		/* ...normally */
+	case PyTrace_C_EXCEPTION:	/* ...with an exception set */
+		if ((((ProfilerObject *)self)->flags & POF_BUILTINS)
+		    && PyCFunction_Check(arg)) {
+			ptrace_leave_call(self,
+					  ((PyCFunctionObject *)arg)->m_ml);
+		}
+		break;
+#endif
+
+	default:
+		break;
+	}
+	return 0;
+}
+
+static int
+pending_exception(ProfilerObject *pObj)
+{
+	if (pObj->flags & POF_NOMEMORY) {
+		pObj->flags -= POF_NOMEMORY;
+		PyErr_SetString(PyExc_MemoryError,
+				"memory was exhausted while profiling");
+		return -1;
+	}
+	return 0;
+}
+
+/************************************************************/
+
+static PyStructSequence_Field profiler_entry_fields[] = {
+	{"code",         "code object or built-in function name"},
+	{"callcount",    "how many times this was called"},
+	{"reccallcount", "how many times called recursively"},
+	{"totaltime",    "total time in this entry"},
+	{"inlinetime",   "inline time in this entry (not in subcalls)"},
+	{"calls",        "details of the calls"},
+	{0}
+};
+
+static PyStructSequence_Field profiler_subentry_fields[] = {
+	{"code",         "called code object or built-in function name"},
+	{"callcount",    "how many times this is called"},
+	{"reccallcount", "how many times this is called recursively"},
+	{"totaltime",    "total time spent in this call"},
+	{"inlinetime",   "inline time (not in further subcalls)"},
+	{0}
+};
+
+static PyStructSequence_Desc profiler_entry_desc = {
+	"_lsprof.profiler_entry", /* name */
+	NULL, /* doc */
+	profiler_entry_fields,
+	6
+};
+
+static PyStructSequence_Desc profiler_subentry_desc = {
+	"_lsprof.profiler_subentry", /* name */
+	NULL, /* doc */
+	profiler_subentry_fields,
+	5
+};
+
+static PyTypeObject StatsEntryType;
+static PyTypeObject StatsSubEntryType;
+
+
+typedef struct {
+	PyObject *list;
+	PyObject *sublist;
+	double factor;
+} statscollector_t;
+
+static int statsForSubEntry(rotating_node_t *node, void *arg)
+{
+	ProfilerSubEntry *sentry = (ProfilerSubEntry*) node;
+	statscollector_t *collect = (statscollector_t*) arg;
+	ProfilerEntry *entry = (ProfilerEntry*) sentry->header.key;
+	int err;
+	PyObject *sinfo;
+	sinfo = PyObject_CallFunction((PyObject*) &StatsSubEntryType,
+				      "((Olldd))",
+				      entry->userObj,
+				      sentry->callcount,
+				      sentry->recursivecallcount,
+				      collect->factor * sentry->tt,
+				      collect->factor * sentry->it);
+	if (sinfo == NULL)
+		return -1;
+	err = PyList_Append(collect->sublist, sinfo);
+	Py_DECREF(sinfo);
+	return err;
+}
+
+static int statsForEntry(rotating_node_t *node, void *arg)
+{
+	ProfilerEntry *entry = (ProfilerEntry*) node;
+	statscollector_t *collect = (statscollector_t*) arg;
+	PyObject *info;
+	int err;
+	if (entry->callcount == 0)
+		return 0;   /* skip */
+
+	if (entry->calls != EMPTY_ROTATING_TREE) {
+		collect->sublist = PyList_New(0);
+		if (collect->sublist == NULL)
+			return -1;
+		if (RotatingTree_Enum(entry->calls,
+				      statsForSubEntry, collect) != 0) {
+			Py_DECREF(collect->sublist);
+			return -1;
+		}
+	}
+	else {
+		Py_INCREF(Py_None);
+		collect->sublist = Py_None;
+	}
+
+	info = PyObject_CallFunction((PyObject*) &StatsEntryType,
+				     "((OllddO))",
+				     entry->userObj,
+				     entry->callcount,
+				     entry->recursivecallcount,
+				     collect->factor * entry->tt,
+				     collect->factor * entry->it,
+				     collect->sublist);
+	Py_DECREF(collect->sublist);
+	if (info == NULL)
+		return -1;
+	err = PyList_Append(collect->list, info);
+	Py_DECREF(info);
+	return err;
+}
+
+PyDoc_STRVAR(getstats_doc, "\
+getstats() -> list of profiler_entry objects\n\
+\n\
+Return all information collected by the profiler.\n\
+Each profiler_entry is a tuple-like object with the\n\
+following attributes:\n\
+\n\
+    code          code object\n\
+    callcount     how many times this was called\n\
+    reccallcount  how many times called recursively\n\
+    totaltime     total time in this entry\n\
+    inlinetime    inline time in this entry (not in subcalls)\n\
+    calls         details of the calls\n\
+\n\
+The calls attribute is either None or a list of\n\
+profiler_subentry objects:\n\
+\n\
+    code          called code object\n\
+    callcount     how many times this is called\n\
+    reccallcount  how many times this is called recursively\n\
+    totaltime     total time spent in this call\n\
+    inlinetime    inline time (not in further subcalls)\n\
+");
+
+static PyObject*
+profiler_getstats(ProfilerObject *pObj, PyObject* noarg)
+{
+	statscollector_t collect;
+	if (pending_exception(pObj))
+		return NULL;
+	if (!pObj->externalTimer)
+		collect.factor = hpTimerUnit();
+	else if (pObj->externalTimerUnit > 0.0)
+		collect.factor = pObj->externalTimerUnit;
+	else
+		collect.factor = 1.0 / DOUBLE_TIMER_PRECISION;
+	collect.list = PyList_New(0);
+	if (collect.list == NULL)
+		return NULL;
+	if (RotatingTree_Enum(pObj->profilerEntries, statsForEntry, &collect)
+	    != 0) {
+		Py_DECREF(collect.list);
+		return NULL;
+	}
+	return collect.list;
+}
+
+static int
+setSubcalls(ProfilerObject *pObj, int nvalue)
+{
+	if (nvalue == 0)
+		pObj->flags &= ~POF_SUBCALLS;
+	else if (nvalue > 0)
+		pObj->flags |=  POF_SUBCALLS;
+	return 0;
+}
+
+static int
+setBuiltins(ProfilerObject *pObj, int nvalue)
+{
+	if (nvalue == 0)
+		pObj->flags &= ~POF_BUILTINS;
+	else if (nvalue > 0) {
+#ifndef PyTrace_C_CALL
+		PyErr_SetString(PyExc_ValueError,
+				"builtins=True requires Python >= 2.4");
+		return -1;
+#else
+		pObj->flags |=  POF_BUILTINS;
+#endif
+	}
+	return 0;
+}
+
+PyDoc_STRVAR(enable_doc, "\
+enable(subcalls=True, builtins=True)\n\
+\n\
+Start collecting profiling information.\n\
+If 'subcalls' is True, also records for each function\n\
+statistics separated according to its current caller.\n\
+If 'builtins' is True, records the time spent in\n\
+built-in functions separately from their caller.\n\
+");
+
+static PyObject*
+profiler_enable(ProfilerObject *self, PyObject *args, PyObject *kwds)
+{
+	int subcalls = -1;
+        int builtins = -1;
+	static const char *kwlist[] = {"subcalls", "builtins", 0};
+	if (!PyArg_ParseTupleAndKeywords(args, kwds, "|ii:enable",
+					 kwlist, &subcalls, &builtins))
+		return NULL;
+	if (setSubcalls(self, subcalls) < 0 || setBuiltins(self, builtins) < 0)
+		return NULL;
+	PyEval_SetProfile(profiler_callback, (PyObject*)self);
+	self->flags |= POF_ENABLED;
+	Py_INCREF(Py_None);
+	return Py_None;
+}
+
+static void
+flush_unmatched(ProfilerObject *pObj)
+{
+	while (pObj->currentProfilerContext) {
+		ProfilerContext *pContext = pObj->currentProfilerContext;
+		ProfilerEntry *profEntry= pContext->ctxEntry;
+		if (profEntry)
+			Stop(pObj, pContext, profEntry);
+		else
+			pObj->currentProfilerContext = pContext->previous;
+		if (pContext)
+			free(pContext);
+	}
+
+}
+
+PyDoc_STRVAR(disable_doc, "\
+disable()\n\
+\n\
+Stop collecting profiling information.\n\
+");
+
+static PyObject*
+profiler_disable(ProfilerObject *self, PyObject* noarg)
+{
+	self->flags &= ~POF_ENABLED;
+	PyEval_SetProfile(NULL, NULL);
+	flush_unmatched(self);
+	if (pending_exception(self))
+		return NULL;
+	Py_INCREF(Py_None);
+	return Py_None;
+}
+
+PyDoc_STRVAR(clear_doc, "\
+clear()\n\
+\n\
+Clear all profiling information collected so far.\n\
+");
+
+static PyObject*
+profiler_clear(ProfilerObject *pObj, PyObject* noarg)
+{
+	clearEntries(pObj);
+	Py_INCREF(Py_None);
+	return Py_None;
+}
+
+static void
+profiler_dealloc(ProfilerObject *op)
+{
+	if (op->flags & POF_ENABLED)
+		PyEval_SetProfile(NULL, NULL);
+	flush_unmatched(op);
+	clearEntries(op);
+	Py_XDECREF(op->externalTimer);
+	op->ob_type->tp_free(op);
+}
+
+static int
+profiler_init(ProfilerObject *pObj, PyObject *args, PyObject *kw)
+{
+	PyObject *o;
+	PyObject *timer = NULL;
+	double timeunit = 0.0;
+	int subcalls = 1;
+#ifdef PyTrace_C_CALL
+	int builtins = 1;
+#else
+	int builtins = 0;
+#endif
+	static const char *kwlist[] = {"timer", "timeunit",
+				       "subcalls", "builtins", 0};
+
+	if (!PyArg_ParseTupleAndKeywords(args, kw, "|Odii:Profiler", kwlist,
+					 &timer, &timeunit,
+					 &subcalls, &builtins))
+		return -1;
+
+	if (setSubcalls(pObj, subcalls) < 0 || setBuiltins(pObj, builtins) < 0)
+		return -1;
+	o = pObj->externalTimer;
+	pObj->externalTimer = timer;
+	Py_XINCREF(timer);
+	Py_XDECREF(o);
+	pObj->externalTimerUnit = timeunit;
+	return 0;
+}
+
+static PyMethodDef profiler_methods[] = {
+	{"getstats",    (PyCFunction)profiler_getstats,
+			METH_NOARGS,			getstats_doc},
+	{"enable",	(PyCFunction)profiler_enable,
+			METH_VARARGS | METH_KEYWORDS,	enable_doc},
+	{"disable",	(PyCFunction)profiler_disable,
+			METH_NOARGS,			disable_doc},
+	{"clear",	(PyCFunction)profiler_clear,
+			METH_NOARGS,			clear_doc},
+	{NULL, NULL}
+};
+
+PyDoc_STRVAR(profiler_doc, "\
+Profiler(custom_timer=None, time_unit=None, subcalls=True, builtins=True)\n\
+\n\
+    Builds a profiler object using the specified timer function.\n\
+    The default timer is a fast built-in one based on real time.\n\
+    For custom timer functions returning integers, time_unit can\n\
+    be a float specifying a scale (i.e. how long each integer unit\n\
+    is, in seconds).\n\
+");
+
+statichere PyTypeObject PyProfiler_Type = {
+	PyObject_HEAD_INIT(NULL)
+	0,                                      /* ob_size */
+	"_lsprof.Profiler",                     /* tp_name */
+	sizeof(ProfilerObject),                 /* tp_basicsize */
+	0,                                      /* tp_itemsize */
+	(destructor)profiler_dealloc,           /* tp_dealloc */
+	0,                                      /* tp_print */
+	0,                                      /* tp_getattr */
+	0,                                      /* tp_setattr */
+	0,                                      /* tp_compare */
+	0,                                      /* tp_repr */
+	0,                                      /* tp_as_number */
+	0,                                      /* tp_as_sequence */
+	0,                                      /* tp_as_mapping */
+	0,                                      /* tp_hash */
+	0,                                      /* tp_call */
+	0,                                      /* tp_str */
+	0,                                      /* tp_getattro */
+	0,                                      /* tp_setattro */
+	0,                                      /* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /* tp_flags */
+	profiler_doc,                           /* tp_doc */
+	0,                                      /* tp_traverse */
+	0,                                      /* tp_clear */
+	0,                                      /* tp_richcompare */
+	0,                                      /* tp_weaklistoffset */
+	0,                                      /* tp_iter */
+	0,                                      /* tp_iternext */
+	profiler_methods,                       /* tp_methods */
+	0,                                      /* tp_members */
+	0,                                      /* tp_getset */
+	0,                                      /* tp_base */
+	0,                                      /* tp_dict */
+	0,                                      /* tp_descr_get */
+	0,                                      /* tp_descr_set */
+	0,                                      /* tp_dictoffset */
+	(initproc)profiler_init,                /* tp_init */
+	PyType_GenericAlloc,                    /* tp_alloc */
+	PyType_GenericNew,                      /* tp_new */
+	PyObject_Del,                           /* tp_free */
+};
+
+static PyMethodDef moduleMethods[] = {
+	{NULL, NULL}
+};
+
+PyMODINIT_FUNC
+init_lsprof(void)
+{
+	PyObject *module, *d;
+	module = Py_InitModule3("_lsprof", moduleMethods, "Fast profiler");
+	d = PyModule_GetDict(module);
+	if (PyType_Ready(&PyProfiler_Type) < 0)
+		return;
+	PyDict_SetItemString(d, "Profiler", (PyObject *)&PyProfiler_Type);
+
+	PyStructSequence_InitType(&StatsEntryType, &profiler_entry_desc);
+	PyStructSequence_InitType(&StatsSubEntryType, &profiler_subentry_desc);
+	Py_INCREF((PyObject*) &StatsEntryType);
+	Py_INCREF((PyObject*) &StatsSubEntryType);
+	PyModule_AddObject(module, "profiler_entry",
+			   (PyObject*) &StatsEntryType);
+	PyModule_AddObject(module, "profiler_subentry",
+			   (PyObject*) &StatsSubEntryType);
+	empty_tuple = PyTuple_New(0);
+}
diff --git a/Modules/rotatingtree.c b/Modules/rotatingtree.c
new file mode 100644
index 0000000..952725b
--- /dev/null
+++ b/Modules/rotatingtree.c
@@ -0,0 +1,121 @@
+#include "rotatingtree.h"
+
+#define KEY_LOWER_THAN(key1, key2)  ((char*)(key1) < (char*)(key2))
+
+/* The randombits() function below is a fast-and-dirty generator that
+ * is probably irregular enough for our purposes.  Note that it's biased:
+ * I think that ones are slightly more probable than zeroes.  It's not
+ * important here, though.
+ */
+
+static unsigned int random_value = 1;
+static unsigned int random_stream = 0;
+
+static int
+randombits(int bits)
+{
+	int result;
+	if (random_stream < (1<<bits)) {
+		random_value *= 1082527;
+		random_stream = random_value;
+	}
+	result = random_stream & ((1<<bits)-1);
+	random_stream >>= bits;
+	return result;
+}
+
+
+/* Insert a new node into the tree.
+   (*root) is modified to point to the new root. */
+void
+RotatingTree_Add(rotating_node_t **root, rotating_node_t *node)
+{
+	while (*root != NULL) {
+		if (KEY_LOWER_THAN(node->key, (*root)->key))
+			root = &((*root)->left);
+		else
+			root = &((*root)->right);
+	}
+	node->left = NULL;
+	node->right = NULL;
+	*root = node;
+}
+
+/* Locate the node with the given key.  This is the most complicated
+   function because it occasionally rebalances the tree to move the
+   resulting node closer to the root. */
+rotating_node_t *
+RotatingTree_Get(rotating_node_t **root, void *key)
+{
+	if (randombits(3) != 4) {
+		/* Fast path, no rebalancing */
+		rotating_node_t *node = *root;
+		while (node != NULL) {
+			if (node->key == key)
+				return node;
+			if (KEY_LOWER_THAN(key, node->key))
+				node = node->left;
+			else
+				node = node->right;
+		}
+		return NULL;
+	}
+	else {
+		rotating_node_t **pnode = root;
+		rotating_node_t *node = *pnode;
+		rotating_node_t *next;
+		int rotate;
+		if (node == NULL)
+			return NULL;
+		while (1) {
+			if (node->key == key)
+				return node;
+			rotate = !randombits(1);
+			if (KEY_LOWER_THAN(key, node->key)) {
+				next = node->left;
+				if (next == NULL)
+					return NULL;
+				if (rotate) {
+					node->left = next->right;
+					next->right = node;
+					*pnode = next;
+				}
+				else
+					pnode = &(node->left);
+			}
+			else {
+				next = node->right;
+				if (next == NULL)
+					return NULL;
+				if (rotate) {
+					node->right = next->left;
+					next->left = node;
+					*pnode = next;
+				}
+				else
+					pnode = &(node->right);
+			}
+			node = next;
+		}
+	}
+}
+
+/* Enumerate all nodes in the tree.  The callback enumfn() should return
+   zero to continue the enumeration, or non-zero to interrupt it.
+   A non-zero value is directly returned by RotatingTree_Enum(). */
+int
+RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
+		  void *arg)
+{
+	int result;
+	rotating_node_t *node;
+	while (root != NULL) {
+		result = RotatingTree_Enum(root->left, enumfn, arg);
+		if (result != 0) return result;
+		node = root->right;
+		result = enumfn(root, arg);
+		if (result != 0) return result;
+		root = node;
+	}
+	return 0;
+}
diff --git a/Modules/rotatingtree.h b/Modules/rotatingtree.h
new file mode 100644
index 0000000..97cc8e8
--- /dev/null
+++ b/Modules/rotatingtree.h
@@ -0,0 +1,27 @@
+/* "Rotating trees" (Armin Rigo)
+ *
+ * Google "splay trees" for the general idea.
+ *
+ * It's a dict-like data structure that works best when accesses are not
+ * random, but follow a strong pattern.  The one implemented here is for
+ * accesses patterns where the same small set of keys is looked up over
+ * and over again, and this set of keys evolves slowly over time.
+ */
+
+#include <stdlib.h>
+
+#define EMPTY_ROTATING_TREE       ((rotating_node_t *)NULL)
+
+typedef struct rotating_node_s rotating_node_t;
+typedef int (*rotating_tree_enum_fn) (rotating_node_t *node, void *arg);
+
+struct rotating_node_s {
+	void *key;
+	rotating_node_t *left;
+	rotating_node_t *right;
+};
+
+void RotatingTree_Add(rotating_node_t **root, rotating_node_t *node);
+rotating_node_t* RotatingTree_Get(rotating_node_t **root, void *key);
+int RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
+		      void *arg);