slides.tex

\documentclass[xcolor=svgnames]{beamer} 
%\usecolortheme[named=PowderBlue]{structure} %structure
\usecolortheme{beaver} %structure
\useoutertheme{infolines} 
%\usetheme[height=7mm]{CambridgeUS} %Rochester
\usetheme{CambridgeUS} %Rochester
\setbeamertemplate{items}[ball] 
\setbeamertemplate{blocks}[rounded][shadow=true] 
\setbeamertemplate{navigation symbols}{} 

\usepackage{xeCJK}
\setCJKmainfont{Hiragino Sans GB}
\usepackage{tikz}
\usepackage{listings}
\usetikzlibrary{shapes,arrows}

\usepackage{color}
 
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
 
\lstset{ %
  %language=C,                % the language of the code
  basicstyle=\footnotesize,           % the size of the fonts that are used for the code
  %numbers=left,                   % where to put the line-numbers
  %numberstyle=\tiny\color{gray},  % the style that is used for the line-numbers
  %stepnumber=2,                   % the step between two line-numbers. If it's 1, each line 
                                  % will be numbered
  numbersep=5pt,                  % how far the line-numbers are from the code
  backgroundcolor=\color{white},      % choose the background color. You must add \usepackage{color}
  showspaces=false,               % show spaces adding particular underscores
  showstringspaces=false,         % underline spaces within strings
  showtabs=false,                 % show tabs within strings adding particular underscores
  frame=single,                   % adds a frame around the code
  rulecolor=\color{black},        % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. commens (green here))
  tabsize=4,                      % sets default tabsize to 2 spaces
  captionpos=b,                   % sets the caption-position to bottom
  breaklines=true,                % sets automatic line breaking
  breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
  title=\lstname,                   % show the filename of files included with \lstinputlisting;
                                  % also try caption instead of title
  keywordstyle=\color{blue},          % keyword style
  commentstyle=\color{dkgreen},       % comment style
  stringstyle=\color{mauve},         % string literal style
  escapeinside={\%*}{*)},            % if you want to add LaTeX within your code
  morekeywords={*,...}               % if you want to add more keywords to the set
}

\hypersetup{ pdfpagemode={FullScreen}}

\title{PYTHON NOTES}
\subtitle{with internals}
\author{Yang Bo}
\institute[Admaster]{
    RDBJ \\
    Admaster
}
\date{2015.5.25}

\begin{document}

\begin{frame}[plain]
  \titlepage
\end{frame}
%----------- slide -------------%
\begin{frame}{Outline of the talk} 
 
\begin{itemize} 
  \item Python Object
  \item Built-in Types 
  \item Memory Management
  \item Reference Count and GC
  \item ENV: Python in this slides means CPython2.7.6
\end{itemize} 
 
\end{frame} 

%------------ python object /pyobject--------%
\begin{frame}[fragile]{Python Object}
    \begin{lstlisting}[language=C]{object.h}
#define PyObject_HEAD                   \
    _PyObject_HEAD_EXTRA                \
    Py_ssize_t ob_refcnt;               \
    struct _typeobject *ob_type;

typedef struct _object {
    PyObject_HEAD
} PyObject;

#define PyObject_VAR_HEAD               \
    PyObject_HEAD                       \
    Py_ssize_t ob_size; /* Number of items in variable part */

typedef struct {
    PyObject_VAR_HEAD
} PyVarObject;
\end{lstlisting} 
\end{frame}

%----------- python object/ pyobject -------------%
\begin{frame}{Python Object}
  \begin{itemize}
    \item Foundations of Everything(interally)
    \item Not change size once created
    \item PyObject / PyVarObject
    \item Reference Count
    \item Type Info: \_teypeobject
    \item Size Info
    \item Layout
  \end{itemize}
\end{frame}

%----------- python object/ pyobject -------------%
\begin{frame}[fragile]{Python Object}
  \begin{itemize}
    \item inheritance 
    \item polymorphism using PyObject
    \item use PyObject * not PyXXObject * when communicating
  \end{itemize}
