This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via 8830309377545a0b0c8f32aaad7e3bdb938ecdef (commit) from add9c7990d7c643190ba76fc4aa8ccc4a2ddacca (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 8830309377545a0b0c8f32aaad7e3bdb938ecdef Author: Kevin Harms <[email protected]> Date: Mon Mar 5 01:44:59 2012 -0600 Updates to eval section of aesop paper, bringing content from aesop performance document. ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/aesop.bib | 26 +++ papers/2011/aesop/evaluation.tex | 357 ++++++++++++++++++++++++++------------ 2 files changed, 271 insertions(+), 112 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/aesop.bib b/papers/2011/aesop/aesop.bib index 32f5ca5..28c7f5c 100644 --- a/papers/2011/aesop/aesop.bib +++ b/papers/2011/aesop/aesop.bib @@ -330,6 +330,32 @@ year = 2008 howpublished = {http://code.sixapart.com/svn/memcached/trunk/server/doc/threads.txt} } +@MISC{hp-cond-variable, + author = {Hewlet Packard Development Company L.P}, + title = {Techniques for Improving the Scalability of Applications Using POSIX Thread Condition Variables.}, + howpublished = {http://h21007.www2.hp.com/portal/download/files/unprot/hpux/MakingConditionVariablesPerform.pdf} +} + +@INPROCEEDINGS{mccabe, + author = {McCabe, T.J}, + title = {A Complexity Measure}, + booktitle = {IEEE Transactions on Software Engineering, vol.SE-2, no.4} + year = {1976}, +} + @Comment pages = {308--320}, + +@MISC{pmccabe, + author = {Paul Bame}, + title = {pmccabe}, + howpublished = {http://parisc-linux.org/~bame/pmccabe/} +} + +@MISC{sloccount, + author = {David A. Wheeler}, + title = {sloccount}, + howpublished = {http://www.dwheeler.com/sloc/} +} + @INPROCEEDINGS{BDB_1999, author = {Olson, Michael A. and Bostic, Keith and Seltzer, Margo}, title = {Berkeley DB}, diff --git a/papers/2011/aesop/evaluation.tex b/papers/2011/aesop/evaluation.tex index e2d14ba..c8b185d 100644 --- a/papers/2011/aesop/evaluation.tex +++ b/papers/2011/aesop/evaluation.tex @@ -1,159 +1,288 @@ -In this paper we evaluate Aesop based on two criteria, runtime efficiency -and progammer productivity. +In this paper we evaluate Aesop based on three criteria, runtime efficiency, +memory efficiency and progammer productivity. + +\subsection{Experiment} + +To evaluate the aesop we created a comparison of different server +implementations. We designed a simple server that uses TCP messaging. +The server recieves requests from a client, sends or recieves +a payload, and then sends an acknowledgement. +The paylod can be generated or discarded, read from a file or written to a file. + +Each of the example servers used for comparison in this document implement +an identical request protocol and are therefore evaluated using the same +client test harness. The client is a basic C program that uses TCP sockets +to send messages to the server. It uses MPI to coordinate processes and +generate a highly concurrent workload. + +The client will execute in a loop generating a specified number of +operations to the server. The general flow is that each client process sends +a request to the server that contains an optional payload. The client then +waits for the server to send an acknowledgment that also contains an +optional payload. + +Each client records the total amount of time taken to execute its workload +(beginning before the initial connection and ending after receipt of the last +acknowledgment). The time taken by the slowest client is reported as the +aggregate run time. Each client also records the time needed to service each +individual request (from before the request is sent until after the +acknowledgment is received) in order to calculate statistics about +individual request latencies. -\subsection{Runtime Efficiency} +\subsubsection{Experiment - Test Cases} -To evaluate the runtime effiecency of aesop we created a comparison of a -server implementations. We selected a simple test case to examine concurrency -within a server. We designed a simple server that uses TCP messaging. -The server recieves requests from a client, sends or recieves a payload, -and then sends an acknowledgement. The paylod can be generated or discarded, -read from a file or written to a file. +There are four distinct test cases run against each server implementation. +All file I/O is done using O\_DIRECT file access mode in order to bypass the +Linux buffer cache and ensure that disk is involved in each I/O transfer. +The number of requests and size of request were chosen to keep the +total runtime of each test case reasonable. -The client is an MPI program which allows launching an arbitrary number of -client instancess and coordinates startup. MPI is used for synchronization -on startup and commmunication of results, the core client program only uses -sockets for communication with the server. +\paragraph*{Read} -\subsubsection{Experiment - Test Types} +The client sends a request with a file name and a size. The server will +then open the file, read the contents up to the size specified. The server +returns the data with the acknowledgement of the operation. -We developed six versions of the server: Aesop, Thread-per-client, -Thread-per-client using non-blocking sockets, Thread-per-operation, -Thread-pool and Event. Each server is setup to report the VmHWM stat when -the application exits. +The read test had clients each issue 16 requests asking for 4 KiB from +disk. Each client specifies a unique file to be read on each request. All +clients specify unique files. The files are first generated by a script +before the tes truns. -\paragraph*{Aesop} +\paragraph*{Write} -The aesop server uses a 'lonely pbranch' to service each client. The underlying -configuration of aesop was using a thread-pool with 16 threads to to handle -network requests and a thread-pool with 4 threads to handle disk operations. +The client sends a request with a file name, size and payload. The server +will then create the file and write the payload. The server then sends an +acknowledgement to the client. -\paragraph*{Thread-per-client} +The write test has clients each issue 16 requests sending 4 KiB of data to +be written to disk. Each client specifies a unique file name for each +request and all clients specify unique files from each other. The directory +containing all the files is deleted between each test iteration. -The thread-per-client server spawns a thread for each client connection. -All requests for each client are handled within that thread. Network and -disk operations all use blocking calls. +\paragraph*{Read-null} -\paragraph*{Thread-per-client-nb} +The read-null test is identical to the read request, except that the +server sends uninitialized data rather than performing any file I/O. The +server allocates a buffer for the response based on the size the client +requested. -The thread-per-client-nb server is the same implementation as the -thread-per-client model but uses non-blocking sockets for network operations. +The read-null test had clients each issue 4096 requests requesting 4 KiB of +data to be returned from the server. -\paragraph*{Thread-per-operation} +\paragraph*{Write-null} -The thread-per-operation server uses an event loop to watch all sockets and then -spawns a thread to handle each request. The request for network and disk -operations are handled in the same thread. +The write-null test is identical to the write request, except that the +server discards incoming data rather than performing any file I/O. The +server will still send an acknowledgement to the client. -\paragraph*{Thread-pool} +The write test had clients each issue 4096 sending 4 KiB of data to be +discarded by the server. -The thread-pool server uses an event loop to watch all sockets for activity -and then puts the request on a queue for it to be handled by a thread within -the thread pool. The request for network and disk operations are handled in -the same thread. +\subsubsection{Experiment - Server Types} -\paragraph*{Event} +We implemented the same request protocol in multiple server daemons +in order to contrast different approaches to concurrent +request processing. Each server uses the same fundamental coding style to +the degree possible. One server is implemented using the Aesop language, +while all other servers are implemented in C. The pthread library was +used in all cases that required explicit threading, while the +libev~\ref{libev-web} library was used in all cases that required an +explicit event loop. -The event server uses a event loop to watch all sockets and handles all -network and disk operations occurs as callbacks from the event loop. The -event model uses on a single thread. +Each server is setup to report the VmHWM stat when the application exits. -All of the event loop implementations use libev [ref]. +\paragraph*{Aesop} -\subsubsection{Experiment - Test Cases} +The Aesop server is implemented in the Aesop programming language. The server +uses a 'lonely pbranch' to service each client. All operations for a client +are handled within a single pbranch. The socket nd file operations are +performed with blocking Aesop function that are provided by the Aesop +standard library. The underlying socket resource uses non-blocking sockets +with a thread pool of 12 threads. The file resource uses synchronous IO and +a thread pool with 4 threads. -Four sepearte tests were run again each server type: read, write, read-null -and write-null. +\paragraph*{Thread-per-client} -The client and server connect over Infiniband using IPoIB. The number of -requests and size of requests were chosen to keep the total runtime of the -test cases reasonable. +The thread-per-client server spawns a thread for each client connection. +All requests for a given client are handled within the same thread. This model +uses blocking socket operations and standard file read and write operations. +Each thread executes until the corresponding client disconnects. -\paragraph*{Read} +\paragraph*{Thread-per-client-nb} -The read test case reads data off of the local scratch disk on each compute -node. The request specifies which file to read and the data is returned in -the acknoledgement. The data is read using O\_DIRECT mode in order to -bypass file caching. The test starts by first generating a set of files -(1 file per client per request) for each client to read, which are used -for all six test types. Each client issues sixteen requests of 4096 bytes. +The thread-per-client-nb server is identical to the thread-per-client +server, except that is uses non-blocking socket calls in place of blocking +socket calls. For example, in order to send a message, a thread will +perform non-blocking sends until it encounters the EWOULDBLOCK error code. +It then polls the socket until it is ready and continues sending data. +We implemented this version to investigate the possible performance difference +between the synchronous and asynchronous socket calls in a scenario where +all other factors are held constant. -\paragraph*{Write} +\paragraph*{Thread-per-operation} -The write test case writes data from the client to the disk. The server sends -and acknowledgement after the write completes. Each write request -involves creating a new file on local disk. The data is written using O\_DIRECT -mode in order to bypass file caching. The files created are deleted between -each test type execution. Each client issues sixteen requests of 4096 bytes. +The thread-per-operation server uses an event loop to watch all sockets for +activity. When a new request is available, a thread is spawned and the request +is handled completely from within that thread. When the request is complete +the thread is destroyed. Blocking socket operations and standard file read +and write functions are used in this implementation. -\paragraph*{Read-null} +\paragraph*{Thread-pool} -The read-null test case has the server return a generated chunk of data -for each client request. The data is returned with the acknowledgement. -Each client issues 4096 requests for 4096 bytes of data. +The thread-pool server uses an event loop to watch all sockets for activity. +When a new request is available, the event loop puts the request on a queue and +wakes up a thread from the thread pool. The request is handled completely +from within a single thread of the thread pool. Blocking sockets and +standard file read and write functions are used in this implementation. The +thread pool was implemented following best practices for scalable condition +variable performance as described in \cite{hp-cond-variable}. -\paragraph*{Write-null} +\paragraph*{Event} -The write-null test case has the client send a payload but then the server -simple discards the data and returns an acknowledgement. Each client issues -4096 requests and send a payload of 4096 bytes of data. +The event server uses an event loop not only to detect incoming requests, +but to service them as well. Each request processing step is executed from +an event loop callback function. The event server uses non-blocking sockets +and asynchronous file I/O. Note that although this implementation does not +use any explicit threads, the operating system can still use multiple cores +to drive both the network and disk. \subsubsection{Experiment - Test System} -The experiment was run on the Argonne Lcaboratory Computing Resource Center -(LCRC) Fusion cluster. Fusion is an IBM iDataPlex dx360 M2 system which has -320 nodes. Each compute node contains two Intel Nehalem 2.6 GH Xeon -processors with a total of 36 GB of RAM. The cluster has Infinband QDR -interconnect. Each compute node also contains a local scratch space which -is a single SATA 7200 RPM hard disk. +All experiments were executed on the Fusion cluster managed by +the Argonne Laboratory Computing Resource Center +(LCRC). Fusion is a IBM iDataPlex dx360 M2 system. It features 320 compute +nodes which each consist of two Intel Nehalem 2.6 GHz Xeon processors and 36 GB +of RAM. The compute nodes have hyper threading disabled. The cluster has +an InfiniBand QDR interconnect. Each compute node also a single SATA 7200 RPM +hard disk for local scratch storage. All disk IO was performed using the +local scratch storage and client/server communication was done over the +IB network using IPoIB. -\subsubsection{Experiment - Results} +We executed 16 clients processes per phyiscal node. The tests were executed +on 65 nodes. One node was used for the server and the other 64 nodes were +used for the clients. We scaled the clients from 16 (1 node) to 1024 (64 nodes). -Aesop's runtime effiecency compares reasonably to the other hand-coded server -types. The thead-per-client test was the fastest method in all four test -cases. The thread-per-client-nb test type was contructed to examine the -performance difference between blocking and non-blocking socket operations. -Aesop uses non-blocking socket operations so this test case is a better -comparison between aesop and a hand tuned server. +\subsection{Runtime Efficiency} -% use subfigure for performance graphs +Figure~\subref{fig:writehist} shows the overall run time of the concurrent write +workload for each server implementation as the number of client processes +is scaled from 16 to 1024. In this graph we see that {aesop} does not +perform as well as the other servers for small workloads (taking 3.2 +seconds at the smallest scale, verses 1.9 seconds for the thread-per-op +server). However, {aesop} is the fastest server at the largest scale +(taking 119.8 seconds verses 130.8 seconds for the nearest competitors +in thread-per-client and thread-per-client-nb). + +Figure~\subref{fig:readhist} shows the results of the read experiment. +Aesop performs more favorably at small scale for this workload than in the +previously shown write workload. At the largest scale, Aesop completes the +test in 48.3 seconds verses 46.1 seconds for the fastest server (thread-pool). +The event server performs particularly poorly in all cases, ultimately +running the largest scale test in 77.2 seconds. + +The small scale results for Aesop may indicate that additional tuning +is needed to improve latency for small test runs. The issue is likely +isolated to the write path of the file I/O resource in the Aesop standard +library, as we see asymmetric results in the read and write tests for Aesop +in terms of its relative performance. + +Aesop is competitive with (and in most cases better than) the other +implementations except for the thread-per-client server in both the +write-null (Figure~\subref{fig:writenull}) and read-null +(Figure~\subref{fig:readnull}) evaluation. We were unable to +isolate a concrete reason for this discrepancy in profiling. One notable +difference in the two implementations, however, is that the +thread-per-client server uses blocking socket operations, while the Aesop +socket resource uses non-blocking operations. Based on this observation, +we implemented the +thread-per-client-nb server to isolate the impact of non-blocking socket +operations on performance. The thread-per-client-nb implementation is +identical to the thread-per-client implementation except that each socket +uses non-blocking operations and polling to transmit and receive data. As +seen in these tests, the use of non-blocking operations slows down the +thread-per-client server to the point that it is practically equivalent to +the Aesop server at scale. + +Another notable observation in these graphs is that the Aesop server is +competitive at small scale, and in fact is the fastest implementation in the +16 client process read-null test and nearly the fastest in the 16 client +process write-null test. This supports the observation from the previous +section that poor Aesop performance at small scale is likely a tuning flaw +in the file resource used in the Aesop standard library, rather than a +fundamental programming language problem. \begin{figure}[t] \centering + \subfigure[Read performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/read-hist.pdf} - \caption{Read performance \label{fig:read-hist}} -\end{figure} + \label{fig:read-hist} + } -\begin{figure}[t] - \centering + \subfigure[Write performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-hist.pdf} - \caption{Write performance \label{fig:write-hist}} -\end{figure} + \label{fig:write-hist} + } -\begin{figure}[t] - \centering + \subfigure[Read-null performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/read-null-hist.pdf} - \caption{Read-null performance \label{fig:read-null-hist}} -\end{figure} + \label{fig:read-null-hist} + } -\begin{figure}[t] - \centering + \subfigure[Write-null performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-null-hist.pdf} - \caption{Write-null performance \label{fig:write-null-hist}} + \label{fig:write-null-hist} + } \end{figure} +\subsubsection{Latency} + +The client measures the latency of each individual request and then computes +the minimum and maximum latency, the first quartile latency and third +quartile latency. The box represents the first and third quartiles and the +whiskers are the minimum and maximum values. The following results are for +the 1024 client size selected from the same iteration as the maximum runtime +graphs. Figure~\subref{fig:writelat} shows Aesop offers vary comparative +latency performance as the other configurations and only notably +thread-per-op and event are significantly worse. The relative latency metrics +are similar for the other test cases. + \begin{figure}[t] \centering + \subfigure[Write memory usage]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-mem.pdf} - \caption{Write memory usage \label{fig:write-mem}} -\end{figure} + \label{fig:write-mem} + } -\begin{figure}[t] - \centering + \subfigure[Write Latency]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-lat.pdf} - \caption{Write Latency \label{fig:write-lat}} + \label{fig:write-lat} + } \end{figure} +\subsection{Memory Efficiency} + +Another aspect of the overall performance is the memory efficiency of each +server implementation. In this section we compare Aesop to the other server +implementations using the same runtime performance experitment. +The memory utilization of each server implementation was captured during +the runtime performance experiments. We recorded the VmHWM stat from the +server when the client test was completed. The VmHWM stat is a Linux-specific +metric that represents the peak resident set size (RSS) of an executable, +where RSS corresponds to the amount of paged-in memory used by the executable. + +In Figure~\subref{fig:writemem} we see that thread-pool limits the +memory usage as the client work load increases because the thread-pool +by design limits the number of requests that can be in progress at once. The +other server implementations scale as the number of clients increase. +Although the Aesop server cannot match the thread-pool server in terms of +memory usage, it does compare favorably to the thread-per-client and +thread-per op servers. Note that the thread-per-client and thread-per-op +models consume virtual memory at a much larger rate due to the number of +thread stacks allocated. We chose not to evaluate this metric, however, +as the resident memory seems to be a more relevant metric in practice. Again, +the memory usage graphs for the other test cases are similar to those shown +in the write test case. + \subsection{Productivity} \begin{table} @@ -164,10 +293,12 @@ comparison between aesop and a hand tuned server. \hline & CC & mod. CC & SLOC \\ \hline -aesop & 15 & 10 & 171 \\ -thread & 17 & 12 & 179 \\ -thread pool & 29 & 23 & 292 \\ -event & 26 & 21 & 328 \\ +aesop & 16 & 11 & 179 \\ +thread-per-client & 17 & 12 & 182 \\ +thread-per-client-nb & 17 & 12 & 184 \\ +thread-per-op & 22 & 17 & 249 \\ +thread-pool & 32 & 26 & 313 \\ +event & 28 & 23 & 341 \\ \hline \end{tabular} \label{tab:complexity} @@ -176,11 +307,13 @@ event & 26 & 21 & 328 \\ \vspace{-.2in} \end{table} -\color{red} -Table~\ref{tab:complexity} compares the code complexity of each -implemenation using McCabe Cyclomatic Complexity (CC), Modified McCabe Cyclomatic -Complexity (mod. CC), and Source Linex of Code (SLOC). TODO: reference the -metrics and the tools that we used to collect them (pmccabe and sloccount). +Table~\ref{tab:complexity} compares the code complexity of each server +implemenation using McCabe Cyclomatic Complexity (CC) \ref{mccabe}, +Modified McCabe Cyclomatic Complexity (mod. CC), and +Source Lines of Code (SLOC). The CC and Mod. CC metrics were measured +using the pmccabe tool, version 2.6, created by Paul Bame \ref{pmccabe}, +while the SLOC metrics were measured using the sloccount tool, +version 2.26, created by David A. Wheeler \ref{sloccount}. To simplify the comparison, all four servers had no error handling except for assertions on expected return codes. The protocol definition (ie, @@ -200,6 +333,7 @@ operation requires 5 disconnected event handlers. So although the event model appears less complex according to CC and mod. CC, qualitatively it is significantly more challenging to develop. +\color{red} \begin{figure}[t] \center \begin{minipage}[b]{.47\textwidth} @@ -307,7 +441,6 @@ __blocking void handleConnection (int fd) \end{minipage} \end{figure} - The aesop code (listing~\ref{lst:aesop}) strongly resembles the threaded code. Instead of creating a thread, a lonely pbranch is used to make sure new connections can be accepted even though the previous connection is still being hooks/post-receive -- Triton-private Repository