Questions about the garbage collector

[Bill Hart]

We have been trying to understand the garbage collector behaviour, since we had some code for which our machine is running out of memory in a matter of an hour.

We already realised that Julia isn't responsible for memory we allocate on the C side unless we use jl_gc_counted_malloc, which we now do everywhere. But it still uses masses of memory where we were roughly expecting no growth in memory usage (lots of short-lived objects and nothing much else).

The behaviour of the gc on my machine seems to be to allocate objects until 23mb of memory is allocated, then do a jl_gc_collect. However, even after reading as much of the GC code in C as I can, I still can't determine why we are observing the behaviour we are seeing.

Here is a concrete example whose behaviour I don't understand:

     function doit2(n::Int)

         s = BigInt(2234567876543456789876545678987654567898765456789876545678)

         for i = 1:n

            s += i

         end

         return s

      end

     doit(10000000000)

This is using Julia's BigInt type which is using a GMP bignum. Julia replaces the GMP memory manager functions with jl_gc_counted_malloc, so indeed Julia knows about all the allocations made here.

But what I don't understand is that the memory usage of Julia starts at about 124mb and rises up to around 1.5gb. The growth is initially fast and it gets slower and slower.

Can someone explain why there is this behaviour? Shouldn't jl_gc_collect be able to collect every one of those allocations every time it reaches the collect_interval of 23mb (which remains constant on my machine with this example)?