\begin{lstlisting}[language=C]{object.c}
long PyObject_Hash(PyObject *v) {
    PyTypeObject *tp = v->ob_type;
    if (tp->tp_hash != NULL)
        return (*tp->tp_hash)(v);
    ......
}
\end{lstlisting} 
\end{frame}

%------------ python object --------%
\begin{frame}[fragile]{Python Object}
    \begin{lstlisting}[language=C]{object.h}
#define _Py_Dealloc(op) (                               \
    _Py_INC_TPFREES(op) _Py_COUNT_ALLOCS_COMMA          \
    (*Py_TYPE(op)->tp_dealloc)((PyObject *)(op)))
#endif /* !Py_TRACE_REFS */

#define Py_INCREF(op) (                         \
    _Py_INC_REFTOTAL  _Py_REF_DEBUG_COMMA       \
    ((PyObject*)(op))->ob_refcnt++)

#define Py_DECREF(op)                                   \
    do {                                                \
        if (_Py_DEC_REFTOTAL  _Py_REF_DEBUG_COMMA       \
        --((PyObject*)(op))->ob_refcnt != 0)            \
            _Py_CHECK_REFCNT(op)                        \
        else                                            \
        _Py_Dealloc((PyObject *)(op));                  \
    } while (0)
\end{lstlisting} 
\end{frame}


%------------ python object / object and type--------%
\begin{frame}[fragile]{Python Object/object and type}
    <type 'object'> and <type 'type'>
    \begin{itemize}
        \item 'object' in python is PyBaseObject\_Type indeed, not PyObject
        \item 'object' is base class of everything, including 'type'
        \item type of all types is 'type'
        \item type of 'object' is 'type'
    \end{itemize}
    \begin{lstlisting}[language=C]{object.h}
PyAPI_DATA(PyTypeObject) PyType_Type; /* built-in 'type' */
PyAPI_DATA(PyTypeObject) PyBaseObject_Type; /* built-in 'object' */
    \end{lstlisting} 
\end{frame}

%------------ python object / example --------%
\begin{frame}[fragile]{Python Object/example}
    \begin{figure}
       \begin{center}
       \includegraphics[width=10cm, height=8cm]{pystring_inheritance.png}
       \end{center}
\end{figure}
\end{frame}

%------------ built-in types / int/ intobject--------%
\begin{frame}[fragile]{Built-in Types/Integer}
\begin{lstlisting}[language=C]{intobject.h}
typedef struct {
    PyObject_HEAD
    long ob_ival;
} PyIntObject;
\end{lstlisting} 
\end{frame}

%------------ built-in types / int / general--------%
\begin{frame}{Built-in Types/Integer}
\begin{itemize} 
    \item cache small: [-5, 257)
  \item cache block: PyIntBlock, each 82
  \item block\_list and free\_list
  \item gc: int\_dealloc
  \item memory usage: largest quantity of integers at one exact time, not how many integers totally had in history
\end{itemize}
\end{frame}

%------------ built-in types / int / efficiency --------%
\begin{frame}[fragile]{Built-in Types/Integer}
\begin{lstlisting}[language=Python]
In [6]: %timeit float("1233")
The slowest run took 13.29 times longer than the fastest. This could mean that an intermediate result is being cached
1000000 loops, best of 3: 233 ns per loop

In [7]: %timeit int("1233")
The slowest run took 5.72 times longer than the fastest. This could mean that an intermediate result is being cached
1000000 loops, best of 3: 708 ns per loop
\end{lstlisting} 
Why?
Let's observe int\_new(objects/intobjects.c) and float\_new(objects/floatobjects.c).
\end{frame}

%------------ python object / string / stringobject--------%
\begin{frame}[fragile]{Built-in Types/String}
\begin{lstlisting}[language=C]{stringobject.h}
typedef struct {
    PyObject_VAR_HEAD
    long ob_shash; // init as -1
    int ob_sstate; // whether interned
    char ob_sval[1]; //trick, 'cos this is not only for gnu c
} PyStringObject;
\end{lstlisting} 
\end{frame}


