fast destruction of std::vector<std::pair<int, int> >

[Mitsuru]

Dear againtry

Thank you for.sharing your codes.

In a series of this post, I understand that the problems I asked (particularly the name of this post) bothers everyone because the problem is too simple to judge what is cause, that is, its premise is essential.

After confirming the cause of overhead in detailed manner,
I hope to ask you again.

Thank you

[againtry]

You're welcome Mtsuru. I hope it helps.

[dutch]

Since your max M is so small, you can easily use just one map (instead of a map of a map) and not bother with a special hash. The key can still be a single size_t, or even an unsigned 32-bit value (which makes it half the size if size_t is 64-bits):

    unordered_map<uint32_t,vector<pair<size_t,size_t>>> data;
    uint32_t key = (uint32_t(m1) << 16) | uint32_t(m2);

Another question:
In the data given previously, suppose the pair (3,4) existed (where 3 and 4 are both from group 1). Then could the vector associated with F(1,2) also contain (3,4) ? Or would that be associated with F(1,1) ?

Also, in the notation F(1,2), does the first of the pair need to come from group 1 and the second from group 2? I.e., is F(1,2) different from F(2,1) ?

[Mitsuru]

Dear dutch

Thank you for your various advices.

 unordered_map<uint32_t,vector<pair<size_t,size_t>>> data;
    uint32_t key = (uint32_t(m1) << 16) | uint32_t(m2);

In fact, I also tried the hashing as you told me, that is, the bit operation.
This modification make programs faster, nevertheless, speed of generation is slower than primitive type, std::size_t.
This overhead is superior to reduction of destruction time reduction,
from
unordered_map<std::size_t, unordered_map<std::size_t, vector<std::pair<std::size_t, std::size_t> > > >
to
unordered_map<std::pair<std::size_t, std::size_t>, vector<std::pair<std::size_t, std::size_t> > >
I suppose that this is due to high frequent call of unordered_map::emplace, which entails calls of hash functions.
(I have intention to consider a way to reduce the calls of emplace)

Another question:
In the data given previously, suppose the pair (3,4) existed (where 3 and 4 are both from group 1). Then could the vector associated with F(1,2) also contain (3,4) ? Or would that be associated with F(1,1) ?

Thank you for your consideration. If (3,4) exists, it is associated with F(1,1).

Also, in the notation F(1,2), does the first of the pair need to come from group 1 and the second from group 2? I.e., is F(1,2) different from F(2,1) ?

In the generation stage of the mapper, as to F(M1, M2), M1 <= M2 is imposed, so that there just F(1,2) exists, but F(2,1) does not exist.

[Mitsuru]

Dear C++ experts,

In this post, I fully realized that I have mere shallow knowledge about techniques about dynamic memory allocation in C++, particularly for STL containers.
(c.f. basis of dynamic allocation (particularly, time overhead), allocator, trivially_destructible, memory pool etc)

If you know organized documents about them,
I would appreciate it if you could tell me.

[mbozzi]

About allocators, see section 34.4 of The C++ Programming Language, 4th. ed. by Stroustrup, ISBN 978-0-321-56384-2

A trivial destructor has no effect, so the storage for an object of trivially-destructible type can be reused without calling its destructor.

You can look up the definition of a trivial destructor in the standard if you want, but in general all destructors do not need to be called unless their side effects are important.

A memory pool like the one I discussed prior ( http://www.cplusplus.com/forum/general/273999/#msg1182423 ) was proposed by some folks at Bloomberg and accepted into C++17 as std::pmr::monotonic_buffer_resource, although compiler support has lagged for several years.

It is usable through std::pmr::polymorphic_allocator. If necessary, an implementation is available in Boost.

For more about this, read
https://wg21.link/n3916
just for motivation & rationale (the details aren't important) then watch this talk
https://www.youtube.com/watch?v=v3dz-AKOVL8

[Mitsuru]

Dear mbozzi

Thank you so much for your teaching, and I will study the techniques.

Kind regards

[Mitsuru]

Finally, I could resolve a series of my problem relating to memory allocation/deallocation.

I understand that matters of constructor/destructor and allocator/deallocator are different.
I trimmed generation of useless objects, and use polymorphic memory resource (monotonic_buffer_resource), then I could attain high speed up in the latter matter.

Thank you for your various advices.