Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An in-depth look at OCaml’s new “best-fit” garbage collector strategy

ocamlpro.com

Post reply on HN
Print view View original

21–30 of 43 posts

Re: An in-depth look at OCaml’s new “best-fit” garbage collector strategy

#21

Post by hinkley »

jjoonathan wrote: post #6

Hell is other peoples' algorithmic choices. My GC-fu isn't high level enough to comment on this one, but I just spent the last two days suffering in dependency hell because someone thought it would be a good idea to use a full-blown SAT solver for package management. Grr.

Sometimes I have lamented the fact that 80% of everything we're ever going to properly discover in Computer Science has already been discovered forty years ago.

What hasn't been explored very well is how to formulate these solutions so mere mortals can comprehend how they work. Algorithms accessibility is, I believe, the limiting factor on building systems any bigger than the ones we have now. When there is one tricky bit in the code, you can get away with asking people to dive in and learn it. When there are 50? 100? Just figuring out the consequences of how those systems interact is a full time job, let alone how they function internally.

Give me a SAT solver, or a parser, or half a dozen other things, that decomposes a problem the way a human would do it, just faster and with far more accuracy, and I could learn it in a week. Take all my Paxoses and replace them with Raft, then swing by and make a second pass on a few.

Re: An in-depth look at OCaml’s new “best-fit” garbage collector strategy

#22

Post by loopback_device »

sgrove wrote: post #13
marcinzm wrote: post #12

Earlier quoted context omitted.

>"It's interesting that many games can afford a constant 10x interpretation overhead for scripts, but not a spikey 1% for garbage collection." Why is that surprising? Games are basically about humans predicting things and random spikes prevent that from happening in time sensitive games. Beyond game play implications, I suspect there's also something about jerkiness in movement that bugs human senses.

It's not entirely surprising, but one might imagine a different approach: always allocate a 1% buffer for an unexpected GC. It's not a very satisfactory answer (and there are likely much better tradeoffs to be made), but given the 10x and 1% comparison (not entirely apples to apples though) the comment sounds a bit more interesting.

How do you allocate a 1% buffer of time? The GC issue in games (or any other timing sensitive application) is about the "world freezing", not memory. Which is why incremental GC is a thing. At best, you're borrowing time.

Re: An in-depth look at OCaml’s new “best-fit” garbage collector strategy

#23

Post by cwzwarich »

jjoonathan wrote: post #11
ignoramous wrote: post #8

Earlier quoted context omitted.

> ...someone thought it would be a good idea to use a full-blown SAT solver for package management Relevant: https://research.swtch.com/version-sat

Right. SAT solvers are an excellent theoretical fit and a terrible practical fit, at least at the current state of tooling. Their runtime _does_ explode and the tooling _is not_ any good at hinting as to why even when the explanation turns out to be very simple. "lol install takes an hour now" makes for a very poor error message, and debugging a black box that takes an hour to evaluate each input is just.... uggggggh…

Do you have an example of a real-world package dependency situation that generates a truly difficult SAT instance?

Re: An in-depth look at OCaml’s new “best-fit” garbage collector strategy

#24

Post by exsf0859 »

sgrove wrote: post #13
marcinzm wrote: post #12

Earlier quoted context omitted.

>"It's interesting that many games can afford a constant 10x interpretation overhead for scripts, but not a spikey 1% for garbage collection." Why is that surprising? Games are basically about humans predicting things and random spikes prevent that from happening in time sensitive games. Beyond game play implications, I suspect there's also something about jerkiness in movement that bugs human senses.

It's not entirely surprising, but one might imagine a different approach: always allocate a 1% buffer for an unexpected GC. It's not a very satisfactory answer (and there are likely much better tradeoffs to be made), but given the 10x and 1% comparison (not entirely apples to apples though) the comment sounds a bit more interesting.

The problem is that with most GC algorithms 1% of the frames take 2x (or even 20x) as long, not that individual frame times vary by 1%.

Re: An in-depth look at OCaml’s new “best-fit” garbage collector strategy

#25

Post by gopiandcode »

k__ wrote: post #7
StreamBright wrote: post #2

"Remember that whatever works best for you, it’s still better than having to malloc and free by hand. Happy allocating!" Nice, they are saying exactly the same as those pesky game developers. https://www.youtube.com/watch?v=tK50z_gUpZI

What's their opinion on Rust?

Before self-hosting, the rust compiler was originally in OCaml so presumably there's an overlap in communities there.

Re: An in-depth look at OCaml’s new “best-fit” garbage collector strategy

#26

Post by rlp »

twic wrote: post #3

I'm not aware of any other industrial-strength GC using this strategy. Are there any? If not, is there something about OCaml that makes this strategy more suitable than it is for other languages? If not, is this a case of this being the best strategy they have the resources to implement, rather than the best possible strategy?

It's not exactly an industrial-strength GC, but Nim uses TLSF to reduce fragmentation: http://www.gii.upv.es/tlsf/. I'm not sure how that compares to the strategy in the article, though.

Re: An in-depth look at OCaml’s new “best-fit” garbage collector strategy

#28

Post by jeffdavis »

hinkley wrote: post #21
jjoonathan wrote: post #6

Hell is other peoples' algorithmic choices. My GC-fu isn't high level enough to comment on this one, but I just spent the last two days suffering in dependency hell because someone thought it would be a good idea to use a full-blown SAT solver for package management. Grr.

Sometimes I have lamented the fact that 80% of everything we're ever going to properly discover in Computer Science has already been discovered forty years ago. What hasn't been explored very well is how to formulate these solutions so mere mortals can comprehend how they work. Algorithms accessibility is, I believe, the limiting factor on building systems any bigger than the ones we have now. When there is one trick…

It's hard to optimize algorithms while also making them general and composable. We are forever reimplementing good ideas in different combinations of systems.

Re: An in-depth look at OCaml’s new “best-fit” garbage collector strategy

#29

Post by otabdeveloper2 »

pjmlp wrote: post #10
StreamBright wrote: post #2

"Remember that whatever works best for you, it’s still better than having to malloc and free by hand. Happy allocating!" Nice, they are saying exactly the same as those pesky game developers. https://www.youtube.com/watch?v=tK50z_gUpZI

Yeah, like Tim Sweeney. "It's interesting that many games can afford a constant 10x interpretation overhead for scripts, but not a spikey 1% for garbage collection." https://twitter.com/timsweeneyepic/status/880607734588211200 https://wiki.unrealengine.com/Garbage_Collection_Overview Which was it again, the engine chosen by Nintendo, Microsoft and Google as first party to their 3D APIs? https://developer.nintendo.com…

The problem with GC isn't the "spikey 1%", it's the fact that GC implies the "everything is a pointer to an object" programming model, which in turn fragments your memory and destroys your cache.

Performance-oriented code implies everything is on the stack and/or packed into large arrays, at which point you don't need a GC after all.

Re: An in-depth look at OCaml’s new “best-fit” garbage collector strategy

#30

Post by _old_dude_ »

hinkley wrote: post #9
the8472 wrote: post #4

Earlier quoted context omitted.

I think the hotspot's CMS old gen allocator used best-fit strategy since its collector didn't compact. But CMS has been deprecated because newer, compacting low pause collectors have taken over its use-cases while being less fragile.

If memory serves, the new one uses an extra object header that points from the old object to the new one during move operations, and any reads of the old object get forwarded to the new one. I'm pretty sure that would have not performed well without the aggressive prediction logic in modern processors. Java 1's object accesses always read through an indirect pointer, but that went away in the name of performance, eit…

They are two new GCs Shenandoah and ZGC.

Indirect pointers or Brooks pointers has it is called were used in Shenandoah v1 to allow an application thread that perform a read to not move the object during the evacuation phase. This strategy has been removed in Shenandoah v2 to have a better throughput so now both read and write by the application move the object during the evacuation phase.

ZGC has never used Brooks pointers.

Post reply on HN