SumiTomohikoのWiki

• howmuch:

• ocaml-3.11.0/byterun/major_gc.c

/* The main entry point for the GC.  Called after each minor GC.
   [howmuch] is the amount of work to do, 0 to let the GC compute it.
   Return the computed amount of work to do.
 */

GCのメインのエントリポイント。各マイナーGCの後で呼び出される。howmuchは、処理量で、0だとGCが処理量を計算する。計算された処理量を返す。

intnat caml_major_collection_slice (intnat howmuch)

• ocaml-3.11.0/intnat

{
  double p, dp;
  intnat computed_work;
  /*
     Free memory at the start of the GC cycle (garbage + free list) (assumed):
                 FM = caml_stat_heap_size * caml_percent_free
                      / (100 + caml_percent_free)

     Assuming steady state and enforcing a constant allocation rate, then
     FM is divided in 2/3 for garbage and 1/3 for free list.
                 G = 2 * FM / 3
     G is also the amount of memory that will be used during this cycle
     (still assuming steady state).

     Proportion of G consumed since the previous slice:
                 PH = caml_allocated_words / G
                    = caml_allocated_words * 3 * (100 + caml_percent_free)
                      / (2 * caml_stat_heap_size * caml_percent_free)
     Proportion of extra-heap resources consumed since the previous slice:
                 PE = caml_extra_heap_resources
     Proportion of total work to do in this slice:
                 P  = max (PH, PE)
     Amount of marking work for the GC cycle:
                 MW = caml_stat_heap_size * 100 / (100 + caml_percent_free)
     Amount of sweeping work for the GC cycle:
                 SW = caml_stat_heap_size

     In order to finish marking with a non-empty free list, we will
     use 40% of the time for marking, and 60% for sweeping.

     If TW is the total work for this cycle,
                 MW = 40/100 * TW
                 SW = 60/100 * TW

     Amount of work to do for this slice:
                 W  = P * TW

     Amount of marking work for a marking slice:
                 MS = P * MW / (40/100)
                 MS = P * caml_stat_heap_size * 250 / (100 + caml_percent_free)
     Amount of sweeping work for a sweeping slice:
                 SS = P * SW / (60/100)
                 SS = P * caml_stat_heap_size * 5 / 3

     This slice will either mark MS words or sweep SS words.
  */

• ocaml-3.11.0/caml_stat_heap_size
• ocaml-3.11.0/caml_percent_free
• ocaml-3.11.0/caml_allocated_words
• ocaml-3.11.0/caml_extra_heap_resources

GCサイクルの開始時における空きメモリ（ゴミとフリーリスト）（仮定）:

FM = caml_stat_heap_size * caml_percent_free / (100 + caml_percent_free)

定常状態であり、一定量ずつ確保し続けていると仮定すると、FMの2/3はゴミであり、1/3はフリーリストとなる:

G = 2 * FM / 3

Gはまた、このサイクル中で使用されるメモリの量である（このときも定常状態を仮定する）。

前のスライスから消費したGの割合は:

PH = caml_allocated_words / G
   = caml_allocated_words * 3 * (100 + caml_percent_free) / (2 * caml_stat_heap_size * caml_percent_free)

前回のスライスから消費したヒープ外のリソースの割合は:

PE = caml_extra_heap_resources

このスライスで実行する処理量は:

P = max (PH, PE)

このGCのサイクルで行うマークの処理量は:

MW = caml_stat_heap_size * 100 / (100 + caml_percent_free)

このGCのサイクルで行うスイープの処理量は:

SW = caml_stat_heap_size

空ではないフリーリストにおいて、マーキングを終了させるためには、40%の時間を使い、60%をスイープに使う。

TWをこのサイクルでの総処理量とすると:

MW = 40 / 100 * TW
SW = 60 / 100 * TW

このスライスでする処理量は:

W = P * TW

マーキングスライスにおけるマーキング量は:

MS = P * MW / (40 / 100)
MS = P * caml_stat_heap_size * 250 / (100 + caml_percent_free)

スイーピングスライスにおけるスイープの処理量は:

SS = P * SW / (60 / 100)
SS = P * caml_stat_heap_size * 5 / 3

このスライスでは、MSワードをマークするか、SSワードをスイープする。

  if (caml_gc_phase == Phase_idle) start_cycle ();

• ocaml-3.11.0/caml_gc_phase
• ocaml-3.11.0/Phase_idle
• ocaml-3.11.0/start_cycle

  p = (double) caml_allocated_words * 3.0 * (100 + caml_percent_free)
      / Wsize_bsize (caml_stat_heap_size) / caml_percent_free / 2.0;

• ocaml-3.11.0/Wsize_bsize

  if (caml_dependent_size > 0){

• ocaml-3.11.0/caml_dependent_size

    dp = (double) caml_dependent_allocated * (100 + caml_percent_free)
         / caml_dependent_size / caml_percent_free;

• ocaml-3.11.0/caml_dependent_allocated

  }else{
    dp = 0.0;
  }
  if (p < dp) p = dp;
  if (p < caml_extra_heap_resources) p = caml_extra_heap_resources;

  caml_gc_message (0x40, "allocated_words = %"
                         ARCH_INTNAT_PRINTF_FORMAT "u\n",
                   caml_allocated_words);
  caml_gc_message (0x40, "extra_heap_resources = %"
                         ARCH_INTNAT_PRINTF_FORMAT "uu\n",
                   (uintnat) (caml_extra_heap_resources * 1000000));
  caml_gc_message (0x40, "amount of work to do = %"
                         ARCH_INTNAT_PRINTF_FORMAT "uu\n",
                   (uintnat) (p * 1000000));

  if (caml_gc_phase == Phase_mark){

• ocaml-3.11.0/Phase_mark

    computed_work = (intnat) (p * Wsize_bsize (caml_stat_heap_size) * 250
                              / (100 + caml_percent_free));
  }else{
    computed_work = (intnat) (p * Wsize_bsize (caml_stat_heap_size) * 5 / 3);
  }
  caml_gc_message (0x40, "ordered work = %ld words\n", howmuch);
  caml_gc_message (0x40, "computed work = %ld words\n", computed_work);
  if (howmuch == 0) howmuch = computed_work;
  if (caml_gc_phase == Phase_mark){
    mark_slice (howmuch);

• ocaml-3.11.0/mark_slice

    caml_gc_message (0x02, "!", 0);
  }else{
    Assert (caml_gc_phase == Phase_sweep);
    sweep_slice (howmuch);

• ocaml-3.11.0/sweep_slice

    caml_gc_message (0x02, "$", 0);
  }

  if (caml_gc_phase == Phase_idle) caml_compact_heap_maybe ();

• ocaml-3.11.0/caml_compact_heap_maybe

  caml_stat_major_words += caml_allocated_words;

• ocaml-3.11.0/caml_stat_major_words

  caml_allocated_words = 0;
  caml_dependent_allocated = 0;
  caml_extra_heap_resources = 0.0;
  return computed_work;
}