\documentclass[12pt]{article}
\title{Profiler internals}
\author{Nick Smallbone}
\usepackage[dvips]{graphicx}
\usepackage{dottex}

\begin{document}
\newenvironment{note}
{\rule{1ex}{1ex}\hspace{1ex}\textbf{Note: }\ignorespaces}{}

\maketitle
\tableofcontents
\newpage

\section{Introduction}

This document shows how the profiler works internally, a little bit. The details
of it aren't going to be correct forever: the design is still changing quite
quickly.

\section{The scanner}

The scanner's job is to start from a set of roots, find as many objects as it
can reach from those, and collect as much information as it can about each
object into a wrapper.

It's the only part of the profiler that should poke objects
directly---everything else should just look at the wrappers. So it's important
that each wrapper contains enough information.

\subsection{Collecting objects}

The best way to show how the scanner works is probably through an example.
We'll look at what the scanner does when asked to scan \verb|ls|, where 
\verb|ls| is defined as:
\begin{verbatim}
ls = [1,2]
ls.append(ls)
\end{verbatim}

The references from \verb|ls| look like:

\begin{dotpic}
ls [label = "ls = [1, 2, ls]"];
ls -> 1;
ls -> 2;
ls -> ls;
\end{dotpic}

The scanner will be started by a call to \verb|scanner.Objects(ls)|, which will
call \verb|scanner.scan(ls)|.

It keeps a queue of objects waiting to be scanned, and a dictionary which stores
wrappers for already-scanned objects (it maps from \verb|id(object)| to a
wrapper).

To begin with, the dictionary will be empty and the queue will only contain
\verb|ls|.

The scanner will take \verb|ls| off the queue, and find a class which can be
used to count it. The next section talks about how it finds that class.

Then it makes an instance of that class, passing \verb|ls| to the constructor.
That will result in a wrapper, which it enters in the wrappers dictionary:

\begin{dotpic}
wrappers [shape=record, label="wrappers | <ls>id(ls)"];
lswrap [label="wrapper(ls)"]

wrappers:ls -> lswrap;
lswrap -> ls;
lswrap -> 1;
lswrap -> 2;

edge [style=dotted];
ls -> 1;
ls -> 2;
ls -> ls;

edge [style=dashed];
lswrap -> ls;
\end{dotpic}

The wrapper contains a field \verb|children|, which is a list of child objects
referenced by the parent object. The solid arrows represent these here.
The dotted arrows are references between the original objects.
The dashed arrows are between a wrapper and its object.

\begin{note}
A lot of important details of the wrapper have been left out---only
what matters to the scanner is left. See the HappyDoc-documentation for details
of what's there.
\end{note}

Now the scanner will add all of the object's children---\verb|1|, \verb|2| and
\verb|ls|---to the queue. It will then take \verb|1| from the queue, and again
will find a wrapper class, use that to make a new wrapper and add that wrapper
to the wrappers dictionary.

It will do the same with \verb|2|. Since \verb|1| and \verb|2| have no child
references, nothing will be added to the queue.

Then it will take \verb|ls| off the queue\footnote{It was added along with
1 and 2.} and see that it's already been counted (since
\verb|id(ls)| is in the dictionary).

So the queue will become empty, and now the scanner will have built a
dictionary of wrappers:

\begin{dotpic}
wrappers [shape=record, label="wrappers | <1>id(1) | <ls>id(ls) | <2>id(2)"];
wrapls [label="wrapper(ls)"]
wrap1 [label="wrapper(1)"]
wrap2 [label="wrapper(2)"]

wrappers:ls -> wrapls;
wrappers:1 -> wrap1;
wrappers:2 -> wrap2;
wrapls -> ls;
wrapls -> 1;
wrapls -> 2;

edge [style=dotted];
ls -> 1;
ls -> 2;
ls -> ls;

edge [style=dashed];
wrapls -> ls;
wrap1 -> 1;
wrap2 -> 2;
\end{dotpic}

Here, \verb|wrapper(ls)| contains references to \verb|1|, \verb|2| and
\verb|ls| directly. 

% The final step is to change these references to point
% at the wrappers rather than the objects.
%The scanner does this by calling the \verb|liftrefs| method of each wrapper,
%which changes the references itself. This will result in:

% Should change layout manually, so all objects are below all wrappers

