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

31–40 of 43 posts

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

#31

Post by hyustan »

Surprised not see any talk about slab allocations.

Typical malloc implementations today use slabs:

A variety of allocation-classes is defined; for example, 1B, 2B, 4B, 8B, ...

Each allocation-class is essentially its own independent heap.

Slabs are really good:

Allocation is fast: a few cycles to determine the slab, then pick the first available cell, done.

Compaction is easy: all cells have the same size!

And I repeat, all cells within an allocation-class have the same size! This means things like pin cards, etc...

Compared to the pointer-chasing inherent to a splay-tree... I do wonder.

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

#32

Post by woadwarrior01 »

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.

That’s because package version selection is a SAT problem.

https://research.swtch.com/version-sat

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

#33

Post by fjfaase »

What about the following strategy: Find the first space that is large enough. If it is smaller than double the size of the required, take it. (A little more space is allocated than would be strictly needed.) If it larger than double the size, split it. This leaves a piece that is at least as big as the current size. Assuming that the allocations have some distribution, it is likely that another piece of memory with this size will be allocated in the future. In this way, the distribution of available spaces will remain about the same as the wanted spaces. (Of course, one should also first round up the size to some power of two and possibly implement a minimum size.)

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

#34

Post by imtringued »

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…

The real problems are conventions and ease of use. You're not going to solve these problems by pointing at a paper from the 80s and shouting "We did this 40 years ago! Why is everyone so dumb nowadays?".

Lets take WebAssembly as an example. It's only reason for existence is convention. You need everyone to agree on an IR that is not only cross platform and stable but also low level and allows execution of untrusted code within a sandbox.

If you look at competitors then it becomes obvious that they are not following these core principles. LLVM IR just isn't meant to be used in a browser. JVM bytecode just wasn't meant to be used in a browser. So what are we going to do? Use them anyway? That's how you get situations like the horribly insecure JVM plugin. You can restrict the JVM plugin to a subset that is secure enough for browsers and add additional opcodes for low level behaviors but then you are no longer using JVM bytecode. It's a completely new invention at that point but Oracle will still hunt you down.

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

#35

Post by StreamBright »

whateveracct wrote: post #18
StreamBright wrote: post #15

Earlier quoted context omitted.

I guess this mentality leads to the current state of play where all UI related latencies are out of the roof compare to the 80s. At work, I deal with systems that require 16G of heap as the minimum. Funnily when things get rewritten in Rust providing the exact same functionality and the same or better performance the memory requirement goes down 10x (or more). It is up to us how much garbage our systems producing, ho…

I've seen multiple production systems rewritten in Rust and the consensus of the developers working on it is that, while the Rust version was more performant, the majority of that performance is attributable to the rewrite itself and not the language. And that a performance-focused rewrite in the original language would have also seen huge performance gains. As the truism goes, if you require your software to be perf…

Sure I bet they feel this way. However, if you look at rewrites like the one at Discord[1], it is dead obvious that the rewrite helped not because of the rewrite by itself but because there is no GC (mostly) and some other smaller things (better data structures for certain tasks). In my experience working a lot for the fortune 500 in the last 15 years is that developers are usually not aware of the low level details of their stack including (but not limited to): networking, garbage collection, concurrency, parallelism. It is the exception (mostly in FAANG companies) when these low level details a very well understood and dealt with. It is no surprise that these companies are picking up Rust because those developers actually understand how much less mental overhead is to work in Rust (once it compiles successfully :) ). I know it is a new language and there are hoops (async/await) but at least we can be sure that there is no need for GC tuning, memory corruption is non existent and a few nice additional properties.

In my mind performance is alway a requirement (and a feature). We just stopped caring a long time ago, because it is easier to think about performance as a hardware or capacity problem, memory as GC problem and so on.

1. https://blog.discordapp.com/why-discord-is-switching-from-go...

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

#36

Post by judofyr »

fjfaase wrote: post #33

What about the following strategy: Find the first space that is large enough. If it is smaller than double the size of the required, take it. (A little more space is allocated than would be strictly needed.) If it larger than double the size, split it. This leaves a piece that is at least as big as the current size. Assuming that the allocations have some distribution, it is likely that another piece of memory with t…

Sounds similar to a buddy allocator: https://en.wikipedia.org/wiki/Buddy_memory_allocation

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

#37

Post by hyperman1 »

imtringued wrote: post #34
hinkley wrote: post #21

Earlier quoted context omitted.

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…

The real problems are conventions and ease of use. You're not going to solve these problems by pointing at a paper from the 80s and shouting "We did this 40 years ago! Why is everyone so dumb nowadays?". Lets take WebAssembly as an example. It's only reason for existence is convention. You need everyone to agree on an IR that is not only cross platform and stable but also low level and allows execution of untrusted c…

This is a bit harsh. JVM byte code was meant to be in the browsers of that time. Plugins were a respected part of the ecosystem back then. There were 2 types of security problems.

The majority were not bytecode related, but were bugs in the interface to the outside world. There is no reason why WebAssembly is better in this regard. E.g. webglvs java' s graphic APIs. This mainly comes from corporate culture prioritizing security. If financial hardship or other stresses befalls the browser maker, webassembly will probably give the same trouble as java had.

The minority were related to the soundness of the jvm itself. Most of these have been fixed. These bugs are in general nasty, as the basics have been valisated by a mathematical proof. A few are still there and very hard to fix, like locking system objects like Thread.class I think this was a learning experience for all secure VMs that follow it, and WebAssembly knew what to avoid because of Java. Only time will tell how good WebAssembly withstands the nasty ideas humanity throws at it.

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

#38

Post by k__ »

gopiandcode wrote: post #25
k__ wrote: post #7

Earlier quoted context omitted.

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.

I mean, game developers, not OCaml devs

The point was, they said "do manaual memory management" if you want speed.

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

#39

Post by joppy »

StreamBright wrote: post #16
k__ wrote: post #7

Earlier quoted context omitted.

What's their opinion on Rust?

Great question. I am really hoping that the non-GC world is taking off with Rust.

How does Rust deal with long-lived objects that cannot be block-scoped (or request-scoped, in the context of a server for example)? A typical example here would be a UI framework, where memory has to be managed for the window and its widgets, and then the entire application is suspended until the next event. The user can open and close windows in random orders, and so on. Perhaps some windows generate a lot of associated data which should be disposed of when that window closes, but can also be dragged over into the other windows and duplicated around, so the data is not “owned” by a single window.

It seems to me that this is where the GC “set and forget” model really shines, since otherwise you just have to do all that work manually using an allocation and a free, or a constructor and a destructor, or some similar pattern. Perhaps Rust has some clever answer for this?

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

#40

Post by nitnelave »

joppy wrote: post #39
StreamBright wrote: post #16

Earlier quoted context omitted.

Great question. I am really hoping that the non-GC world is taking off with Rust.

How does Rust deal with long-lived objects that cannot be block-scoped (or request-scoped, in the context of a server for example)? A typical example here would be a UI framework, where memory has to be managed for the window and its widgets, and then the entire application is suspended until the next event. The user can open and close windows in random orders, and so on. Perhaps some windows generate a lot of associ…

It seems like you want a reference-counted pointer: you get shared ownership, and the object is deleted when the last reference to the pointer is deleted.

Similar to C++'s std::shared_ptr

Post reply on HN