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

[Bonita Montero]

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.

[daniel...@gmail.com]

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

[Öö Tiib]

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.

[Bonita Montero]

> 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.

[Öö Tiib]

Groundless assertion noted.

[Bonita Montero]

>>> 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.

[Öö Tiib]

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

[Bonita Montero]

>> 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.

[Öö Tiib]

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.

[daniel...@gmail.com]

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

[Bonita Montero]

> 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.

[Öö Tiib]

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.

[Öö Tiib]

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

[Bonita Montero]

> 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.

[Bonita Montero]

> 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.

[Öö Tiib]

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>

[Tim Rentsch]

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

[Öö Tiib]

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.