GC is very slow in the presence of weak hashtables

Bug #1241771 reported by Ilya Perminov
10
This bug affects 2 people
Affects Status Importance Assigned to Milestone
SBCL
Fix Released
Low
Unassigned

Bug Description

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.

Revision history for this message
Ilya Perminov (iperminov) wrote :
Revision history for this message
Paul Khuong (pvk) wrote :

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.

Changed in sbcl:
status: New → Triaged
importance: Undecided → Low
Revision history for this message
Ilya Perminov (iperminov) wrote :

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
}

Revision history for this message
Ilya Perminov (iperminov) wrote :

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;
    }

Revision history for this message
Ilya Perminov (iperminov) wrote :

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).

Revision history for this message
Stas Boukarev (stassats) wrote :

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

Revision history for this message
Ilya Perminov (iperminov) wrote :

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.

Revision history for this message
Stas Boukarev (stassats) wrote :

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. */

Revision history for this message
Stas Boukarev (stassats) wrote :

I made a slightly simplifed test.

Revision history for this message
Stas Boukarev (stassats) wrote :

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

Revision history for this message
Stas Boukarev (stassats) wrote :

Is fixed by 05726638c109c7c3b21c2c282451ac25a3e52538

Changed in sbcl:
status: Triaged → Fix Committed
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.