Changeset 13263


Ignore:
Timestamp:
Dec 8, 2009, 5:11:40 PM (10 years ago)
Author:
gz
Message:

Changes in handling of weak vectors (i.e. populations and weak hash vectors) in ephemeral gc. Depending on how these changes affect performance in different use cases, it might be necessary to make them user-configurable, but for now I just made them unconditional.

  • all populations (including in particular all terminable populations) are processed at every gc. In normal use, population data has newest conses at the front, and processing will terminate as soon as it reaches a cons not in the area being gc'd, so in practice this will only process cells actually added in the current generation, which should limit the performance impact on ephemeral gc.
  • all weak hash vectors that have keys in ephemeral areas are processed at every gc. (Unfortunately, that means weak-on-value hash tables are NOT processed during egc).
  • egc always uses the :non-circular weak processing method for hash vectors. This means that certain kinds of cross-references between weak keys and values in weak hash tables will keep objects from being collected during ephemeral gc.

Details:

  • when marking memoized area, collect weak any hash tables on GCweakvll
  • add new global WEAKVLL to store weak populations between gc's
  • keep the gc-link field in weak vectors untagged (i.e. tagged as a fixnum), and forward them manually after compacting the heap, so that can forward them correctly regardless of area they're in
  • save WEAKVLL when image is saved
  • always use weak method 1 in egc
