RubyとPythonの違いからガベージコレクタを理解する - ワザノバ | wazanova.jp
これ、ちょっと気になるところがあったんで元記事参照したんだけど、
「抄訳」っていっていいくらい元記事から減量してたのね。
Visualizing Garbage Collection in Ruby and Python - Pat Shaughnessy
あと元記事の作者さん Ruby Under a Microscope の著者だったんだー。
しかし元記事まで追いかけてる人いなさそう?
はてなブックマーク - RubyとPythonの違いからガベージコレクタを理解する - ワザノバ | wazanova.jp
Twitter / 検索 - http://wazanova.jp/post/65317231718/ruby-python
implement を「インプリ」としちゃうのはとても気になるのだけどそれはまあおいといて。
RubyとPythonの違いからガベージコレクタを理解する - ワザノバ | wazanova.jp
ガベージコレクタは、「ゴミを集める」という行為だけでなく、「新しいオブジェクトのためにメモリをあてがう。」
「不要なオブジェクトを見つける」「不要なオブジェクトからメモリを取り戻す。」という、人間の心臓が血液を浄化
するような働きをしている。
心臓は血液の浄化をしないよねというのははてダのコメントの中にもありましたが
元記事の該当部分を見ると
Visualizing Garbage Collection in Ruby and Python - Pat Shaughnessy
The Beating Heart of Your Application
GC systems do much more than just “collect garbage.” In fact, they perform three important tasks. They
allocate memory for new objects,
identify garbage objects, and
reclaim memory from garbage objects.
Imagine if your application was a human body: All of the elegant code you write, your business logic, your
algorithms, would be the brain or the intelligence inside the application. Following this analogy, what part
of the body do you think the garbage collector would be?
[ I got lots of fun answers from the RuPy audience: kidneys, white blood cells :) ]
I think the garbage collector is the beating heart of your application. Just as your heart provides blood and
nutrients to the rest of the your body, the garbage collector provides memory and objects for your application
to use. If your heart stopped beating you would die in seconds. If the garbage collector stopped or ran slowly
－ if it had clogged arteries － your application would slow down and eventually die!
なーんかいきなり分量が…w
んーと、どこに「心臓が血液を浄化」にあたる文が?
Just as your heart provides blood and nutrients to the rest of the your body
が流れ的には該当するんだろうけど、「boold and nutrients(血液と栄養素)」を「供給」だよねえ。これ。
この際だから後続の部分も。
あ、元記事の画像は無視してるのでその辺よろしく。
1) Rubyのメモリ
Rubyは、コードが実行される前に、数千のオブジェクトを先につくり、それをリンクされたfree listに置く。[図] そして、
上記のコードサンプルにあるNode.new (1)がコールされると、オブジェクトを一つfree listから取って渡してくれる = コ
ードで利用されるアクティブなオブジェクトになる。[図]（もちろん実際には他の役割を担うオブジェクトもあって、もっと
複雑だが、話しをシンプルにするためにこの図の考え方を使って説明している。）
次にNode.newが再びコールされると、二つ目のオブジェクトをfree listから渡してくれる。 [図] このMRIの仕組みは、
1960年にJohn McCarthyがLispの開発の過程でつくったアルゴリズムを用いている。
The Free List
When we call Node.new(1) above, what does Ruby do, exactly? How does Ruby go about creating a new object for us?
Surprisingly, it does very little! In fact, long before your code starts to run, Ruby creates thousands of
objects ahead of time and places them on a linked list, called the free list. Here’s what the free list might
look like, conceptually:
Imagine each of the while squares above is an unused, precreated Ruby object. When we call Node.new, Ruby
simply takes one of these objects and hands it to us:
In the diagram above, the gray square on the left represents an active Ruby object we’re using in our code,
while the remaining white squares are unused objects. [ Note: of course, my diagrams are a simplified version
of reality. In fact, Ruby would use another object to hold the string “ABC,” a third object to hold the class
definition of Node, and still other objects to hold the parsed, abstract syntax tree (AST) representation of my
code, etc. ]
This simple algorithm of using a linked list of precreated objects was invented over 50 years ago by a legendary
computer scientist named John McCarthy, while he was working on the original implementation of Lisp. Lisp was
not only one of the first functional programming languages, but also contained a number of other groundbreaking
advances in computer science. One of these was the concept of automatically managing your application’s memory
using garbage collection.
The standard version of Ruby, also known as “Matz’s Ruby Interpreter” (MRI), uses a GC algorithm similar to
the one used by McCarthy’s implementation of Lisp in 1960. For better or worse, Ruby uses a 53 year old
algorithm for garbage collection. Just as Lisp did, Ruby creates objects ahead of time and hands them to your
code when you allocate new objects or values.
long before your code starts to run, Ruby creates thousands of objects ahead of time and places them on a linked list, called the free list.
が、
Rubyは、コードが実行される前に、数千のオブジェクトを先につくり、それをリンクされたfree listに置く。
こうなる?
The standard version of Ruby, also known as “Matz’s Ruby Interpreter” (MRI), uses a GC algorithm similar to
the one used by McCarthy’s implementation of Lisp in 1960.
が
このMRIの仕組みは、1960年にJohn McCarthyがLispの開発の過程でつくったアルゴリズムを用いている。
というのは、
元記事で“Matz’s Ruby Interpreter” (MRI)
って書いてるのに、MRI だけ書いちゃあ
特に Ruby を知らない人にはなんだそれという状態になってしまうだろうし、
原文の similar to がどっか行っちゃってるし、逆に「(Lisp の)開発の過程」ってのはどこから来たの?
2) Pythonのメモリ
Pythonも、リストのためにオブジェクトを再利用するのでfree listの仕組みを内部ではもっているが、通常はRubyとは違う
メモリの扱いをする。PythonはオブジェクトをつくったらすぐにOSにメモリを要求する。[図]（Pythonは実際、OSヒープ上
に追加の抽象化レイヤをつくるメモリ適用システムをインプリするが、今回はその詳細の説明は割愛。）二つ目のオブジェ
クトをつくる場合も同様に、OSにメモリを要求する。[図]
What about Python?
While Python also uses free lists for various reasons internally (it recycles certain objects such as lists),
it normally allocates memory for new objects and values differently than Ruby does.
Suppose we create a Node object using Python:
Python, unlike Ruby, will ask the operating system for memory immediately when you create the object. (Python
actually implements its own memory allocation system which provides an additional layer of abstraction on top
of the OS heap. But I don’t have time to get into those details today.)
When we create a second object, Python will again ask the OS for more memory:
Pythonは実際、OSヒープ上に追加の抽象化レイヤをつくるメモリ適用システムをインプリするが、今回はその詳細の説明は割愛。
its own memory allocation system
allocation と application を勘違いした?
＞「メモリ適用システム」
3) Rubyは未利用のオブジェクトを放置
Rubyでオブジェクトが次々つくられると、free listの残りが少なくなる。[図] n1に新しいバリューがアサインされると、
古いバリューが残ったオブジェクトが放置されていることに注目してほしい。[図]
Ruby leaves unused objects lying around in memory until the next GC process runs.
Seems simple enough; at the moment we create an object Python takes the time to find and allocate memory for us.
Ruby Developers Live in a Messy House
Back to Ruby. As we allocate more and more objects, Ruby will continue to hand us precreated objects from the
free list. As it does this, the free list will become shorter:
…and shorter:
Notice as I continue to assign new values to n1, Ruby leaves the old values behind. The ABC, JKL and MNO nodes
remain in memory. Ruby doesn’t immediately clean up old objects my code is no longer using! Working as a Ruby
developer is like living in a messy house, with clothes lying on the floor or dirty dishes in the kitchen sink.
As a Ruby developer you have to work with unused, garbage objects surrounding you.
unused は「未使用」じゃないかなあ。
「バリューがアサイン」…うーん。
4) Pythonは未利用のオブジェクトを掃除
PythonではオブジェクトのC構造の内部に参照カウントという整数をもち、初期数値は１。1という数字は一つのポインターが
指す、参照されているという意味。[図] 新しいnodeがつくられて、元のnodeが不要になると、そこの参照カウントがゼロに
なる。[図] すぐにPythonはそのメモリをOSに戻す。[図] 参照カウンターは、同じ1960年にGeorgeCollinsが生み出したアル
ゴリズム。次に、n2がn1と同じnodeを参照すると、従前にn2が参照していたnodeは掃除される。 [図]
Python Developers Live in a Tidy Household
Python cleans up garbage objects immediately after your code is done using them.
Garbage collection works quite differently in Python than in Ruby. Let’s return to our three Python Node
objects from earlier:
Internally, whenever we create an object Python saves an integer inside the object’s C structure, called the
reference count. Initially, Python sets this value to 1:
The value of 1 indicates there is one pointer or reference to each of the three objects. Now suppose we create
a new node, JKL:
Just as before, Python sets the reference count in JKL to be 1. However, also notice since we changed n1 to
point to JKL, it no longer references ABC, and that Python decremented its reference count down to 0.
At this point, the Python garbage collector immediately jumps into action! Whenever an object’s reference
count reaches zero, Python immediately frees it, returning it’s memory to the operating system:
Above Python reclaims the memory used by the ABC node. Remember, Ruby simply leaves old objects lying around
and doesn’t release their memory.
This garbage collection algorithm is known as reference counting. It was invented by George Collins in 1960 –
not coincidentally the same year John McCarthy invented the free list algorithm. As Mike Bernstein said in his
fantastic presentation on garbage collection at the Gotham Ruby Conference back in June: “1960 was a good year
for Garbage Collectors….”
Working as a Python developer is like living in a tidy house; you know, the kind of place where your roommates
are a bit OCD and are constantly cleaning up after you. As soon as you put down a dirty dish or glass, someone
has already put it away in the dishwasher!
Now for a second example. Suppose we set n2 to refer to the same node as n1:
Above to the left you can see Python has decremented the reference count for DEF and will immediately garbage
collect the DEF node. Also note that the JKL now has a reference count of 2, since both n1 and n2 point to it.
なんという文章量の違い。
参照カウンターは、同じ1960年にGeorgeCollinsが生み出したアルゴリズム。
原文を削りまくってるから「同じ」1960年と言われてもなんじゃそりゃ感が。
5) RubyのMark & Sweepアルゴリズム
Rubyのゴミが溜まり続ける構造では、いずれfree listが枯渇する。そうなるとRubyはアプリを止め、全体をループし、メモ
リがあてられているオブジェクトにマークをつける。[図] 内部的にはRubyは、マークされているか、そうでないかをfree
bitmapで管理している。 [図] Rubyは、unix copy-on-writeの最適化を利用するためbitmapを別のメモリ場所に保管している。
マークされていないオブジェクトは掃除される。[図] Rubyは、一連の作業においてオブジェクトをコピーせずに、内部のポ
インターを調整して新しいlink listを作成することで、オブジェクトをリストに返しているので、作業はかなり短い時間で
完了する。
Mark and Sweep
Eventually a messy house fills up with trash and life can’t continue as usual. After your Ruby program runs for
some time, the free list will eventually be entirely used up:
Here all of the precreated Ruby objects have been used by our application (they are all gray) and no objects
remain on the free list (no white squares are left).
At this point Ruby uses another algorithm invented by McCarthy known as Mark and Sweep. First Ruby stops your
application; Ruby uses “stop the world garbage collection.” Ruby then loops through all of the pointers,
variables and other references our code makes to objects and other values. Ruby also iterates over internal
pointers used by its virtual machine. It marks each object that it is able to reach using these pointers. I
indicate these marks using the letter M here:
Above the three objects marked with “M” are live, active objects that our application is still using.
Internally, Ruby actually uses a series of bits known as the free bitmap to keep track of which objects are
marked or not:
Ruby saves the free bitmap in a separate memory location in order to take full advantage of Unix copy-on-write
optimization. For more information on this, see my article Why You Should Be Excited About Garbage Collection
in Ruby 2.0.
If the marked objects are live, the remaining, unmarked objects must be garbage, meaning they are no longer
being used by our code. I’ll show the garbage objects as white squares below:
Next Ruby sweeps the unused, garbage objects back onto the free list:
Internally this happens quite quickly, since Ruby doesn’t actually copy objects around from one place to
another. Instead, Ruby places the garbage objects back onto the free list by adjusting internal pointers to
form a new linked list.
Now Ruby can give these garbage objects back to us the next time we create a new Ruby object. In Ruby, objects
are reincarnated, and enjoy multiple lives!
わざわざ英字で「link list」はないわー。
6) Mark & Sweepと参照カウント
参照カウントをガベージコレクタのアルゴリズムに採用しない言語がある理由は、
各オブジェクトの内部に参照カウントを置くスペースを確保したり、変数/参照を上下変化させるオペーレーションなど、
この手法のインプリは難易度が高い。
Pythonは頻度高く参照カウントを更新していて、例えば大きなデータ構造の利用をやめると、参照カウントの修正が一
気に、かつかなり複雑な作業になり、アプリが遅くなる可能性がある。
参照カウントは、巡回するデータ構造には使えない。（次回詳細説明）
Mark and Sweep vs. Reference Counting
At first glance, Python’s GC algorithm seems far superior to Ruby’s: why live in a messy house when you can
live in a tidy one? Why does Ruby force your application to stop running periodically each time it cleans up,
instead of using Python’s algorithm?
Reference counting isn’t as simple as it seems at first glance, however. There are a number of reasons why many
languages don’t use a reference counting GC algorithm like Python does:
First, it’s difficult to implement. Python has to leave room inside of each object to hold the reference
count. There’s a minor space penalty for this. But worse, a simple operation such a changing a variable or
reference becomes a more complex operation since Python needs to increment one counter, decrement another,
and possibly free the object.
Second, it can be slower. Although Python performs GC work smoothly as your application runs (cleaning dirty
dishes as soon as you put them in the sink), this isn’t necessarily faster. Python is constantly updating
the reference count values. And when you stop using a large data structure, such as a list containing many
elements, Python might have to free many objects all at once. Decrementing reference counts can be a complex,
recursive process.
Finally, it doesn’t always work. As we’ll see in my next post containing my notes from the rest of this
presentation, reference counting can’t handle cyclic data structures – data structures that contain
circular references.
変数/参照を上下変化させるオペーレーション
とは?
あと、cyclic data structures は「循環」(している)データ構造じゃないかなあ。
Cyclic Redundancy Check では
「巡回冗長検査」だけど。
良い記事見つけて書いてるんだからもっと頑張って欲しいなあ。
Go言語で苦労したポイントの事例 - ワザノバ | wazanova.jp
Spotify: 大きな障害の予兆となる小さな障害 [Postmortem7] - ワザノバ | wazanova.jp
あ、他の記事の元記事との突き合わせはやってません。