%\begin{dotpic}
%wrappers [shape=record, label="wrappers | <1>id(1) | <ls>id(ls) | <2>id(2)"];

%wrapls [label="wrapper(ls)"]
%wrap1 [label="wrapper(1)"]
%wrap2 [label="wrapper(2)"]

%wrappers:ls -> wrapls;
%wrappers:1 -> wrap1;
%wrappers:2 -> wrap2;
%wrapls -> wrapls;
%wrapls -> wrap1;
%wrapls -> wrap2;

%edge [style=dotted];
%ls -> 1;
%ls -> 2;
%ls -> ls;

%edge [style=dashed];
%wrapls -> ls;
%wrap1 -> 1;
%wrap2 -> 2;

%\end{dotpic}

% decorators...

In this way the scanner has found all objects that can be reached from \verb|ls|
and constructed a set of wrappers that ``mirrors'' the set of objects.

\subsection{Constructing wrapper types}

This section describes how the scanner finds a wrapper class for each object.

All necessary information is contained in the \verb|sizes| module. There are
four dictionaries which map from \verb|id(something)| to wrapper class.

Here are the first three. If the \verb|id| of the object, or type of the
object, as appropriate, is found in one of these, the wrapper class associated
with it is used without looking further. They are tried in this order:

\begin{itemize}
\item \verb|sizes.object|---maps from object id to wrapper class.

This is useful when some single objects need to be treated specially.

\item \verb|sizes.wholetype|---maps from type id to wrapper class.

Subclasses of the type do not match this - only the exact type given.
This dictionary is normally not filled manually, but by the scanner as it finds
new types, using \verb|sizes.type| (see below).

\item \verb|sizes.instance|---maps from type id to wrapper class.
Each entry matches any (non-proper) subclass of the type id.

This can be used to tag objects specially by deriving them from some class.
For example, any object deriving from \verb|wrapper.ignored| is given a
size of 0 and no children by an entry in here.
\end{itemize}

If any of those three match, the wrapper class is found very quickly.
But complex objects are possible, through inheritance. Every possible compound
type can't be kept, so instead the scanner generates new wrapper classes from
the entries in \verb|sizes.type|.

Each entry is a wrapper class for a single type, excluding its base classes.
The scanner, when given an object of an unknown type, will find its
MRO\footnote{Method resolution order---a list of all superclasses.}, look up
each class found there in \verb|sizes.type| to get a list of wrapper classes,
and make a new wrapper class which inherits from all those it found.

It will then put the new wrapper class in \verb|sizes.wholetype|, so that it
won't have to be generated again for this type.

For example (this is not a valid class, but never mind),
\begin{verbatim}
class ListDict(list, dict):
    pass
\end{verbatim}
would, if it was valid, have a MRO of (list, dict, object). The scanner will
find
\begin{verbatim}
sizes.type[id(list)] == ListObject
sizes.type[id(dict)] == DictObject
sizes.type[id(object)] == GCObject
\end{verbatim}
and will construct a compound wrapper class:
\begin{verbatim}
class ListDictObject(ListObject, DictObject, GCObject):
    pass
sizes.wholetype[ListDict] = ListDictObject
\end{verbatim}
and instantiate \verb|ListDictObject| to get a wrapper for a \verb|ListDict|
instance.

There's one other complication: entries in the dictionaries don't
\emph{have} to be ids. They can also be direct object or type references
(where these are hashable) or, in the case of types, the name of the type
(useful where it's hard to find an instance of the type or the type itself
to put into the dictionary).

For example, DictObject could be entered into \verb|sizes.type[id(dict)]|,
\verb|sizes.type[dict]| or \verb|sizes.type["__builtin__.dict"]|. When the
scanner encounters it there it will turn it into the id form anyway.

\subsubsection{Built-in wrapper types}

These classes are defined in \verb|wrapper.py|, and aren't specific (hopefully)
to any particular implementation of Python:

\begin{itemize}
\item \verb|ObjectWrapper|---this is the base class for all wrappers. It defines
various functions which are used by the scanner, for example \verb|liftrefs|.
It defines enough that most subclasses only need to override the \verb|__init__|
function (to add type-specific code).

\item \verb|ZeroObject|---this is just \verb|ObjectWrapper| in disguise. When
given an object it will give it a size of 0 and no children.
\end{itemize}

\subsubsection{CPython-specific wrapper types}

