Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

You can't cheat the phone company.


devel / comp.lang.c++ / deque<> vs. list<> for a queue

SubjectAuthor
* deque<> vs. list<> for a queueBonita Montero
+- Re: deque<> vs. list<> for a queueBonita Montero
`* Re: deque<> vs. list<> for a queuePavel
 `- Re: deque<> vs. list<> for a queueBonita Montero

1
deque<> vs. list<> for a queue

<uj7du6$2ojtg$1@raubtier-asyl.eternal-september.org>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2683&group=comp.lang.c%2B%2B#2683

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!raubtier-asyl.eternal-september.org!.POSTED!not-for-mail
From: Bonita.M...@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: deque<> vs. list<> for a queue
Date: Fri, 17 Nov 2023 11:06:02 +0100
Organization: A noiseless patient Spider
Lines: 71
Message-ID: <uj7du6$2ojtg$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 17 Nov 2023 10:05:58 -0000 (UTC)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="e41417b6cf735d042fee3411535cd521";
logging-data="2903984"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18saC4Zt+agAjX43vDS/S8MvbpgbQp0h/A="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:GjiOK9SXttAIFRjB/LFbENM6tBw=
Content-Language: de-DE
 by: Bonita Montero - Fri, 17 Nov 2023 10:06 UTC

I know that a deque is superior to a list if you want to have a queue
because it does chunk-allocations, thereby allogating the storage for
multiple nodes at once. But I was curious about what's the actual per-
formance-impact. And I was interested in how many allocations were
saved through a deque. So I overloaded new and delete, redirected the
allocation to malloc and free and counted the number of allocations.

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <chrono>
#include <optional>
#include <list>

using namespace std;
using namespace chrono;

uint64_t allocs = 0;

void *operator new( size_t n )
{ ++allocs;
return malloc( n );
}

void operator delete( void *p ) noexcept
{ free( p );
}

