[complement-svn] SF.net SVN: complement: [1321] trunk/explore/perf/STL
Status: Pre-Alpha
Brought to you by:
complement
From: <com...@us...> - 2006-10-16 15:03:07
|
Revision: 1321 http://svn.sourceforge.net/complement/?rev=1321&view=rev Author: complement Date: 2006-10-16 08:02:27 -0700 (Mon, 16 Oct 2006) Log Message: ----------- add tests for expression template (proxy string objects) technique Modified Paths: -------------- trunk/explore/perf/STL/compare.tex trunk/explore/perf/STL/lib/Makefile trunk/explore/perf/STL/string/Makefile trunk/explore/perf/STL/string/test.sh trunk/explore/perf/STL/strings.gplot Added Paths: ----------- trunk/explore/perf/STL/lib/texpr/ trunk/explore/perf/STL/lib/texpr/Makefile trunk/explore/perf/STL/string/add-proxy/ trunk/explore/perf/STL/string/add-proxy/Makefile trunk/explore/perf/STL/string/add-proxy/Makefile.inc trunk/explore/perf/STL/string/add-proxy/STLport-add-str-proxy/ trunk/explore/perf/STL/string/add-proxy/STLport-add-str-proxy/Makefile trunk/explore/perf/STL/string/add-proxy/STLport-default/ trunk/explore/perf/STL/string/add-proxy/STLport-default/Makefile trunk/explore/perf/STL/string/add-proxy/libstdc++/ trunk/explore/perf/STL/string/add-proxy/libstdc++/Makefile trunk/explore/perf/STL/string/add-proxy/str.cc Removed Paths: ------------- trunk/explore/perf/STL/build/lib/forcestringterm/ trunk/explore/perf/STL/build/lib/libstdc++/ trunk/explore/perf/STL/build/lib/malloc/ trunk/explore/perf/STL/build/lib/newalloc/ trunk/explore/perf/STL/build/lib/noshortstr/ trunk/explore/perf/STL/lib/forcestringterm/ Property Changed: ---------------- trunk/explore/perf/STL/build/lib/ Property changes on: trunk/explore/perf/STL/build/lib ___________________________________________________________________ Name: svn:ignore - *.so* + *.so* texpr libstdc++ malloc newalloc noshortstr Modified: trunk/explore/perf/STL/compare.tex =================================================================== --- trunk/explore/perf/STL/compare.tex 2006-10-13 15:08:00 UTC (rev 1320) +++ trunk/explore/perf/STL/compare.tex 2006-10-16 15:02:27 UTC (rev 1321) @@ -1,4 +1,4 @@ -% -*- LaTeX -*- Time-stamp: <06/01/05 13:08:22 ptr> +% -*- LaTeX -*- Time-stamp: <06/10/16 19:00:51 ptr> \documentclass[a4paper]{article} @@ -30,21 +30,16 @@ \maketitle \begin{abstract} -This article present comparison of -strings implementation in \STLport{} and \libstd. +This article present comparison of STL strings with copy-on-write and +non-copy-on-write argorithms, based on \STLport{} strings and ropes +and \libstd{} implementations. -This tests also can help to answer on question: -is it strings copy algorithm with constant complexity -better than algorithm with linear complexity? -This comparison is done on the base of STLport strings, ropes -and \libstd{} strings. +Some related issues, like fstream and stringstream performance +are also under consideration. -Small mesure for iostreams implementations (and adequate C code) -and publication of test times for two hardware (but both has x86 architecture) -platforms was recently added. - I expect that this results will help to make decision between -STL implementations as well proper choice of strings implementation. +STL implementations as well proper choice of strings implementation +and STL usage technique. \end{abstract} \tableofcontents @@ -53,14 +48,13 @@ In the tests was used following computers and operational envirinments: \begin{enumerate} - \item Hands-made machine (assembled by Tersys company) with two $1.33$-GHz - AMD$^{\mbox{\tiny\textregistered}}$ Athlon$^{\mbox{\tiny\textregistered}}$ XP 1500+ processors under Linux (kernel 2.6.12.5, \verb|glibc| 2{.}2{.}5);\label{AMD} - \item ASUS assembled computer with Intel$^{\mbox{\tiny\textregistered}}$ Pentium$^{\mbox{\tiny\textregistered}}$ 4 $2.4$-GHz processor under Linux (kernel 2.6.12.5, \verb|glibc| 2{.}2{.}5). + \item Tyan Tiger motherboard, two $1.33$-GHz + AMD$^{\mbox{\tiny\textregistered}}$ Athlon$^{\mbox{\tiny\textregistered}}$ XP 1500+ processors under Linux (kernel 2.6.16.26, \verb|glibc| 2{.}3{.}6);\label{AMD} \end{enumerate} \section{Compilers} -For Unix-like systems was used GNU gcc 3{.}4{.}4 +In tests was used GNU gcc 3{.}4{.}4 or 4{.}1{.}1 with appropriate \verb|libstdc++| libraries (version~3). @@ -68,7 +62,7 @@ Due to ``time'' function has different options and output format on Linux and other UINIXes, I use program \texttt{time} from -\texttt{complement}\footnote{\texttt{http://complement.sourceforge.net}} +\texttt{complement}\footnote{\texttt{http://complement.sourceforge.net}, see appropriate SVN repository on SourceForge.} project bundle\footnote{Portability note: system should has \texttt{wait3} function.}. By the way this function provide high-precision time measure. @@ -108,6 +102,9 @@ \section{The Tests Descriptions\label{TestsDescr}} +All tests are ``synthetic'', to show the diference in programming +technique. + \subsection{Add Characters to String\label{incr-string} (test \#1)} @@ -139,29 +136,29 @@ \begin{center} \input strings.tex \end{center} - \caption{Comparison of \libstd{} and \STLport{} - strings implementation. Single thread. $t$ is a wall time for tests. - The implementation of strings in \STLport{} (copy algorithm complexity $O(n)$) - drammaticaly faster than ones in \libstd{} or ropes in \STLport{} - (copy algorithm complexity $O(1)$) for tests with strings modification. - If the test only copy string, the implementation with $O(1)$ complexity - is better. + \caption{STL strings implementations comparison. Single thread. $t$ is a wall time + for tests. + The implementation of strings in \STLport{} (non-COW) + drammaticaly faster than COW implementations (\libstd{} and + ropes in \STLport{}) in tests that modify strings. + But if the test only copy string, the COW implementation show better + performance. \label{STLport-gpp-strings}} \end{figure} -\begin{figure} - \begin{center} - \input intel-amd.tex - \end{center} - \caption{Comparison of two x86 platforms. See platforms description - on page~\pageref{AMD}. This graphics show that higher frequency isn't - synonym of better perfomance\label{intel-amd}} -\end{figure} +%\begin{figure} +% \begin{center} +% \input intel-amd.tex +% \end{center} +% \caption{Comparison of two x86 platforms. See platforms description +% on page~\pageref{AMD}. This graphics show that higher frequency isn't +% synonym of better perfomance\label{intel-amd}} +%\end{figure} \subsection{String copy\label{params-string} (test \#4)} This test intended to hilight the cost of strings copy (jusr copy, without modifications). -Implementations of strings that use algorithms with constant copy time ($O(1)$) +Implementations of strings that use copy-on-write algorithms expected to show better results here. @@ -169,7 +166,7 @@ You can see (fig.~\ref{STLport-gpp-strings}) that \libstd{} show better results than \STLport{} in this test. The reason is that \libstd{} -use copy algorithm with $O(1)$ complexity: during copy operation +use COW algorithm: during copy operation there are no memory allocation occur---two strings refer to the same memory chunk (like \verb|tmp| and \verb|par| on line~$9$). This test has three copy operations (lines~$7$, $9$ and $20$). @@ -208,8 +205,39 @@ But you see, for ``short'' strings test with ``short'' strings optimization show time that $43\%$ better! +\subsection{String proxy objects\label{add-string-proxy} (tests \#8 and \#9)} + +The agregation of strings using the \verb|+| operator is an expensive operation +as it requires construction of temporary objects that need memory allocation +and deallocation. The problem can be even more important if you are adding +several strings together in a single expression. To avoid this problem \STLport{} +implement expression template. With this technique addition of 2 strings is not +a string anymore but a temporary object having a reference to each of the +original strings involved in the expression. This object carry information +directly to the destination string to set its size correctly and only make +a single call to the allocator. This technique also works for the addition of +$N$ elements where elements are \verb|basic_string|, \verb|C| string or a +single character. + +The drawback can be longer compilation time and bigger executable size. + +Another problem is that some compilers (gcc) fail to use string proxy object +if do with class derived from string. + +Let's try to estimate the benefits from string proxy technique with following test. + +\lstinputlisting{string/add-proxy/str.cc} + +Test \#8 is default \STLport{}, in test \#9 used temporary string objects. +For \libstd{} both \#8 and \#9 are the same test. + + \section{Role of Allocators} +Note: in the \verb|glibc| 2{.}3{.}6 enhancement of memory allocation +(over \verb|glibc| 2{.}2{.}5) leads to +advantage of \STLport{}'s \verb|node_alloc| became insignificant. + The \STLport{} provide default ``optimized'' memory allocator (\verb|node_alloc|). This allocator was used when I run strings tests for \STLport{} (see section~\ref{TestsDescr}). May be the win of \STLport{} is @@ -254,7 +282,7 @@ except that every test run simultaneously in two threads. -\subsection{Comparison of \STLport{} and \libstd} +\subsection{Comparison of \STLport{} and \libstd in multi-threaded applications} \begin{figure} \begin{center} @@ -424,6 +452,13 @@ \caption{Streams.\label{streams}} \end{figure} +\begin{figure} + \begin{center} + \input streams-1.tex + \end{center} + \caption{Streams.\label{streamsOne}} +\end{figure} + \subsection{Format output to file\label{fstream-format} (test \#1)} First test is a format output to a file. File stream opened for writing @@ -447,6 +482,10 @@ \lstinputlisting{stream/fstream-raw/str2.c} +And, as reference, unbuffered output (unistd): + +\lstinputlisting{stream/fstream-raw/str3.c} + \subsection{Raw output to string\label{sstream-raw} (test \#3)} Raw write to string stream. Modified: trunk/explore/perf/STL/lib/Makefile =================================================================== --- trunk/explore/perf/STL/lib/Makefile 2006-10-13 15:08:00 UTC (rev 1320) +++ trunk/explore/perf/STL/lib/Makefile 2006-10-16 15:02:27 UTC (rev 1321) @@ -1,6 +1,6 @@ # -*- Makefile -*- Time-stamp: <05/12/26 23:57:38 ptr> -DIRS = default malloc newalloc misc noshortstr forcestringterm +DIRS = default malloc newalloc misc noshortstr texpr # STLPORT_SRC_DIR = ${HOME}/STLport.lab/STLport # include file, generated by configure, if available Property changes on: trunk/explore/perf/STL/lib/texpr ___________________________________________________________________ Name: svn:ignore + obj Added: trunk/explore/perf/STL/lib/texpr/Makefile =================================================================== --- trunk/explore/perf/STL/lib/texpr/Makefile (rev 0) +++ trunk/explore/perf/STL/lib/texpr/Makefile 2006-10-16 15:02:27 UTC (rev 1321) @@ -0,0 +1,32 @@ +# -*- Makefile -*- Time-stamp: <05/12/27 01:08:40 ptr> + +# STLPORT_SRC_DIR := /export/home/ptr/STLport.lab/STLport +# include file, generated by configure, if available +-include ../../../../Makefiles/config.mak + +SRCROOT := ${STLPORT_DIR}/build +INSTALL_LIB_DIR := ../../build/lib/texpr +INSTALL_LIB_DIR_DBG := . +INSTALL_LIB_DIR_STLDBG := . +INSTALL_BIN_DIR := . +INSTALL_BIN_DIR_DBG := . +INSTALL_BIN_DIR_STLDBG := . +ALL_TAGS := install-release-shared + +COMPILER_NAME := gcc + +STLPORT_INCLUDE_DIR = ${STLPORT_DIR}/stlport +include ../Makefile.inc +include ${SRCROOT}/Makefiles/top.mak + +ifeq ($(OSNAME),linux) +DEFS += -D_STLP_REAL_LOCALE_IMPLEMENTED -D_GNU_SOURCE -D_STLP_LEAKS_PEDANTIC +endif + +DEFS += -D_STLP_USE_TEMPLATE_EXPRESSION + +# options for build with boost support +ifdef STLP_BUILD_BOOST_PATH +INCLUDES += -I$(STLP_BUILD_BOOST_PATH) +endif + Modified: trunk/explore/perf/STL/string/Makefile =================================================================== --- trunk/explore/perf/STL/string/Makefile 2006-10-13 15:08:00 UTC (rev 1320) +++ trunk/explore/perf/STL/string/Makefile 2006-10-16 15:02:27 UTC (rev 1321) @@ -1,6 +1,6 @@ # -*- Makefile -*- Time-stamp: <05/12/27 00:15:29 ptr> -DIRS = add add-ropes find find-ropes ops ops-ropes params params-ropes/STLport-default params-ropes/STLport-malloc params-ref params-ref-ropes/STLport-default params-ref-ropes/STLport-malloc params-ref-ropes/STLport-newalloc params-short +DIRS = add add-ropes find find-ropes ops ops-ropes params params-ropes/STLport-default params-ropes/STLport-malloc params-ref params-ref-ropes/STLport-default params-ref-ropes/STLport-malloc params-ref-ropes/STLport-newalloc params-short add-proxy all: for d in $(DIRS); do \ Added: trunk/explore/perf/STL/string/add-proxy/Makefile =================================================================== --- trunk/explore/perf/STL/string/add-proxy/Makefile (rev 0) +++ trunk/explore/perf/STL/string/add-proxy/Makefile 2006-10-16 15:02:27 UTC (rev 1321) @@ -0,0 +1,23 @@ +# -*- Makefile -*- Time-stamp: <05/12/27 00:39:55 ptr> + +DIRS = STLport-default STLport-add-str-proxy libstdc++ + +all: + for d in $(DIRS); do \ + (cd $$d; ${MAKE});\ + done + +clean: + for d in $(DIRS); do \ + (cd $$d; ${MAKE} clean); \ + done + +clobber: + for d in $(DIRS); do \ + (cd $$d; ${MAKE} clobber); \ + done + +depend: + for d in $(DIRS); do \ + (cd $$d; ${MAKE} depend); \ + done Added: trunk/explore/perf/STL/string/add-proxy/Makefile.inc =================================================================== --- trunk/explore/perf/STL/string/add-proxy/Makefile.inc (rev 0) +++ trunk/explore/perf/STL/string/add-proxy/Makefile.inc 2006-10-16 15:02:27 UTC (rev 1321) @@ -0,0 +1,5 @@ +# -*- makefile -*- Time-stamp: <02/03/11 16:03:54 ptr> +# $Id: Makefile.inc 999 2004-07-29 09:01:20Z ptr $ + +PRGNAME = str +SRC_CC = ../str.cc Property changes on: trunk/explore/perf/STL/string/add-proxy/STLport-add-str-proxy ___________________________________________________________________ Name: svn:ignore + obj Added: trunk/explore/perf/STL/string/add-proxy/STLport-add-str-proxy/Makefile =================================================================== --- trunk/explore/perf/STL/string/add-proxy/STLport-add-str-proxy/Makefile (rev 0) +++ trunk/explore/perf/STL/string/add-proxy/STLport-add-str-proxy/Makefile 2006-10-16 15:02:27 UTC (rev 1321) @@ -0,0 +1,14 @@ +# -*- Makefile -*- Time-stamp: <05/12/27 00:41:26 ptr> + +SRCROOT := ../../../../.. +COMPILER_NAME := gcc + +ALL_TAGS := release-shared + + +include ../Makefile.inc +include ${SRCROOT}/Makefiles/top.mak + +DEFS += -D_STLP_USE_TEMPLATE_EXPRESSION + +release-shared: LDSEARCH = -L../../../build/lib/texpr -Wl,-rpath=../build/lib/texpr Property changes on: trunk/explore/perf/STL/string/add-proxy/STLport-default ___________________________________________________________________ Name: svn:ignore + obj Added: trunk/explore/perf/STL/string/add-proxy/STLport-default/Makefile =================================================================== --- trunk/explore/perf/STL/string/add-proxy/STLport-default/Makefile (rev 0) +++ trunk/explore/perf/STL/string/add-proxy/STLport-default/Makefile 2006-10-16 15:02:27 UTC (rev 1321) @@ -0,0 +1,12 @@ +# -*- Makefile -*- Time-stamp: <05/12/27 00:40:16 ptr> + +SRCROOT := ../../../../.. +COMPILER_NAME := gcc + +ALL_TAGS := release-shared + + +include ../Makefile.inc +include ${SRCROOT}/Makefiles/top.mak + +release-shared: LDSEARCH = -L../../../build/lib -Wl,-rpath=../build/lib Property changes on: trunk/explore/perf/STL/string/add-proxy/libstdc++ ___________________________________________________________________ Name: svn:ignore + obj Added: trunk/explore/perf/STL/string/add-proxy/libstdc++/Makefile =================================================================== --- trunk/explore/perf/STL/string/add-proxy/libstdc++/Makefile (rev 0) +++ trunk/explore/perf/STL/string/add-proxy/libstdc++/Makefile 2006-10-16 15:02:27 UTC (rev 1321) @@ -0,0 +1,14 @@ +# -*- Makefile -*- Time-stamp: <05/12/27 00:40:46 ptr> + +SRCROOT := ../../../../.. +COMPILER_NAME := gcc +WITHOUT_STLPORT := 1 + +ALL_TAGS := release-shared + + +USE_STDLIB := yes + +include ../Makefile.inc +include ${SRCROOT}/Makefiles/top.mak + Added: trunk/explore/perf/STL/string/add-proxy/str.cc =================================================================== --- trunk/explore/perf/STL/string/add-proxy/str.cc (rev 0) +++ trunk/explore/perf/STL/string/add-proxy/str.cc 2006-10-16 15:02:27 UTC (rev 1321) @@ -0,0 +1,20 @@ +// -*- C++ -*- Time-stamp: <03/04/04 23:07:39 ptr> + +#include <string> + +using namespace std; + +int main( int, char * const * ) +{ + string s; + string s1 = "1234567"; + string s2 = "12345678901234567890"; + string s3 = ".ext"; + string s4 = " /* my comment about this */"; + + for ( int i = 0; i < 100000000; ++i ) { + s = s1 + "/" + s2 + s3 + " => " + s4; + } + + return 0; +} Modified: trunk/explore/perf/STL/string/test.sh =================================================================== --- trunk/explore/perf/STL/string/test.sh 2006-10-13 15:08:00 UTC (rev 1320) +++ trunk/explore/perf/STL/string/test.sh 2006-10-16 15:02:27 UTC (rev 1321) @@ -1,6 +1,6 @@ #!/bin/sh # -# Time-stamp: <04/07/15 01:16:23 ptr> +# Time-stamp: <06/10/16 18:25:07 ptr> # BASEDIR=${PWD}/../../.. @@ -31,6 +31,12 @@ done # dummy: echo $j `../stat.awk s.log` >> libstd++.dat +let j=j+1 +runtest add-proxy/libstdc++ +echo $j `../stat.awk s.log` >> libstd++.dat +# and dummy again: +let j=j+1 +echo $j `../stat.awk s.log` >> libstd++.dat rm -f STLport.dat touch STLport.dat @@ -43,6 +49,12 @@ done runtest params-short/STLport-no-short-str echo $j `../stat.awk s.log` >> STLport.dat +let j=j+1 +runtest add-proxy/STLport-default +echo $j `../stat.awk s.log` >> STLport.dat +let j=j+1 +runtest add-proxy/STLport-add-str-proxy +echo $j `../stat.awk s.log` >> STLport.dat rm -f STLport-malloc.dat touch STLport-malloc.dat Modified: trunk/explore/perf/STL/strings.gplot =================================================================== --- trunk/explore/perf/STL/strings.gplot 2006-10-13 15:08:00 UTC (rev 1320) +++ trunk/explore/perf/STL/strings.gplot 2006-10-16 15:02:27 UTC (rev 1321) @@ -22,7 +22,7 @@ set output "strings.eps" -plot [0.9:7.1][0:25] 'string/STLport.dat' using ($1):($6) notitle w l lt 1, \ +plot [0.9:9.1][0:25] 'string/STLport.dat' using ($1):($6) notitle w l lt 1, \ 'string/STLport.dat' using ($1):($6):($7) title "STLport" w yerrorbars lt 1, \ 'string/libstd++.dat' using ($1):($6) notitle w l lt 2, \ 'string/libstd++.dat' using ($1):($6):($7) title "libstd++" w yerrorbars lt 2, \ @@ -31,22 +31,22 @@ #pause(-1) -set output "intel-amd.eps" +#set output "intel-amd.eps" -plot [0.9:7.1] 'string/STLport.dat' using ($1):($6) notitle w l lt 1, \ - 'string/STLport.dat' using ($1):($6):($7) title "STLport, computer \\#1" w yerrorbars lt 1, \ - 'string/libstd++.dat' using ($1):($6) notitle w l lt 2, \ - 'string/libstd++.dat' using ($1):($6):($7) title "libstd++, computer \\#1" w yerrorbars lt 2, \ - 'string/STLport-1.dat' using ($1):($6) notitle w l lt 3, \ - 'string/STLport-1.dat' using ($1):($6):($7) title "STLport, computer \\#2" w yerrorbars lt 3, \ - 'string/libstd++-1.dat' using ($1):($6) notitle w l lt 4, \ - 'string/libstd++-1.dat' using ($1):($6):($7) title "libstd++, computer \\#2" w yerrorbars lt 4 +#plot [0.9:7.1] 'string/STLport.dat' using ($1):($6) notitle w l lt 1, \ +# 'string/STLport.dat' using ($1):($6):($7) title "STLport, computer \\#1" w yerrorbars lt 1, \ +# 'string/libstd++.dat' using ($1):($6) notitle w l lt 2, \ +# 'string/libstd++.dat' using ($1):($6):($7) title "libstd++, computer \\#1" w yerrorbars lt 2, \ +# 'string/STLport-1.dat' using ($1):($6) notitle w l lt 3, \ +# 'string/STLport-1.dat' using ($1):($6):($7) title "STLport, computer \\#2" w yerrorbars lt 3, \ +# 'string/libstd++-1.dat' using ($1):($6) notitle w l lt 4, \ +# 'string/libstd++-1.dat' using ($1):($6):($7) title "libstd++, computer \\#2" w yerrorbars lt 4 #pause(-1) set output "alloc.eps" -plot [0.9:7.1] 'string/STLport.dat' using ($1):($6) notitle w l lt 1, \ +plot [0.9:9.1] 'string/STLport.dat' using ($1):($6) notitle w l lt 1, \ 'string/STLport.dat' using ($1):($6):($7) title "node alloc" w yerrorbars lt 1, \ 'string/STLport-newalloc.dat' using ($1):($6) notitle w l lt 2, \ 'string/STLport-newalloc.dat' using ($1):($6):($7) title "new alloc" w yerrorbars lt 2, \ @@ -174,4 +174,15 @@ 'stream/stdio.dat' using ($1):($6):($7) title "stdio" w yerrorbars lt 4, \ 'stream/unistd.dat' using ($1):($6):($7) title "unistd" w yerrorbars lt 5 +set output "streams-1.eps" + +plot [0.9:3.1] 'stream/STLport.dat' using ($1):($6) notitle w l lt 1, \ + 'stream/STLport.dat' using ($1):($6):($7) title "node alloc" w yerrorbars lt 1, \ + 'stream/STLport-malloc.dat' using ($1):($6) notitle w l lt 2, \ + 'stream/STLport-malloc.dat' using ($1):($6):($7) title "malloc" w yerrorbars lt 2, \ + 'stream/libstdc++.dat' using ($1):($6) notitle w l lt 3, \ + 'stream/libstdc++.dat' using ($1):($6):($7) title "libstdc++" w yerrorbars lt 3, \ + 'stream/stdio.dat' using ($1):($6) notitle w l lt 4, \ + 'stream/stdio.dat' using ($1):($6):($7) title "stdio" w yerrorbars lt 4 + #pause(-1) This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |