Пользователь
30,2
рейтинг
10 октября 2014 в 21:17

Разработка → Визуализация алгоритмов для сборки мусора tutorial

Большинство разработчиков воспринимают сборку мусора (garbage collection) как нечто само собой разумеющееся. Это стандартный процесс, который периодически освобождает память, удаляя ненужные объекты. А вот американский программист Кен Фокс (Ken Fox) захотел досконально разобраться и заглянуть «под капот» современных сборщиков мусора.

Кен «поигрался» с пятью разными алгоритмами сборки мусора и опубликовал маленькие анимации, которые наглядно демонстрируют их работу.

Анимации большего размера выложены на github.com/kenfox/gc-viz.

Краткое пояснение по инфографике. Каждая картинка целиком — это память, выделенная для программы. Сначала она чёрная, то есть неиспользуемая, но постепенно начинается подсвечиваться ярко-жёлтым (операции записи) и ярко-зелёным (операции чтения). Со временем записанные фрагменты темнеют, чтобы показать развитие процесса во времени.

Можно заметить, что по ходу выполнения программа начинает игнорировать отдельные участки памяти. Они и считаются «мусором».

На первой анимации показано, как работает программа без сборщика мусора, то есть по методу очистки в конце. Самый простой способ: нужно дождаться окончания процесса, а потом очистить всё сразу. Это на удивление эффективная техника, пишет автор, если у вас есть способ разбить процесс на отдельные задачи. Так поступает, например, веб-сервер Apache.

Для контраста, вот как выглядит та же программа, но со сборщиком мусора, использующим технику подсчёта ссылок. Это ещё один относительно простой метод, когда подсчитывается количество ссылок на объект в памяти, и если оно падает до нуля, то объект удаляется.

Подсчёт ссылок — единственный алгоритм, хорошо совместимый с разными менеджерами ресурсов.

На анимации появились красные пикселы, которые соответствуют операции подсчёта ссылок. Можно оценить и эффективность сборщика, если сразу после красной вспышки область памяти освобождается.

В блоге автора и на его странице Github можно изучить также алгоритмы сборщиков типа Mark-Sweep, который решает проблему с обработкой циклических структур в памяти (анимация справа), Mark-Compact с перемещением объектов в памяти (анимация) и копирующего сборщика, который тоже перемещает объекты в памяти, но делает это более простым способом (анимация).

По теме:
Garbage Collection наглядно
Анатолий Ализар @alizar
карма
749,5
рейтинг 30,2
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (8)

  • –18
    Над наглядностью еще нужно работать, по моему мнению… На фоне последних визуализаций, которые я видел (вот этой например), выглядит слабовато!
  • –10
    автор играет в майнкрафт?
  • +1
    А где сама программа, действия которой визуализируются?
    • 0
      Комментарий в исходном файле
      /* The C++ main is a close analogue of this Ruby code: */
      
      dkp_log = File.foreach("dkp.log").map { |line|
        amount, person, thing = line.strip.split(",")
        [ amount.to_i, person, thing ]
      }
      
      standings = dkp_log.group_by { |trans| trans[1] }.map { |person, history|
        [ person, history.reduce(0) { |sum, trans| sum + trans[0] } ]
      }.sort { |a, b| b[1] <=> a[1] }
      
      • 0
        Почему аллокатор в «программе со сборщиком мусора» не дает освобожденные участки памяти в повторное владение?
        • 0
          У автора программы это помечено в TODO:
          // TODO: implement a first-fit algorithm instead of just the bump allocator.
          // free must add memory back to allocator, blocks should be coalesced
          
          • +3
            Да что ж со мной сегодня такое? Ослеп и оглуп. Риторический вопрос: и к чему тогда вся эта анимационная гифомания? :)
      • +8
        Блин, зачем я пишу? Ализар же. Не заметил сразу почему-то.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.