Armin Rigo avatar Armin Rigo committed 4734acd

The FSCONS talk, draft.

Comments (0)

Files changed (19)

talk/fscons2012/GIL.fig

+#FIG 3.2  Produced by xfig version 3.2.5b
+Landscape
+Center
+Metric
+A4      
+100.00
+Single
+-2
+1200 2
+2 2 0 1 0 9 50 -1 20 0.000 0 0 7 0 0 5
+	 1125 1350 2475 1350 2475 1800 1125 1800 1125 1350
+2 2 0 1 0 9 50 -1 20 0.000 0 0 -1 0 0 5
+	 3600 1350 4725 1350 4725 1800 3600 1800 3600 1350
+2 2 0 1 0 9 50 -1 20 0.000 0 0 -1 0 0 5
+	 5850 1350 7200 1350 7200 1800 5850 1800 5850 1350
+2 2 0 1 0 4 50 -1 20 0.000 0 0 -1 0 0 5
+	 2475 1800 3600 1800 3600 2250 2475 2250 2475 1800
+2 2 0 1 0 4 50 -1 20 0.000 0 0 -1 0 0 5
+	 4725 1800 5850 1800 5850 2250 4725 2250 4725 1800
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 1125 2025 7425 2025
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 1125 1575 7425 1575
Add a comment to this file

talk/fscons2012/GIL.png

Added
New image

talk/fscons2012/Makefile

+# you can find rst2beamer.py here:
+# http://codespeak.net/svn/user/antocuni/bin/rst2beamer.py
+
+# WARNING: to work, it needs this patch for docutils
+# https://sourceforge.net/tracker/?func=detail&atid=422032&aid=1459707&group_id=38414
+
+talk.pdf: talk.rst author.latex title.latex stylesheet.latex
+	rst2beamer.py --stylesheet=stylesheet.latex --documentoptions=14pt talk.rst talk.latex || exit
+	sed 's/\\date{}/\\input{author.latex}/' -i talk.latex || exit
+	sed 's/\\maketitle/\\input{title.latex}/' -i talk.latex || exit
+	sed 's/\\usepackage\[latin1\]{inputenc}/\\usepackage[utf8]{inputenc}/' -i talk.latex || exit
+	pdflatex talk.latex  || exit
+
+view: talk.pdf
+	evince talk.pdf &
+
+xpdf: talk.pdf
+	xpdf talk.pdf &

talk/fscons2012/STM.fig

+#FIG 3.2  Produced by xfig version 3.2.5b
+Landscape
+Center
+Metric
+A4      
+100.00
+Single
+-2
+1200 2
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 1125 1575 7425 1575
+2 2 0 1 0 9 50 -1 20 0.000 0 0 7 0 0 5
+	 1125 1350 2475 1350 2475 1800 1125 1800 1125 1350
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 1125 2025 7425 2025
+2 2 0 1 0 4 50 -1 20 0.000 0 0 -1 0 0 5
+	 1125 1800 2250 1800 2250 2250 1125 2250 1125 1800
+2 2 0 1 0 9 50 -1 20 0.000 0 0 -1 0 0 5
+	 2700 1350 3825 1350 3825 1800 2700 1800 2700 1350
+2 2 0 1 0 4 50 -1 20 0.000 0 0 -1 0 0 5
+	 2475 1800 3600 1800 3600 2250 2475 2250 2475 1800
+2 2 0 1 0 9 50 -1 20 0.000 0 0 -1 0 0 5
+	 4050 1350 5400 1350 5400 1800 4050 1800 4050 1350
+2 2 0 1 0 4 50 -1 20 0.000 0 0 -1 0 0 5
+	 3825 1800 4950 1800 4950 2250 3825 2250 3825 1800
Add a comment to this file

talk/fscons2012/STM.png

Added
New image

talk/fscons2012/author.latex

+\definecolor{rrblitbackground}{rgb}{0.0, 0.0, 0.0}
+
+\title[Software Transactional Memory "for real"]{Software Transactional Memory{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }"for real"}
+\author[Armin Rigo]
+{Armin Rigo}
+
+\institute{FSCONS 2012}
+\date{November 10, 2012}

talk/fscons2012/beamerdefs.txt