int main()
{ auto bench = []( auto queue )
{
for( size_t i = 0; i != 10'000; ++i )
queue.emplace_back( (ostringstream() << "no short string
optimization: " << i).str() );
auto start = high_resolution_clock::now();
constexpr size_t ROUNDS = 100'000'000;
uint64_t allocsBefore = ::allocs;
for( size_t r = ROUNDS; r--; )
{
string str( move( queue.front() ) );
queue.pop_front();
queue.emplace_back( move( str ) );
}
double ns = (double)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / ROUNDS;
uint64_t allocs = ::allocs - allocsBefore;
cout << ns << ": " << allocs << endl;
};
bench( deque<string>() );
bench( list<string>() );
}

With MSVC I get the following results on a AMD 7950X Zen4 CPU:
4.01774: 6384
23.5851: 100000000
So the deque is about eight times faster and has 15.600 times less
allocations. So the chunk size must be really large with MSVC's
deque.
With g++ 12.3.0 the results are the following:
3.13869: 6250000
11.8536: 100000000
So the deque is about 3.5 times faster and the chunks seem rather
small with 16 elements per chunk. Nevertheless libstdc++ seems to
have the faster memory allocator so that allocating so much more
chunks doesn't result in less performance. The better allocation
performance shows also with the list-performance.
So the decision is for a deque if you can afford the memory blend.

Re: deque<> vs. list<> for a queue

<uj7fa2$2opq8$1@raubtier-asyl.eternal-september.org>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2684&group=comp.lang.c%2B%2B#2684

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!raubtier-asyl.eternal-september.org!.POSTED!not-for-mail
From: Bonita.M...@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: deque<> vs. list<> for a queue
Date: Fri, 17 Nov 2023 11:29:27 +0100
Organization: A noiseless patient Spider
Lines: 76
Message-ID: <uj7fa2$2opq8$1@raubtier-asyl.eternal-september.org>
References: <uj7du6$2ojtg$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 17 Nov 2023 10:29:22 -0000 (UTC)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="e41417b6cf735d042fee3411535cd521";
logging-data="2910024"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+9ZDFjutGbYQuzTEKvmAYX3NLNG/RpLKc="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:/DVm3CjdeDak5X+ue33jU7cuN4I=
Content-Language: de-DE
In-Reply-To: <uj7du6$2ojtg$1@raubtier-asyl.eternal-september.org>
 by: Bonita Montero - Fri, 17 Nov 2023 10:29 UTC

I guess that MSVC's deque-implementation attaches an just emptied front
chunk to the back's capactity. Maybe I'll find a way to prove that.

Am 17.11.2023 um 11:06 schrieb Bonita Montero:
> I know that a deque is superior to a list if you want to have a queue
> because it does chunk-allocations, thereby allogating the storage for
> multiple nodes at once. But I was curious about what's the actual per-
> formance-impact. And I was interested in how many allocations were
> saved through a deque. So I overloaded new and delete, redirected the
> allocation to malloc and free and counted the number of allocations.
>
> #include <iostream>
> #include <deque>
> #include <string>
> #include <sstream>
> #include <chrono>
> #include <optional>
> #include <list>
>
> using namespace std;
> using namespace chrono;
>
> uint64_t allocs = 0;
>
> void *operator new( size_t n )
> {
>     ++allocs;
>     return malloc( n );
> }
>
> void operator delete( void *p ) noexcept
> {
>     free( p );
> }
>
> int main()
> {
>     auto bench = []( auto queue )
>     {
>         for( size_t i = 0; i != 10'000; ++i )
>             queue.emplace_back( (ostringstream() << "no short string
> optimization: " << i).str() );
>         auto start = high_resolution_clock::now();
>         constexpr size_t ROUNDS = 100'000'000;
>         uint64_t allocsBefore = ::allocs;
>         for( size_t r = ROUNDS; r--; )
>         {
>             string str( move( queue.front() ) );
>             queue.pop_front();
>             queue.emplace_back( move( str ) );
>         }
>         double ns = (double)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / ROUNDS;
>         uint64_t allocs = ::allocs - allocsBefore;
>         cout << ns << ": " << allocs << endl;
>     };
>     bench( deque<string>() );
>     bench( list<string>() );
> }
>
> With MSVC I get the following results on a AMD 7950X Zen4 CPU:
>     4.01774: 6384
>     23.5851: 100000000
> So the deque is about eight times faster and has 15.600 times less
> allocations. So the chunk size must be really large with MSVC's
> deque.
> With g++ 12.3.0 the results are the following:
>     3.13869: 6250000
>     11.8536: 100000000
> So the deque is about 3.5 times faster and the chunks seem rather
> small with 16 elements per chunk. Nevertheless libstdc++ seems to
> have the faster memory allocator so that allocating so much more
> chunks doesn't result in less performance. The better allocation
> performance shows also with the list-performance.
> So the decision is for a deque if you can afford the memory blend.

Re: deque<> vs. list<> for a queue

<KwV5N.18774$gg_1.11873@fx09.iad>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2691&group=comp.lang.c%2B%2B#2691

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx09.iad.POSTED!not-for-mail
Subject: Re: deque<> vs. list<> for a queue
Newsgroups: comp.lang.c++
References: <uj7du6$2ojtg$1@raubtier-asyl.eternal-september.org>
From: pauldont...@removeyourself.dontspam.yahoo (Pavel)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Firefox/91.0 SeaMonkey/2.53.17.1
MIME-Version: 1.0
In-Reply-To: <uj7du6$2ojtg$1@raubtier-asyl.eternal-september.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 74
Message-ID: <KwV5N.18774$gg_1.11873@fx09.iad>
X-Complaints-To: https://www.astraweb.com/aup
NNTP-Posting-Date: Sat, 18 Nov 2023 02:42:50 UTC
Date: Fri, 17 Nov 2023 21:42:49 -0500
X-Received-Bytes: 3497
 by: Pavel - Sat, 18 Nov 2023 02:42 UTC

Bonita Montero wrote:
> I know that a deque is superior to a list if you want to have a queue
> because it does chunk-allocations, thereby allogating the storage for
> multiple nodes at once. But I was curious about what's the actual per-
> formance-impact. And I was interested in how many allocations were
> saved through a deque. So I overloaded new and delete, redirected the
> allocation to malloc and free and counted the number of allocations.
>
> #include <iostream>
> #include <deque>
> #include <string>
> #include <sstream>
> #include <chrono>
> #include <optional>
> #include <list>
>
> using namespace std;
> using namespace chrono;
>
> uint64_t allocs = 0;
>
> void *operator new( size_t n )
> {
>     ++allocs;
>     return malloc( n );
> }
>
> void operator delete( void *p ) noexcept
> {
>     free( p );
> }
>
> int main()
> {
>     auto bench = []( auto queue )
>     {
>         for( size_t i = 0; i != 10'000; ++i )
>             queue.emplace_back( (ostringstream() << "no short string
> optimization: " << i).str() );
>         auto start = high_resolution_clock::now();
>         constexpr size_t ROUNDS = 100'000'000;
>         uint64_t allocsBefore = ::allocs;
>         for( size_t r = ROUNDS; r--; )
>         {
>             string str( move( queue.front() ) );
>             queue.pop_front();
>             queue.emplace_back( move( str ) );
>         }
>         double ns = (double)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / ROUNDS;
>         uint64_t allocs = ::allocs - allocsBefore;
>         cout << ns << ": " << allocs << endl;
>     };
>     bench( deque<string>() );
>     bench( list<string>() );
> }
>
> With MSVC I get the following results on a AMD 7950X Zen4 CPU:
>     4.01774: 6384
>     23.5851: 100000000
> So the deque is about eight times faster and has 15.600 times less
> allocations. So the chunk size must be really large with MSVC's
> deque.
> With g++ 12.3.0 the results are the following:
>     3.13869: 6250000
>     11.8536: 100000000
> So the deque is about 3.5 times faster and the chunks seem rather
> small with 16 elements per chunk. Nevertheless libstdc++ seems to
> have the faster memory allocator so that allocating so much more
> chunks doesn't result in less performance. The better allocation
> performance shows also with the list-performance.
> So the decision is for a deque if you can afford the memory blend.

This particular test will most likely be bested by boost::circular_buffer.

Re: deque<> vs. list<> for a queue

<uj9dvj$36dpk$1@raubtier-asyl.eternal-september.org>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2693&group=comp.lang.c%2B%2B#2693

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!raubtier-asyl.eternal-september.org!.POSTED!not-for-mail
From: Bonita.M...@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: deque<> vs. list<> for a queue
Date: Sat, 18 Nov 2023 05:19:04 +0100
Organization: A noiseless patient Spider
Lines: 7
Message-ID: <uj9dvj$36dpk$1@raubtier-asyl.eternal-september.org>
References: <uj7du6$2ojtg$1@raubtier-asyl.eternal-september.org>
<KwV5N.18774$gg_1.11873@fx09.iad>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 18 Nov 2023 04:18:59 -0000 (UTC)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="18b2886e41555d2d68af11cb4f52fad3";
logging-data="3356468"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/gBmMh+Yxy1Jpxm5V9TRWTipiFBFrO64A="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:wpVQdRFHOR/AY8oms/3OXTbI2WY=
Content-Language: de-DE
In-Reply-To: <KwV5N.18774$gg_1.11873@fx09.iad>
 by: Bonita Montero - Sat, 18 Nov 2023 04:19 UTC

Am 18.11.2023 um 03:42 schrieb Pavel:

> This particular test will most likely be bested by boost::circular_buffer.

I've got about 18 cycles per rotate from the back to the front unter
linux. A circular buffer wouldn't be much more efficient and has the
drawback that it is expensive to extend.


devel / comp.lang.c++ / deque<> vs. list<> for a queue

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor