Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #79686 > unrolled thread

std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint

Back to article view | Back to comp.lang.c++

Contents

  std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-21 16:08 +0200
    Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint "daniel...@gmail.com" <danielaparker@gmail.com> - 2021-05-21 12:59 -0700
    Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Öö Tiib <ootiib@hot.ee> - 2021-05-21 14:29 -0700
      Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-22 08:14 +0200
        Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-22 11:23 +0200
          Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Öö Tiib <ootiib@hot.ee> - 2021-05-22 03:32 -0700
            Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-22 12:43 +0200
              Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Öö Tiib <ootiib@hot.ee> - 2021-05-22 05:11 -0700
                Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-22 14:46 +0200
                  Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Öö Tiib <ootiib@hot.ee> - 2021-05-22 05:57 -0700
                    Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-05-22 07:49 -0700
                      Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Öö Tiib <ootiib@hot.ee> - 2021-05-22 08:23 -0700
                    Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-22 15:04 +0200
                      Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Öö Tiib <ootiib@hot.ee> - 2021-05-22 06:51 -0700
        Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Öö Tiib <ootiib@hot.ee> - 2021-05-22 02:11 -0700
      Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint "daniel...@gmail.com" <danielaparker@gmail.com> - 2021-05-22 05:28 -0700
        Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Öö Tiib <ootiib@hot.ee> - 2021-05-22 05:54 -0700
          Re: std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-22 15:06 +0200

#79686 — std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint

Can anyone tell me what
	std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint
is good for ? The key maps totally chaotic to a hash which is reduced
to a bucket-index. So there should be no way to guess a hint. So this
looks to me like a total nonsense-API.

[toc] | [next] | [standalone]

#79701

On Friday, May 21, 2021 at 10:08:46 AM UTC-4, Bonita Montero wrote:
> Can anyone tell me what 
> std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint 
> is good for ? The key maps totally chaotic to a hash which is reduced 
> to a bucket-index. So there should be no way to guess a hint. So this 
> looks to me like a total nonsense-API.

The hint is of course useless when keys are unique, as they must be for std::unordered_map.
However, the hint can be meaningful for std::unordered_multimap, when keys are
equivalent. The Standard specifies that both std::unordered_map and  std::unordered_multimap 
satisfy the type requirement "unordered associative container", which has the emplace_hint function,
hence both container types have it. The Standard also allows implementations to ignore the hint.
At a quick glance, it looks like Microsoft's implementation ignores the hint for both container types,
while gcc's uses it for equivalent keys.

Daniel    

[toc] | [prev] | [next] | [standalone]

#79702

On Friday, 21 May 2021 at 17:08:46 UTC+3, Bonita Montero wrote:
> Can anyone tell me what 
> std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint 
> is good for ? The key maps totally chaotic to a hash which is reduced 
> to a bucket-index. So there should be no way to guess a hint. So this 
> looks to me like a total nonsense-API.

Some code that used map can be faster and with less changes switched
to use of unordered_map.  Also some generic code can be used for both.
Even if implementation ignores that hint  there is slight performance
potential as it returns only iterator not pair<iterator,bool> like emplace. 
If implementation does not ignore that hint then it can also fail faster.
That is important when fails are frequent.

[toc] | [prev] | [next] | [standalone]

#79703

> Even if implementation ignores that hint  there is slight performance
> potential as it returns only iterator not pair<iterator,bool> like emplace.

But you hand over an additional iterator, which outweighs
this advantage.

[toc] | [prev] | [next] | [standalone]

#79704

>>> Even if implementation ignores that hint there is slight performance
>>> potential as it returns only iterator not pair<iterator,bool> like emplace.

>> But you hand over an additional iterator, which outweighs
>> this advantage.

> Groundless assertion noted.

Imagine the simplest case when the iterator is simply a pointer
internally. Moving a pointer has the same cost on todays CPUs
than a bool.

[toc] | [prev] | [next] | [standalone]

#79706

On Saturday, 22 May 2021 at 12:23:48 UTC+3, Bonita Montero wrote:
> >>> Even if implementation ignores that hint there is slight performance 
> >>> potential as it returns only iterator not pair<iterator,bool> like emplace. 
> 
> >> But you hand over an additional iterator, which outweighs 
> >> this advantage. 
> 
> > Groundless assertion noted.
> Imagine the simplest case when the iterator is simply a pointer 
> internally. Moving a pointer has the same cost on todays CPUs 
> than a bool.

I understand that imagination was ground to your shallow claim. But
fruits of imagination are better dismissed in engineering.

[toc] | [prev] | [next] | [standalone]

#79707

>> Imagine the simplest case when the iterator is simply a pointer
>> internally. Moving a pointer has the same cost on todays CPUs
>> than a bool.

> I understand that imagination was ground to your shallow claim.
> But fruits of imagination are better dismissed in engineering.

You're arrogant and stupid.
Look at this code:

#include <unordered_map>
#include <utility>

using namespace std;

using umi_t  = unordered_map<int, int>;
using umi_it = umi_t::iterator;

pair<umi_it, bool> f123( umi_t &um )
{
	return pair<umi_it, bool>( um.begin(), true );
}

umi_it f456( umi_t &um )
{
	return um.begin();
}

This results in this:

	.file	"x.cpp"
	.text
	.p2align 4,,15
	.globl 
_Z4f123RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE
	.type 
_Z4f123RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE, 
@function
_Z4f123RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE:
.LFB1603:
	.cfi_startproc
	movq	16(%rdi), %rax
	movl	$1, %edx
	ret
	.cfi_endproc
.LFE1603:
	.size 
_Z4f123RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE, 
.-_Z4f123RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE
	.p2align 4,,15
	.globl 
_Z4f456RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE
	.type 
_Z4f456RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE, 
@function
_Z4f456RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE:
.LFB1621:
	.cfi_startproc
	movq	16(%rdi), %rax
	ret
	.cfi_endproc
.LFE1621:
	.size 
_Z4f456RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE, 
.-_Z4f456RSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE
	.ident	"GCC: (Debian 6.3.0-18+deb9u1) 6.3.0 20170516"
	.section	.note.GNU-stack,"",@progbits

So the difference is just one move as I told.
And as you can see from the abvove, an iterator is just a pointer
for this container. And passing a hint-iterator would be just an
additional move. So the additional bool is outweight by the hint.

[toc] | [prev] | [next] | [standalone]

#79708

On Saturday, 22 May 2021 at 13:43:45 UTC+3, Bonita Montero wrote:
> >> Imagine the simplest case when the iterator is simply a pointer 
> >> internally. Moving a pointer has the same cost on todays CPUs 
> >> than a bool. 
> 
> > I understand that imagination was ground to your shallow claim. 
> > But fruits of imagination are better dismissed in engineering.
> 
> You're arrogant and stupid. 

You are mirroring how you feel yourself to me.

> Look at this code: 

I wrote "Even if implementation ignores that hint there is slight
performance potential as it returns only iterator not 
pair<iterator,bool> like emplace. "
You groundlessly claimed that passing (allegedly unused) iterator
there somehow outweights that advantage.

To my dismissing of your groundless claims you now just 
demonstrate inability to profile difference of performance of
emplace_hint and emplace of unordered_map implementation
that ignores that hint (AFAIK msvc does).

How I am arrogant and stupid? I was simply correct that you pull
your claims out from ignorance and imagination and you yourself
demonstrated it to everybody.

[toc] | [prev] | [next] | [standalone]

#79710

> I wrote "Even if implementation ignores that hint there is slight
> performance potential as it returns only iterator not
> pair<iterator,bool> like emplace. "

Yes, and I've shown that the difference is just an move-instruction.
And this is the same difference when passing hint.

> You groundlessly claimed that passing (allegedly unused) iterator
> there somehow outweights that advantage.

Yes, because this is a identical move.

> How I am arrogant and stupid? ...

Yes, ultra-stupid.

[toc] | [prev] | [next] | [standalone]

#79712

On Saturday, 22 May 2021 at 15:46:58 UTC+3, Bonita Montero wrote:
> > I wrote "Even if implementation ignores that hint there is slight 
> > performance potential as it returns only iterator not 
> > pair<iterator,bool> like emplace. "
> Yes, and I've shown that the difference is just an move-instruction. 
> And this is the same difference when passing hint.
> > You groundlessly claimed that passing (allegedly unused) iterator 
> > there somehow outweights that advantage.
> Yes, because this is a identical move. 
> 
> > How I am arrogant and stupid? ... 
> 
> Yes, ultra-stupid.

All your life you are doomed to claim groundless garbage and
then to run from discussions with pathetic insults. Does it feel
good?

[toc] | [prev] | [next] | [standalone]

#79713

Tiib <ootiib@hot.ee> writes:

> On Saturday, 22 May 2021 at 15:46:58 UTC+3, Bonita Montero wrote:
>
>>> I wrote "Even if implementation ignores that hint there is slight
>>> performance potential as it returns only iterator not
>>> pair<iterator,bool> like emplace. "
>>
>> Yes, and I've shown that the difference is just an move-instruction.
>> And this is the same difference when passing hint.
>>
>>> You groundlessly claimed that passing (allegedly unused) iterator
>>> there somehow outweights that advantage.
>>
>> Yes, because this is a identical move.
>>
>>> How I am arrogant and stupid? ...
>>
>> Yes, ultra-stupid.
>
> All your life you are doomed to claim groundless garbage and
> then to run from discussions with pathetic insults.  Does it feel
> good?

Which brings up the question, why then do you bother responding?
Or even reading the posts to begin with?

[toc] | [prev] | [next] | [standalone]

#79719

On Saturday, 22 May 2021 at 17:49:52 UTC+3, Tim Rentsch wrote:
> Tiib <oot...@hot.ee> writes: 
> 
> > On Saturday, 22 May 2021 at 15:46:58 UTC+3, Bonita Montero wrote: 
> > 
> >>> I wrote "Even if implementation ignores that hint there is slight 
> >>> performance potential as it returns only iterator not 
> >>> pair<iterator,bool> like emplace. " 
> >> 
> >> Yes, and I've shown that the difference is just an move-instruction. 
> >> And this is the same difference when passing hint. 
> >> 
> >>> You groundlessly claimed that passing (allegedly unused) iterator 
> >>> there somehow outweights that advantage. 
> >> 
> >> Yes, because this is a identical move. 
> >> 
> >>> How I am arrogant and stupid? ... 
> >> 
> >> Yes, ultra-stupid. 
> > 
> > All your life you are doomed to claim groundless garbage and 
> > then to run from discussions with pathetic insults. Does it feel 
> > good?
> 
> Which brings up the question, why then do you bother responding? 
> Or even reading the posts to begin with?

The idea that profiling of real thing can be replaced with 
imagination and guessing is indeed quite common and boring
mistake that perhaps does not deserve discussions.
Otherwise I'm just reading a book and as it is Saturday am not too
busy with anything.
 

[toc] | [prev] | [next] | [standalone]

#79714

> All your life you are doomed to claim groundless garbage ...

You could say that if you'd understand what I told.
But you didn't.

[toc] | [prev] | [next] | [standalone]

#79716

On Saturday, 22 May 2021 at 16:05:15 UTC+3, Bonita Montero wrote:
> > All your life you are doomed to claim groundless garbage ... 
> 
> You could say that if you'd understand what I told. 
> But you didn't.

Such empty screams of disagreeing "No!" and "No I didnt!"
are integral part of the song "So brave sir robin ran away,
bravely ran away away..."
 <https://www.youtube.com/watch?v=BZwuTo7zKM8>

[toc] | [prev] | [next] | [standalone]

#79705

On Saturday, 22 May 2021 at 09:14:26 UTC+3, Bonita Montero wrote:
> > Even if implementation ignores that hint there is slight performance 
> > potential as it returns only iterator not pair<iterator,bool> like emplace.
> But you hand over an additional iterator, which outweighs 
> this advantage.

Groundless assertion noted.

[toc] | [prev] | [next] | [standalone]

#79709

On Friday, May 21, 2021 at 5:29:26 PM UTC-4, Öö Tiib wrote:
> On Friday, 21 May 2021 at 17:08:46 UTC+3, Bonita Montero wrote: 
> > Can anyone tell me what 
> > std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint 
> > is good for ? The key maps totally chaotic to a hash which is reduced 
> > to a bucket-index. So there should be no way to guess a hint. So this 
> > looks to me like a total nonsense-API.
> Some code that used map can be faster and with less changes switched 
> to use of unordered_map. 

Who does that? Microsoft doesn't. gcc doesn't. Microsoft and gcc share
implementation details between unordered_map and unordered_multimap,
not map. And even there, the shared code doesn't leak into the interface, 
it's introduced as a data member that unordered_map and unordered_multimap
both delegate to. And why would the Standard, which mandates emplace_hint
in both container types, care about these implementation details?

No, the only reason that emplace_hint appears in both unordered_map, where it's
useless, and unordered_multimap, where it makes some sense with equivalent
keys, is because the Standard mandated that both container types satisfy the 
same type requirement "unordered associative container".

Daniel

[toc] | [prev] | [next] | [standalone]

#79711

On Saturday, 22 May 2021 at 15:29:00 UTC+3, daniel...@gmail.com wrote:
> On Friday, May 21, 2021 at 5:29:26 PM UTC-4, Öö Tiib wrote: 
> > On Friday, 21 May 2021 at 17:08:46 UTC+3, Bonita Montero wrote: 
> > > Can anyone tell me what 
> > > std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::emplace_hint 
> > > is good for ? The key maps totally chaotic to a hash which is reduced 
> > > to a bucket-index. So there should be no way to guess a hint. So this 
> > > looks to me like a total nonsense-API. 
> > Some code that used map can be faster and with less changes switched 
> > to use of unordered_map.
>
> Who does that? Microsoft doesn't. gcc doesn't. Microsoft and gcc share 
> implementation details between unordered_map and unordered_multimap, 
> not map. 

Sorry for me not expressing myself clearly enough. I mean I do it.
Usage of std::map for dictionary to what alphabetic orders of keys
does not matter is unfortunately common. If searches to such
dictionary show up as factor in profiler then I propose to switch to
unordered_map. 

That work can be so small as replacing:
using RecordDictionary = std::map<std::string, Record>;
with:
using RecordDictionary = std::unordered_map<std::string, Record>;
and then running tests and then profiling.
  
But if  emplace_hint of RecordDictionary was used  in code then
the tests would not compile and so more changes would be needed. 

[toc] | [prev] | [next] | [standalone]

#79715

> That work can be so small as replacing:
> using RecordDictionary = std::map<std::string, Record>;
> with:
> using RecordDictionary = std::unordered_map<std::string, Record>;
> and then running tests and then profiling.
> But if  emplace_hint of RecordDictionary was used  in code then
> the tests would not compile and so more changes would be needed.

I think it's not really because of that because the hint-parameter
could be removed in a blink of an eye.
I think it's about generic code interfacing to generic containers
which need this identical interface-specification.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web