Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

We can predict everything, except the future.


devel / comp.lang.c++ / Re: unordered_map vs. map

SubjectAuthor
* unordered_map vs. mapBonita Montero
+- Re: unordered_map vs. mapBonita Montero
`* Re: unordered_map vs. mapAndrey Tarasevich
 `- Re: unordered_map vs. mapBonita Montero

1
unordered_map vs. map

<ursqmv$19lv0$1@raubtier-asyl.eternal-september.org>

  copy mid

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

  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: unordered_map vs. map
Date: Fri, 1 Mar 2024 16:03:01 +0100
Organization: A noiseless patient Spider
Lines: 58
Message-ID: <ursqmv$19lv0$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, 1 Mar 2024 15:02:55 -0000 (UTC)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="562ca5826301ca46c61678f52578b195";
logging-data="1365984"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX182Vv40/mHvIJxun4/+ntThXoDmoZv84xc="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:5vYos1jgRnSvoWB8rFui7mKIILE=
Content-Language: de-DE
 by: Bonita Montero - Fri, 1 Mar 2024 15:03 UTC

I had the idea that an unordered_map with copying the contents to a
vector and sorting afterwards might be faster than constructing a
similar map<>, which is sorted by nature. So I wrote some code for
that:

#include <iostream>
#include <chrono>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;
using namespace chrono;

int main()
{ auto tm = []( char const *head, auto fn )
{
auto start = high_resolution_clock::now();
fn();
cout << head << duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / 1.0e9 << endl;
};
tm( "unordered->sort: ",
[&]()
{
unordered_map<unsigned, unsigned> unsorted;
for( unsigned i = 0; i != 1'000'000; ++i )
unsorted.emplace( i, i );
vector<pair<unsigned, unsigned>> sorted;
sorted.reserve( unsorted.size() );
copy( unsorted.begin(), unsorted.end(), back_inserter( sorted ) );
sort( sorted.begin(), sorted.end(), []( auto &lhs, auto &rhs ) {
return lhs.first < rhs.first; } );
} );
tm( "ordered: ",
[&]()
{
map<unsigned, unsigned> sorted;
for( unsigned i = 0; i != 1'000'000; ++i )
sorted.emplace( i, i );
} );
}

With g++ 12 having a unordered_map and sorting afterwards is about twice
as fast:

unordered->sort: 0.0476365
ordered: 0.0908241

With MSVC both versions are much slower:

unordered->sort: 0.204837
ordered: 0.0862239

I think with MSVC the memory allocator must be much more conservative
than libstdc++'s thread-caching allocator.

Re: unordered_map vs. map

<urtb72$1dchq$1@raubtier-asyl.eternal-september.org>

  copy mid

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

  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: unordered_map vs. map
Date: Fri, 1 Mar 2024 20:44:40 +0100
Organization: A noiseless patient Spider
Lines: 68
Message-ID: <urtb72$1dchq$1@raubtier-asyl.eternal-september.org>
References: <ursqmv$19lv0$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, 1 Mar 2024 19:44:34 -0000 (UTC)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="562ca5826301ca46c61678f52578b195";
logging-data="1487418"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+pSZGfBo8nceJuUFjRwFx4db87qZjpshc="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:5tm3XKHE0HxFslfxGhc8wZD2wKU=
Content-Language: de-DE
In-Reply-To: <ursqmv$19lv0$1@raubtier-asyl.eternal-september.org>
 by: Bonita Montero - Fri, 1 Mar 2024 19:44 UTC

