[PATCH] Enhance _Hashtable for range insertion 0/5

[François Dumont]

I knew you were going to ask for it but was to impatient to propose 
those patches to wait anymore.

Attached you'll find what I start to work on. But I am quite 
disappointed by the results. At least it's showing  that results are not 
worst.

To be honest I was also hoping some feedback from potential users 
interesting in testing those patches. And maybe there are some well 
known (and free) benches that I could challenge ?

François

On 21/06/22 19:12, Jonathan Wakely wrote:
> On Mon, 20 Jun 2022 at 17:58, François Dumont via Libstdc++
> <libstdc++@gcc.gnu.org> wrote:
>> Hi
>>
>> Here is a series of patch to enhance _Hashtable behavior mostly in the
>> context of range insertion. I also start considering the problem of
>> memory fragmentation in this container with 2 objectives:
>>
>> - It is easier to find out when you're done with the elements of a
>> bucket if the last node of the bucket N is the before-begin node of
>> bucket N + 1.
>>
>> - It is faster to loop through nodes of a bucket if those node are close
>> in memory, ultimately we should have addressof(Node + 1) ==
>> addressof(Node) + 1
> Have these changes been profiled or benchmarked? Is it measurably
> faster? By how much?
>
>
>> [1/5] Make more use of user hints as both insertion and allocation hints.
>>
>> [2/5] Introduce a new method to check if we are still looping through
>> the same bucket's nodes
>>
>> [3/5] Consider that all initializer_list elements are going to be inserted
>>
>> [4/5] Introduce a before-begin cache policy to remember which bucket is
>> currently pointing on it
>>
>> [5/5] Prealloc nodes on _Hashtable copy and introduce a new assignment
>> method which replicate buckets data structure
>>
>> François
>>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bench.patch
Type: text/x-patch
Size: 9007 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20220626/4a73b2cd/attachment.bin>