www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - rt/aaA.d Line: 553

reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
I hesitated to post this on the topic of druntime because 
probably I will learn something new if I am totally/stupidly 
wrong.

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

...
     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?
Feb 14 2020
next sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Friday, 14 February 2020 at 22:57:31 UTC, Ferhat Kurtulmuş 
wrote:

 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?


`used` counts both filled and deleted buckets, so it shouldn't be 
incremented when changing a deleted bucket into a filled bucket.
Feb 14 2020
parent reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Friday, 14 February 2020 at 23:19:31 UTC, Paul Backus wrote:

 On Friday, 14 February 2020 at 22:57:31 UTC, Ferhat Kurtulmuş 
 wrote:

 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?


 `used` counts both filled and deleted buckets, so it shouldn't 
 be incremented when changing a deleted bucket into a filled 
 bucket.


     İf ((aa.used + 1)* 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;
     else
         ++aa.used;
Feb 14 2020
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 2/14/20 6:36 PM, Ferhat Kurtulmuş wrote:

      İf ((aa.used + 1)* GROW_DEN > aa.dim * GROW_NUM)
          aa.grow(ti.key);


This call is expensive (it reallocates all the buckets and reinserts all 
the existing data into the new bucket), it should be avoided if in the 
end we will not be incrementing used.

-Steve
Feb 14 2020
parent reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Friday, 14 February 2020 at 23:41:45 UTC, Steven Schveighoffer 
wrote:

 On 2/14/20 6:36 PM, Ferhat Kurtulmuş wrote:

      İf ((aa.used + 1)* GROW_DEN > aa.dim * GROW_NUM)
          aa.grow(ti.key);


 This call is expensive (it reallocates all the buckets and 
 reinserts all the existing data into the new bucket), it should 
 be avoided if in the end we will not be incrementing used.

 -Steve


I am trying to write a gc-free AA based on the original runtime 
code (mem with malloc and free). My question is that why my 
version is slower (about 1.5 times slower) than the runtime 
version?

https://controlc.com/2e58c305

Those are some differences from runtime version:

- nogc and no typeid of course.
- does not care about postblit of key types (don't need it, 
assume only basic types are allowed for key type)
- runtime version uses typeid to do some alignments which are not 
implemented in my version. Is that the reason why my code is 
slower?
Feb 15 2020
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 2/15/20 6:49 AM, Ferhat Kurtulmuş wrote:

 On Friday, 14 February 2020 at 23:41:45 UTC, Steven Schveighoffer wrote:

 On 2/14/20 6:36 PM, Ferhat Kurtulmuş wrote:

      İf ((aa.used + 1)* GROW_DEN > aa.dim * GROW_NUM)
          aa.grow(ti.key);


 This call is expensive (it reallocates all the buckets and reinserts 
 all the existing data into the new bucket), it should be avoided if in 
 the end we will not be incrementing used.


 
 I am trying to write a gc-free AA based on the original runtime code 
 (mem with malloc and free). My question is that why my version is slower 
 (about 1.5 times slower) than the runtime version?


Have you ensured you are using -inline, -O, and -release? This is how 
druntime is compiled.


 https://controlc.com/2e58c305
 
 Those are some differences from runtime version:
 
 - nogc and no typeid of course.
 - does not care about postblit of key types (don't need it, assume only 
 basic types are allowed for key type)


Postblit should be automatic for your code because you are doing the 
types directly.


 - runtime version uses typeid to do some alignments which are not 
 implemented in my version. Is that the reason why my code is slower?


No, alignments are important only if you don't have the type, which you 
do. The runtime uses void pointers and opaque structs, so it has to 
duplicate what the compiler is already doing for you.

Your code looks like a direct port, except for the allocations, so it 
should be as fast if compiled the same. Your code might even be faster, 
because it's going to be able to inline more aggressively. There may be 
issues with cache coherency, but I'm not sure how to find or diagnoce those.

I'll note that you are going to leak some memory because you are not 
freeing deleted buckets when you resize. In the GC version, the GC takes 
care of those.

-Steve
Feb 15 2020
parent reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Saturday, 15 February 2020 at 14:30:20 UTC, Steven 
Schveighoffer wrote:

 On 2/15/20 6:49 AM, Ferhat Kurtulmuş wrote:

 On Friday, 14 February 2020 at 23:41:45 UTC, Steven





 I'll note that you are going to leak some memory because you 
 are not freeing deleted buckets when you resize. In the GC 
 version, the GC takes care of those.

 -Steve


I appreciate it for reviewing the code and your comments. Speed 
is good now. I put it on the dub db. I hope I am not violating 
any copyright. I included name of the original author (Martin 
Nowak) in the code, and explicitly stated that "betterC port of 
druntime/blob/master/src/rt/aaA.d".

What do you think about this one? I am not free-ing deleted entry 
in remove method:
https://github.com/aferust/bcaa/blob/a37b4ee4455477abc82425f32e9cf45394f4c4a1/source/bcaa.d#L228-L230

but here in resize:
https://github.com/aferust/bcaa/blob/a37b4ee4455477abc82425f32e9cf45394f4c4a1/source/bcaa.d#L190-L194

Thus, deleted buckets will wait until a resize call to free them. 
I think this is better for speed.
Feb 15 2020
next sibling parent Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Saturday, 15 February 2020 at 15:21:08 UTC, Ferhat Kurtulmuş 
wrote:

 On Saturday, 15 February 2020 at 14:30:20 UTC, Steven 
 Schveighoffer wrote:

 On 2/15/20 6:49 AM, Ferhat Kurtulmuş wrote:

 On Friday, 14 February 2020 at 23:41:45 UTC, Steven






Ops I ve made commits. Here are the links up to date
https://github.com/aferust/bcaa/blob/3f0f4eaf550a28b80cd95a4f2589b1f3a53fe6c0/source/bcaa.d#L193-L195

https://github.com/aferust/bcaa/blob/3f0f4eaf550a28b80cd95a4f2589b1f3a53fe6c0/source/bcaa.d#L231-L233
Feb 15 2020
prev sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 2/15/20 10:21 AM, Ferhat Kurtulmuş wrote:

 On Saturday, 15 February 2020 at 14:30:20 UTC, Steven Schveighoffer wrote:

 On 2/15/20 6:49 AM, Ferhat Kurtulmuş wrote:

 On Friday, 14 February 2020 at 23:41:45 UTC, Steven




 

 I'll note that you are going to leak some memory because you are not 
 freeing deleted buckets when you resize. In the GC version, the GC 
 takes care of those.


 
 I appreciate it for reviewing the code and your comments. Speed is good 
 now. I put it on the dub db. I hope I am not violating any copyright. I 
 included name of the original author (Martin Nowak) in the code, and 
 explicitly stated that "betterC port of druntime/blob/master/src/rt/aaA.d".
 
 What do you think about this one? I am not free-ing deleted entry in 
 remove method:
 https://github.com/aferust/bcaa/blob/a37b4ee4455477abc82425f32e9cf45394f4c4a1/sou
ce/bcaa.d#L228-L230 
 
 
 but here in resize:
 https://github.com/aferust/bcaa/blob/a37b4ee4455477abc82425f32e9cf45394f4c4a1/sou
ce/bcaa.d#L190-L194 


Yes, that is the moment they truly become garbage (in the GC version), 
so it's where you should free them.

-Steve
Feb 15 2020
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
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
Feb 14 2020
parent Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Friday, 14 February 2020 at 23:28:39 UTC, Steven Schveighoffer 
wrote:

 On 2/14/20 5:57 PM, Ferhat Kurtulmuş wrote:



 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


Thank you, I didn't know that.
Feb 14 2020