These classes are defined in \verb|cpython/rules.py| and
\verb|cpython/crules.pyx|, and are CPython-specific.

\begin{itemize}
\item \verb|BaseObject|---this used to do something interesting, but now is yet
another alias for \verb|ObjectWrapper|\ldots

\item \verb|SimpleObject|---using \verb|str| on an instance of this class will
print out the wrapped object (whereas \verb|ObjectWrapper| will only mention
the type).

\item \verb|GCObject|---instances of this class will ask the garbage collector
what references the parent object has to find children. \verb|object|'s entry
in \verb|sizes.type| uses this, so any type that doesn't go out of its way
to do otherwise will use this.

\item \verb|SimpleGCObject|---a descendant of \verb|SimpleObject| and
\verb|GCObject|.

\item \verb|Object|---counts any instance of \verb|object|.
It uses the object's type's \verb|__basicsize__| as the size of the object.

\item \verb|ListObject|, \verb|TupleObject|, \verb|StringObject|,
\verb|UnicodeObject|, \\ \verb|DictObject|, \verb|SetObject|, \verb|FrameObject|,
\verb|SliceObject|, \\ \verb|InstanceObject|, \verb|ModuleObject|,
\verb|DictIterObject|, \verb|LongObject|, \\ \verb|CodeObject|,
\verb|FileWrapper|---wrapper classes for various types.
\end{itemize}

There is also an extension module, \verb|utils.c|, which contains a few
functions used by the wrapper classes.

\subsubsection{Other CPython-specific code}
\verb|cpython/rules.py| contains a couple of other CPython-specific functions
that are used by the rest of the profiler:

\begin{itemize}
\item \verb|getname(t)|---given a type object, produce a vaguely sensible name
for it. The scanner uses it to allow entering type names instead of types
into the various \verb|sizes| dictionaries.

\item \verb|roots()|---returns a list of objects which should be used as roots
if none are specified in the call to \verb|scan|. A sensible thing to use for
this is \verb|sys._getframe()|.

The function must return roots only and not all objects! In other words, it
should return a few objects from which everything else can be reached in a
top-down way. This is so that the scanner can ignore wrappers - it will go no
further if it encounters a wrapper object, but if \verb|roots()| returns parts 
of a wrapper, the scanner will have no way of knowing and will count them
anyway. And it's not very useful to be told that all the memory is being used
by wrappers :-)

So \verb|gc.get_objects()| is \emph{not} a suitable implementation of
\verb|roots()|.
\end{itemize}

\section{Possible extensions}

These aren't thought out very well yet---they're just ideas.

\subsection{Virtual objects}

The scanner only counts real Python objects---in CPython, ones which are represented by a \verb|PyObject *|. \ldots It might be useful to be able to represent things like shared libraries as well.\footnote{Although perhaps not, since data from a program image normally uses copy-on-write.}

These could be represented by wrappers which didn't refer to a real object, but instead to some dummy object just used to give the wrapper \emph{something} to refer to.

In fact this can be done without changing the scanner, like so:

\begin{itemize}
\item Define a \verb|VirtualObject| class which carries around with it size and reference information. 
\item Define a \verb|VirtualWrapper| class which, when it is instantiated with a \verb|VirtualObject|, just asks the \verb|VirtualObject| for its size and references.
\item Set \verb|sizes.instance[VirtualObject] = VirtualWrapper|.
\end{itemize}

Then code which wants to reference a non-Python object can just give a \verb|VirtualObject| instance as one of its children. The scanner will see the entry in \verb|sizes.instance| and instantiate a \verb|VirtualWrapper| on the object, and everything will just work :-).

Well, not quite. If the object is a shared library, it will contain definitions of other Python objects, so parts will be counted twice. This problem appears again below.

\subsection{Overlapping objects}

Some of the Python objects counted are tiny and it seems pedantic to count them separately.

For example, you might expect a wrapper for a module to contain references to everything defined at the top level of the module. Instead, it just contains a reference to the module's dictionary---and the dictionary contains the references to objects.

It would be nice to collapse the module and its dictionary into a single wrapper. But that can't be done yet, because there might be direct references to the dictionary.

I'm not sure how to fix that. Perhaps having views, or something like that, would help\ldots{}in any case, a good solution to this would also fix the problem with virtual objects above, since a raw C object containing a Python object somewhere could be represented as a virtual object overlapping with a Python object.

\end{document}