%------------ python object /string / intern--------%
\begin{frame}{Built-in Types/String}
\begin{itemize} 
  \item not changable.
      \begin{itemize}
        \item the good: used as key in dict
        \item the bad: efficiency in join
      \end{itemize}
  \item you can have \textbackslash0 in your string, for size is determined by ob\_size and tp\_itemsize
  \item PyString\_FromString PyString\_FromStringAndSize
  \item intern
    \end{itemize} 
\end{frame}

%------------ python object / string / memory layout example--------%
\begin{frame}[fragile]{Built-in Types/String}
    \begin{figure}
       \begin{center}
       \includegraphics[width=10cm, height=3.5cm]{pystring_memory.png}
       \end{center}
\end{figure}
\end{frame}

%------------ python object /string--------%
\begin{frame}{Built-in Types/String}
intern
\begin{itemize} 
        \item a cache mechanism, working with hash can speed up python by 20\%
        \item happens at compile time, not run time
        \item by default, only cache strings consist of numbers, alphabets and underscores, but built-in intern() can be used to cache any string.
        \item internaly, use a dict <PyObject *, PyObject *> named 'interned' to store, and the two refs in interned don't count.
        \item nullstring and characters array use intern
        \item names like "\_\_name\_\_", "\_\_doc\_\_" are interned
        \item see implementations in codeobject.c stringobject.c
\end{itemize} 
\end{frame}

%------------ python object /string--------%
\begin{frame}{Built-in Types/String}
efficiency of "+="/"+" and "join"
\begin{itemize}
    \item string\_join allocate memory once for all the items
    \item += and + allocate memory everytime it executes, but optimized for short string, which resize the lvalue. see BINARY\_ADD, INPLACE\_ADD, string\_concatenate in Python/ceval.c
    \item older version of concatenate is string\_concat in Object/stringobject.c which malloc a new memory
\end{itemize}
PEP8: do not rely on CPython's efficient implementation of in-place string concatenation for statements in the form a += b or a = a + b . This optimization is fragile even in CPython (it only works for some types) and isn't present at all in implementations that don't use refcounting. 
\end{frame}

%------------ python object /string--------%
\begin{frame}{Built-in Types/String}
stringlib fastsearch 
\begin{itemize}
    \item based on a mix between boyer-moore and horspool
    \item 'in' operation
\end{itemize}
\end{frame}

%------------ python object / list--------%
\begin{frame}[fragile]{Built-in Types/List}
\begin{lstlisting}[language=C]{listobject.h}
typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;
    /* ob_item contains space for 'allocated' elements.  The number * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     * Items must normally not be NULL, except during construction when * the list is not yet visible outside the function that builds it.  */
    Py_ssize_t allocated;
} PyListObject;
\end{lstlisting} 
\end{frame}

%------------ python object /list --------%
\begin{frame}{Built-in Types/List}
\begin{itemize} 
  \item ob\_size and allocated is like size and capacity of vector in c++
  \item only one method to init: PyList\_New
  \item cache mechanism: free\_list, which hold 80 objects
  \item list\_dealloc to return PyListObject to free\_list
  \item memory management in list\_resize:
    \begin{itemize} 
        \item newsize < allocated \&\& newsize > allocated/2, no need to realloc
        \item (0, 4, 8, 16, 25, 35, 46, 58, 72, 88)
        \item otherwise shrink or enlarge
    \end{itemize} 
\end{itemize} 
\end{frame}

%------------ python object /list --------%
\begin{frame}{Built-in Types/List}
misc notes
\begin{itemize} 
    \item insert when > len(list) or < -len(list)
    \item xrange / range
    \item tim sort
    \item consider array
    \item consider tuple
        \begin{itemize} 
            \item allocate once
            \item cache 2000, each <20 elements
            \item read-only, better fit for concurrency
        \end{itemize} 
\end{itemize} 
\end{frame}

%------------ python object / dict--------%
\begin{frame}[fragile]{Built-in Types/Dict}
\begin{lstlisting}[language=C]{dictobject.h}
typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;  /* # Active + # Dummy */
    Py_ssize_t ma_used;  /* # Active */
    Py_ssize_t ma_mask;
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};
\end{lstlisting} 
\end{frame}


