Как запланировать циклы сбора для пользовательского сборщика меток? - PullRequest
Новая
       41

Как запланировать циклы сбора для пользовательского сборщика меток?

4 голосов
/ 16 июня 2011

Я написал простой сборщик мусора для виртуальной машины Postscript, и у меня возникают трудности при разработке достойного набора правил для того, когда делать коллекцию (когда свободный список слишком короткий?) И когда выделять новыепробел (когда много места для использования?).

Я уже писал снизу вверх, но этот вопрос касается дизайна верхнего уровня.Поэтому я чувствую, что нахожусь в шаткой земле.Все объекты управляются, и доступ осуществляется только через операторские функции, поэтому это коллектор в C, а не для C.

Основная функция распределителя называется gballoc: 

unsigned gballoc(mfile *mem, unsigned sz) {
    unsigned z = adrent(mem, FREE);
    unsigned e;
    memcpy(&e, mem->base+z, sizeof(e));
    while (e) {
        if (szent(mem,e) >= sz) {
            memcpy(mem->base+z, mem->base+adrent(mem,e), sizeof(unsigned));
            return e;
        }
        z = adrent(mem,e);
        memcpy(&e, mem->base+z, sizeof(e));
    }
    return mtalloc(mem, 0, sz);
}

Я уверен, что это бессмысленно, не зная, что означают все типы и функции, поэтому вот псевдокод той же функции: 

gballoc
    load free list head into ptr
    while ptr is not NULL
        if free element size is large enough
            return element, removed from list
        next ptr
    fallback to allocating new space

Итак, сначала все просто-подход "без резьбы (но выделения сохраняют свой размер; таким образом, большое пространство, повторно используемое для маленького объекта, может быть повторно использовано для большого объекта, позже).

Но когда я должен вызвать collect()?

Редактировать: Остальной код и связанные с ним модули были размещены в comp.lang.postscript, в ветке: http://groups.google.com/group/comp.lang.postscript/browse_thread/thread/56c1734709ee33f1#

Ответы [ 2 ]

1 голос
/ 17 июня 2011

Вот стратегия периодического сбора, включенная в исходный код: 

enum { PERIOD = 10 };

unsigned gballoc(mfile *mem, unsigned sz) {
    unsigned z = adrent(mem, FREE);
    unsigned e;
    static period = PERIOD;
    memcpy(&e, mem->base+z, sizeof(e));
try_again:
    while (e) {
        if (szent(mem,e) >= sz) {
            memcpy(mem->base+z, mem->base+adrent(mem,e), sizeof(unsigned));
            return e;
        }
        z = adrent(mem,e);
        memcpy(&e, mem->base+z, sizeof(e));
    }
    if (--period == 0) {
        period = PERIOD;
        collect(mem, 0);
        goto try_again;
    }
    return mtalloc(mem, 0, sz);
}
1 голос
/ 16 июня 2011

Есть несколько применимых философий:

  • Делать сборку мусора как последнее препятствие для расширения кучи во время выделения. Это, наверное, самая распространенная стратегия.
  • Периодически выполняйте сборку мусора, как каждое сотое выделение или освобождение. В некоторых ситуациях это может снизить общие усилия по сбору мусора, не позволяя фрагментации выйти из-под контроля.
  • Не занимайтесь сборкой мусора. Всегда возможная стратегия, особенно для краткосрочных или простых программ.

Как разработчику сборки мусора, может быть желательно дать выбор стратегии приложению, поскольку оно может знать, какая из них будет наиболее эффективной. Конечно, если у него нет предпочтений, вы должны выбрать значение по умолчанию.

...