#define _SECURE_SCL 0\n#define _SCL_SECURE_NO_WARNINGS\n\n#include <algorithm> \/\/ std::swap\n#include <iostream>\n#include <vector>\n#include <stack>\n#include <stddef.h> \/\/ ptrdiff_t\n#include <type_traits> \/\/ std::is_pod\nusing namespace std;\n\n#undef UNICODE\n#define UNICODE\n#include <Windows.h>\n\ntypedef ptrdiff_t Size;\ntypedef Size Index;\n\ntemplate< class Type, class Container >\nvoid reserve( Size const newBufSize, std::stack< Type, Container >& st )\n{\n struct Access: std::stack< Type, Container >\n {\n static Container& container( std::stack< Type, Container >& st )\n {\n return st.*&Access::c;\n }\n };\n\n Access::container( st ).reserve( newBufSize );\n}\n\nclass HighResolutionTimer\n{\npublic:\n HighResolutionTimer();\n double GetFrequency() const;\n void Start() ;\n double Stop();\n double GetTime() const;\n\nprivate:\n LARGE_INTEGER start;\n LARGE_INTEGER stop;\n double frequency;\n};\n\nHighResolutionTimer::HighResolutionTimer()\n{\n frequency = GetFrequency();\n}\n\ndouble HighResolutionTimer::GetFrequency() const\n{\n LARGE_INTEGER proc_freq;\n if (!::QueryPerformanceFrequency(&proc_freq))\n return -1;\n return static_cast< double >( proc_freq.QuadPart );\n}\n\nvoid HighResolutionTimer::Start()\n{\n DWORD_PTR oldmask = ::SetThreadAffinityMask(::GetCurrentThread(), 0);\n ::QueryPerformanceCounter(&start);\n ::SetThreadAffinityMask(::GetCurrentThread(), oldmask);\n}\n\ndouble HighResolutionTimer::Stop()\n{\n DWORD_PTR oldmask = ::SetThreadAffinityMask(::GetCurrentThread(), 0);\n ::QueryPerformanceCounter(&stop);\n ::SetThreadAffinityMask(::GetCurrentThread(), oldmask);\n return ((stop.QuadPart - start.QuadPart) \/ frequency);\n} \n\ndouble HighResolutionTimer::GetTime() const\n{\n LARGE_INTEGER time;\n ::QueryPerformanceCounter(&time);\n return time.QuadPart \/ frequency;\n}\n\ntemplate< class Type, bool elemTypeIsPOD = !!std::is_pod< Type >::value >\nclass FastStack;\n\ntemplate< class Type >\nclass FastStack< Type, true >\n{\nprivate:\n Type* st_;\n Index lastIndex_;\n Size capacity_;\n\npublic:\n Size const size() const { return lastIndex_ + 1; }\n Size const capacity() const { return capacity_; }\n\n void reserve( Size const newCapacity )\n {\n if( newCapacity > capacity_ )\n {\n FastStack< Type >( *this, newCapacity ).swapWith( *this );\n }\n }\n\n void push( Type const& x )\n {\n if( size() == capacity() )\n {\n reserve( 2*capacity() );\n }\n st_[++lastIndex_] = x;\n }\n\n void pop()\n {\n --lastIndex_;\n }\n\n Type top() const\n {\n return st_[lastIndex_];\n }\n\n void swapWith( FastStack& other ) throw()\n {\n using std::swap;\n swap( st_, other.st_ );\n swap( lastIndex_, other.lastIndex_ );\n swap( capacity_, other.capacity_ );\n }\n\n void operator=( FastStack other )\n {\n other.swapWith( *this );\n }\n\n ~FastStack()\n {\n delete[] st_;\n }\n\n FastStack( Size const aCapacity = 0 )\n : st_( new Type[aCapacity] )\n , capacity_( aCapacity )\n {\n lastIndex_ = -1;\n }\n\n FastStack( FastStack const& other, int const newBufSize = -1 )\n {\n capacity_ = (newBufSize < other.size()? other.size(): newBufSize);\n st_ = new Type[capacity_];\n lastIndex_ = other.lastIndex_;\n copy( other.st_, other.st_ + other.size(), st_ ); \/\/ Can't throw for POD.\n }\n};\n\ntemplate< class Type >\nvoid reserve( Size const newCapacity, FastStack< Type >& st )\n{\n st.reserve( newCapacity );\n}\n\ntemplate< class StackType >\nvoid test( char const* const description )\n{\n for( int it = 0; it < 4; ++it )\n {\n StackType st;\n reserve( 200, st );\n\n \/\/ after this two loops, st's capacity will be 141 so there will be no more reallocating\n for( int i = 0; i < 100; ++i ) { st.push( i ); }\n for( int i = 0; i < 100; ++i ) { st.pop(); }\n\n \/\/ when you uncomment this line, std::stack performance will magically rise about 18%\n \/\/ std::vector<int> magicVector(10);\n\n HighResolutionTimer timer;\n timer.Start();\n\n for( Index i = 0; i < 1000000000; ++i )\n {\n st.push( i );\n (void) st.top();\n if( i % 100 == 0 && i != 0 )\n {\n for( int j = 0; j < 100; ++j ) { st.pop(); }\n }\n }\n\n double const totalTime = timer.Stop();\n wcout << description << \": \" << totalTime << endl;\n }\n}\n\nint main()\n{\n typedef stack< Index, vector< Index > > SStack;\n typedef FastStack< Index > FStack;\n\n test< SStack >( \"std::stack\" );\n test< FStack >( \"FastStack\" );\n\n cout << \"Done\";\n}\n<\/code><\/pre>\nResults on this slow-as-molasses Samsung RC530 laptop:<\/p>\n
\n[D:\\dev\\test\\so\\12704314]\n> a\nstd::stack: 3.21319\nstd::stack: 3.16456\nstd::stack: 3.23298\nstd::stack: 3.20854\nFastStack: 1.97636\nFastStack: 1.97958\nFastStack: 2.12977\nFastStack: 2.13507\nDone\n[D:\\dev\\test\\so\\12704314]\n> _\n<\/pre>\nAnd similarly for Visual C++.<\/p>\n
Now let’s look at a typical implementation of std::vector::push_back<\/code>, which is called by std::stack<T, std::vector<T>>::push<\/code> (in passing, I know of only 3 programmers who have ever used this indentation style, namely PJP, Petzold and myself; I now, since 1998 or thereabouts, think it’s horrible!):<\/p>\nvoid push_back(const value_type& _Val)\n { \/\/ insert element at end\n if (_Inside(_STD addressof(_Val)))\n { \/\/ push back an element\n size_type _Idx = _STD addressof(_Val) - this->_Myfirst;\n if (this->_Mylast == this->_Myend)\n _Reserve(1);\n _Orphan_range(this->_Mylast, this->_Mylast);\n this->_Getal().construct(this->_Mylast,\n this->_Myfirst[_Idx]);\n ++this->_Mylast;\n }\n else\n { \/\/ push back a non-element\n if (this->_Mylast == this->_Myend)\n _Reserve(1);\n _Orphan_range(this->_Mylast, this->_Mylast);\n this->_Getal().construct(this->_Mylast,\n _Val);\n ++this->_Mylast;\n }\n }\n<\/code><\/pre>\nI suspect<\/em> that the measured inefficiency lies at least partly in all the stuff going on there, and perhaps<\/em> it’s also a matter of automatically generated safety checks.<\/p>\nFor a debug build the std::stack<\/code> performance is so extremely ungood that I gave up waiting for any result.<\/p>\n
\nEDIT<\/strong>: following Xeo\u2019s comment below I updated push<\/code> to check for “self-push” in the case of buffer reallocation, by factoring that out as a separate function:<\/p>\nvoid push( Type const& x )\n{\n if( size() == capacity() )\n {\n reserveAndPush( x );\n }\n st_[++lastIndex_] = x;\n}\n<\/code><\/pre>\nMysteriously, although reserveAndPush<\/code> is never called<\/em> in this testing, it affects the performance \u2013 due to code size not fitting cache?<\/p>\n\n[D:\\dev\\test\\so\\12704314]\n> a\nstd::stack: 3.21623\nstd::stack: 3.30501\nstd::stack: 3.24337\nstd::stack: 3.27711\nFastStack: 2.52791\nFastStack: 2.44621\nFastStack: 2.44759\nFastStack: 2.47287\nDone\n[D:\\dev\\test\\so\\12704314]\n> _\n<\/pre>\n<\/p>\n
\nEDIT 2<\/strong>: DeadMG showed that the code must be buggy. I believe the problem was a missing return<\/code>, plus the expression computing new size (twice zero is still zero). He also pointed out that I forgot to show reserveAndPush<\/code>. Should be:<\/p>\nvoid reserveAndPush( Type const& x )\n{\n Type const xVal = x;\n reserve( capacity_ == 0? 1 : 2*capacity_ );\n push( xVal );\n}\n\nvoid push( Type const& x )\n{\n if( size() == capacity() )\n {\n return reserveAndPush( x ); \/\/ <-- The crucial \"return\".\n }\n st_[++lastIndex_] = x;\n}\n<\/code><\/pre>\n<\/p><\/div>\n<\/div>\n<\/div>\n
19<\/span> <\/p><\/div>\n<\/div>\n[ad_2]<\/p>\n
solved std stack performance issues [closed] <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] The many comments (and even answers) focus on the risks in your implementation. Yet the question stands. As directly demonstrated below rectifying the perceived code shortcomings would not change anything significant about the performance. Here is the OP’s code modified to be (A) safe, and (B) supporting the same operations as std::stack, and (C) … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[324,325,376,774],"class_list":["post-5483","post","type-post","status-publish","format-standard","hentry","category-solved","tag-c","tag-performance","tag-stack","tag-windows"],"yoast_head":"\n[Solved] std stack performance issues [closed] - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] std stack performance issues [closed] - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] The many comments (and even answers) focus on the risks in your implementation. Yet the question stands. As directly demonstrated below rectifying the perceived code shortcomings would not change anything significant about the performance. Here is the OP’s code modified to be (A) safe, and (B) supporting the same operations as std::stack, and (C) ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-08-28T19:29:02+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] std stack performance issues [closed]\",\"datePublished\":\"2022-08-28T19:29:02+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/\"},\"wordCount\":274,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"c++\",\"performance\",\"stack\",\"windows\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/\",\"name\":\"[Solved] std stack performance issues [closed] - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-08-28T19:29:02+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] std stack performance issues [closed]\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] std stack performance issues [closed] - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] std stack performance issues [closed] - JassWeb","og_description":"[ad_1] The many comments (and even answers) focus on the risks in your implementation. Yet the question stands. As directly demonstrated below rectifying the perceived code shortcomings would not change anything significant about the performance. Here is the OP’s code modified to be (A) safe, and (B) supporting the same operations as std::stack, and (C) ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/","og_site_name":"JassWeb","article_published_time":"2022-08-28T19:29:02+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] std stack performance issues [closed]","datePublished":"2022-08-28T19:29:02+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/"},"wordCount":274,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["c++","performance","stack","windows"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/","url":"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/","name":"[Solved] std stack performance issues [closed] - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-08-28T19:29:02+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-std-stack-performance-issues-closed\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] std stack performance issues [closed]"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/5483","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=5483"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/5483\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=5483"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=5483"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=5483"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}