%------------ python object / dict--------%
\begin{frame}[fragile]{Built-in Types/Dict}
\begin{lstlisting}[language=C]{dictobject.h}
typedef struct {
    /* Cached hash code of me_key.  Note that hash codes are C longs.
     * We have to use Py_ssize_t instead because dict_popitem() abuses
     * me_hash to hold a search finger.
     */
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;
\end{lstlisting} 
\end{frame}

%------------ python object / dict --------%
\begin{frame}{Built-in Types/Dict}
\begin{itemize} 
  \item hash table with open addressing
  \item unused/active/dummy
  \item ma\_smalltable and ma\_table
  \item lookdict and lookdict\_string
  \item PyDict\_New
  \item cache mechanism: free\_list, which hold 80 objects
  \item memory management in dictresize:
    \begin{itemize} 
        \item if fill > 2/3 size, adjust size.
        \item size * 2 or size * 4
    \end{itemize} 
\end{itemize} 
\end{frame}

%------------ mem --------%
\begin{frame}{Memory Allocators}
    \begin{figure}
       \begin{center}
           \includegraphics[width=10cm, height=5cm]{memory_allocators.png}
       \end{center}
\end{figure}
\end{frame}

%------------ mem -------%
\begin{frame}{Memory Allocators}
\begin{itemize} 
  \item Layer 0 is OS's allocators
  \item Layer 1 is just a simple wrapper of Layer 0, in forms of both macro and funtion
  \item Layer 2 is the core mechanism--pymalloc. PyObject\_\{Malloc,Realloc,Free\}
  \item Layer 3 is type specific memory cache
\end{itemize} 
\end{frame}

%------------ refcnt and gc --------%
\begin{frame}{pymalloc}
\begin{itemize} 
  \item block: works for <256B, when >256B, use Layer 1. block must be 8B alignment.
  \item pool: same as mem page size(4KB), manage blocks of same size
  \item arena: has 64 pools.
  \item usedpools: array of head pointers of USED pool
\end{itemize} 
\end{frame}

\begin{frame}{Mark-Sweep Garbage Collection}
\begin{itemize} 
  \item break unreachable reference cycles
  \item doesn't explicity deallocate any objects, just breaks cycles
  \item automaticlly run by interpreter every once in a while. sys.getcheckinterval()
  \item auto gc object without \_\_del\_\_
  \item stop the world to gc
  \item expensive, cost is linear to number of references of vector in program.
\end{itemize} 
\end{frame}

\begin{frame}{Generational GC}
\begin{itemize}
  \item most objects live either for a very short time or for a very long time
  \item divide object into 3 generations(0, 1, 2)
  \item each new object is generation 0.
  \item n-th gen. gc analyses objects of gen. 0-n
  \item any object that survived n-th gen. gc is promoted to n+1-th gen.
  \item (700, 10, 10) 700 is alloc - dealloc, 10s are times of prior gen gc.
\end{itemize}
\end{frame}

\begin{frame}{Memory Leak}
\begin{itemize}
  \item leak in modules written in c/c++
  \item integers and floats
  \item gc won't collect any objects in cycles where at least one object has \_\_del\_\_
  \item hidding references
\end{itemize}
\end{frame}

\begin{frame}{Memory Leak}
Hidding References
\begin{itemize}
  \item closures, functools.partial, etc
  \item sys.exc\_traceback keeps last exception handled in this stack frame including the whole stack state when exception occurs.
  \item sys.last\_traceback keeps unhandled excption including whole stack state
\end{itemize}
\end{frame}

\begin{frame}{What to do}
\begin{itemize}
    \item use context manager("with") instead of \_\_del\_\_
    \item use weakref
    \item if you really need \_\_del\_\_, be careful of ref cycle
    \item tools: pdb/objgraph/guppy/heapy/memory\_profiler/line\_profiler/gc.collect()
\end{itemize}
\end{frame}

\begin{frame}[c]{} % [c] is the default
    \begin{center}\Huge
        Q \& A
    \end{center}
\end{frame} 
\end{document}