Location:
branches/working-0711/ccl
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • branches/working-0711/ccl/compiler/X86/x86-arch.lisp

    r13070 r13263  
    7777    image-name                          ; current image name
    7878    initial-tcr                         ; initial thread's context record
     79    weakvll                             ; all populations as of last GC
    7980    ))
    8081
  • branches/working-0711/ccl/lisp-kernel/gc-common.c

    r13070 r13263  
    196196  if (terminatablep) {
    197197    deref(weakv,1+3) = termination_list;
    198     if (termination_list != lisp_nil) {
    199       deref(weakv,1) = GCweakvll;
    200       GCweakvll = weakv;
    201     }
     198  }
     199  if (termination_list != lisp_nil) {
     200    deref(weakv,1) = GCweakvll;
     201    GCweakvll = untag(weakv);
     202  } else {
     203    deref(weakv,1) = lisp_global(WEAKVLL);
     204    lisp_global(WEAKVLL) = untag(weakv);
    202205  }
    203206}
     
    256259  /* Do nothing, just add htabv to GCweakvll */
    257260  LispObj *base = (LispObj *) ptr_from_lispobj(untag(htabv));
    258  
    259   deref(base,1) = GCweakvll;
    260   GCweakvll = htabv;
     261
     262  base[1] = GCweakvll;
     263  GCweakvll = ptr_to_lispobj(base);
    261264}
    262265
     
    265268{
    266269  /* Do nothing, just add htabv to GCdwsweakvll */
     270  deref(htabv,1) = GCdwsweakvll;
     271  GCdwsweakvll = htabv;
     272}
     273
     274void
     275traditional_mark_weak_htabv(LispObj htabv)
     276{
     277  int i, skip = hash_table_vector_header_count;;
    267278  LispObj *base = (LispObj *) ptr_from_lispobj(untag(htabv));
    268  
    269   deref(base,1) = GCdwsweakvll;
    270   GCdwsweakvll = htabv;
    271 }
    272 
    273 void
    274 traditional_mark_weak_htabv(LispObj htabv)
    275 {
    276   int i, skip = hash_table_vector_header_count;;
    277279
    278280  for (i = 2; i <= skip; i++) {
    279     rmark(deref(htabv,i));
    280   }
    281 
    282   deref(htabv,1) = GCweakvll;
    283   GCweakvll = htabv;
     281    rmark(base[i]);
     282  }
     283  base[1] = GCweakvll;
     284  GCweakvll = ptr_to_lispobj(base);
    284285}
    285286
     
    309310    pairp += 2;
    310311  }
    311 
    312   deref(htabv,1) = GCweakvll;
    313   GCweakvll = htabv;
     312  deref(htabv,1)  = GCweakvll;
     313  GCweakvll = (LispObj)untag(htabv);
    314314}
    315315
     
    427427 
    428428void
     429mark_termination_lists()
     430{
     431  /*
     432     Mark the termination lists in all terminatable weak vectors, which
     433     are now linked together on GCweakvll, and add them to WEAKVLL,
     434     which already contains all other weak vectors.
     435  */
     436  LispObj pending = GCweakvll,
     437          *base = (LispObj *)NULL;
     438
     439  while (pending) {
     440    base = ptr_from_lispobj(pending);
     441    pending = base[1];
     442
     443    mark_root(base[1+3]);
     444  }
     445  if (base) {
     446    base[1] = lisp_global(WEAKVLL);
     447    lisp_global(WEAKVLL) = GCweakvll;
     448  }
     449
     450}
     451
     452
     453void
    429454traditional_markhtabvs()
    430455{
    431   LispObj this, header, pending;
     456  LispObj *base, this, header, pending;
    432457  int subtag;
    433458  hash_table_vector_header *hashp;
     
    439464   
    440465    while (GCweakvll) {
    441       this = GCweakvll;
    442       GCweakvll = deref(this,1);
     466      base = ptr_from_lispobj(GCweakvll);
     467      GCweakvll = base[1];
    443468     
    444       header = header_of(this);
     469      header = base[0];
    445470      subtag = header_subtag(header);
    446471     
    447472      if (subtag == subtag_weak) {
    448         natural weak_type = deref(this,2);
    449         deref(this,1) = pending;
    450         pending = this;
     473        natural weak_type = base[2];
     474        this = ptr_to_lispobj(base) + fulltag_misc;
     475        base[1] = pending;
     476        pending = ptr_to_lispobj(base);
    451477        if ((weak_type & population_type_mask) == population_weak_alist) {
    452478          if (mark_weak_alist(this, weak_type)) {
     
    457483        natural elements = header_element_count(header);
    458484
    459         hashp = (hash_table_vector_header *) ptr_from_lispobj(untag(this));
     485        hashp = (hash_table_vector_header *) base;
    460486        if (hashp->flags & nhash_weak_mask) {
    461           deref(this,1) = pending;
    462           pending = this;
     487          base[1] = pending;
     488          pending = ptr_to_lispobj(base);
    463489          if (mark_weak_hash_vector(hashp, elements)) {
    464490            marked_new = true;
     
    466492        }
    467493      } else {
    468         Bug(NULL, "Strange object on weak vector linked list: 0x~08x\n", this);
     494        Bug(NULL, "Strange object on weak vector linked list: " LISP "\n", base);
    469495      }
    470496    }
     
    481507
    482508  while (pending) {
    483     this = pending;
    484     pending = deref(this,1);
    485     deref(this,1) = (LispObj)NULL;
    486 
    487     subtag = header_subtag(header_of(this));
     509    base = ptr_from_lispobj(pending);
     510    pending = base[1];
     511    base[1] = (LispObj)NULL;
     512
     513    this = ptr_to_lispobj(base) + fulltag_misc;
     514
     515    subtag = header_subtag(base[0]);
    488516    if (subtag == subtag_weak) {
    489517      reapweakv(this);
     
    492520    }
    493521  }
    494 
    495   /* Finally, mark the termination lists in all terminatable weak vectors
    496      They are now linked together on GCweakvll.
    497      This is where to store  lisp_global(TERMINATION_LIST) if we decide to do that,
    498      but it will force terminatable popualations to hold on to each other
    499      (set TERMINATION_LIST before clearing GCweakvll, and don't clear deref(this,1)).
    500      */
    501   pending = GCweakvll;
    502   GCweakvll = (LispObj)NULL;
    503   while (pending) {
    504     this = pending;
    505     pending = deref(this,1);
    506     deref(this,1) = (LispObj)NULL;
    507     mark_root(deref(this,1+3));
    508   }
     522  mark_termination_lists();
    509523}
    510524
     
    512526ncircle_markhtabvs()
    513527{
    514   LispObj this, header, pending = 0;
     528  LispObj *base, this, header, pending = 0;
    515529  int subtag;
    516   Boolean marked_new;
    517530
    518531  /* First, process any weak hash tables that may have
     
    527540
    528541  while (GCweakvll) {
    529     this = GCweakvll;
    530     GCweakvll = deref(this,1);
    531      
    532     header = header_of(this);
     542    base = ptr_from_lispobj(GCweakvll);
     543    GCweakvll = base[1];
     544    base[1] = (LispObj)NULL;
     545
     546    this = ptr_to_lispobj(base) + fulltag_misc;
     547
     548    header = base[0];
    533549    subtag = header_subtag(header);
    534550     
    535551    if (subtag == subtag_weak) {
    536       natural weak_type = deref(this,2);
    537       deref(this,1) = pending;
    538       pending = this;
     552      natural weak_type = base[2];
     553      base[1] = pending;
     554      pending = ptr_to_lispobj(base);
    539555      if ((weak_type & population_type_mask) == population_weak_alist) {
    540         if (mark_weak_alist(this, weak_type)) {
    541           marked_new = true;
    542           }
     556        mark_weak_alist(this, weak_type);
    543557      }
    544558    } else if (subtag == subtag_hash_vector) {
     
    553567
    554568  while (pending) {
    555     this = pending;
    556     pending = deref(this,1);
    557     deref(this,1) = (LispObj)NULL;
    558 
    559     subtag = header_subtag(header_of(this));
     569    base = ptr_from_lispobj(pending);
     570    pending = base[1];
     571    base[1] = (LispObj)NULL;
     572
     573    this = ptr_to_lispobj(base) + fulltag_misc;
     574
     575    subtag = header_subtag(base[0]);
    560576    if (subtag == subtag_weak) {
    561577      reapweakv(this);
     
    565581  }
    566582
    567   /* Finally, mark the termination lists in all terminatable weak vectors
    568      They are now linked together on GCweakvll.
    569      This is where to store  lisp_global(TERMINATION_LIST) if we decide to do that,
    570      but it will force terminatable popualations to hold on to each other
    571      (set TERMINATION_LIST before clearing GCweakvll, and don't clear deref(this,1)).
    572      */
    573   pending = GCweakvll;
    574   GCweakvll = (LispObj)NULL;
    575   while (pending) {
    576     this = pending;
    577     pending = deref(this,1);
    578     deref(this,1) = (LispObj)NULL;
    579     mark_root(deref(this,1+3));
    580   }
     583  mark_termination_lists();
    581584}
    582585
     
    915918
    916919void
     920forward_weakvll()
     921{
     922  LispObj *ptr = &(lisp_global(WEAKVLL)), this, new, old;
     923
     924  while (this = *ptr) {
     925    old = this + fulltag_misc;
     926    new = node_forwarding_address(old);
     927    if (old != new) {
     928      *ptr = untag(new);
     929    }
     930    ptr = &(deref(new,1));
     931  }
     932}
     933
     934
     935void
    917936forward_memoized_area(area *a, natural num_memo_dnodes)
    918937{
     
    11001119  TCR *other_tcr;
    11011120  natural static_dnodes;
    1102 
    1103   install_weak_mark_functions(lisp_global(WEAK_GC_METHOD) >> fixnumshift);
    1104  
     1121  natural weak_method = lisp_global(WEAK_GC_METHOD) >> fixnumshift;
     1122
    11051123#ifndef FORCE_DWS_MARK
    11061124  if ((natural) (tcr->cs_limit) == CS_OVERFLOW_FORCE_LIMIT) {
     
    11271145
    11281146  if (GCephemeral_low) {
     1147    weak_method = 1;   /* egc, so use faster algorithm */
    11291148    if ((oldfree-g1_area->low) < g1_area->threshold) {
    11301149      to = g1_area;
     
    11461165  }
    11471166
     1167  install_weak_mark_functions(weak_method);
     1168 
    11481169  if (GCverbose) {
    11491170    char buf[16];
     
    11941215    zero_bits(GCmarkbits, GCndnodes_in_area);
    11951216    GCweakvll = (LispObj)NULL;
     1217
     1218    if (GCn_ephemeral_dnodes) {
     1219      /* For egc case, initialize GCweakvll with populations not in the
     1220         GC area.  Weak hash vectors, and populations in the GC area,
     1221         will be added during marking.
     1222      */
     1223      LispObj this = lisp_global(WEAKVLL); /* all populations as of last gc */
     1224      while (this) {
     1225        LispObj *base = ptr_from_lispobj(this);
     1226        LispObj next = base[1];
     1227        natural dnode = gc_dynamic_area_dnode(this);
     1228        if (dnode >= GCndynamic_dnodes_in_area) {
     1229          base[1] = GCweakvll;
     1230          GCweakvll = ptr_to_lispobj(base);
     1231        }
     1232        else {
     1233          base[1] = (LispObj)NULL;
     1234        }
     1235        this = next;
     1236      }
     1237    }
     1238    lisp_global(WEAKVLL) = (LispObj)NULL;
     1239
    11961240
    11971241    if (GCn_ephemeral_dnodes == 0) {
     
    12581302    }
    12591303 
    1260     if (lisp_global(OLDEST_EPHEMERAL)) {
     1304    if (GCephemeral_low) {
    12611305      mark_memoized_area(tenured_area, area_dnode(a->low,tenured_area->low));
    12621306    }
     
    13951439 
    13961440    a->active = (BytePtr) ptr_from_lispobj(compact_dynamic_heap());
     1441
     1442    forward_weakvll();
     1443
    13971444    if (to) {
    13981445      tenure_to_area(to);
  • branches/working-0711/ccl/lisp-kernel/image.c

    r13188 r13263  
    8080      }
    8181#endif
    82 
     82      if (header_subtag(w0) == subtag_weak) {
     83        LispObj link = start[1];
     84        if ((link >= low) && (link < high)) {
     85          start[1] = (link+bias);
     86        }
     87      }
    8388      if ((w0 >= low) && (w0 < high) &&
    8489          ((1<<fulltag) & RELOCATABLE_FULLTAG_MASK)) {
     
    493498    case G2_THRESHOLD:
    494499      break;
     500    case WEAKVLL:
     501      break;
    495502    default:
    496503      lisp_global(i) = 0;
  • branches/working-0711/ccl/lisp-kernel/lisp_globals.h

    r13070 r13263  
    7070#define IMAGE_NAME (-47)        /* --image-name arg */
    7171#define INITIAL_TCR (-48)       /* initial thread tcr */
     72#define WEAKVLL (-49)           /* all populations as of last GC */
    7273
    73 #define MIN_KERNEL_GLOBAL INITIAL_TCR
     74#define MIN_KERNEL_GLOBAL WEAKVLL
    7475
    7576/* These are only non-zero when an image is being saved or loaded */
  • branches/working-0711/ccl/lisp-kernel/ppc-constants.s

    r13070 r13263  
    184184])
    185185
    186 num_lisp_globals = 48            /* MUST UPDATE THIS !!! */
     186num_lisp_globals = 49            /* MUST UPDATE THIS !!! */
    187187       
    188188        _struct(lisp_globals,lisp_globals_limit-(num_lisp_globals*node_size))
     189         _node(weakvll)                 /* all populations as of last GC */
    189190         _node(initial_tcr)             /* initial thread tcr */
    190191         _node(image_name)              /* --image-name argument */
  • branches/working-0711/ccl/lisp-kernel/ppc-gc.c

    r13070 r13263  
    329329      }
    330330      if (subtag == subtag_weak) {
    331         deref(ptr_to_lispobj(base),1) = GCweakvll;
    332         GCweakvll = n;
     331        deref(n, 1) = GCweakvll;
     332        GCweakvll = untag(n);
    333333      }
    334334    }
     
    606606      if (subtag == subtag_weak) {
    607607        deref(n, 1) = GCweakvll;
    608         GCweakvll = n;
     608        GCweakvll = untag(n);
    609609      }
    610610
     
    798798    if (header_subtag(next) == subtag_weak) {
    799799      deref(this, 1) = GCweakvll;
    800       GCweakvll = this;
     800      GCweakvll = untag(this);
    801801    }
    802802    goto Climb;
     
    963963      x2 = *p++;
    964964      bits &= ~(BIT0_MASK >> bitidx);
     965
     966      if (header_subtag(x1) == subtag_hash_vector) {
     967        LispObj flags = ((hash_table_vector_header *) p-2)->flags;
     968        if (flags & nhash_weak_mask) {
     969          *(p-1) = GCweakvll;
     970          GCweakvll = ptr_to_lispobj(p - 1);
     971          x2 = 0;
     972        }
     973      }
     974
    965975      keep_x1 = mark_ephemeral_root(x1);
    966976      keep_x2 = mark_ephemeral_root(x2);
     
    10221032          element_count -= 1;
    10231033        start[1] = GCweakvll;
    1024         GCweakvll = (LispObj) (((natural) start) + fulltag_misc);   
     1034        GCweakvll = ptr_to_lispobj(start);
    10251035      }
    10261036
  • branches/working-0711/ccl/lisp-kernel/x86-constants.s

    r13070 r13263  
    6666define([seen_aok_bit],[28])       
    6767       
    68 num_lisp_globals = 48            /* MUST UPDATE THIS !!!   */
     68num_lisp_globals = 49            /* MUST UPDATE THIS !!!   */
    6969       
    7070        _struct(lisp_globals,lisp_globals_limit-(num_lisp_globals*node_size))
     71         _node(weakvll)                 /* all populations as of last GC */
    7172         _node(initial_tcr)             /* initial thread tcr */
    7273         _node(image_name)              /* --image-name argument */
  • branches/working-0711/ccl/lisp-kernel/x86-gc.c

    r13188 r13263  
    390390
    391391/* Sooner or later, this probably wants to be in assembler */
    392 /* Return false if n is definitely not an ephemeral node, true if
    393    it might be */
    394392void
    395393mark_root(LispObj n)
     
    530528
    531529      if (subtag == subtag_pool) {
    532         deref(base, 1) = lisp_nil;
     530        deref(n, 1) = lisp_nil;
    533531      }
    534532     
     
    564562      }
    565563      if (subtag == subtag_weak) {
    566         deref(ptr_to_lispobj(base),1) = GCweakvll;
    567         GCweakvll = n;
     564        deref(n, 1) = GCweakvll;
     565        GCweakvll = untag(n);
    568566      }
    569567    }
     
    774772      if (subtag == subtag_weak) {
    775773        deref(n, 1) = GCweakvll;
    776         GCweakvll = n;
     774        GCweakvll = untag(n);
    777775      }
    778776
     
    10971095    if (header_subtag(next) == subtag_weak) {
    10981096      deref(this, 1) = GCweakvll;
    1099       GCweakvll = this;
     1097      GCweakvll = untag(this);
    11001098    }
    11011099    goto Climb;
     
    12871285      x2 = *p++;
    12881286      bits &= ~(BIT0_MASK >> bitidx);
     1287
     1288      if (header_subtag(x1) == subtag_hash_vector) {
     1289        LispObj flags = ((hash_table_vector_header *) p-2)->flags;
     1290        if (flags & nhash_weak_mask) {
     1291          *(p-1) = GCweakvll;
     1292          GCweakvll = ptr_to_lispobj(p - 2);
     1293          x2 = 0;
     1294        }
     1295      }
     1296
    12891297      keep_x1 = mark_ephemeral_root(x1);
    12901298      keep_x2 = mark_ephemeral_root(x2);
     
    13521360          element_count -= 1;
    13531361        start[1] = GCweakvll;
    1354         GCweakvll = (LispObj) (((natural) start) + fulltag_misc);   
     1362        GCweakvll = ptr_to_lispobj(start);
    13551363      }
    13561364
Note: See TracChangeset for help on using the changeset viewer.