As an alternative experiment, I implemented a kind of bignum type using Julia arrays of UInts which I then pass to GMP low level mpn functions (which don't do any allocations on the C side). I only implemented the + operator, just enough to make this example work.

The behaviour in this case is that memory usage is constant at around 124mb. There is no growth in memory usage over time.

Why is the one example using so much memory and the other is not?

Note that the bignums do not grow here. They are always essentially 3 or 4 limbs or something like that, in both examples.

Some other quick questions someone might be able to answer:

* Is there any difference in GC behaviour between using & vs Ref in ccall?

* Does the Julia GC have a copying allocator for the short lived generation(s)?

* Does the Julia GC do a full mark and sweep every collection? Even of the long lived generation(s)? If not, which part of the GC code is responsible for deciding when to do a more involved sweep vs a faster sweep. I am having some trouble orienting myself with the code, and I'd really like to understand it a bit better.

* Can someone confirm whether the "pools" mentioned in the GC code refer to pools for different sized allocations. Are there multiple pools for the same sized allocation, or did I misunderstand that?

Thanks in advance.

Bill.

[Yichao Yu]

On Mar 15, 2016 11:56 AM, "'Bill Hart' via julia-users" <julia...@googlegroups.com> wrote:
>
> We have been trying to understand the garbage collector behaviour, since we had some code for which our machine is running out of memory in a matter of an hour.
>
> We already realised that Julia isn't responsible for memory we allocate on the C side unless we use jl_gc_counted_malloc, which we now do everywhere. But it still uses masses of memory where we were roughly expecting no growth in memory usage (lots of short-lived objects and nothing much else).

Haven't finish the whole email but just want to point out first that julia is never responsible for freeing memory you malloced, (even with jl gc counted malloc) the function merely make the gc aware of the memory usage and you always need to free it explicitly.

[Bill Hart]

On 15 March 2016 at 17:04, Yichao Yu <yyc...@gmail.com> wrote:

On Mar 15, 2016 11:56 AM, "'Bill Hart' via julia-users" <julia...@googlegroups.com> wrote:
>
> We have been trying to understand the garbage collector behaviour, since we had some code for which our machine is running out of memory in a matter of an hour.
>
> We already realised that Julia isn't responsible for memory we allocate on the C side unless we use jl_gc_counted_malloc, which we now do everywhere. But it still uses masses of memory where we were roughly expecting no growth in memory usage (lots of short-lived objects and nothing much else).

Haven't finish the whole email but just want to point out first that julia is never responsible for freeing memory you malloced, (even with jl gc counted malloc) the function merely make the gc aware of the memory usage and you always need to free it explicitly.

Yes, of course. We have finalizers for all C objects and the memory manager on the C side always calls the appropriate julia free function when it cleans up.

Note that the example I gave is just using Julia's own BigInts, nothing of our own on the C side. It doesn't run the machine out of memory, but still exhibits the same basic behaviour of allocating gigabytes of memory when it should be able to collect basically everything every time Julia does a gc_collect.

Bill. 

[Bill Hart]

Here is the (very primitive) example using mpn's that I mentioned.

import Base: +

typealias ZZ Array{UInt, 1}

function +(a::ZZ, b::Int)

   r = ZZ(length(a))

   ccall((:__gmpn_add_1, :libgmp), Void, (Ptr{UInt}, Ptr{UInt}, Int, Int), r, a, 3, b)

   return r

end

function doit(n::Int)

   a = ZZ(3)

   a[1] = rand(UInt)

   a[2] = rand(UInt)

   a[3] = rand(UInt)

   for s = 1:n

      a += s

   end

   return a

end

This code, unlike the Julia BigInt example does not exhibit the same behaviour. The memory usage is exactly as I would expect. It doesn't grow at all.

Bill.

[Bill Hart]

Just to clarify what I meant by "Julia can't be responsible for...." I was talking about the fact that the garbage collector does a gc_collect every 23mb on my machine. If memory is allocated on the C side without calling jl_gc_counted_malloc to do so, Julia can't be expected to include these allocations in its count as it tries to work out if 23mb have been allocated yet (and hence a gc_collect should be initiated).

So I just meant Julia can't be expected to know about the allocations unless we inform it. We of course remain responsible for cleaning it up.

[Tobias Knopp]

Seems to be an issue specific for BigNum. I would expect in the line

  s += i

new BigNum objects are created (and in turn allocated) and in turn the gc will kick in from time to time and run the finalizers of the BigNum objects that are not rooted anymore.

[Bill Hart]

Yes, s+=i just calls the + function for bignums, which indeed creates a new BigNum object each iteration.

[It would incidentally be great if we could overload += directly in Julia!! I wouldn't mind if it was required to return an immutable object because I could still return a new immutable object wrapping the old internals after they have been updated. But this is an aside and not related to the issue here.]

Note in particular that my mpn example creates a new Array every iteration and yet it doesn't show the same behaviour.

The difference is surely either something to do with finalizers or to do with the difference between an allocation Julia merely counts and an allocation Julia actually garbage collects.

It's not limited to BigInt's anyway. All of our types in Nemo operate the same way as GMP bignums. So this issue affects every single one of the types coming from C libraries that we interface to. It seems to affect any C objects that do allocations of their own, even when we go to the trouble of informing Julia of these allocations via use of jl_gc_counted_malloc instead of malloc.

To understand what is causing the problem, we need to understand the Julia garbage collector better.

Bill.

[Yichao Yu]

On Mar 15, 2016 11:56 AM, "'Bill Hart' via julia-users" <julia...@googlegroups.com> wrote:
>

> We have been trying to understand the garbage collector behaviour, since we had some code for which our machine is running out of memory in a matter of an hour.
>
> We already realised that Julia isn't responsible for memory we allocate on the C side unless we use jl_gc_counted_malloc, which we now do everywhere. But it still uses masses of memory where we were roughly expecting no growth in memory usage (lots of short-lived objects and nothing much else).
>
> The behaviour of the gc on my machine seems to be to allocate objects until 23mb of memory is allocated, then do a jl_gc_collect. However, even after reading as much of the GC code in C as I can, I still can't determine why we are observing the behaviour we are seeing.
>
> Here is a concrete example whose behaviour I don't understand:
>
>      function doit2(n::Int)
>          s = BigInt(2234567876543456789876545678987654567898765456789876545678)
>          for i = 1:n
>             s += i
>          end
>          return s
>       end
>
>      doit(10000000000)
>
>
> This is using Julia's BigInt type which is using a GMP bignum. Julia replaces the GMP memory manager functions with jl_gc_counted_malloc, so indeed Julia knows about all the allocations made here.
>
> But what I don't understand is that the memory usage of Julia starts at about 124mb and rises up to around 1.5gb. The growth is initially fast and it gets slower and slower.

I can't really reproduce this behavior.

I assume doit is doit2 and not another function you defined somewhere else.

>
> Can someone explain why there is this behaviour? Shouldn't jl_gc_collect be able to collect every one of those allocations every time it reaches the collect_interval of 23mb (which remains constant on my machine with this example)?
>
> As an alternative experiment, I implemented a kind of bignum type using Julia arrays of UInts which I then pass to GMP low level mpn functions (which don't do any allocations on the C side). I only implemented the + operator, just enough to make this example work.
>
> The behaviour in this case is that memory usage is constant at around 124mb. There is no growth in memory usage over time.
>
> Why is the one example using so much memory and the other is not?
>
> Note that the bignums do not grow here. They are always essentially 3 or 4 limbs or something like that, in both examples.
>
> Some other quick questions someone might be able to answer:
>
> * Is there any difference in GC behaviour between using & vs Ref in ccall?

Ref is heap allocated. & is not.

>
> * Does the Julia GC have a copying allocator for the short lived generation(s)?

It has two generation and not copy

>
> * Does the Julia GC do a full mark and sweep every collection?

No

> Even of the long lived generation(s)? If not, which part of the GC code is responsible for deciding when to do a more involved sweep vs a faster sweep. I am having some trouble orienting myself with the code, and I'd really like to understand it a bit better.

The counters in _jl_gc_collect

>
> * Can someone confirm whether the "pools" mentioned in the GC code refer to pools for different sized allocations. Are there multiple pools for the same sized allocation, or did I misunderstand that?

Pools are for small objects and they are segregated by size.

>
> Thanks in advance.
>
> Bill.
>
>
>

[Yichao Yu]

On Tue, Mar 15, 2016 at 1:45 PM, Yichao Yu <yyc...@gmail.com> wrote:
>
> On Mar 15, 2016 11:56 AM, "'Bill Hart' via julia-users"
> <julia...@googlegroups.com> wrote:
>>
>> We have been trying to understand the garbage collector behaviour, since
>> we had some code for which our machine is running out of memory in a matter
>> of an hour.
>>
>> We already realised that Julia isn't responsible for memory we allocate on
>> the C side unless we use jl_gc_counted_malloc, which we now do everywhere.
>> But it still uses masses of memory where we were roughly expecting no growth
>> in memory usage (lots of short-lived objects and nothing much else).
>>
>> The behaviour of the gc on my machine seems to be to allocate objects
>> until 23mb of memory is allocated, then do a jl_gc_collect. However, even
>> after reading as much of the GC code in C as I can, I still can't determine
>> why we are observing the behaviour we are seeing.
>>
>> Here is a concrete example whose behaviour I don't understand:
>>
>> function doit2(n::Int)
>> s =
>> BigInt(2234567876543456789876545678987654567898765456789876545678)
>> for i = 1:n
>> s += i
>> end
>> return s
>> end
>>
>> doit(10000000000)

Another note is that adding finalizers will (currently) extend the
lifetime of an object. https://github.com/JuliaLang/julia/pull/13995
should solve this problem but I'm holding on to it before we finish
some other GC rework.

[Bill Hart]

Thanks for your answers. Please see my followup questions below.

On 15 March 2016 at 18:45, Yichao Yu <yyc...@gmail.com> wrote:

On Mar 15, 2016 11:56 AM, "'Bill Hart' via julia-users" <julia...@googlegroups.com> wrote:
>
> We have been trying to understand the garbage collector behaviour, since we had some code for which our machine is running out of memory in a matter of an hour.
>
> We already realised that Julia isn't responsible for memory we allocate on the C side unless we use jl_gc_counted_malloc, which we now do everywhere. But it still uses masses of memory where we were roughly expecting no growth in memory usage (lots of short-lived objects and nothing much else).
>
> The behaviour of the gc on my machine seems to be to allocate objects until 23mb of memory is allocated, then do a jl_gc_collect. However, even after reading as much of the GC code in C as I can, I still can't determine why we are observing the behaviour we are seeing.
>
> Here is a concrete example whose behaviour I don't understand:
>
>      function doit2(n::Int)
>          s = BigInt(2234567876543456789876545678987654567898765456789876545678)
>          for i = 1:n
>             s += i
>          end
>          return s
>       end
>
>      doit(10000000000)
>
>
> This is using Julia's BigInt type which is using a GMP bignum. Julia replaces the GMP memory manager functions with jl_gc_counted_malloc, so indeed Julia knows about all the allocations made here.
>
> But what I don't understand is that the memory usage of Julia starts at about 124mb and rises up to around 1.5gb. The growth is initially fast and it gets slower and slower.

I can't really reproduce this behavior.

I assume doit is doit2 and not another function you defined somewhere else.

Yes, I meant doit2 of course.

I'm really amazed you can't reproduce this. I can reproduce it over a wide variety of Julia versions on a variety of machines!

I'm monitoring memory usage with top, not with Julia itself. 

>
> Can someone explain why there is this behaviour? Shouldn't jl_gc_collect be able to collect every one of those allocations every time it reaches the collect_interval of 23mb (which remains constant on my machine with this example)?
>
> As an alternative experiment, I implemented a kind of bignum type using Julia arrays of UInts which I then pass to GMP low level mpn functions (which don't do any allocations on the C side). I only implemented the + operator, just enough to make this example work.
>
> The behaviour in this case is that memory usage is constant at around 124mb. There is no growth in memory usage over time.
>
> Why is the one example using so much memory and the other is not?
>
> Note that the bignums do not grow here. They are always essentially 3 or 4 limbs or something like that, in both examples.
>
> Some other quick questions someone might be able to answer:
>
> * Is there any difference in GC behaviour between using & vs Ref in ccall?

Ref is heap allocated. & is not.

Do you mean the Ref object itself is heap allocated but the & object is stack allocated? Or are you referring to a GC "heap" vs a pool or something?

Why was & deprecated? It sounds like & should be faster, no?

>
> * Does the Julia GC have a copying allocator for the short lived generation(s)?

It has two generation and not copy

So do the pools constitute the new generation? Or is the new generation separate from the pools?

I noticed in the code that it looks like things get promoted if they survive more than 2 generations (currently). But what happens to the objects between generations 1 and 2 if they are not copied?

Or do you mean it has 2 generations plus a long term generation?

>
> * Does the Julia GC do a full mark and sweep every collection?

No

> Even of the long lived generation(s)? If not, which part of the GC code is responsible for deciding when to do a more involved sweep vs a faster sweep. I am having some trouble orienting myself with the code, and I'd really like to understand it a bit better. 

The counters in _jl_gc_collect

You mean quick_count?

In my version of Julia in gc.c, quick_count is set to 0 and incremented, but never used anywhere. How does this affect the behaviour? Is it used somewhere else in Julia?

Or do you mean inc_count? I see this determines scanned_bytes_goal, which again is not used anywhere that I can see.

I can't see anywhere else that inc_count is used either.

>
> * Can someone confirm whether the "pools" mentioned in the GC code refer to pools for different sized allocations. Are there multiple pools for the same sized allocation, or did I misunderstand that?

Pools are for small objects and they are segregated by size.

Thanks.

 

>
> Thanks in advance.
>
> Bill.
>
>
>

[Bill Hart]

This at least sounds like it might be related to the problem we are seeing.

I guess it means an object with a finalizer cannot be immediately cleaned up if it is short lived. The only way for such an object to get cleaned up is in long lived territory, which the state diagram seems to suggest is the only place a finalizer can even be scheduled. Is that about correct (I have to explain it to someone else, so I'm hoping to not tell them too many wrong things).

Bill. 

[Yichao Yu]

On Tue, Mar 15, 2016 at 2:18 PM, 'Bill Hart' via julia-users

I'm using htop.

>>
>>
>> >
>> > Can someone explain why there is this behaviour? Shouldn't jl_gc_collect
>> > be able to collect every one of those allocations every time it reaches the
>> > collect_interval of 23mb (which remains constant on my machine with this
>> > example)?
>> >
>> > As an alternative experiment, I implemented a kind of bignum type using
>> > Julia arrays of UInts which I then pass to GMP low level mpn functions
>> > (which don't do any allocations on the C side). I only implemented the +
>> > operator, just enough to make this example work.
>> >
>> > The behaviour in this case is that memory usage is constant at around
>> > 124mb. There is no growth in memory usage over time.
>> >
>> > Why is the one example using so much memory and the other is not?
>> >
>> > Note that the bignums do not grow here. They are always essentially 3 or
>> > 4 limbs or something like that, in both examples.
>> >
>> > Some other quick questions someone might be able to answer:
>> >
>> > * Is there any difference in GC behaviour between using & vs Ref in
>> > ccall?
>>
>> Ref is heap allocated. & is not.
>
> Do you mean the Ref object itself is heap allocated but the & object is
> stack allocated? Or are you referring to a GC "heap" vs a pool or something?

heap as in allocated through the GC.
& does not create a new object and is a special syntax for ccall

>
> Why was & deprecated? It sounds like & should be faster, no?

Yes, it is, and that's why we don't have a depward for it. The
performance of Ref can be brought on pair with & with some compilar
optimizations (search for stack allocation on the issue tracker) and I
don't think we'll fully deprecate & before that.

>>
>> >
>> > * Does the Julia GC have a copying allocator for the short lived
>> > generation(s)?
>>
>> It has two generation and not copy
>
> So do the pools constitute the new generation? Or is the new generation
> separate from the pools?

They are all in the same pool

>
> I noticed in the code that it looks like things get promoted if they survive
> more than 2 generations (currently). But what happens to the objects between

more than 2 collection*

> generations 1 and 2 if they are not copied?

See the lifetime diagram in gc.c, they are marked differently.

>
> Or do you mean it has 2 generations plus a long term generation?

See also https://github.com/yuyichao/explore/blob/master/julia/new_gc/bit_swap.md
if you are interested.

>>
>> >
>> > * Does the Julia GC do a full mark and sweep every collection?
>>
>> No
>>
>> > Even of the long lived generation(s)? If not, which part of the GC code
>> > is responsible for deciding when to do a more involved sweep vs a faster
>> > sweep. I am having some trouble orienting myself with the code, and I'd
>> > really like to understand it a bit better.
>>
>> The counters in _jl_gc_collect
>
> You mean quick_count?
>
> In my version of Julia in gc.c, quick_count is set to 0 and incremented, but
> never used anywhere. How does this affect the behaviour? Is it used
> somewhere else in Julia?
>
> Or do you mean inc_count? I see this determines scanned_bytes_goal, which
> again is not used anywhere that I can see.
>
> I can't see anywhere else that inc_count is used either.

There are a lot of heuristics. see the logic that makes `sweep_mask =
GC_MARKED`. I believe I've recently removed those unused counters on
master.

[Yichao Yu]

On Tue, Mar 15, 2016 at 2:29 PM, 'Bill Hart' via julia-users

I don't think the state diagram covers finalizer.
The issue with the finalizer is that they are arbitrary julia code and
cannot be run in the GC. They need to run after the GC finishes and
therefore must survive the sweep. This will make them survive one more
GC than what they would have been and make them likely to end up in
the old gen. (If most of your temporaries don't survive more than a GC
this shouldn't be an issue.)

> to explain it to someone else, so I'm hoping to not tell them too many wrong
> things).
>
> Bill.

One way to get an idea of what's causing the memory issue is to call
`gc(true)` or `gc(false)` from time to time (you can call it multiple
times in a row but don't call it in every iteration, it'll be terribly
slow).

[Bill Hart]

Can I ask how recent your Julia is. I see this with Julia 0.4 and Julia 0.5 with 100 day old master (I can't update to something more recent as someone removed a documented feature of Julia and the issue was marked WontFix https://github.com/JuliaLang/julia/issues/14919 , so I can't current try a later Julia).

I see. That is a relief. We'll stick with & for now.

 

>>
>> >
>> > * Does the Julia GC have a copying allocator for the short lived
>> > generation(s)?
>>
>> It has two generation and not copy
>
> So do the pools constitute the new generation? Or is the new generation
> separate from the pools?

They are all in the same pool

>
> I noticed in the code that it looks like things get promoted if they survive
> more than 2 generations (currently). But what happens to the objects between

more than 2 collection*

I see, so collections can happen at any time, not when some block of memory is "full".

> generations 1 and 2 if they are not copied?

See the lifetime diagram in gc.c, they are marked differently.

>
> Or do you mean it has 2 generations plus a long term generation?

See also https://github.com/yuyichao/explore/blob/master/julia/new_gc/bit_swap.md
if you are interested.

Thanks.

 

>>
>> >
>> > * Does the Julia GC do a full mark and sweep every collection?
>>
>> No
>>
>> > Even of the long lived generation(s)? If not, which part of the GC code
>> > is responsible for deciding when to do a more involved sweep vs a faster
>> > sweep. I am having some trouble orienting myself with the code, and I'd
>> > really like to understand it a bit better.
>>
>> The counters in _jl_gc_collect
>
> You mean quick_count?
>
> In my version of Julia in gc.c, quick_count is set to 0 and incremented, but
> never used anywhere. How does this affect the behaviour? Is it used
> somewhere else in Julia?
>
> Or do you mean inc_count? I see this determines scanned_bytes_goal, which
> again is not used anywhere that I can see.
>
> I can't see anywhere else that inc_count is used either.

There are a lot of heuristics. see the logic that makes `sweep_mask =
GC_MARKED`. I believe I've recently removed those unused counters on
master.

Ah ok. It sounds like you have a more recent gc than me, and possibly this also explains why you don't observe the behaviour I see.

I actually reported the behaviour on the day the generational gc behaviour was switched on. Nobody replied at the time, which made me wonder if anyone had noticed. The behaviour has been the same for us from that time until 100 days ago when we stopped updating Julia.

 

Bll.

[Yichao Yu]

On Tue, Mar 15, 2016 at 2:45 PM, 'Bill Hart' via julia-users
<julia...@googlegroups.com> wrote:
>
>
> Can I ask how recent your Julia is. I see this with Julia 0.4 and Julia 0.5

0.5.0-dev+3106
I could try 0.4 later.

> with 100 day old master (I can't update to something more recent as someone
> removed a documented feature of Julia and the issue was marked WontFix
> https://github.com/JuliaLang/julia/issues/14919 , so I can't current try a
> later Julia).
>
>>

>> Yes, it is, and that's why we don't have a depward for it. The
>> performance of Ref can be brought on pair with & with some compilar
>> optimizations (search for stack allocation on the issue tracker) and I
>> don't think we'll fully deprecate & before that.
>>
>
> I see. That is a relief. We'll stick with & for now.
>

>> more than 2 collection*
>
>
> I see, so collections can happen at any time, not when some block of memory
> is "full".

Yes, it happens whenever the GC thinks there are enough allocation
since the last time.

>
>>
>> > generations 1 and 2 if they are not copied?
>>
>> See the lifetime diagram in gc.c, they are marked differently.
>>
>> >
>> > Or do you mean it has 2 generations plus a long term generation?
>>
>> See also
>> https://github.com/yuyichao/explore/blob/master/julia/new_gc/bit_swap.md
>> if you are interested.
>
>
> Thanks.
>
>

[Bill Hart]

On 15 March 2016 at 19:45, Bill Hart <goodwi...@googlemail.com> wrote:

>
> I noticed in the code that it looks like things get promoted if they survive
> more than 2 generations (currently). But what happens to the objects between

more than 2 collection*

I see, so collections can happen at any time, not when some block of memory is "full".

Actually, let me ask this a bit more precisely.

Suppose a collection has occurred. Then there are big gaps where memory has been reclaimed, between blocks that are still in use. If there is no copying collector, how does the gc avoid fragmentation?

I see that each page of memory is released as it is found to contain no objects still in use. Is that the only mechanism used to control fragmentation?

Bill. 

[Mauro]

>> Can I ask how recent your Julia is. I see this with Julia 0.4 and Julia 0.5
>
> 0.5.0-dev+3106
> I could try 0.4 later.

Yes, that's it. I can see Bill's memory behavior on 0.4.3 (starts at
130MB, goes to ~1.4GB when running doit2) but not on yesterday's 0.5
(starts at 150MB, when running doit2 it stays at 180MB).

[Bill Hart]

Good to hear the problem seems to be fixed in recent 0.5. Thanks for checking this.

That gives me more motivation for fixing our code so it can run on the latest 0.5. Hopefully I can find a way.

I wonder what the issue was, and whether the person who fixed it even realised they had fixed it. :-)

Bill.

[Bill Hart]

> I see. That is a relief. We'll stick with & for now.
>
>> more than 2 collection*
>
>
> I see, so collections can happen at any time, not when some block of memory
> is "full".

Yes, it happens whenever the GC thinks there are enough allocation
since the last time.

So for you a "generation" has no relation to a "collection"?

If not, what is your definition of a generation?

Does Julia just have two generations, short term and long term? And each object in the short term generation has a collection count. Once the collection count hits 2 the object is promoted to long term generation by marking it, but it stays right where it is in the same "pool"?

Bill.

[Yichao Yu]

> I wonder what the issue was, and whether the person who fixed it even realised they had fixed it. :-)

There were many GC related PRs. Some of them are for mem-leak. I don't
remember any one in particular about malloc though....

> Actually, let me ask this a bit more precisely.
>
> Suppose a collection has occurred. Then there are big gaps where memory has been reclaimed, between blocks that are still in use. If there is no copying collector, how does the gc avoid fragmentation?
>
> I see that each page of memory is released as it is found to contain no objects still in use. Is that the only mechanism used to control fragmentation?

It doesn't avoid fragmentation. This isn't a big issue for julia's
allocator since the pools are size segregated and it is never
necessary to find a slot of large enough size by walking the free
list.
This will cause more memory usage and I don't think there's a way
around it without moving. We'd like to try implement moving but as you
may guess this is a relatively hard problem. Fortunately I think
there's a relatively clear upgrade path although there are a lot of
other improvement we'd like to implement before that.

> So for you a "generation" has no relation to a "collection"?

I use collection only as in the "collection" in "doing a garbage collection"

>
> If not, what is your definition of a generation?

Julia GC has two generations. Objects are allocated in the young gen
and are promoted to the old gen if they survive long enough.
This is not much different from a traditional generational collector
although instead of using the memory space (address range) to keep
track of the metadata (the generation an object is in) we use the GC
bit to keep track of that info inline and avoid the moving.

>
> Does Julia just have two generations, short term and long term?

Yes, young and old.

> And each object in the short term generation has a collection count. Once the collection count hits 2 the object is promoted to long term generation by marking it, but it stays right where it is in the same "pool"?

Right.

The generational part of the GC is a little messy. This is mainly
because the new GC was designed to be an incremental GC and then
gradually transformed into a generational GC....... (they are
suprisingly similar....).

[Bill Hart]

On 15 March 2016 at 20:24, Yichao Yu <yyc...@gmail.com> wrote:

> I wonder what the issue was, and whether the person who fixed it even realised they had fixed it. :-)

There were many GC related PRs. Some of them are for mem-leak. I don't
remember any one in particular about malloc though....

> Actually, let me ask this a bit more precisely.
>
> Suppose a collection has occurred. Then there are big gaps where memory has been reclaimed, between blocks that are still in use. If there is no copying collector, how does the gc avoid fragmentation?
>
> I see that each page of memory is released as it is found to contain no objects still in use. Is that the only mechanism used to control fragmentation?

It doesn't avoid fragmentation. This isn't a big issue for julia's
allocator since the pools are size segregated and it is never
necessary to find a slot of large enough size by walking the free
list.

Yeah I wondered about that.

 

This will cause more memory usage and I don't think there's a way
around it without moving. We'd like to try implement moving but as you
may guess this is a relatively hard problem. Fortunately I think
there's a relatively clear upgrade path although there are a lot of
other improvement we'd like to implement before that.

Sure. GC at least has a reputation for being "hard".

 

> So for you a "generation" has no relation to a "collection"?

I use collection only as in the "collection" in "doing a garbage collection"

>
> If not, what is your definition of a generation?

Julia GC has two generations. Objects are allocated in the young gen
and are promoted to the old gen if they survive long enough.
This is not much different from a traditional generational collector
although instead of using the memory space (address range) to keep
track of the metadata (the generation an object is in) we use the GC
bit to keep track of that info inline and avoid the moving.

>
> Does Julia just have two generations, short term and long term?

Yes, young and old.

> And each object in the short term generation has a collection count. Once the collection count hits 2 the object is promoted to long term generation by marking it, but it stays right where it is in the same "pool"?

Right.

Great, thanks. I understand better now. Not all the ins and outs, but a much better overall picture.

 

The generational part of the GC is a little messy. This is mainly
because the new GC was designed to be an incremental GC and then
gradually transformed into a generational GC....... (they are
suprisingly similar....).

Oh I didn't even realise that LOL. I thought Julia just switched to a generational gc and that's it. Probably at the time I didn't even know there was a difference between incremental and generational. I probably couldn't write down a definition of either even now. But at least I have nonzero knowledge of the Julia GC which will help me answer all the questions I keep getting from my colleagues on it.

Bill.

[Yichao Yu]

On master, yes, that's all, the incremental GC never hit the master.
I'm just talking about the PR that did this. In fact the original PR
still has the "wrong" title
https://github.com/JuliaLang/julia/pull/5227.

[Bill Hart]

>> The generational part of the GC is a little messy. This is mainly
>> because the new GC was designed to be an incremental GC and then
>> gradually transformed into a generational GC....... (they are
>> suprisingly similar....).
>>
>
> Oh I didn't even realise that LOL. I thought Julia just switched to a
> generational gc and that's it. Probably at the time I didn't even know there

On master, yes, that's all, the incremental GC never hit the master.
I'm just talking about the PR that did this. In fact the original PR
still has the "wrong" title
https://github.com/JuliaLang/julia/pull/5227.

So that PR was interesting reading. But now I have a new question (or two).

Is it correct that the GC is not incremental, in the sense that low pause times were not gained by making the gc incremental (in the end), but by collecting the new generations more often than the old?

Or is there now also some incremental behaviour as well?

Are there plans in this direction in the future?

I was also unaware that LLVM makes it difficult to implement a moving GC. I hadn't realised that. I see the original author in that PR actually mentioned fragmentation as being an issue, though the current behaviour doesn't seem too bad anyway.

Bill.

[Yichao Yu]

On Mar 15, 2016 4:16 PM, "'Bill Hart' via julia-users" <julia...@googlegroups.com> wrote:
>>
>>
>> >> The generational part of the GC is a little messy. This is mainly
>> >> because the new GC was designed to be an incremental GC and then
>> >> gradually transformed into a generational GC....... (they are
>> >> suprisingly similar....).
>> >>
>> >
>> > Oh I didn't even realise that LOL. I thought Julia just switched to a
>> > generational gc and that's it. Probably at the time I didn't even know there
>>
>> On master, yes, that's all, the incremental GC never hit the master.
>> I'm just talking about the PR that did this. In fact the original PR
>> still has the "wrong" title
>> https://github.com/JuliaLang/julia/pull/5227.
>
>
> So that PR was interesting reading. But now I have a new question (or two).
>
> Is it correct that the GC is not incremental, in the sense that low pause times were not gained by making the gc incremental (in the end), but by collecting the new generations more often than the old?

Right.

>
> Or is there now also some incremental behaviour as well?

No.

>
> Are there plans in this direction in the future?

Maybe. Not really on my own todo list and unlikely to be high priority.

>
> I was also unaware that LLVM makes it difficult to implement a moving GC. I hadn't realised that.

I didn't actually read the whole thread (it was also before I joint.) I assume you mean that using llvm instead of our own codegen backend makes moving harder. This is generally true for keeping track of any metadata in codegen when you don't control literally everything about it.