+.. colors
+.. ===========================
+
+.. role:: green
+.. role:: red
+
+
+.. general useful commands
+.. ===========================
+
+.. |pause| raw:: latex
+
+   \pause
+
+.. |small| raw:: latex
+
+   {\small
+
+.. |end_small| raw:: latex
+
+   }
+
+.. |scriptsize| raw:: latex
+
+   {\scriptsize
+
+.. |end_scriptsize| raw:: latex
+
+   }
+
+.. |strike<| raw:: latex
+
+   \sout{
+
+.. closed bracket
+.. ===========================
+
+.. |>| raw:: latex
+
+   }
+
+
+.. example block
+.. ===========================
+
+.. |example<| raw:: latex
+
+   \begin{exampleblock}{
+
+
+.. |end_example| raw:: latex
+
+   \end{exampleblock}
+
+
+
+.. alert block
+.. ===========================
+
+.. |alert<| raw:: latex
+
+   \begin{alertblock}{
+
+
+.. |end_alert| raw:: latex
+
+   \end{alertblock}
+
+
+
+.. columns
+.. ===========================
+
+.. |column1| raw:: latex
+
+   \begin{columns}
+      \begin{column}{0.45\textwidth}
+
+.. |column2| raw:: latex
+
+      \end{column}
+      \begin{column}{0.45\textwidth}
+
+
+.. |end_columns| raw:: latex
+
+      \end{column}
+   \end{columns}
+
+
+
+.. |snake| image:: ../../img/py-web-new.png
+           :scale: 15%
+           
+
+
+.. nested blocks
+.. ===========================
+
+.. |nested| raw:: latex
+
+   \begin{columns}
+      \begin{column}{0.85\textwidth}
+
+.. |end_nested| raw:: latex
+
+      \end{column}
+   \end{columns}

talk/fscons2012/stylesheet.latex

+\usetheme{Boadilla}
+\usecolortheme{whale}
+\setbeamercovered{transparent}
+\setbeamertemplate{navigation symbols}{}
+
+\definecolor{darkgreen}{rgb}{0, 0.5, 0.0}
+\newcommand{\docutilsrolegreen}[1]{\color{darkgreen}#1\normalcolor}
+\newcommand{\docutilsrolered}[1]{\color{red}#1\normalcolor}
+
+\newcommand{\green}[1]{\color{darkgreen}#1\normalcolor}
+\newcommand{\red}[1]{\color{red}#1\normalcolor}

talk/fscons2012/summary.txt

+
+- multicore machines, manycore machines
+
+- focus on cases where using more cores is harder than making more processes
+
+
+- using locks
+- using stm/htm
+
+- HTM: Haswell
+- STM: read/write barriers, picture
+
+
+- the deeper problem is: you have to use threads
+- messy
+
+- parallel with GC: common programming languages are either fully GC'ed or
+  not at all
+
+- what do you get if you run *everything* in STM/HTM?
+
+- longer transactions, corresponding to larger parts of the program
+
+- the thread model becomes implicit
+
+- demo
+
+
+- GIL/STM pictures
+- can pretend it is one-core
+
+- always gives correct results, but maybe too many conflicts
+
+- "the right side" of the problem, in my opinion: debugging tools etc.
+  (same as: GC is "the right side": no crashes, but you need occasionally
+  to understand memory-not-freed problems)

talk/fscons2012/talk.latex

+\documentclass[14pt]{beamer}
+\usepackage{hyperref}
+\usepackage{fancyvrb}
+
+\makeatletter
+\def\PY@reset{\let\PY@it=\relax \let\PY@bf=\relax%
+    \let\PY@ul=\relax \let\PY@tc=\relax%
+    \let\PY@bc=\relax \let\PY@ff=\relax}
+\def\PY@tok#1{\csname PY@tok@#1\endcsname}
+\def\PY@toks#1+{\ifx\relax#1\empty\else%
+    \PY@tok{#1}\expandafter\PY@toks\fi}
+\def\PY@do#1{\PY@bc{\PY@tc{\PY@ul{%
+    \PY@it{\PY@bf{\PY@ff{#1}}}}}}}
+\def\PY#1#2{\PY@reset\PY@toks#1+\relax+\PY@do{#2}}
+
+\def\PY@tok@gd{\def\PY@bc##1{\fcolorbox[rgb]{0.80,0.00,0.00}{1.00,0.80,0.80}{##1}}}
+\def\PY@tok@gu{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.20,0.00}{##1}}}
+\def\PY@tok@gt{\def\PY@tc##1{\textcolor[rgb]{0.60,0.80,0.40}{##1}}}
+\def\PY@tok@gs{\let\PY@bf=\textbf}
+\def\PY@tok@gr{\def\PY@tc##1{\textcolor[rgb]{1.00,0.00,0.00}{##1}}}
+\def\PY@tok@cm{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.00,0.60,1.00}{##1}}}
+\def\PY@tok@vg{\def\PY@tc##1{\textcolor[rgb]{0.00,0.20,0.20}{##1}}}
+\def\PY@tok@m{\def\PY@tc##1{\textcolor[rgb]{1.00,0.40,0.00}{##1}}}
+\def\PY@tok@mh{\def\PY@tc##1{\textcolor[rgb]{1.00,0.40,0.00}{##1}}}
+\def\PY@tok@cs{\let\PY@bf=\textbf\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.00,0.60,1.00}{##1}}}
+\def\PY@tok@ge{\let\PY@it=\textit}
+\def\PY@tok@vc{\def\PY@tc##1{\textcolor[rgb]{0.00,0.20,0.20}{##1}}}
+\def\PY@tok@il{\def\PY@tc##1{\textcolor[rgb]{1.00,0.40,0.00}{##1}}}
+\def\PY@tok@go{\def\PY@tc##1{\textcolor[rgb]{0.67,0.67,0.67}{##1}}}
+\def\PY@tok@cp{\def\PY@tc##1{\textcolor[rgb]{0.00,0.60,0.60}{##1}}}
+\def\PY@tok@gi{\def\PY@bc##1{\fcolorbox[rgb]{0.00,0.80,0.00}{0.80,1.00,0.80}{##1}}}
+\def\PY@tok@gh{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.20,0.00}{##1}}}
+\def\PY@tok@ni{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.60,0.60,0.60}{##1}}}
+\def\PY@tok@nl{\def\PY@tc##1{\textcolor[rgb]{0.60,0.60,1.00}{##1}}}
+\def\PY@tok@nn{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.80,1.00}{##1}}}
+\def\PY@tok@no{\def\PY@tc##1{\textcolor[rgb]{0.20,0.40,0.00}{##1}}}
+\def\PY@tok@na{\def\PY@tc##1{\textcolor[rgb]{0.20,0.00,0.60}{##1}}}
+\def\PY@tok@nb{\def\PY@tc##1{\textcolor[rgb]{0.20,0.40,0.40}{##1}}}
+\def\PY@tok@nc{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.67,0.53}{##1}}}
+\def\PY@tok@nd{\def\PY@tc##1{\textcolor[rgb]{0.60,0.60,1.00}{##1}}}
+\def\PY@tok@ne{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.80,0.00,0.00}{##1}}}
+\def\PY@tok@nf{\def\PY@tc##1{\textcolor[rgb]{0.80,0.00,1.00}{##1}}}
+\def\PY@tok@si{\def\PY@tc##1{\textcolor[rgb]{0.67,0.00,0.00}{##1}}}
+\def\PY@tok@s2{\def\PY@tc##1{\textcolor[rgb]{0.80,0.20,0.00}{##1}}}
+\def\PY@tok@vi{\def\PY@tc##1{\textcolor[rgb]{0.00,0.20,0.20}{##1}}}
+\def\PY@tok@nt{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.20,0.00,0.60}{##1}}}
+\def\PY@tok@nv{\def\PY@tc##1{\textcolor[rgb]{0.00,0.20,0.20}{##1}}}
+\def\PY@tok@s1{\def\PY@tc##1{\textcolor[rgb]{0.80,0.20,0.00}{##1}}}
+\def\PY@tok@gp{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,0.60}{##1}}}
+\def\PY@tok@sh{\def\PY@tc##1{\textcolor[rgb]{0.80,0.20,0.00}{##1}}}
+\def\PY@tok@ow{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,0.00}{##1}}}
+\def\PY@tok@sx{\def\PY@tc##1{\textcolor[rgb]{0.80,0.20,0.00}{##1}}}
+\def\PY@tok@bp{\def\PY@tc##1{\textcolor[rgb]{0.20,0.40,0.40}{##1}}}
+\def\PY@tok@c1{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.00,0.60,1.00}{##1}}}
+\def\PY@tok@kc{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.40,0.60}{##1}}}
+\def\PY@tok@c{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.00,0.60,1.00}{##1}}}
+\def\PY@tok@mf{\def\PY@tc##1{\textcolor[rgb]{1.00,0.40,0.00}{##1}}}
+\def\PY@tok@err{\def\PY@tc##1{\textcolor[rgb]{0.67,0.00,0.00}{##1}}\def\PY@bc##1{\colorbox[rgb]{1.00,0.67,0.67}{##1}}}
+\def\PY@tok@kd{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.40,0.60}{##1}}}
+\def\PY@tok@ss{\def\PY@tc##1{\textcolor[rgb]{1.00,0.80,0.20}{##1}}}
+\def\PY@tok@sr{\def\PY@tc##1{\textcolor[rgb]{0.20,0.67,0.67}{##1}}}
+\def\PY@tok@mo{\def\PY@tc##1{\textcolor[rgb]{1.00,0.40,0.00}{##1}}}
+\def\PY@tok@mi{\def\PY@tc##1{\textcolor[rgb]{1.00,0.40,0.00}{##1}}}
+\def\PY@tok@kn{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.40,0.60}{##1}}}
+\def\PY@tok@o{\def\PY@tc##1{\textcolor[rgb]{0.33,0.33,0.33}{##1}}}
+\def\PY@tok@kr{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.40,0.60}{##1}}}
+\def\PY@tok@s{\def\PY@tc##1{\textcolor[rgb]{0.80,0.20,0.00}{##1}}}
+\def\PY@tok@kp{\def\PY@tc##1{\textcolor[rgb]{0.00,0.40,0.60}{##1}}}
+\def\PY@tok@w{\def\PY@tc##1{\textcolor[rgb]{0.73,0.73,0.73}{##1}}}
+\def\PY@tok@kt{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.47,0.53}{##1}}}
+\def\PY@tok@sc{\def\PY@tc##1{\textcolor[rgb]{0.80,0.20,0.00}{##1}}}
+\def\PY@tok@sb{\def\PY@tc##1{\textcolor[rgb]{0.80,0.20,0.00}{##1}}}
+\def\PY@tok@k{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.40,0.60}{##1}}}
+\def\PY@tok@se{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.80,0.20,0.00}{##1}}}
+\def\PY@tok@sd{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.80,0.20,0.00}{##1}}}
+
+\def\PYZbs{\char`\\}
+\def\PYZus{\char`\_}
+\def\PYZob{\char`\{}
+\def\PYZcb{\char`\}}
+\def\PYZca{\char`\^}
+\def\PYZsh{\char`\#}
+\def\PYZpc{\char`\%}
+\def\PYZdl{\char`\$}
+\def\PYZti{\char`\~}
+% for compatibility with earlier versions
+\def\PYZat{@}
+\def\PYZlb{[}
+\def\PYZrb{]}
+\makeatother
+
+
+\definecolor{rrblitbackground}{rgb}{0.55, 0.3, 0.1}
+
+\newenvironment{rtbliteral}{
+
+\begin{ttfamily}
+
+\color{rrblitbackground}
+
+}{
+
+\end{ttfamily}
+
+}
+
+% generated by Docutils <http://docutils.sourceforge.net/>
+\usepackage{fixltx2e} % LaTeX patches, \textsubscript
+\usepackage{cmap} % fix search and cut-and-paste in Acrobat
+\usepackage{ifthen}
+\usepackage[T1]{fontenc}
+\usepackage[utf8]{inputenc}
+\usepackage{graphicx}
+
+%%% Custom LaTeX preamble
+% PDF Standard Fonts
+\usepackage{mathptmx} % Times
+\usepackage[scaled=.90]{helvet}
+\usepackage{courier}
+
+%%% User specified packages and stylesheets
+\input{stylesheet.latex}
+
+%%% Fallback definitions for Docutils-specific commands
+
+% hyperlinks:
+\ifthenelse{\isundefined{\hypersetup}}{
+  \usepackage[colorlinks=true,linkcolor=blue,urlcolor=blue]{hyperref}
+  \urlstyle{same} % normal text font (alternatives: tt, rm, sf)
+}{}
+\hypersetup{
+  pdftitle={Software Transactional Memory ``for real''},
+}
+
+%%% Title Data
+\title{\phantomsection%
+  Software Transactional Memory ``for real''%
+  \label{software-transactional-memory-for-real}}
+\author{}
+\input{author.latex}
+
+%%% Body
+\begin{document}
+\input{title.latex}
+
+% colors
+
+% ===========================
+
+% general useful commands
+
+% ===========================
+
+% closed bracket
+
+% ===========================
+
+% example block
+
+% ===========================
+
+% alert block
+
+% ===========================
+
+% columns
+
+% ===========================
+
+% nested blocks
+
+% ===========================
+\begin{frame}
+\frametitle{Introduction}
+
+%
+\begin{itemize}
+
+\item This talk is about programming multi- or many-core machines
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{About myself}
+
+%
+\begin{itemize}
+
+\item Armin Rigo
+
+\item ``Language implementation guy''
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item PyPy project
+%
+\begin{itemize}
+
+\item Python in Python
+
+\item includes a Just-in-Time Compiler ``Generator'' for Python
+and any other dynamic language
+
+\end{itemize}
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Motivation}
+
+%
+\begin{itemize}
+
+\item A single-core program is getting exponentially slower than a multi-core one
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item Using several processes exchanging data
+%
+\begin{itemize}
+
+\item works fine in some cases
+
+\item but becomes a large mess in others
+
+\end{itemize}
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item Using several threads
+%
+\begin{itemize}
+
+\item this talk!
+
+\end{itemize}
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Common solution}
+
+%
+\begin{itemize}
+
+\item Organize your program in multiple threads
+
+\item Add synchronization when accessing shared, non-read-only data
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Synchronization with locks}
+
+%
+\begin{itemize}
+
+\item Carefully place locks around every access to shared data
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item How do you know if you missed a place?
+%
+\begin{itemize}
+
+\item hard to catch by writing tests
+
+\item instead you get obscure rare run-time crashes
+
+\end{itemize}
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item Issues when scaling to a large program
+%
+\begin{itemize}
+
+\item order of acquisition
+
+\item deadlocks
+
+\end{itemize}
+
+\end{itemize}
+\end{frame}
+\begin{frame}[containsverbatim,fragile]
+\frametitle{Synchronization with TM}
+
+%
+\begin{itemize}
+
+\item TM = Transactional Memory
+
+\end{itemize}
+
+\pause
+
+\begin{Verbatim}[commandchars=\\\{\}]
+----------------   --------------------
+Locks              Transactional Memory
+----------------   --------------------
+
+mylock.acquire();    atomic \PYZob{}
+x = list1.pop();       x = list1.pop();
+list2.append(x);       list2.append(x);
+mylock.release();    \PYZcb{}
+\end{Verbatim}
+
+\end{frame}
+\begin{frame}
+\frametitle{Locks versus TM}
+
+%
+\begin{itemize}
+
+\item Locks
+
+\end{itemize}
+
+\noindent\makebox[\textwidth][c]{\includegraphics[scale=0.700000]{withlock.png}}
+%
+\begin{itemize}
+
+\item TM
+
+\end{itemize}
+
+\noindent\makebox[\textwidth][c]{\includegraphics[scale=0.700000]{withstm0.png}}
+\end{frame}
+\begin{frame}
+\frametitle{Locks versus TM}
+
+%
+\begin{itemize}
+
+\item Locks
+
+\end{itemize}
+
+\noindent\makebox[\textwidth][c]{\includegraphics[scale=0.700000]{withlock.png}}
+%
+\begin{itemize}
+
+\item TM in case of conflict
+
+\end{itemize}
+
+\noindent\makebox[\textwidth][c]{\includegraphics[scale=0.700000]{withstm.png}}
+\end{frame}
+\begin{frame}
+\frametitle{Synchronization with TM}
+
+%
+\begin{itemize}
+
+\item ``Optimistic'' approach:
+%
+\begin{itemize}
+
+\item no lock to protect shared data in memory
+
+\item instead, track all memory accesses
+
+\item detect actual conflicts
+
+\item if conflict, restart the whole ``transaction''
+
+\end{itemize}
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item Easier to use
+%
+\begin{itemize}
+
+\item no need to name locks
+
+\item no deadlocks
+
+\item ``composability''
+
+\end{itemize}
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{HTM versus STM}
+
+%
+\begin{itemize}
+
+\item HTM = Hardware Transactional Memory
+%
+\begin{itemize}
+
+\item Intel Haswell CPU, 2013
+
+\item and others
+
+\end{itemize}
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item STM = Software Transactional Memory
+%
+\begin{itemize}
+
+\item various approaches
+
+\item large overhead (2x-10x), but getting faster
+
+\item experimental in PyPy: read/write barriers, as with GC
+
+\end{itemize}
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{The catch}
+
+
+\pause
+%
+\begin{itemize}
+
+\item You Still Have To Use Threads
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item Threads are hard to debug, non-reproductible
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item Threads are Messy
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Issue with threads}
+
+%
+\begin{itemize}
+
+\item TM does not solve this problem:
+
+\item How do you know if you missed a place to put \texttt{atomic} around?
+%
+\begin{itemize}
+
+\item hard to catch by writing tests
+
+\item instead you get obscure rare run-time crashes
+
+\end{itemize}
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item What if we put \texttt{atomic} everywhere?
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Analogy with Garbage Collection}
+
+%
+\begin{itemize}
+
+\item Explicit Memory Management:
+%
+\begin{itemize}
+
+\item messy, hard to debug rare leaks or corruptions
+
+\end{itemize}
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item Automatic GC solves it
+%
+\begin{itemize}
+
+\item common languages either have a GC or not
+
+\item if they have a GC, it controls almost \emph{all} objects
+
+\item not just a small part of them
+
+\end{itemize}
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Proposed solution}
+
+%
+\begin{itemize}
+
+\item Put \texttt{atomic} everywhere...
+
+\item in other words, Run Everything with TM
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Proposed solution}
+
+%
+\begin{itemize}
+
+\item Really needs TM.  With locks, you'd get this:
+
+\end{itemize}
+
+\noindent\makebox[\textwidth][c]{\includegraphics[scale=0.700000]{GIL.png}}
+%
+\begin{itemize}
+
+\item With TM you can get this:
+
+\end{itemize}
+
+\noindent\makebox[\textwidth][c]{\includegraphics[scale=0.700000]{STM.png}}
+\end{frame}
+\begin{frame}
+\frametitle{In a few words}
+
+%
+\begin{itemize}
+
+\item Longer transactions
+
+\item Corresponding to larger parts of the program
+
+\item The underlying multi-threaded model becomes implicit
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Typical example}
+
+%
+\begin{itemize}
+
+\item You want to run \texttt{f1()} and \texttt{f2()} and \texttt{f3()}
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item Assume they are ``mostly independent''
+%
+\begin{itemize}
+
+\item i.e. we expect that we can run them in parallel
+
+\item but we cannot prove it, we just hope that in the common case we can
+
+\end{itemize}
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item In case of conflicts, we don't want random behavior
+%
+\begin{itemize}
+
+\item i.e. we don't want thread-like non-determinism and crashes
+
+\end{itemize}
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Pooling and atomic statements}
+
+%
+\begin{itemize}
+
+\item Solution: use a library that creates a pool of threads
+
+\item Each thread picks a function from the list and runs it
+with \texttt{atomic}
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Results}
+
+%
+\begin{itemize}
+
+\item The behavior is ``as if'' we had run \texttt{f1()}, \texttt{f2()}
+and \texttt{f3()} sequentially
+
+\item The programmer chooses if he wants this fixed order,
+or if any order is fine
+
+\item Threads are hidden from the programmer
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{More generally}
+
+%
+\begin{itemize}
+
+\item This was an example only
+
+\item \textbf{TM gives various new ways to hide threads under a nice interface}
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Not the Ultimate Solution}
+
+%
+\begin{itemize}
+
+\item Much easier for the programmer to get reproducible results
+
+\item But maybe too many conflicts
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item ``The right side'' of the problem
+%
+\begin{itemize}
+
+\item start with a working program, and improve performance
+
+\item as opposed to: with locks, start with a fast program, and debug crashes
+
+\item we will need new debugging tools
+
+\end{itemize}
+
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{PyPy-STM}
+
+%
+\begin{itemize}
+
+\item PyPy-STM: a version of PyPy with Software Transactional Memory
+%
+\begin{itemize}
+
+\item in-progress, but basically working
+
+\end{itemize}
+
+\item \url{http://pypy.org/}
+
+\end{itemize}
+
+\pause
+%
+\begin{itemize}
+
+\item Thank you!
+
+\end{itemize}
+\end{frame}
+
+\end{document}
Add a comment to this file

talk/fscons2012/talk.pdf

Binary file added.

talk/fscons2012/talk.rst

+.. include:: beamerdefs.txt
+
+============================================
+Software Transactional Memory "for real"
+============================================
+
+
+Introduction
+------------------
+
+* This talk is about programming multi- or many-core machines
+
+
+About myself
+------------------
+
+* Armin Rigo
+
+* "Language implementation guy"
+
+|pause|
+
+* PyPy project
+
+  - Python in Python
+
+  - includes a Just-in-Time Compiler "Generator" for Python
+    and any other dynamic language
+
+
+Motivation
+----------------------
+
+* A single-core program is getting exponentially slower than a multi-core one
+
+|pause|
+
+* Using several processes exchanging data
+
+  - works fine in some cases
+
+  - but becomes a large mess in others
+
+|pause|
+
+* Using several threads
+
+  - this talk!
+
+
+Common solution
+----------------------
+
+* Organize your program in multiple threads
+
+* Add synchronization when accessing shared, non-read-only data
+
+
+Synchronization with locks
+--------------------------
+
+* Carefully place locks around every access to shared data
+
+|pause|
+
+* How do you know if you missed a place?
+
+  - hard to catch by writing tests
+
+  - instead you get obscure rare run-time crashes
+
+|pause|
+
+* Issues when scaling to a large program
+
+  - order of acquisition
+
+  - deadlocks
+
+
+Synchronization with TM
+-----------------------
+
+* TM = Transactional Memory
+
+|pause|
+
+.. sourcecode:: plain
+
+    ----------------   --------------------
+    Locks              Transactional Memory
+    ----------------   --------------------
+
+    mylock.acquire();    atomic {
+    x = list1.pop();       x = list1.pop();
+    list2.append(x);       list2.append(x);
+    mylock.release();    }
+
+
+Locks versus TM
+---------------
+
+* Locks
+
+.. image:: withlock.png
+   :scale: 70%
+   :align: center
+
+* TM
+
+.. image:: withstm0.png
+   :scale: 70%
+   :align: center
+
+
+Locks versus TM
+---------------
+
+* Locks
+
+.. image:: withlock.png
+   :scale: 70%
+   :align: center
+
+* TM in case of conflict
+
+.. image:: withstm.png
+   :scale: 70%
+   :align: center
+
+
+Synchronization with TM
+-----------------------
+
+* "Optimistic" approach:
+
+  - no lock to protect shared data in memory
+
+  - instead, track all memory accesses
+
+  - detect actual conflicts
+
+  - if conflict, restart the whole "transaction"
+
+|pause|
+
+* Easier to use
+
+  - no need to name locks
+
+  - no deadlocks
+
+  - "composability"
+
+
+HTM versus STM
+--------------
+
+* HTM = Hardware Transactional Memory
+
+  - Intel Haswell CPU, 2013
+
+  - and others
+
+|pause|
+
+* STM = Software Transactional Memory
+
+  - various approaches
+
+  - large overhead (2x-10x), but getting faster
+
+  - experimental in PyPy: read/write barriers, as with GC
+
+
+The catch
+---------
+
+|pause|
+
+* You Still Have To Use Threads
+
+|pause|
+
+* Threads are hard to debug, non-reproductible
+
+|pause|
+
+* Threads are Messy
+
+
+Issue with threads
+------------------
+
+* TM does not solve this problem:
+
+* How do you know if you missed a place to put ``atomic`` around?
+
+  - hard to catch by writing tests
+
+  - instead you get obscure rare run-time crashes
+
+|pause|
+
+* What if we put ``atomic`` everywhere?
+
+
+Analogy with Garbage Collection
+-------------------------------
+
+* Explicit Memory Management:
+
+  - messy, hard to debug rare leaks or corruptions
+
+|pause|
+
+* Automatic GC solves it
+
+  - common languages either have a GC or not
+
+  - if they have a GC, it controls almost *all* objects
+
+  - not just a small part of them
+
+
+Proposed solution
+-----------------
+
+* Put ``atomic`` everywhere...
+
+* in other words, Run Everything with TM
+
+
+Proposed solution
+-----------------
+
+* Really needs TM.  With locks, you'd get this:
+
+.. image:: GIL.png
+   :scale: 70%
+   :align: center
+
+* With TM you can get this:
+
+.. image:: STM.png
+   :scale: 70%
+   :align: center
+
+
+In a few words
+--------------
+
+* Longer transactions
+
+* Corresponding to larger parts of the program
+
+* The underlying multi-threaded model becomes implicit
+
+
+Typical example
+---------------
+
+* You want to run ``f1()`` and ``f2()`` and ``f3()``
+
+|pause|
+
+* Assume they are "mostly independent"
+
+  - i.e. we expect that we can run them in parallel
+
+  - but we cannot prove it, we just hope that in the common case we can
+
+|pause|
+
+* In case of conflicts, we don't want random behavior
+
+  - i.e. we don't want thread-like non-determinism and crashes
+
+
+Pooling and atomic statements
+-----------------------------
+
+* Solution: use a library that creates a pool of threads
+
+* Each thread picks a function from the list and runs it
+  with ``atomic``
+
+
+Results
+-------
+
+* The behavior is "as if" we had run ``f1()``, ``f2()``
+  and ``f3()`` sequentially
+
+* The programmer chooses if he wants this fixed order,
+  or if any order is fine
+
+* Threads are hidden from the programmer
+
+
+More generally
+--------------
+
+* This was an example only
+
+* **TM gives various new ways to hide threads under a nice interface**
+
+
+Not the Ultimate Solution
+-------------------------
+
+* Much easier for the programmer to get reproducible results
+
+* But maybe too many conflicts
+
+|pause|
+
+* "The right side" of the problem
+
+  - start with a working program, and improve performance
+
+  - as opposed to: with locks, start with a fast program, and debug crashes
+
+  - we will need new debugging tools
+
+
+PyPy-STM
+--------
+
+* PyPy-STM: a version of PyPy with Software Transactional Memory
+
+  - in-progress, but basically working
+
+* http://pypy.org/
+
+|pause|
+
+* Thank you!

talk/fscons2012/title.latex

+\begin{titlepage}
+\begin{figure}[h]
+\includegraphics[width=60px]{../../logo/pypy_small128.png}
+\end{figure}
+\end{titlepage}

talk/fscons2012/withlock.fig

+#FIG 3.2  Produced by xfig version 3.2.5b
+Landscape
+Center
+Metric
+A4      
+100.00
+Single
+-2
+1200 2
+2 2 0 1 0 9 50 -1 20 0.000 0 0 -1 0 0 5
+	 3600 1350 4725 1350 4725 1800 3600 1800 3600 1350
+2 2 0 1 0 4 50 -1 20 0.000 0 0 -1 0 0 5
+	 4725 1800 5850 1800 5850 2250 4725 2250 4725 1800
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 630 2025 8010 2025
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 630 1575 8010 1575
+2 2 0 1 0 6 50 -1 20 0.000 0 0 7 0 0 5
+	 1125 1350 3600 1350 3600 1800 1125 1800 1125 1350
+2 2 0 1 0 6 50 -1 20 0.000 0 0 -1 0 0 5
+	 4725 1350 7200 1350 7200 1800 4725 1800 4725 1350
+2 2 0 1 0 6 50 -1 20 0.000 0 0 -1 0 0 5
+	 5850 1800 7515 1800 7515 2250 5850 2250 5850 1800
+2 2 0 1 0 6 50 -1 20 0.000 0 0 -1 0 0 5
+	 1125 1800 3735 1800 3735 2295 1125 2295 1125 1800
Add a comment to this file

talk/fscons2012/withlock.png

Added
New image

talk/fscons2012/withstm.fig

+#FIG 3.2  Produced by xfig version 3.2.5b
+Landscape
+Center
+Metric
+A4      
+100.00
+Single
+-2
+1200 2
+2 2 0 1 0 6 50 -1 20 0.000 0 0 -1 0 0 5
+	 4725 1350 7200 1350 7200 1800 4725 1800 4725 1350
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 630 1575 8010 1575
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 630 2025 8010 2025
+2 2 0 1 0 6 50 -1 20 0.000 0 0 7 0 0 5
+	 1125 1350 3600 1350 3600 1800 1125 1800 1125 1350
+2 2 0 1 0 9 50 -1 20 0.000 0 0 -1 0 0 5
+	 3600 1350 4725 1350 4725 1800 3600 1800 3600 1350
+2 2 0 1 0 18 50 -1 20 0.000 0 0 -1 0 0 5
+	 3735 1800 4860 1800 4860 2295 3735 2295 3735 1800
+2 2 0 1 0 4 50 -1 20 0.000 0 0 -1 0 0 5
+	 4275 1800 5400 1800 5400 2295 4275 2295 4275 1800
+2 2 0 1 0 6 50 -1 20 0.000 0 0 -1 0 0 5
+	 5400 1800 7065 1800 7065 2295 5400 2295 5400 1800
+2 2 0 1 0 6 50 -1 20 0.000 0 0 -1 0 0 5
+	 1125 1800 3735 1800 3735 2295 1125 2295 1125 1800
Add a comment to this file

talk/fscons2012/withstm.png

Added
New image

talk/fscons2012/withstm0.fig

+#FIG 3.2  Produced by xfig version 3.2.5b
+Landscape
+Center
+Metric
+A4      
+100.00
+Single
+-2
+1200 2
+2 2 0 1 0 6 50 -1 20 0.000 0 0 -1 0 0 5
+	 4725 1350 7200 1350 7200 1800 4725 1800 4725 1350
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 630 1575 8010 1575
+2 1 0 1 0 4 51 -1 20 0.000 0 0 7 1 0 2
+	0 0 1.00 60.00 120.00
+	 630 2025 8010 2025
+2 2 0 1 0 6 50 -1 20 0.000 0 0 7 0 0 5
+	 1125 1350 3600 1350 3600 1800 1125 1800 1125 1350
+2 2 0 1 0 9 50 -1 20 0.000 0 0 -1 0 0 5
+	 3600 1350 4725 1350 4725 1800 3600 1800 3600 1350
+2 2 0 1 0 6 50 -1 20 0.000 0 0 -1 0 0 5
+	 4860 1800 6525 1800 6525 2295 4860 2295 4860 1800
+2 2 0 1 0 4 50 -1 20 0.000 0 0 -1 0 0 5
+	 3735 1800 4860 1800 4860 2295 3735 2295 3735 1800
+2 2 0 1 0 6 50 -1 20 0.000 0 0 -1 0 0 5
+	 1125 1800 3735 1800 3735 2295 1125 2295 1125 1800
Add a comment to this file

talk/fscons2012/withstm0.png

Added
New image
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.