rt/aaA.d Line: 553

[Steven Schveighoffer]

On 2/14/20 5:57 PM, Ferhat Kurtulmuş wrote:
> I hesitated to post this on the topic of druntime because probably I 
> will learn something new if I am totally/stupidly wrong.

There are no stupid questions, and this is the learn forum. So you are 
in the right place!

> 
> In druntime/blob/master/src/rt/aaA.d Lines 553-562:

One thing to learn, you can select a section of lines from github (click 
on first line, then shift-click on last line), then press the 'y' key, 
and it will generate a permanent link to those lines.

https://github.com/dlang/druntime/blob/a581dc6d1d3bf796fcebd982221d0b3d6bbae437/src/rt/aaA.d#L553-L562

> 
> ...
>      auto p = aa.findSlotInsert(hash);
>      if (p.deleted)
>          --aa.deleted;
>      // check load factor and possibly grow
>      else if (++aa.used * GROW_DEN > aa.dim * GROW_NUM)
>      {
>          aa.grow(ti.key);
>          p = aa.findSlotInsert(hash);
>          assert(p.empty);
>      }
> ...
> 
> findSlotInsert are called two times. Why not:
> 
>      if (++aa.used * GROW_DEN > aa.dim * GROW_NUM)
>          aa.grow(ti.key);
> 
>      auto p = aa.findSlotInsert(hash); // only one call is enough?
> 
>      if (p.deleted)
>          --aa.deleted;
> ...
> 
> If I am not wrong this modification will not corrupt the current state 
> of the hash table?

A cursory reading:

I think the case where you find the insert slot and the p.deleted is 
true, you can avoid the grow function.

The grow function is much more expensive than findInsertSlot, so calling 
it twice is preferable.

The reason we have the deleted status is because we want to reuse 
memory, but we can't free the memory if it had a dangling reference to it.

The only time those deleted nodes turn into garbage is on a resize.

HOWEVER, one case where we can avoid the double search is if there are 
no deleted nodes (we keep a count of them). This should be reasonably 
often in most cases because you insert nodes and don't remove them, or 
you grew the AA and all deleted nodes are purged.

So maybe change to:

Bucket *p;

if(aa.deleted > 0 && (p = aa.findSlotInsert(hash)).deleted)
    --aa.deleted;
else // everything else the same

-Steve