Am 01.03.2024 um 16:03 schrieb Bonita Montero:
> I had the idea that an unordered_map with copying the contents to a
> vector and sorting afterwards might be faster than constructing a
> similar map<>, which is sorted by nature. So I wrote some code for
> that:
>
> #include <iostream>
> #include <chrono>
> #include <unordered_map>
> #include <map>
> #include <algorithm>
> #include <vector>
>
> using namespace std;
> using namespace chrono;
>
> int main()
> {
>     auto tm = []( char const *head, auto fn )
>     {
>         auto start = high_resolution_clock::now();
>         fn();
>         cout << head << duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / 1.0e9 << endl;
>     };
>     tm( "unordered->sort: ",
>         [&]()
>         {
>             unordered_map<unsigned, unsigned> unsorted;
unsorted.reserve( 1'000'000 );
>             for( unsigned i = 0; i != 1'000'000; ++i )
>                 unsorted.emplace( i, i );
>             vector<pair<unsigned, unsigned>> sorted;
>             sorted.reserve( unsorted.size() );
>             copy( unsorted.begin(), unsorted.end(), back_inserter(
> sorted ) );
>             sort( sorted.begin(), sorted.end(), []( auto &lhs, auto
> &rhs ) { return lhs.first < rhs.first; } );
>         } );
>     tm( "ordered: ",
>         [&]()
>         {
>             map<unsigned, unsigned> sorted;
>             for( unsigned i = 0; i != 1'000'000; ++i )
>                 sorted.emplace( i, i );
>         } );
> }
>
> With g++ 12 having a unordered_map and sorting afterwards is about twice
> as fast:
>
>     unordered->sort: 0.0476365
>     ordered: 0.0908241
>
> With MSVC both versions are much slower:
>
>     unordered->sort: 0.204837
>     ordered: 0.0862239
>
> I think with MSVC the memory allocator must be much more conservative
> than libstdc++'s thread-caching allocator.

If I reserve a number of buckets according to the inserted notes in
the unordered_map I get +46% speedup with g++ and +110% on Windows.
Never throught that rehashing the buckets could be that expensive
since the number of rehashes is only logarithmic to the number of
inserted nodes.

Re: unordered_map vs. map

<uru3re$1i8fc$2@dont-email.me>

  copy mid

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

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: andreyta...@hotmail.com (Andrey Tarasevich)
Newsgroups: comp.lang.c++
Subject: Re: unordered_map vs. map
Date: Fri, 1 Mar 2024 18:45:02 -0800
Organization: A noiseless patient Spider
Lines: 15
Message-ID: <uru3re$1i8fc$2@dont-email.me>
References: <ursqmv$19lv0$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: Sat, 2 Mar 2024 02:45:02 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="0c95f5849fd7969cdf0526beba2d8ebc";
logging-data="1647084"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18oKaNbpLJw38lHrPD5Kyx7"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:rE2s7ykZTQXaoe7skxXemNspip8=
Content-Language: en-US
In-Reply-To: <ursqmv$19lv0$1@raubtier-asyl.eternal-september.org>
 by: Andrey Tarasevich - Sat, 2 Mar 2024 02:45 UTC

On 03/01/24 7:03 AM, Bonita Montero wrote:
> I had the idea that an unordered_map with copying the contents to a
> vector and sorting afterwards might be faster than constructing a
> similar map<>, which is sorted by nature. So I wrote some code for

Um... This is common knowledge. In general case, if have you all your
data available to you in advance, it is always faster to use a good
off-line sorting algorithm than an on-line sorting algorithm.

The on-line nature of `std::map`-based sorting is the luxury for which
you pay in extra overhead.

--
Best regards,
Andrey

Re: unordered_map vs. map

<uruhb3$1ocbp$1@raubtier-asyl.eternal-september.org>

  copy mid

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

  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: unordered_map vs. map
Date: Sat, 2 Mar 2024 07:35:21 +0100
Organization: A noiseless patient Spider
Lines: 15
Message-ID: <uruhb3$1ocbp$1@raubtier-asyl.eternal-september.org>
References: <ursqmv$19lv0$1@raubtier-asyl.eternal-september.org>
<uru3re$1i8fc$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 2 Mar 2024 06:35:15 -0000 (UTC)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="f9047fbcab9d30f29491e78f7dd1b6ad";
logging-data="1847673"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX193/TeVWVND/uFi95K36VSyCQPBELMzcqE="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:cGGAQus/r3LC8vTvuSD5PwJGoZk=
In-Reply-To: <uru3re$1i8fc$2@dont-email.me>
Content-Language: de-DE
 by: Bonita Montero - Sat, 2 Mar 2024 06:35 UTC

Am 02.03.2024 um 03:45 schrieb Andrey Tarasevich:
> On 03/01/24 7:03 AM, Bonita Montero wrote:
>> I had the idea that an unordered_map with copying the contents to a
>> vector and sorting afterwards might be faster than constructing a
>> similar map<>, which is sorted by nature. So I wrote some code for
>
> Um... This is common knowledge. ...

That MSCVC isn't faster with that ?

> The on-line nature of `std::map`-based sorting is the luxury for which
> you pay in extra overhead.

Walking the pointer chain in the tree is just slow because it
is serialized operation with no instruction level parallelism.


devel / comp.lang.c++ / Re: unordered_map vs. map

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor