Authorea

Brandon Holt add mortarboard/rmd version about 9 years ago

Commit id: eb9fc8b6c5aff995ee0b286c2c9ac45cecfb7f59

deletions | additions

paper.pdf paper.tex paper.md paper.html figure/*.pdf figure/*.png *.log *.bbl *.out

PDFLATEX ?= pdflatex -halt-on-error -file-line-error BIBTEX ?= bibtex PANDOC ?= pandoc --natbib -S --standalone ifneq ($(QUIET),) PDFLATEX += -interaction=batchmode ERRFILTER := > /dev/null || (egrep ':[[:digit:]]+:' *.log && false) BIBTEX += -terse else PDFLATEX += -interaction=nonstopmode ERRFILTER= endif PAPER += paper .PHONY: all all: pdf web view web: $(PAPER).html pdf: $(PAPER).pdf view: $(PAPER).pdf open -a Skim $(PAPER).pdf $(PAPER).md: $(PAPER).Rmd common.R Makefile Rscript --slave -e "library(knitr); source('common.R'); knit('"$<"')" $(PAPER).tex: $(PAPER).md template.tex Makefile $(PANDOC) --template=template.tex -o $@ $< $(PAPER).html: $(PAPER).md template.html Makefile # $(PANDOC) --template=template.tex -o $@ $< # Rscript --slave -e "library(knitr); pandoc('"$<"')" $(PANDOC) --template=template.html -o $@ $< %.pdf: %.tex $(PDFLATEX) $^ $(BIBTEX) $(basename $^) $(PDFLATEX) $^ $(PDFLATEX) $^ clean: rm -f $(PAPER).{tex,pdf,log,out,html,md,aux,bbl,blg}

../bibliography/biblio.bib

suppressPackageStartupMessages(require(RMySQL)) suppressPackageStartupMessages(require(sqldf)) suppressPackageStartupMessages(require(ggplot2)) suppressPackageStartupMessages(require(reshape)) options(RMySQL.dbname="claret") # (rest comes from $HOME/.my.cnf) db <- function(query, factors=c(), numeric=c()) { d <- sqldf(query) d[factors] <- lapply(d[factors], factor) d[numeric] <- lapply(d[numeric], as.numeric) return(d) } num <- function(var) as.numeric(as.character(var)) save <- function(g, name=FILE_BASE, file=sprintf("%s/%s.pdf",FILE_DIR,name), w=3.3, h=3.1) { ggsave(plot=g, filename=file, width=w, height=h) print(sprintf("saved: %s", file)) } prettify <- function(str) gsub('_',' ',gsub('([a-z])([a-z]+)',"\\U\\1\\E\\2",str,perl=TRUE)) regex_match <- function(reg,str) length(grep(reg,str)) > 0 label_pretty <- function(variable, value) { vname <- if (regex_match('variable|value',variable)) '' else sprintf('%s:', variable) lapply(paste(vname, prettify(as.character(value))), paste, collapse="\n") } geom_mean <- function(geom) stat_summary(fun.y='mean', geom=geom, labeller=label_pretty) geom_meanbar <- function(labeller=label_pretty) { return(list( stat_summary(fun.y=mean, geom='bar', position='dodge'), stat_summary(fun.data=mean_cl_normal, geom='errorbar', width=0.2, position='dodge') )) } # The palette with grey: cbPalette <- c("#0072B2", "#E69F00", "#009E73", "#D55E00", "#CC79A7", "#56B4E9", "#F0E442", "#999999") theme_mine <- list( # To use for fills, add scale_fill_manual(values=cbPalette), # To use for line and point colors, add scale_colour_manual(values=cbPalette), # basic black and white theme theme( panel.background = element_rect(fill="white"), panel.border = element_rect(fill=NA, color="grey50"), panel.grid.major = element_line(color="grey80", size=0.2), panel.grid.minor = element_line(color="grey90", size=0.2), strip.background = element_rect(fill="grey90", color="grey50"), strip.background = element_rect(fill="grey80", color="grey50"), axis.ticks = element_line(colour="black"), panel.grid = element_line(colour="black"), axis.text.y = element_text(colour="black"), axis.text.x = element_text(colour="black"), text = element_text(size=9, family="Helvetica") ) )

# Notes on implementing new features ## Autoref extension It would be best if I could easily add `\autoref{}` calls using Markdown syntax so we can automatically get nice "Section #", or "Figure #" references in Latex *and* HTML. To start with, the simplest version could just work for adding autoref calls and use `\labels` to declare the labels themselves. Proposed syntax: ~~~{r, fig.cap="Throughput as we scale up concurrency.\label{throughput}"} ...plotting code... ~~~ As you can see in [#throughput]. Look into implementing this as a [Pandoc filter](http://johnmacfarlane.net/pandoc/scripting.html).

--- title: 'Claret: Using Data Types for Highly Concurrent Distributed Transactions' preprint: true author: - {family: Holt, given: Brandon, affiliation: 1, email: bholt} - {family: Zhang, given: Irene, affiliation: 1, email: iyzhang} - {family: Ports, given: Dan, affiliation: 1, email: dkp} - {family: Oskin, given: Mark, affiliation: 1, email: oskin} - {family: Ceze, given: Luis, affiliation: 1, email: luisceze} organization: - {id: 1, name: University of Washington} conference: name: PaPoC 2015 location: 'April 21, 2015, Bordeaux, France' year: 2015 doi: 0 layout: sigplanconf bibliography: biblio.bib output: pdf_document: fig_caption: yes abstract: | Building database applications out of data structures rather than simple string values allows the flexibility and fine-grained control of typical key-value databases while providing better performance and scalability. Composing transactions out of linearizable data structure operations exposes concurrency in a safe way, making it simple to implement efficiently and easy to reason about. --- ```{r setup, include=FALSE} opts_chunk$set(dev = 'pdf') ``` # Introduction Providing strong consistency in interactions with databases greatly aids programmers in their ability to write correct code. However, when scaling services under heavy load to millions or billions of users, systems today often must give up these consistency guarantees to meet tight performance goals. A wide variety of NoSQL databases support a more relaxed, or eventually consistent model, and in the majority of cases, it seems that this lack of consistency does not hinder them — the observation being that most times, transactional updates are unneccessary because potential conflicts are just not likely to be observed, and the users may even accept minor inconsistencies, such as two tweets being out of temporal order. However, this is leaving a lot to chance. If it truly is the case that these interactions shouldn't conflict in observable ways, or that certain parts of the application can tolerate imprecision, then why not capture those properties in the programming model for these databases? What if the semantics of operations were known to the database, so it could continue to ignore cases where ordering or consistency really don't matter, but could step in and mediate those specific instances where it could be a problem. And what if the programmer could express the semantics they desire succintly and rigorously? We argue that the correct way to express and enforce these semantics is through the use of an old computer science standby: abstract data types (ADTs). Rather than treating the values in a key/value store simply as strings, making them into more complex data types provides a richer interface, exposing ample opportunities for optimization to the database and a clean mechanism for programmers to express their intentions. Performance benefits come from understanding the properties of ADT operations: those that commute with each other can be performed concurrently, even on multiple copies of the record. This means that transactions whose operations commute abort less, approaching the performance without transactions. This cleanly captures the cases described above where conflicts were unobservable or ordering didn't matter but in a safe way because any operations that don't in fact commute will be handled with traditional concurrency control. Using insights from multi-core concurrent data structures, we show in \autoref{comm} that it is practical to reason about the matrix of commutativity among operations and build implementations that make the right tradeoff between the amount of concurrency allowed and the efficiency of tracking it. Selecting the right data type for the job gives programmers a clean, precise way to express their desired behavior. For instance, rather than using a generic integer to generate unique identifiers, a `UniqueID` type, realizing that contiguity isn't necessary, can be trivially parallelized and distributed. Though this is an extremely simple case (and nearly universally adopted optimization), it fits the same mold as more nuanced decisions, such as choosing to represent the number of times a given post has been "retweeted" as a `HyperLogLog`, which can efficiently yield the approximate number of unique users, rather than a costly precise `Set`. Though selecting data structures for the job at hand is nothing new to programmers, only a handful of databases, such as Redis, MongoDB or Riak, support this flexibility, and they do not use the abstraction it affords to enforce strongly consistent transactions. # Commutativity {#comm} Commutativity is well known, especially in distributed systems, for enabling important optimizations. Since the 80s, commutativity has been exploited by database systems designers \cite{Weihl:1988,Fekete:90}, within the safe confines of relational models, where knowledge of query plans and complete control of the data structures allows systems to determine when transactions may conflict. Recently, commutativity has seen a resurgence in systems without a predefined data model, such as NoSQL databases and transactional memory. In the realm of eventual consistency, commutativity has been leveraged for convergence guarantees. RedBlue consistency allows executing commutative ("blue") operations locally, knowing they will eventually converge. Similarly, conflict-free replicated data types (CRDTs) \cite{Shapiro:SSS11} define commutative merge functions for all operations to ensure that replicas will converge. Lynx \cite{Zhang:SOSP13} uses knowledge of some commutative operations to make tracking serializability cheaper in chained transactions. Doppel \cite{Narula:OSDI14} added several explicitly commutative operations on records which they exploited to better handle common high-contention situations such as counters and "top-k lists" in the context of a single node multicore database. Finally, HyFlow \cite{Kim:EuroPar13}, a distributed transactional memory framework, reorders commutative operations on specific data types to execute before others to allow them to operate concurrently on a single version of a record. ## Commutativity Specifications \begin{table} \centering \begin{tabular}{lll} \textbf{method:} & \textbf{commutes with:} & \textbf{when:} \\ \hline \texttt{add(x) -> void} & \texttt{add(y)} & $\forall x, y$ \\ \texttt{remove(x) -> void} & \texttt{remove(y)} & $\forall x, y$ \\ & \texttt{add(y)} & $x \ne y$ \\ \texttt{size() -> int} & \texttt{add(x)} & $x \in Set$ \\ & \texttt{remove(x)} & $x \notin Set$ \\ \texttt{getall() -> list} & \texttt{add(x)} & $x \in Set$ \\ & \texttt{remove(x)} & $x \notin Set$ \\ & \texttt{size()} & $always$ \\ \hline \end{tabular} \caption{\label{spec} Commutativity Specification for Set.} \end{table} Though *commutativity* is often discussed in terms of an operation commuting with all other operations, it is actually more nuanced. If a pair of operations commute, then executing them in either order will produce the same result. Using the definitions from \cite{Kulkarni:PLDI11}, whether or not a pair of method invocations commute is a property of the data type and is a function of the methods, their arguments, their return values, and the *abstract* state of their target. We call the full set of commutativity rules for a data type its *commutativity specification.* An example specification for a *Set* is shown in \autoref{tab:spec}. It is important to note that interface choice affects commutativity: if `add(x)` returned a boolean that expressed if the item was added or not, then `add(x)` would only commute with `add(y)` if $x \ne y$. In this case, the difference doesn't drastically impact commutativity, but it would affect the cost of checking commutativity dynamically. For a given data type interface, there is one specification that expresses the maximum concurrency, like the one in \autoref{tab:spec}, but there may be many that express varying degrees of commutativity. The space of possible specifications forms a *lattice* where $\top$ specifies the maximum possible commutativity, and $\bot$ represents the case where no operations are allowed to commute. As Kulkarni \cite{Kulkarni:PLDI11} explored, there is a complicated tradeoff between exposing more concurrency and efficiently tracking commutativity. Data structure designers and users navigate these choices to optimize their programs. ## Transactional Boosting If two operations on the same record in two different transactions commute, then the transactions can safely execute concurrently, even though they both update the record. This technique of raising the level of abstraction in transactions to operations is known as *transactional boosting* \cite{Herlihy:PPoPP08}. This straightforward use of commutativity was shown to significantly improve abort rates in state-of-the-art software transactional memory. In \autoref{eval}, we show how it can be applied to distributed transactions. ## Other opportunities Sometimes, due to heavily skewed workloads such as those arising from social networks, there may be so many requests to a single record that just executing all the operations, even without aborting, is a bottleneck which prevents scaling. The Ellen Degeneres selfie retweet is a prime example of this. In addition to transactional boosting, which we evaluate in this work, there are many other uses for commutativity. We mention just a few here which we have yet to evaluate. ### Record splitting for parallelism Doppel \cite{Narula:OSDI14} observed that several contentious operations, such as incrementing counters or keeping track of the maximum bid, actually commute because the application doesn't need the output of each update operation. This allows them to *split* hot records onto multiple cores and execute commutative operations in parallel, *reconciling* them back to a single value before executing reads or non-commuting operations. This observation can be generalized via ADTs: operations can operate on copies of a record in parallel provided they commute with each other and provided they can be combined at the end of a phase before beginning to execute a new phase with a different set of operations that didn't commute with the first set. ### Combining Another way to reduce contention on a shared data structure is to synchronize hierarchically: first with a couple immediate neighbors, then possibly with more clusters of neighbors, and finally with the data structure itself. This is known as combining \cite{flatCombining,yew:combining-trees,funnels} in the multi-processing literature, and could be applied to contended records in our model just as well as to shared data structures where it originated. # Data type selection Choosing the right data type for your application can have profound performance implications. As mentioned before, the interface can determine what commutes simply by exposing more information than necessary. By selecting the semantics that are most permissive or specialized for their particular use case, programmers can ensure that the system is given the best chance of scaling performance effectively. By allowing approximations or non-determinism, performance may be further improved. ## Unique identifiers As an extremely simple motivating example, imagine a programmer wants a unique identifier for each new post. They might naively choose a `Counter` which returns the next number in the sequence whenever `next` is called. Ensuring each caller gets the next value without skipping any ends up being very expensive, as implementers of TPC-C \cite{TPCC}, which explicitly requires this, know well. In most cases, however, the programmer could use a special `UniqueID` type, whose only criteria is that each call to `next` returns a different value, which can be implemented trivially in a number of efficient highly-concurrent ways. ## Probabilistic data types Some data types have *probabilistic* guarantees about their semantics, which, rather than always returning a precisely correct answer, trade off some accuracy for better performance or storage. Some better-known examples include *bloom filters*\cite{bloom}, *hyperloglog* \cite{hyperloglog}, and *count-min sketch* \cite{countminsketch}. Hyperloglog, which also appears in Redis \cite{redis}, estimates the cardinality (size) of a set within a fixed error bound. Twitter's streaming analytics system \cite{summingbird} leverages these probabilistic data types to handle the high volume of data needing to be processed. We expect similar improvements to be had from their use in Claret. ## Conflict-free replicated data types CRDTs, which were invented for eventual consistency, can actually be fit into our model as well, as a new kind of data type with loosly synchronized semantics. These data types might allow multiple copies in different shards to asynchronously update each other on the operations they've seen. By defining the same kind of *merge* function as traditional CRDTs, these replicas could ensure they all converge to the same state. For instance, a Set CRDT must decide what to do when two clients concurrently add and remove the same key — usually this is handled by choosing a preference for adds. Clients of this data type might find it more difficult to reason about, since a remove may appear to never have happened, but one can imagine making this tradeoff in parts of the application where it otherwise cannot scale. This mixing in of non-serializability should not be taken lightly. To ensure that serializable transactions aren't tainted by inconsistent information from these kinds of data types, some form of information flow or static analysis (via a type system) could be employed in client code. # Evaluation {#eval} To show the efficacy of leveraging commutative operations, we use an application typical of web workloads: a simplified Twitter clone known as *Retwis*. In \autoref{tput} you can see that with commutativity, transaction throughput scales with increased concurrency. ```{r throughput, fig.cap="Throughput on uniform random workload.\\label{tput}", fig.width=3.5, fig.height=3, echo=F, message=F, warning=F, error=F} data <- function(d) { d$abort_rate <- d$txn_failed / (d$txn_count + d$txn_failed) d$throughput <- d$txn_count * num(d$nclients) / d$total_time # d$throughput <- d$ntxns * num(d$nclients) / d$total_time d$avg_latency_ms <- d$txn_time / d$txn_count * 1000 return(d) } d <- data(db(" select * from tapir where generator_time is not null and total_time is not null and (initusers = 50 or initusers = 500) and name like 'claret-v%' ", factors=c('nshards', 'nclients'), numeric=c('total_time', 'txn_count') )) ggplot(d, aes( x = nclients, y = throughput, group = ccmode, fill = ccmode, color = ccmode ))+ # geom_meanbar()+ stat_smooth()+ facet_grid(~nshards, labeller=label_pretty)+ theme_mine ```

%----------------------------------------------------------------------------- % % LaTeX Class/Style File % % Name: sigplanconf.cls % % Purpose: A LaTeX 2e class file for SIGPLAN conference proceedings. % This class file supercedes acm_proc_article-sp, % sig-alternate, and sigplan-proc. % % Author: Paul C. Anagnostopoulos % Windfall Software % 978 371-2316 % paul [atsign] windfall.com % % Created: 12 September 2004 % % Revisions: See end of file. % % This work is licensed under the Creative Commons Attribution License. % To view a copy of this license, visit % http://creativecommons.org/licenses/by/3.0/ % or send a letter to Creative Commons, 171 2nd Street, Suite 300, % San Francisco, California, 94105, U.S.A. % %----------------------------------------------------------------------------- \NeedsTeXFormat{LaTeX2e}[1995/12/01] \ProvidesClass{sigplanconf}[2013/07/02 v2.8 ACM SIGPLAN Proceedings] % The following few pages contain LaTeX programming extensions adapted % from the ZzTeX macro package. % Token Hackery % ----- ------- \def \@expandaftertwice {\expandafter\expandafter\expandafter} \def \@expandafterthrice {\expandafter\expandafter\expandafter\expandafter \expandafter\expandafter\expandafter} % This macro discards the next token. \def \@discardtok #1{}% token % This macro removes the `pt' following a dimension. {\catcode `\p = 12 \catcode `\t = 12 \gdef \@remover #1pt{#1} } % \catcode % This macro extracts the contents of a macro and returns it as plain text. % Usage: \expandafter\@defof \meaning\macro\@mark \def \@defof #1:->#2\@mark{#2} % Control Sequence Names % ------- -------- ----- \def \@name #1{% {\tokens} \csname \expandafter\@discardtok \string#1\endcsname} \def \@withname #1#2{% {\command}{\tokens} \expandafter#1\csname \expandafter\@discardtok \string#2\endcsname} % Flags (Booleans) % ----- ---------- % The boolean literals \@true and \@false are appropriate for use with % the \if command, which tests the codes of the next two characters. \def \@true {TT} \def \@false {FL} \def \@setflag #1=#2{\edef #1{#2}}% \flag = boolean % IF and Predicates % -- --- ---------- % A "predicate" is a macro that returns \@true or \@false as its value. % Such values are suitable for use with the \if conditional. For example: % % \if \@oddp{\x} \else \fi % A predicate can be used with \@setflag as follows: % % \@setflag \flag = {} % Here are the predicates for TeX's repertoire of conditional % commands. These might be more appropriately interspersed with % other definitions in this module, but what the heck. % Some additional "obvious" predicates are defined. \def \@eqlp #1#2{\ifnum #1 = #2\@true \else \@false \fi} \def \@neqlp #1#2{\ifnum #1 = #2\@false \else \@true \fi} \def \@lssp #1#2{\ifnum #1 < #2\@true \else \@false \fi} \def \@gtrp #1#2{\ifnum #1 > #2\@true \else \@false \fi} \def \@zerop #1{\ifnum #1 = 0\@true \else \@false \fi} \def \@onep #1{\ifnum #1 = 1\@true \else \@false \fi} \def \@posp #1{\ifnum #1 > 0\@true \else \@false \fi} \def \@negp #1{\ifnum #1 < 0\@true \else \@false \fi} \def \@oddp #1{\ifodd #1\@true \else \@false \fi} \def \@evenp #1{\ifodd #1\@false \else \@true \fi} \def \@rangep #1#2#3{\if \@orp{\@lssp{#1}{#2}}{\@gtrp{#1}{#3}}\@false \else \@true \fi} \def \@tensp #1{\@rangep{#1}{10}{19}} \def \@dimeqlp #1#2{\ifdim #1 = #2\@true \else \@false \fi} \def \@dimneqlp #1#2{\ifdim #1 = #2\@false \else \@true \fi} \def \@dimlssp #1#2{\ifdim #1 < #2\@true \else \@false \fi} \def \@dimgtrp #1#2{\ifdim #1 > #2\@true \else \@false \fi} \def \@dimzerop #1{\ifdim #1 = 0pt\@true \else \@false \fi} \def \@dimposp #1{\ifdim #1 > 0pt\@true \else \@false \fi} \def \@dimnegp #1{\ifdim #1 < 0pt\@true \else \@false \fi} \def \@vmodep {\ifvmode \@true \else \@false \fi} \def \@hmodep {\ifhmode \@true \else \@false \fi} \def \@mathmodep {\ifmmode \@true \else \@false \fi} \def \@textmodep {\ifmmode \@false \else \@true \fi} \def \@innermodep {\ifinner \@true \else \@false \fi} \long\def \@codeeqlp #1#2{\if #1#2\@true \else \@false \fi} \long\def \@cateqlp #1#2{\ifcat #1#2\@true \else \@false \fi} \long\def \@tokeqlp #1#2{\ifx #1#2\@true \else \@false \fi} \long\def \@xtokeqlp #1#2{\expandafter\ifx #1#2\@true \else \@false \fi} \long\def \@definedp #1{% \expandafter\ifx \csname \expandafter\@discardtok \string#1\endcsname \relax \@false \else \@true \fi} \long\def \@undefinedp #1{% \expandafter\ifx \csname \expandafter\@discardtok \string#1\endcsname \relax \@true \else \@false \fi} \def \@emptydefp #1{\ifx #1\@empty \@true \else \@false \fi}% {\name} \let \@emptylistp = \@emptydefp \long\def \@emptyargp #1{% {#n} \@empargp #1\@empargq\@mark} \long\def \@empargp #1#2\@mark{% \ifx #1\@empargq \@true \else \@false \fi} \def \@empargq {\@empargq} \def \@emptytoksp #1{% {\tokenreg} \expandafter\@emptoksp \the#1\@mark} \long\def \@emptoksp #1\@mark{\@emptyargp{#1}} \def \@voidboxp #1{\ifvoid #1\@true \else \@false \fi} \def \@hboxp #1{\ifhbox #1\@true \else \@false \fi} \def \@vboxp #1{\ifvbox #1\@true \else \@false \fi} \def \@eofp #1{\ifeof #1\@true \else \@false \fi} % Flags can also be used as predicates, as in: % % \if \flaga \else \fi % Now here we have predicates for the common logical operators. \def \@notp #1{\if #1\@false \else \@true \fi} \def \@andp #1#2{\if #1% \if #2\@true \else \@false \fi \else \@false \fi} \def \@orp #1#2{\if #1% \@true \else \if #2\@true \else \@false \fi \fi} \def \@xorp #1#2{\if #1% \if #2\@false \else \@true \fi \else \if #2\@true \else \@false \fi \fi} % Arithmetic % ---------- \def \@increment #1{\advance #1 by 1\relax}% {\count} \def \@decrement #1{\advance #1 by -1\relax}% {\count} % Options % ------- \@setflag \@authoryear = \@false \@setflag \@blockstyle = \@false \@setflag \@copyrightwanted = \@true \@setflag \@explicitsize = \@false \@setflag \@mathtime = \@false \@setflag \@natbib = \@true \@setflag \@ninepoint = \@true \newcount{\@numheaddepth} \@numheaddepth = 3 \@setflag \@onecolumn = \@false \@setflag \@preprint = \@false \@setflag \@reprint = \@false \@setflag \@tenpoint = \@false \@setflag \@times = \@false % Note that all the dangerous article class options are trapped. \DeclareOption{9pt}{\@setflag \@ninepoint = \@true \@setflag \@explicitsize = \@true} \DeclareOption{10pt}{\PassOptionsToClass{10pt}{article}% \@setflag \@ninepoint = \@false \@setflag \@tenpoint = \@true \@setflag \@explicitsize = \@true} \DeclareOption{11pt}{\PassOptionsToClass{11pt}{article}% \@setflag \@ninepoint = \@false \@setflag \@explicitsize = \@true} \DeclareOption{12pt}{\@unsupportedoption{12pt}} \DeclareOption{a4paper}{\@unsupportedoption{a4paper}} \DeclareOption{a5paper}{\@unsupportedoption{a5paper}} \DeclareOption{authoryear}{\@setflag \@authoryear = \@true} \DeclareOption{b5paper}{\@unsupportedoption{b5paper}} \DeclareOption{blockstyle}{\@setflag \@blockstyle = \@true} \DeclareOption{cm}{\@setflag \@times = \@false} \DeclareOption{computermodern}{\@setflag \@times = \@false} \DeclareOption{executivepaper}{\@unsupportedoption{executivepaper}} \DeclareOption{indentedstyle}{\@setflag \@blockstyle = \@false} \DeclareOption{landscape}{\@unsupportedoption{landscape}} \DeclareOption{legalpaper}{\@unsupportedoption{legalpaper}} \DeclareOption{letterpaper}{\@unsupportedoption{letterpaper}} \DeclareOption{mathtime}{\@setflag \@mathtime = \@true} \DeclareOption{natbib}{\@setflag \@natbib = \@true} \DeclareOption{nonatbib}{\@setflag \@natbib = \@false} \DeclareOption{nocopyrightspace}{\@setflag \@copyrightwanted = \@false} \DeclareOption{notitlepage}{\@unsupportedoption{notitlepage}} \DeclareOption{numberedpars}{\@numheaddepth = 4} \DeclareOption{numbers}{\@setflag \@authoryear = \@false} %%%\DeclareOption{onecolumn}{\@setflag \@onecolumn = \@true} \DeclareOption{preprint}{\@setflag \@preprint = \@true} \DeclareOption{reprint}{\@setflag \@reprint = \@true} \DeclareOption{times}{\@setflag \@times = \@true} \DeclareOption{titlepage}{\@unsupportedoption{titlepage}} \DeclareOption{twocolumn}{\@setflag \@onecolumn = \@false} \DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}} \ExecuteOptions{9pt,indentedstyle,times} \@setflag \@explicitsize = \@false \ProcessOptions \if \@onecolumn \if \@notp{\@explicitsize}% \@setflag \@ninepoint = \@false \PassOptionsToClass{11pt}{article}% \fi \PassOptionsToClass{twoside,onecolumn}{article} \else \PassOptionsToClass{twoside,twocolumn}{article} \fi \LoadClass{article} \def \@unsupportedoption #1{% \ClassError{proc}{The standard '#1' option is not supported.}} % This can be used with the 'reprint' option to get the final folios. \def \setpagenumber #1{% \setcounter{page}{#1}} \AtEndDocument{\label{sigplanconf@finalpage}} % Utilities % --------- \newcommand{\setvspace}[2]{% #1 = #2 \advance #1 by -1\parskip} % Document Parameters % -------- ---------- % Page: \setlength{\hoffset}{-1in} \setlength{\voffset}{-1in} \setlength{\topmargin}{1in} \setlength{\headheight}{0pt} \setlength{\headsep}{0pt} \if \@onecolumn \setlength{\evensidemargin}{.75in} \setlength{\oddsidemargin}{.75in} \else \setlength{\evensidemargin}{.75in} \setlength{\oddsidemargin}{.75in} \fi % Text area: \newdimen{\standardtextwidth} \setlength{\standardtextwidth}{42pc} \if \@onecolumn \setlength{\textwidth}{40.5pc} \else \setlength{\textwidth}{\standardtextwidth} \fi \setlength{\topskip}{8pt} \setlength{\columnsep}{2pc} \setlength{\textheight}{54.5pc} % Running foot: \setlength{\footskip}{30pt} % Paragraphs: \if \@blockstyle \setlength{\parskip}{5pt plus .1pt minus .5pt} \setlength{\parindent}{0pt} \else \setlength{\parskip}{0pt} \setlength{\parindent}{12pt} \fi \setlength{\lineskip}{.5pt} \setlength{\lineskiplimit}{\lineskip} \frenchspacing \pretolerance = 400 \tolerance = \pretolerance \setlength{\emergencystretch}{5pt} \clubpenalty = 10000 \widowpenalty = 10000 \setlength{\hfuzz}{.5pt} % Standard vertical spaces: \newskip{\standardvspace} \setvspace{\standardvspace}{5pt plus 1pt minus .5pt} % Margin paragraphs: \setlength{\marginparwidth}{36pt} \setlength{\marginparsep}{2pt} \setlength{\marginparpush}{8pt} \setlength{\skip\footins}{8pt plus 3pt minus 1pt} \setlength{\footnotesep}{9pt} \renewcommand{\footnoterule}{% \hrule width .5\columnwidth height .33pt depth 0pt} \renewcommand{\@makefntext}[1]{% \noindent \@makefnmark \hspace{1pt}#1} % Floats: \setcounter{topnumber}{4} \setcounter{bottomnumber}{1} \setcounter{totalnumber}{4} \renewcommand{\fps@figure}{tp} \renewcommand{\fps@table}{tp} \renewcommand{\topfraction}{0.90} \renewcommand{\bottomfraction}{0.30} \renewcommand{\textfraction}{0.10} \renewcommand{\floatpagefraction}{0.75} \setcounter{dbltopnumber}{4} \renewcommand{\dbltopfraction}{\topfraction} \renewcommand{\dblfloatpagefraction}{\floatpagefraction} \setlength{\floatsep}{18pt plus 4pt minus 2pt} \setlength{\textfloatsep}{18pt plus 4pt minus 3pt} \setlength{\intextsep}{10pt plus 4pt minus 3pt} \setlength{\dblfloatsep}{18pt plus 4pt minus 2pt} \setlength{\dbltextfloatsep}{20pt plus 4pt minus 3pt} % Miscellaneous: \errorcontextlines = 5 % Fonts % ----- \if \@times \renewcommand{\rmdefault}{ptm}% \if \@mathtime \usepackage[mtbold,noTS1]{mathtime}% \else %%% \usepackage{mathptm}% \fi \else \relax \fi \if \@ninepoint \renewcommand{\normalsize}{% \@setfontsize{\normalsize}{9pt}{10pt}% \setlength{\abovedisplayskip}{5pt plus 1pt minus .5pt}% \setlength{\belowdisplayskip}{\abovedisplayskip}% \setlength{\abovedisplayshortskip}{3pt plus 1pt minus 2pt}% \setlength{\belowdisplayshortskip}{\abovedisplayshortskip}} \renewcommand{\tiny}{\@setfontsize{\tiny}{5pt}{6pt}} \renewcommand{\scriptsize}{\@setfontsize{\scriptsize}{7pt}{8pt}} \renewcommand{\small}{% \@setfontsize{\small}{8pt}{9pt}% \setlength{\abovedisplayskip}{4pt plus 1pt minus 1pt}% \setlength{\belowdisplayskip}{\abovedisplayskip}% \setlength{\abovedisplayshortskip}{2pt plus 1pt}% \setlength{\belowdisplayshortskip}{\abovedisplayshortskip}} \renewcommand{\footnotesize}{% \@setfontsize{\footnotesize}{8pt}{9pt}% \setlength{\abovedisplayskip}{4pt plus 1pt minus .5pt}% \setlength{\belowdisplayskip}{\abovedisplayskip}% \setlength{\abovedisplayshortskip}{2pt plus 1pt}% \setlength{\belowdisplayshortskip}{\abovedisplayshortskip}} \renewcommand{\large}{\@setfontsize{\large}{11pt}{13pt}} \renewcommand{\Large}{\@setfontsize{\Large}{14pt}{18pt}} \renewcommand{\LARGE}{\@setfontsize{\LARGE}{18pt}{20pt}} \renewcommand{\huge}{\@setfontsize{\huge}{20pt}{25pt}} \renewcommand{\Huge}{\@setfontsize{\Huge}{25pt}{30pt}} \else\if \@tenpoint \relax \else \relax \fi\fi % Abstract % -------- \renewenvironment{abstract}{% \section*{Abstract}% \normalsize}{% } % Bibliography % ------------ \renewenvironment{thebibliography}[1] {\section*{\refname \@mkboth{\MakeUppercase\refname}{\MakeUppercase\refname}}% \list{\@biblabel{\@arabic\c@enumiv}}% {\settowidth\labelwidth{\@biblabel{#1}}% \leftmargin\labelwidth \advance\leftmargin\labelsep \@openbib@code \usecounter{enumiv}% \let\p@enumiv\@empty \renewcommand\theenumiv{\@arabic\c@enumiv}}% \bibfont \clubpenalty4000 \@clubpenalty \clubpenalty \widowpenalty4000% \sfcode`\.\@m} {\def\@noitemerr {\@latex@warning{Empty `thebibliography' environment}}% \endlist} \if \@natbib \if \@authoryear \typeout{Using natbib package with 'authoryear' citation style.} \usepackage[authoryear,square]{natbib} \bibpunct{(}{)}{;}{a}{}{,} % Change fences to parentheses; % citation separator to semicolon; % eliminate comma between author and year. \let \cite = \citep \else \typeout{Using natbib package with 'numbers' citation style.} \usepackage[numbers,sort&compress,square]{natbib} \fi \setlength{\bibsep}{3pt plus .5pt minus .25pt} \fi \def \bibfont {\small} % Categories % ---------- \@setflag \@firstcategory = \@true \newcommand{\category}[3]{% \if \@firstcategory \paragraph*{Categories and Subject Descriptors}% \@setflag \@firstcategory = \@false \else \unskip ;\hspace{.75em}% \fi \@ifnextchar [{\@category{#1}{#2}{#3}}{\@category{#1}{#2}{#3}[]}} \def \@category #1#2#3[#4]{% {\let \and = \relax #1 [\textit{#2}]% \if \@emptyargp{#4}% \if \@notp{\@emptyargp{#3}}: #3\fi \else :\space \if \@notp{\@emptyargp{#3}}#3---\fi \textrm{#4}% \fi}} % Copyright Notice % --------- ------ \def \ftype@copyrightbox {8} \def \@toappear {} \def \@permission {} \def \@reprintprice {} \def \@copyrightspace {% \@float{copyrightbox}[b]% \vbox to 1.2in{% \vfill \parbox[b]{20pc}{% \scriptsize \if \@preprint [Copyright notice will appear here once 'preprint' option is removed.]\par \else \@toappear \fi \if \@reprint \noindent Reprinted from \@conferencename, \@proceedings, \@conferenceinfo, pp.~\number\thepage--\pageref{sigplanconf@finalpage}.\par \fi}}% \end@float} \newcommand{\reprintprice}[1]{% \gdef \@reprintprice {#1}} \reprintprice{\$15.00} \long\def \toappear #1{% \def \@toappear {#1}} \toappear{% \noindent \@permission \par \vspace{2pt} \noindent \textsl{\@conferencename}, \quad \@conferenceinfo. \par \noindent Copyright \copyright\ \@copyrightyear\ ACM \@copyrightdata \dots \@reprintprice.\par \noindent http://dx.doi.org/10.1145/\@doi } \newcommand{\permission}[1]{% \gdef \@permission {#1}} \permission{% Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].} % These are two new rights management and bibstrip text blocks. \newcommand{\exclusivelicense}{% \permission{% Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].} \toappear{% \noindent \@permission \par \vspace{2pt} \noindent \textsl{\@conferencename}, \quad \@conferenceinfo. \par \noindent Copyright is held by the owner/author(s). Publication rights licensed to ACM. \par \noindent ACM \@copyrightdata \dots \@reprintprice.\par \noindent http://dx.doi.org/10.1145/\@doi}} \newcommand{\permissiontopublish}{% \permission{% Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).}% \toappear{% \noindent \@permission \par \vspace{2pt} \noindent \textsl{\@conferencename}, \quad \@conferenceinfo. \par \noindent Copyright is held by the owner/author(s). \par \noindent ACM \@copyrightdata.\par \noindent http://dx.doi.org/10.1145/\@doi}} % The following permission notices are % for the traditional copyright transfer agreement option. % Exclusive license and permission-to-publish % give more complicated permission notices. % These are not covered here. \newcommand{\ACMCanadapermission}{% \permission{% ACM acknowledges that this contribution was authored or co-authored by an affiliate of the Canadian National Government. As such, the Crown in Right of Canada retains an equal interest in the copyright. Reprint requests should be forwarded to ACM.}} \newcommand{\ACMUSpermission}{% \permission{% ACM acknowledges that this contribution was authored or co-authored by a contractor or affiliate of the United States Government. As such, the United States Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.}} \newcommand{\USpublicpermission}{% \permission{% This paper is authored by an employee(s) of the United States Government and is in the public domain. Non-exclusive copying or redistribution is allowed, provided that the article citation is given and the authors and the agency are clearly identified as its source.}% \toappear{% \noindent \@permission \par \vspace{2pt} \noindent \textsl{\@conferencename}, \quad \@conferenceinfo. \par \noindent ACM \@copyrightdata.\par \noindent http://dx.doi.org/10.1145/\@doi}} \newcommand{\authorversion}[4]{% \permission{% Copyright \copyright\ ACM, #1. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in #2, #3, http://dx.doi.org/10.1145/#4.}} % Enunciations % ------------ \def \@begintheorem #1#2{% {name}{number} \trivlist \item[\hskip \labelsep \textsc{#1 #2.}]% \itshape\selectfont \ignorespaces} \def \@opargbegintheorem #1#2#3{% {name}{number}{title} \trivlist \item[% \hskip\labelsep \textsc{#1\ #2}% \if \@notp{\@emptyargp{#3}}\nut (#3).\fi]% \itshape\selectfont \ignorespaces} % Figures % ------- \@setflag \@caprule = \@true \long\def \@makecaption #1#2{% \addvspace{4pt} \if \@caprule \hrule width \hsize height .33pt \vspace{4pt} \fi \setbox \@tempboxa = \hbox{\@setfigurenumber{#1.}\nut #2}% \if \@dimgtrp{\wd\@tempboxa}{\hsize}% \noindent \@setfigurenumber{#1.}\nut #2\par \else \centerline{\box\@tempboxa}% \fi} \newcommand{\nocaptionrule}{% \@setflag \@caprule = \@false} \def \@setfigurenumber #1{% {\rmfamily \bfseries \selectfont #1}} % Hierarchy % --------- \setcounter{secnumdepth}{\@numheaddepth} \newskip{\@sectionaboveskip} \setvspace{\@sectionaboveskip}{10pt plus 3pt minus 2pt} \newskip{\@sectionbelowskip} \if \@blockstyle \setlength{\@sectionbelowskip}{0.1pt}% \else \setlength{\@sectionbelowskip}{4pt}% \fi \renewcommand{\section}{% \@startsection {section}% {1}% {0pt}% {-\@sectionaboveskip}% {\@sectionbelowskip}% {\large \bfseries \raggedright}} \newskip{\@subsectionaboveskip} \setvspace{\@subsectionaboveskip}{8pt plus 2pt minus 2pt} \newskip{\@subsectionbelowskip} \if \@blockstyle \setlength{\@subsectionbelowskip}{0.1pt}% \else \setlength{\@subsectionbelowskip}{4pt}% \fi \renewcommand{\subsection}{% \@startsection% {subsection}% {2}% {0pt}% {-\@subsectionaboveskip}% {\@subsectionbelowskip}% {\normalsize \bfseries \raggedright}} \renewcommand{\subsubsection}{% \@startsection% {subsubsection}% {3}% {0pt}% {-\@subsectionaboveskip} {\@subsectionbelowskip}% {\normalsize \bfseries \raggedright}} \newskip{\@paragraphaboveskip} \setvspace{\@paragraphaboveskip}{6pt plus 2pt minus 2pt} \renewcommand{\paragraph}{% \@startsection% {paragraph}% {4}% {0pt}% {\@paragraphaboveskip} {-1em}% {\normalsize \bfseries \if \@times \itshape \fi}} \renewcommand{\subparagraph}{% \@startsection% {subparagraph}% {4}% {0pt}% {\@paragraphaboveskip} {-1em}% {\normalsize \itshape}} % Standard headings: \newcommand{\acks}{\section*{Acknowledgments}} \newcommand{\keywords}{\paragraph*{Keywords}} \newcommand{\terms}{\paragraph*{General Terms}} % Identification % -------------- \def \@conferencename {} \def \@conferenceinfo {} \def \@copyrightyear {} \def \@copyrightdata {[to be supplied]} \def \@proceedings {[Unknown Proceedings]} \newcommand{\conferenceinfo}[2]{% \gdef \@conferencename {#1}% \gdef \@conferenceinfo {#2}} \newcommand{\copyrightyear}[1]{% \gdef \@copyrightyear {#1}} \let \CopyrightYear = \copyrightyear \newcommand{\copyrightdata}[1]{% \gdef \@copyrightdata {#1}} \let \crdata = \copyrightdata \newcommand{\doi}[1]{% \gdef \@doi {#1}} \newcommand{\proceedings}[1]{% \gdef \@proceedings {#1}} % Lists % ----- \setlength{\leftmargini}{13pt} \setlength\leftmarginii{13pt} \setlength\leftmarginiii{13pt} \setlength\leftmarginiv{13pt} \setlength{\labelsep}{3.5pt} \setlength{\topsep}{\standardvspace} \if \@blockstyle \setlength{\itemsep}{1pt} \setlength{\parsep}{3pt} \else \setlength{\itemsep}{1pt} \setlength{\parsep}{3pt} \fi \renewcommand{\labelitemi}{{\small \centeroncapheight{\textbullet}}} \renewcommand{\labelitemii}{\centeroncapheight{\rule{2.5pt}{2.5pt}}} \renewcommand{\labelitemiii}{$-$} \renewcommand{\labelitemiv}{{\Large \textperiodcentered}} \renewcommand{\@listi}{% \leftmargin = \leftmargini \listparindent = 0pt} %%% \itemsep = 1pt %%% \parsep = 3pt} %%% \listparindent = \parindent} \let \@listI = \@listi \renewcommand{\@listii}{% \leftmargin = \leftmarginii \topsep = 1pt \labelwidth = \leftmarginii \advance \labelwidth by -\labelsep \listparindent = \parindent} \renewcommand{\@listiii}{% \leftmargin = \leftmarginiii \labelwidth = \leftmarginiii \advance \labelwidth by -\labelsep \listparindent = \parindent} \renewcommand{\@listiv}{% \leftmargin = \leftmarginiv \labelwidth = \leftmarginiv \advance \labelwidth by -\labelsep \listparindent = \parindent} % Mathematics % ----------- \def \theequation {\arabic{equation}} % Miscellaneous % ------------- \newcommand{\balancecolumns}{% \vfill\eject \global\@colht = \textheight \global\ht\@cclv = \textheight} \newcommand{\nut}{\hspace{.5em}} \newcommand{\softraggedright}{% \let \\ = \@centercr \leftskip = 0pt \rightskip = 0pt plus 10pt} % Program Code % ------- ---- \newcommand{\mono}[1]{% {\@tempdima = \fontdimen2\font \texttt{\spaceskip = 1.1\@tempdima #1}}} % Running Heads and Feet % ------- ----- --- ---- \def \@preprintfooter {} \newcommand{\preprintfooter}[1]{% \gdef \@preprintfooter {#1}} \if \@preprint \def \ps@plain {% \let \@mkboth = \@gobbletwo \let \@evenhead = \@empty \def \@evenfoot {\scriptsize \rlap{\textit{\@preprintfooter}}\hfil \thepage \hfil \llap{\textit{\@formatyear}}}% \let \@oddhead = \@empty \let \@oddfoot = \@evenfoot} \else\if \@reprint \def \ps@plain {% \let \@mkboth = \@gobbletwo \let \@evenhead = \@empty \def \@evenfoot {\scriptsize \hfil \thepage \hfil}% \let \@oddhead = \@empty \let \@oddfoot = \@evenfoot} \else \let \ps@plain = \ps@empty \let \ps@headings = \ps@empty \let \ps@myheadings = \ps@empty \fi\fi \def \@formatyear {% \number\year/\number\month/\number\day} % Special Characters % ------- ---------- \DeclareRobustCommand{\euro}{% \protect{\rlap{=}}{\sf \kern .1em C}} % Title Page % ----- ---- \@setflag \@addauthorsdone = \@false \def \@titletext {\@latex@error{No title was provided}{}} \def \@subtitletext {} \newcount{\@authorcount} \newcount{\@titlenotecount} \newtoks{\@titlenotetext} \def \@titlebanner {} \renewcommand{\title}[1]{% \gdef \@titletext {#1}} \newcommand{\subtitle}[1]{% \gdef \@subtitletext {#1}} \newcommand{\authorinfo}[3]{% {names}{affiliation}{email/URL} \global\@increment \@authorcount \@withname\gdef {\@authorname\romannumeral\@authorcount}{#1}% \@withname\gdef {\@authoraffil\romannumeral\@authorcount}{#2}% \@withname\gdef {\@authoremail\romannumeral\@authorcount}{#3}} \renewcommand{\author}[1]{% \@latex@error{The \string\author\space command is obsolete; use \string\authorinfo}{}} \newcommand{\titlebanner}[1]{% \gdef \@titlebanner {#1}} \renewcommand{\maketitle}{% \pagestyle{plain}% \if \@onecolumn {\hsize = \standardtextwidth \@maketitle}% \else \twocolumn[\@maketitle]% \fi \@placetitlenotes \if \@copyrightwanted \@copyrightspace \fi} \def \@maketitle {% \begin{center} \@settitlebanner \let \thanks = \titlenote {\leftskip = 0pt plus 0.25\linewidth \rightskip = 0pt plus 0.25 \linewidth \parfillskip = 0pt \spaceskip = .7em \noindent \LARGE \bfseries \@titletext \par} \vskip 6pt \noindent \Large \@subtitletext \par \vskip 12pt \ifcase \@authorcount \@latex@error{No authors were specified for this paper}{}\or \@titleauthors{i}{}{}\or \@titleauthors{i}{ii}{}\or \@titleauthors{i}{ii}{iii}\or \@titleauthors{i}{ii}{iii}\@titleauthors{iv}{}{}\or \@titleauthors{i}{ii}{iii}\@titleauthors{iv}{v}{}\or \@titleauthors{i}{ii}{iii}\@titleauthors{iv}{v}{vi}\or \@titleauthors{i}{ii}{iii}\@titleauthors{iv}{v}{vi}% \@titleauthors{vii}{}{}\or \@titleauthors{i}{ii}{iii}\@titleauthors{iv}{v}{vi}% \@titleauthors{vii}{viii}{}\or \@titleauthors{i}{ii}{iii}\@titleauthors{iv}{v}{vi}% \@titleauthors{vii}{viii}{ix}\or \@titleauthors{i}{ii}{iii}\@titleauthors{iv}{v}{vi}% \@titleauthors{vii}{viii}{ix}\@titleauthors{x}{}{}\or \@titleauthors{i}{ii}{iii}\@titleauthors{iv}{v}{vi}% \@titleauthors{vii}{viii}{ix}\@titleauthors{x}{xi}{}\or \@titleauthors{i}{ii}{iii}\@titleauthors{iv}{v}{vi}% \@titleauthors{vii}{viii}{ix}\@titleauthors{x}{xi}{xii}% \else \@latex@error{Cannot handle more than 12 authors}{}% \fi \vspace{1.75pc} \end{center}} \def \@settitlebanner {% \if \@andp{\@preprint}{\@notp{\@emptydefp{\@titlebanner}}}% \vbox to 0pt{% \vskip -32pt \noindent \textbf{\@titlebanner}\par \vss}% \nointerlineskip \fi} \def \@titleauthors #1#2#3{% \if \@andp{\@emptyargp{#2}}{\@emptyargp{#3}}% \noindent \@setauthor{40pc}{#1}{\@false}\par \else\if \@emptyargp{#3}% \noindent \@setauthor{17pc}{#1}{\@false}\hspace{3pc}% \@setauthor{17pc}{#2}{\@false}\par \else \noindent \@setauthor{12.5pc}{#1}{\@false}\hspace{2pc}% \@setauthor{12.5pc}{#2}{\@false}\hspace{2pc}% \@setauthor{12.5pc}{#3}{\@true}\par \relax \fi\fi \vspace{20pt}} \def \@setauthor #1#2#3{% {width}{text}{unused} \vtop{% \def \and {% \hspace{16pt}} \hsize = #1 \normalfont \centering \large \@name{\@authorname#2}\par \vspace{5pt} \normalsize \@name{\@authoraffil#2}\par \vspace{2pt} \textsf{\@name{\@authoremail#2}}\par}} \def \@maybetitlenote #1{% \if \@andp{#1}{\@gtrp{\@authorcount}{3}}% \titlenote{See page~\pageref{@addauthors} for additional authors.}% \fi} \newtoks{\@fnmark} \newcommand{\titlenote}[1]{% \global\@increment \@titlenotecount \ifcase \@titlenotecount \relax \or \@fnmark = {\ast}\or \@fnmark = {\dagger}\or \@fnmark = {\ddagger}\or \@fnmark = {\S}\or \@fnmark = {\P}\or \@fnmark = {\ast\ast}% \fi \,$^{\the\@fnmark}$% \edef \reserved@a {\noexpand\@appendtotext{% \noexpand\@titlefootnote{\the\@fnmark}}}% \reserved@a{#1}} \def \@appendtotext #1#2{% \global\@titlenotetext = \expandafter{\the\@titlenotetext #1{#2}}} \newcount{\@authori} \iffalse \def \additionalauthors {% \if \@gtrp{\@authorcount}{3}% \section{Additional Authors}% \label{@addauthors}% \noindent \@authori = 4 {\let \\ = ,% \loop \textbf{\@name{\@authorname\romannumeral\@authori}}, \@name{\@authoraffil\romannumeral\@authori}, email: \@name{\@authoremail\romannumeral\@authori}.% \@increment \@authori \if \@notp{\@gtrp{\@authori}{\@authorcount}} \repeat}% \par \fi \global\@setflag \@addauthorsdone = \@true} \fi \let \addauthorsection = \additionalauthors \def \@placetitlenotes { \the\@titlenotetext} % Utilities % --------- \newcommand{\centeroncapheight}[1]{% {\setbox\@tempboxa = \hbox{#1}% \@measurecapheight{\@tempdima}% % Calculate ht(CAP) - ht(text) \advance \@tempdima by -\ht\@tempboxa % ------------------ \divide \@tempdima by 2 % 2 \raise \@tempdima \box\@tempboxa}} \newbox{\@measbox} \def \@measurecapheight #1{% {\dimen} \setbox\@measbox = \hbox{ABCDEFGHIJKLMNOPQRSTUVWXYZ}% #1 = \ht\@measbox} \long\def \@titlefootnote #1#2{% \insert\footins{% \reset@font\footnotesize \interlinepenalty\interfootnotelinepenalty \splittopskip\footnotesep \splitmaxdepth \dp\strutbox \floatingpenalty \@MM \hsize\columnwidth \@parboxrestore %%% \protected@edef\@currentlabel{% %%% \csname p@footnote\endcsname\@thefnmark}% \color@begingroup \def \@makefnmark {$^{#1}$}% \@makefntext{% \rule\z@\footnotesep\ignorespaces#2\@finalstrut\strutbox}% \color@endgroup}} % LaTeX Modifications % ----- ------------- \def \@seccntformat #1{% \@name{\the#1}% \@expandaftertwice\@seccntformata \csname the#1\endcsname.\@mark \quad} \def \@seccntformata #1.#2\@mark{% \if \@emptyargp{#2}.\fi} % Revision History % -------- ------- % Date Person Ver. Change % ---- ------ ---- ------ % 2004.09.12 PCA 0.1--4 Preliminary development. % 2004.11.18 PCA 0.5 Start beta testing. % 2004.11.19 PCA 0.6 Obsolete \author and replace with % \authorinfo. % Add 'nocopyrightspace' option. % Compress article opener spacing. % Add 'mathtime' option. % Increase text height by 6 points. % 2004.11.28 PCA 0.7 Add 'cm/computermodern' options. % Change default to Times text. % 2004.12.14 PCA 0.8 Remove use of mathptm.sty; it cannot % coexist with latexsym or amssymb. % 2005.01.20 PCA 0.9 Rename class file to sigplanconf.cls. % 2005.03.05 PCA 0.91 Change default copyright data. % 2005.03.06 PCA 0.92 Add at-signs to some macro names. % 2005.03.07 PCA 0.93 The 'onecolumn' option defaults to '11pt', % and it uses the full type width. % 2005.03.15 PCA 0.94 Add at-signs to more macro names. % Allow margin paragraphs during review. % 2005.03.22 PCA 0.95 Implement \euro. % Remove proof and newdef environments. % 2005.05.06 PCA 1.0 Eliminate 'onecolumn' option. % Change footer to small italic and eliminate % left portion if no \preprintfooter. % Eliminate copyright notice if preprint. % Clean up and shrink copyright box. % 2005.05.30 PCA 1.1 Add alternate permission statements. % 2005.06.29 PCA 1.1 Publish final first edition of guide. % 2005.07.14 PCA 1.2 Add \subparagraph. % Use block paragraphs in lists, and adjust % spacing between items and paragraphs. % 2006.06.22 PCA 1.3 Add 'reprint' option and associated % commands. % 2006.08.24 PCA 1.4 Fix bug in \maketitle case command. % 2007.03.13 PCA 1.5 The title banner only displays with the % 'preprint' option. % 2007.06.06 PCA 1.6 Use \bibfont in \thebibliography. % Add 'natbib' option to load and configure % the natbib package. % 2007.11.20 PCA 1.7 Balance line lengths in centered article % title (thanks to Norman Ramsey). % 2009.01.26 PCA 1.8 Change natbib \bibpunct values. % 2009.03.24 PCA 1.9 Change natbib to use the 'numbers' option. % Change templates to use 'natbib' option. % 2009.09.01 PCA 2.0 Add \reprintprice command (suggested by % Stephen Chong). % 2009.09.08 PCA 2.1 Make 'natbib' the default; add 'nonatbib'. % SB Add 'authoryear' and 'numbers' (default) to % control citation style when using natbib. % Add \bibpunct to change punctuation for % 'authoryear' style. % 2009.09.21 PCA 2.2 Add \softraggedright to the thebibliography % environment. Also add to template so it will % happen with natbib. % 2009.09.30 PCA 2.3 Remove \softraggedright from thebibliography. % Just include in the template. % 2010.05.24 PCA 2.4 Obfuscate class author's email address. % 2011.11.08 PCA 2.5 Add copyright notice to this file. % Remove 'sort' option from natbib when using % 'authoryear' style. % Add the \authorversion command. % 2013.02.22 PCA 2.6 Change natbib fences to parentheses when % using 'authoryear' style. % 2013.05.17 PCA 2.7 Change standard and author copyright text. % 2013.07.02 TU 2.8 More changes to permission/copyright notes. % Replaced ambiguous \authorpermission with % \exclusivelicense and \permissiontopublish

$title$

$body$

\documentclass[10pt $if(preprint)$, preprint$endif$]{sigplanconf} % amsmath package, useful for mathematical formulas \usepackage{amsmath} % amssymb package, useful for mathematical symbols \usepackage{amssymb} % graphicx package, useful for including eps and pdf graphics % include graphics with the command \includegraphics \usepackage{graphicx} % \usepackage{longtable,booktabs} % % \makeatletter % \let\oldlt\longtable % \let\endoldlt\endlongtable % \def\longtable{\@ifnextchar[\longtable@i \longtable@ii} % \def\longtable@i[#1]{\begin{figure}[t] % \onecolumn % \begin{minipage}{0.5\textwidth} % \oldlt[#1] % } % \def\longtable@ii{\begin{figure}[t] % \onecolumn % \begin{minipage}{0.5\textwidth} % \oldlt % } % \def\endlongtable{\endoldlt % \end{minipage} % \twocolumn % \end{figure}} % \makeatother % cite package, to clean up citations in the main text. Do not remove. % \usepackage{cite} \usepackage{color} \usepackage[scaled=0.8]{inconsolata} \usepackage{ifxetex,ifluatex} \ifxetex \usepackage{fontspec,xltxtra,xunicode} \defaultfontfeatures{Mapping=tex-text,Scale=MatchLowercase} \newcommand{\euro}{€} \else \ifluatex \usepackage{fontspec} \defaultfontfeatures{Mapping=tex-text,Scale=MatchLowercase} \newcommand{\euro}{€} \else \usepackage[utf8]{inputenc} \usepackage{eurosym} \fi \fi \usepackage{color} \usepackage{fancyvrb} \DefineShortVerb[commandchars=\\\{\}]{\|} \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}} % Add ',fontsize=\small' for more characters per line \newenvironment{Shaded}{}{} \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{{#1}}}} \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{{#1}}} \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{{#1}}} \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{{#1}}} \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{{#1}}} \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}} \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}} \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{{#1}}}} \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{{#1}}} \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{{#1}}}} \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{{#1}}} \newcommand{\RegionMarkerTok}[1]{{#1}} \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{{#1}}}} \newcommand{\NormalTok}[1]{{#1}} \ifxetex \usepackage[setpagesize=false, % page size defined by xetex unicode=false, % unicode breaks when used with xetex xetex, colorlinks=true, linkcolor=blue]{hyperref} \else \usepackage[unicode=true, colorlinks=true, linkcolor=blue]{hyperref} \fi \hypersetup{breaklinks=true, pdfborder={0 0 0}} \setlength{\parindent}{0pt} \setlength{\parskip}{6pt plus 2pt minus 1pt} \setlength{\emergencystretch}{3em} % prevent overfull lines % \setcounter{secnumdepth}{0} % \EndDefineVerbatimEnvironment{Highlighting} \usepackage{listings} \usepackage{float} \floatstyle{plain} \newfloat{listing}{t}{lop} \floatname{listing}{Listing} \def\listingautorefname{Listing} \newfloat{table}{t}{lop} \floatname{table}{Table} \def\tableautorefname{Table} \def\Snospace~{\S{}} \renewcommand*\sectionautorefname{\Snospace} \renewcommand*\subsectionautorefname{\Snospace} \renewcommand*\subsubsectionautorefname{\Snospace} \begin{document} \special{papersize=8.5in,11in} \setlength{\pdfpageheight}{\paperheight} \setlength{\pdfpagewidth}{\paperwidth} \conferenceinfo{$conference.year$}{$conference.location$} \copyrightyear{$conference.year$} \doi{$doi$} \title{$title$} \authorinfo{ $for(author)$$author.given$ $author.family$$sep$\and $endfor$ }{ $for(organization)$ $organization.name$ $endfor$ }{ \{$for(author)$$author.email$$sep$,$endfor$\}@cs.washington.edu } \maketitle \begin{abstract} $abstract$ \end{abstract} $body$ \bibliographystyle{abbrv} \bibliography{$bibliography$} \end{document}