GC is very slow in the presence of weak hashtables

[Ilya Perminov]

Weak hashtables severely affect GC performance.
In my test, GC time goes from 100ms to 20s, after creating a
reasonably large hashtable.
Tested using SBCL 1.1.12, Linux x86_64.

[Paul Khuong (pvk)]

Pretty much all the support for weak references in SBCL has mediocre to bad asymptotics. Bruno Haible's write-up (http://www.haible.de/bruno/papers/cs/weak/WeakDatastructures-writeup.html) describes interesting and practical improvements. Sadly, no one has had the time and energy to code them up yet.

[Ilya Perminov (iperminov)]

The problem is in scavenge_newspace_generation in gencgc.c: the function calls scav_weak_hash_tables after
scavenging every set of new areas, i.e. scav_weak_hash_tables is called O(heap_size) times in the worst case.
It seems there is an easy way to reduce GC time - to move scavenging of weak hash tables out from the loop that
scavenge normal data (though it is the first time I'm looking at the SBCL GC, so I can be completely wrong). In pseudo code:
The current logic:
while (changes) {
    scavenge normal data
    scavenge weak hash tables
}

The new logic:
while (changes) {
   while (changes) {
       scavenge normal data
   }
   scavenge weak hash tables
}

[Ilya Perminov (iperminov)]

Here is a patch that implements the change I described. It is much smaller than it looks. I just removed calls of
scav_weak_hash_tables from the loop ("while (current_new_areas_index > 0)") and wrapped the loop with

    while (current_new_areas_index > 0) {

        **** original loop is here ****

        scav_weak_hash_tables();

        /* Flush the current regions updating the tables. */
        gc_alloc_update_all_page_tables();

        current_new_areas_index = new_areas_index;
    }

[Ilya Perminov (iperminov)]

Acctually, the comment in gencgc.c, which mentions Bruno Haible's write-up, seems to be too optimistic.
Currently cost of weak hash table GCing is O(W^2*N), not O(W^2+N).

[Stas Boukarev (stassats)]

What I noticed is that if you remove (defparameter *data* (make-tree 10000)), it's as fast as normal hashtables.

[Ilya Perminov (iperminov)]

Yes, the size of *data* affects GC time, because the part of GC time related to weak hash tables depends on the total heap size, and that is the problem.

[Stas Boukarev (stassats)]

And this seems to only happen with conses which are linked through CAR, and not CDR. And trans_list says
/* Try to linearize the list in the cdr direction to help reduce paging. */

[Stas Boukarev (stassats)]

I made a slightly simplifed test.

[Stas Boukarev (stassats)]

And timings are:
  0.010 seconds of real time
  0.012000 seconds of total run time (0.012000 user, 0.000000 system)
  [ Run times consist of 0.012 seconds GC time, and 0.000 seconds non-GC time. ]
  120.00% CPU
  37,382,102 processor cycles
  0 bytes consed

Evaluation took:
  0.903 seconds of real time
  0.904000 seconds of total run time (0.904000 user, 0.000000 system)
  [ Run times consist of 0.904 seconds GC time, and 0.000 seconds non-GC time. ]
  100.11% CPU
  3,152,752,809 processor cycles
  0 bytes consed

[Stas Boukarev (stassats)]

Is fixed by 05726638c109c7c3b21c2c282451ac25a3e52538