Implement a low latency, incremental garbage collector

[ufechner7]

For applications like games, real-time flight simulators, audio processing and controller prototypes the time that the current garbage collector blocks the application is too long.
Therefore an incremental garbage collector should be implemented, with the option to specify an upper time limit for each call.
For more details see:
https://groups.google.com/forum/?fromgroups=#!topic/julia-users/9T89qzC2qJo
and:
#5227

The language Lua is using an incremental garbage collector since version 5.1. Some results how it performs in realtime control applications are shown in:
https://lwn.net/images/conf/rtlws-2011/proc/Klotzbuecher.pdf

[timholy]

#5227

[ufechner7]

Could you please reopen this issue?
#5227 does NOT address it any longer: Citation:
"
I've disabled the incremental marking/sweeping temporarily. I plan on adding them again (all the infrastructure is in place) but as it targets more niche use cases (latency problems) I think it might be better merging before and getting it into people's hand.
"
This issue is about addressing these "niche usecases".

[carnaval]

true

[ufechner7]

Thanks for reopening. Do you have a test case? Otherwise I will write one.

[StefanKarpinski]

This issue strikes me as too vague to be useful. All other things being equal, of course we want our GC to be low latency (which essentially implies incremental).

[StefanKarpinski]

But I guess it's satisfying to have an issue to close when merging a new GC.

[ufechner7]

I wrote a little test script:
https://gist.github.com/ufechner7/39124402f17eee3f40a8

First of all I want to say, that the new garbage collector performs MUCH better than the old one.
With Julia 0.4.0-dev+6909 I achieve a jitter of about 2ms and a crest factor of the execution time of my workload of about 1.23. (Core i7, 3.4 GHz, sandybridge, no hyperthreading, Ubuntu 12.04).
With Julia 0.3.10 the jitter is about 20 ms and the crest factor about 2.5. This means, for the given example Julia 0.4 is by a factor of 10 better then Julia 0.3. This is already very nice.

Nevertheless:
In the paper, referenced in my first comment a maximal jitter of only 57 us (microseconds) was reported for Lua. Ok, they used a different test program, so you cannot compare the results. Soon I want to implement the same test program in Lua and Python to have a realistic comparison. I am pretty sure, that the jitter can be reduced much more than the 2 ms of Julia 0.4. Half a millisecond would be nice.

To run the test script type:
include("RealTime.jl")
main()

[ufechner7]

The good performance of the new garbage collector is not yet mentioned in the file "News.md". What about adding a line in the section Library Improvements -> Other improvements like:
"A new, generational garbage collector was implement (see: #5227). In some use cases it can reduce the worst case time for garbage collection by a factor of ten."

[ufechner7]

But perhaps the issue #5227 should be renamed to "WIP: Implement generational garbage collector." to avoid confusion.

[ViralBShah]

Yes, we should mention the improved GC in NEWS.md.

[ufechner7]

There is a bounty for fixing this issue available:
https://www.bountysource.com/issues/5020251-implement-a-low-latency-incremental-garbage-collector

[ufechner7]

Why did you add the wont't fix label? Would also be useful for the new audio packages.

[zdnz]

Better GC -> Realtime or bust!

[StefanKarpinski]

I'm not sure why @vtjnash added the "won't fix" label. As I've said before though, having this issue around isn't really helpful. Everyone always wants better, faster GC – and no core dev is about to forget that. The bounty is similarly pointless and offers an insultingly small amount of money for something that has literally cost tens of millions of dollars to achieve in other systems.