Changeset 13294


Ignore:
Timestamp:
Dec 15, 2009, 1:48:05 AM (10 years ago)
Author:
gz
Message:

Use refbits in mark_weak_hash_vector and reaphashv to avoid paging in uninteresting parts of tenured weak hash vectors.
Also arrange so tenured weak-on-value hash tables are processed, not just weak-on-key.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/working-0711/ccl/lisp-kernel/gc-common.c

    r13293 r13294  
    216216    *hashp = (hash_table_vector_header *) ptr_from_lispobj(untag(hashv));
    217217  natural
    218     dnode,
     218    dnode;
     219  signed_natural
    219220    npairs = (header_element_count(hashp->header) -
    220221              (hash_table_vector_header_count -1)) >> 1;
    221222  LispObj *pairp = (LispObj*) (hashp+1), weakelement;
    222   Boolean
    223     weak_on_value = ((hashp->flags & nhash_weak_value_mask) != 0);
     223  int weak_index = (((hashp->flags & nhash_weak_value_mask) == 0) ? 0 : 1);
    224224  Boolean
    225225    keys_frozen = ((hashp->flags & nhash_keys_frozen_mask) != 0);
     
    227227  int tag;
    228228
    229   /* TODO: hashv might be in old space, in which case should use refbits
    230      rather than touching all entries
    231   */
    232 
    233   while (npairs--) {
    234     if (weak_on_value) {
    235       weakelement = pairp[1];
    236     } else {
    237       weakelement = pairp[0];
    238     }
     229  natural *tenured_low = (LispObj *)tenured_area->low;
     230  natural tenured_dnodes = area_dnode(GCarealow, tenured_low);
     231  natural memo_dnode = area_dnode(ptr_to_lispobj(pairp+weak_index), tenured_low);
     232  Boolean
     233    hashv_tenured = (memo_dnode < tenured_dnodes);
     234  natural bits, bitidx, *bitsp;
     235
     236  if (hashv_tenured) {
     237    set_bitidx_vars(tenured_area->refbits, memo_dnode, bitsp, bits, bitidx);
     238  }
     239
     240  while (true) {
     241    if (hashv_tenured) {
     242      while (bits == 0) {
     243        int skip = nbits_in_word - bitidx;
     244        npairs -= skip;
     245        if (npairs <= 0) break;
     246        pairp += (skip+skip);
     247        bitidx = 0;
     248        bits = *++bitsp;
     249      }
     250      if (bits != 0) {
     251        int skip = (count_leading_zeros(bits) - bitidx);
     252        if (skip != 0) {
     253          npairs -= skip;
     254          pairp += (skip+skip);
     255          bitidx += skip;
     256        }
     257      }
     258    }
     259
     260    if (npairs <= 0) break;
     261
     262    weakelement = pairp[weak_index];
    239263    tag = fulltag_of(weakelement);
    240264    if (is_node_fulltag(tag)) {
     
    255279    }
    256280    pairp += 2;
     281    --npairs;
    257282  }
    258283  deref(hashv, 1) = lisp_global(WEAKVLL);
     
    324349mark_weak_hash_vector(hash_table_vector_header *hashp, natural elements)
    325350{
    326   natural flags = hashp->flags, key_dnode, val_dnode;
     351  natural flags = hashp->flags, weak_dnode, nonweak_dnode;
    327352  Boolean
    328353    marked_new = false,
    329     key_marked,
    330     val_marked,
    331     weak_value = ((flags & nhash_weak_value_mask) != 0);
     354    weak_marked;
     355  int non_weak_index = (((flags & nhash_weak_value_mask) != 0) ? 0 : 1);
    332356  int
    333357    skip = hash_table_vector_header_count-1,
    334     key_tag,
    335     val_tag,
     358    weak_tag,
     359    nonweak_tag,
    336360    i;
     361  signed_natural
     362    npairs = (elements - skip) >> 1;
    337363  LispObj
    338364    *pairp = (LispObj*) (hashp+1),
    339     key,
    340     val;
     365    weak,
     366    nonweak;
     367
     368  natural *tenured_low = (LispObj *)tenured_area->low;
     369  natural tenured_dnodes = area_dnode(GCarealow, tenured_low);
     370  natural memo_dnode = area_dnode(ptr_to_lispobj(pairp+non_weak_index), tenured_low);
     371  Boolean hashv_tenured = (memo_dnode < tenured_dnodes);
     372  natural bits, bitidx, *bitsp;
     373
     374  if (hashv_tenured) {
     375    set_bitidx_vars(tenured_area->refbits, memo_dnode, bitsp, bits, bitidx);
     376  }
    341377
    342378  /* Mark everything in the header */
     
    346382  }
    347383
    348   elements -= skip;
    349 
    350   /* TODO: the hash table might be in old space, in which case should use refbits
    351      rather than touching all entries
    352   */
    353 
    354   for (i = 0; i<elements; i+=2, pairp+=2) {
    355     key = pairp[0];
    356     val = pairp[1];
    357     key_marked = val_marked = true;
    358     key_tag = fulltag_of(key);
    359     val_tag = fulltag_of(val);
    360     if (is_node_fulltag(key_tag)) {
    361       key_dnode = gc_area_dnode(key);
    362       if ((key_dnode < GCndnodes_in_area) &&
    363           ! ref_bit(GCmarkbits,key_dnode)) {
    364         key_marked = false;
    365       }
    366     }
    367     if (is_node_fulltag(val_tag)) {
    368       val_dnode = gc_area_dnode(val);
    369       if ((val_dnode < GCndnodes_in_area) &&
    370           ! ref_bit(GCmarkbits,val_dnode)) {
    371         val_marked = false;
    372       }
    373     }
    374 
    375     if (weak_value) {
    376       if (val_marked & !key_marked) {
    377         mark_root(key);
    378         marked_new = true;
    379       }
    380     } else {
    381       if (key_marked & !val_marked) {
    382         mark_root(val);
    383         marked_new = true;
    384       }
    385     }
     384  while (true) {
     385    if (hashv_tenured) {
     386      while (bits == 0) {
     387        int skip = nbits_in_word - bitidx;
     388        npairs -= skip;
     389        if (npairs <= 0) break;
     390        pairp += (skip+skip);
     391        bitidx = 0;
     392        bits = *++bitsp;
     393      }
     394      if (bits != 0) {
     395        int skip = count_leading_zeros(bits) - bitidx;
     396        if (skip != 0) {
     397          npairs -= skip;
     398          pairp += (skip+skip);
     399          bitidx += skip;
     400        }
     401      }
     402    }
     403    if (npairs <= 0) break;
     404
     405    nonweak = pairp[non_weak_index];
     406    weak = pairp[1-non_weak_index];
     407
     408    nonweak_tag = fulltag_of(nonweak);
     409    if (is_node_fulltag(nonweak_tag)) {
     410      nonweak_dnode = gc_area_dnode(nonweak);
     411      if ((nonweak_dnode < GCndnodes_in_area) &&
     412          ! ref_bit(GCmarkbits,nonweak_dnode)) {
     413        weak_marked = true;
     414        weak_tag = fulltag_of(weak);
     415        if (is_node_fulltag(weak_tag)) {
     416          weak_dnode = gc_area_dnode(weak);
     417          if ((weak_dnode < GCndnodes_in_area) &&
     418              ! ref_bit(GCmarkbits, weak_dnode)) {
     419            weak_marked = false;
     420          }
     421        }
     422        if (weak_marked) {
     423          mark_root(nonweak);
     424          marked_new = true;
     425        }
     426      }
     427    }
     428
     429    pairp+=2;
     430    --npairs;
    386431  }
    387432  return marked_new;
     
    862907init_weakvll ()
    863908{
     909  LispObj this = lisp_global(WEAKVLL); /* all weak vectors as of last gc */
     910
    864911  GCweakvll = (LispObj)NULL;
     912  lisp_global(WEAKVLL) = (LispObj)NULL;
    865913
    866914  if (GCn_ephemeral_dnodes) {
     
    868916       GC area.  Weak vectors in the GC area will be added during marking.
    869917    */
    870     LispObj this = lisp_global(WEAKVLL); /* all weak vectors as of last gc */
     918
    871919    LispObj *tenured_low = (LispObj *)tenured_area->low;
    872920    natural tenured_dnodes = area_dnode(GCarealow, tenured_low);
     
    890938          if (header_subtag(base[0]) != subtag_hash_vector)
    891939            Bug(NULL, "Unexpected entry " LISP " -> " LISP " on WEAKVLL", base, base[0]);
    892           /* hash vectors are already singled out for special processing if they */
    893           /* have any ephemeral keys, but not if they have ephemeral values. */
    894           if (((hash_table_vector_header *)base)->flags & nhash_weak_value_mask) {
    895             dnode = area_dnode(&base[0], tenured_low);
    896             if (dnode < tenured_dnodes) {
    897               set_bit(refbits, dnode); /* need to look at it anyway */
     940          dnode = area_dnode(base, tenured_low);
     941          if ((dnode < tenured_dnodes) && !ref_bit(refbits, dnode)) {
     942            Boolean drop = true;
     943            /* hash vectors get marked headers if they have any ephemeral keys */
     944            /* but not if they have ephemeral values. */
     945            if (((hash_table_vector_header *)base)->flags & nhash_weak_value_mask) {
     946              signed_natural count = (header_element_count(base[0]) + 2) >> 1;
     947              natural bits, bitidx, *bitsp;
     948              set_bitidx_vars(refbits, dnode, bitsp, bits, bitidx);
     949              while ((0 < count) && (bits == 0)) {
     950                int skip = nbits_in_word - bitidx;
     951                count -= skip;
     952                bits = *++bitsp;
     953                bitidx = 0;
     954              }
     955              count -=  (count_leading_zeros(bits) - bitidx);
     956
     957              if (0 < count) {
     958                set_bit(refbits, dnode); /* has ephemeral values, mark header */
     959                drop = false;
     960              }
    898961            }
     962            if (drop) { /* if nothing ephemeral, drop it from GCweakvll. */
     963              GCweakvll = base[1];
     964              base[1] = lisp_global(WEAKVLL);
     965              lisp_global(WEAKVLL) = ptr_to_lispobj(base);
     966            }
    899967          }
    900968        }
     
    903971    }
    904972  }
    905   lisp_global(WEAKVLL) = (LispObj)NULL;
    906973}
    907974
Note: See TracChangeset for help on using the changeset viewer.