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

A Tour of Safe Tracing GC Designs in Rust

manishearth.github.io

Post reply on HN
Print view View original

21–30 of 61 posts

Re: A Tour of Safe Tracing GC Designs in Rust

#21

Post by an_opabinia »

joppy wrote: post #5
amelius wrote: post #4

Wouldn't it make more sense to have garbage collectors at the level of LLVM? That way, you could have direct access to all the pointers in a program without jumping through the language's hoops. And other languages could benefit from it too.

Yes, it makes total sense for the garbage collector to be tightly coupled to the memory allocation system, which is also tightly coupled to code generation (as is done in the case of various high-performance managed languages: Java, C#, Haskell, …). I remember hearing a talk a few years ago about a system of the kind you’re talking about - a kind of “managed language” micro-core that ran alongside LLVM so that it cou…

The performance is still too bad for anything but Java on real applications. The other killer feature, ahead of time compilation, is really clunky, and its most innovative change, static initialization at build time by default, was reverted to runtime initialization.

Re: A Tour of Safe Tracing GC Designs in Rust

#22

Post by pjmlp »

astrange wrote: post #20
pjmlp wrote: post #18

Earlier quoted context omitted.

Actually it is the other way around. https://github.com/ixy-languages/ixy-languages No wonder that M1 has specific architecture optimizations that help streamline ARC boilerplate code, while Swift 5.5 will bring more aggressive optimizations (disabled by default, because application can crash if weak/owned references are annotated improperly => WWDC 2021 talk)

This isn't representative of application code and there isn't even any mention of the metrics I mentioned… > No wonder that M1 has specific architecture optimizations that help streamline ARC boilerplate code No it doesn't. I told you it didn't the last time you said this.

> This isn't representative of application code and there isn't even any mention of the metrics I mentioned…

Yeah, that is the usual answer when benchmarks prove how much urban myth reference counting performance is actually like.

> No it doesn't. I told you it didn't the last time you said this.

Did you?

There is more important stuff in life to store on my brain than a list of who replies to me on hacker news.

Anyway,

https://github.com/apple/swift/blob/main/stdlib/public/Swift...

https://twitter.com/ErrataRob/status/1331735383193903104

Re: A Tour of Safe Tracing GC Designs in Rust

#23

Post by astrange »

pjmlp wrote: post #22
astrange wrote: post #20

Earlier quoted context omitted.

This isn't representative of application code and there isn't even any mention of the metrics I mentioned… > No wonder that M1 has specific architecture optimizations that help streamline ARC boilerplate code No it doesn't. I told you it didn't the last time you said this.

> This isn't representative of application code and there isn't even any mention of the metrics I mentioned… Yeah, that is the usual answer when benchmarks prove how much urban myth reference counting performance is actually like. > No it doesn't. I told you it didn't the last time you said this. Did you? There is more important stuff in life to store on my brain than a list of who replies to me on hacker news. Anywa…

> Yeah, that is the usual answer when benchmarks prove how much urban myth reference counting performance is actually like.

CPU/wall time benchmarks are not that relevant to system performance (seriously!) because second-order effects matter more. But if you had peak memory and page demand graphs that would matter.

For a network driver I don't know if it'd really look any different though. That's mostly arena allocations.

> https://twitter.com/ErrataRob/status/1331735383193903104

The fast atomics and JavaScript instructions do exist but aren't "special", they're just part of the ARM ISA.

Re: A Tour of Safe Tracing GC Designs in Rust

#24

Post by celeritascelery »

zozbot234 wrote: post #17
tialaramex wrote: post #15

Earlier quoted context omitted.

> particularly as people finally attempt to mitigate the waste of moving to 64-bit by using tagged pointers It's very fraught to try to "mitigate the waste" at the top of the pointer. Everybody involved is clear that what you're doing there is saving up pain for yourself because periodically more of those "wasted" bits become significant and each time that happens if you've been using them now you've incurred a maint…

> Whereas if I steal ten bits at the top of the pointer, when Intel ships Ice Lake CPUs my compiler now crashes. Good luck debugging that! That's not how it works. The x86-64 ISA requires these "top" bits to be properly sign extended when actually accessing addresses, so any binary code that's using this "trick" is forward compatible wrt. future CPU's that might enable a bigger virtual address space. The only concern…

Until the virtual address space gets so big that there are no bits left at the top that are "free". As soon as you have a 64 bit virtual address space, pointer tagging the top bits no longer works. Your program is now broken on the new CPU.

Re: A Tour of Safe Tracing GC Designs in Rust

#25

Post by celeritascelery »

pjmlp wrote: post #22
astrange wrote: post #20

Earlier quoted context omitted.

This isn't representative of application code and there isn't even any mention of the metrics I mentioned… > No wonder that M1 has specific architecture optimizations that help streamline ARC boilerplate code No it doesn't. I told you it didn't the last time you said this.

> This isn't representative of application code and there isn't even any mention of the metrics I mentioned… Yeah, that is the usual answer when benchmarks prove how much urban myth reference counting performance is actually like. > No it doesn't. I told you it didn't the last time you said this. Did you? There is more important stuff in life to store on my brain than a list of who replies to me on hacker news. Anywa…

Thanks for sharing these links! Super interesting. I do have a question though. The ixy benchmarks seem to imply that RC is generally slower then GC (go and C# are much faster then swift and are only outdone by languages with manual memory management).

However in the tweet thread you shared, the poster said

> all that reference counting overhead (already more efficient than garbage collection) gets dropped in half.

Implying that reference counting is actually more efficient. I don't know how to rectify these two observations. Do you have any insights?

Re: A Tour of Safe Tracing GC Designs in Rust

#26

Post by tialaramex »

zozbot234 wrote: post #17
tialaramex wrote: post #15

Earlier quoted context omitted.

> particularly as people finally attempt to mitigate the waste of moving to 64-bit by using tagged pointers It's very fraught to try to "mitigate the waste" at the top of the pointer. Everybody involved is clear that what you're doing there is saving up pain for yourself because periodically more of those "wasted" bits become significant and each time that happens if you've been using them now you've incurred a maint…

> Whereas if I steal ten bits at the top of the pointer, when Intel ships Ice Lake CPUs my compiler now crashes. Good luck debugging that! That's not how it works. The x86-64 ISA requires these "top" bits to be properly sign extended when actually accessing addresses, so any binary code that's using this "trick" is forward compatible wrt. future CPU's that might enable a bigger virtual address space. The only concern…

> That's not how it works. The x86-64 ISA requires these "top" bits to be properly sign extended when actually accessing addresses.

On Coffee Lake no more than 48 bits of the virtual address are "real". If I steal ten of the 64 bits from the top, all the actual address information is preserved and I've lost nothing. My compiler works just fine.

On Ice Lake up to 57 bits of the virtual address are "real". Since I'm stealing ten of the 64 bits from the top, I only have 54 bits left, so 3 significant bits were dropped and I don't have them any more. Sign-extending the wrong value won't magically make it into the right value.

Re: A Tour of Safe Tracing GC Designs in Rust

#27

Post by devit »

celeritascelery wrote: post #24
zozbot234 wrote: post #17

Earlier quoted context omitted.

> Whereas if I steal ten bits at the top of the pointer, when Intel ships Ice Lake CPUs my compiler now crashes. Good luck debugging that! That's not how it works. The x86-64 ISA requires these "top" bits to be properly sign extended when actually accessing addresses, so any binary code that's using this "trick" is forward compatible wrt. future CPU's that might enable a bigger virtual address space. The only concern…

Until the virtual address space gets so big that there are no bits left at the top that are "free". As soon as you have a 64 bit virtual address space, pointer tagging the top bits no longer works. Your program is now broken on the new CPU.

Of course competent programmers using the top K bits of the pointer would make sure that the kernel and memory allocator operate so that they don't allocate memory outside a (64 - K)-bit address space, regardless of what the CPU supports (e.g. Linux mmap as one would expect won't allocate beyond 2^48 unless explicitly requested).

And obviously any intelligent CPU architect, if they make a CPU that masks the upper bits, they would make the number of bits that gets masked configurable per-process and not dependent on the maximum virtual address space supported by the CPU.

Re: A Tour of Safe Tracing GC Designs in Rust

#28

Post by pjmlp »

celeritascelery wrote: post #25
pjmlp wrote: post #22

Earlier quoted context omitted.

> This isn't representative of application code and there isn't even any mention of the metrics I mentioned… Yeah, that is the usual answer when benchmarks prove how much urban myth reference counting performance is actually like. > No it doesn't. I told you it didn't the last time you said this. Did you? There is more important stuff in life to store on my brain than a list of who replies to me on hacker news. Anywa…

Thanks for sharing these links! Super interesting. I do have a question though. The ixy benchmarks seem to imply that RC is generally slower then GC (go and C# are much faster then swift and are only outdone by languages with manual memory management). However in the tweet thread you shared, the poster said > all that reference counting overhead (already more efficient than garbage collection) gets dropped in half. I…

The observation is done by point of view of Swift developers.

The only reason why Swift has reference counting was historical.

Objective-C GC implementation failed, because it was very hard to mix frameworks compiled with and without GC enabled, alongside the usual issues of C memory semantics.

https://developer.apple.com/library/archive/documentation/Co...

Check "Inapplicable Patterns" section.

So Apple did the right design decision, instead of trying to fix tracing GC in such environment, just like Microsoft does in COM, they looked into Cocoa [retain/release] pattern, automated that, and in a marketing swoop sold that solution as ARC.

Swift as Objective-C replacement, naturally had to build on top of ARC as means to keep compatibility with Objective-C runtime without additional overhead (check RCW/CCW for how .NET GC deals with COM).

Here is a paper about Swift performance,

http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf

> As shown in the figure, performing RC operations takes on average 42% of the execution time in client programs, and 15% in server programs. The average across all programs can be shown to be 32%. The Swift compiler does implement optimization techniques to reduce the number of RC operations similar to those described in Section 2.2.2. Without them, the overhead would be higher. The RC overhead is lower in server programs than in client programs. This is because server programs spend relatively less time in Swift code and RC operations; they spend relatively more time in runtime functions for networking and I/O written in C++.

It makes technical sense that Swift uses reference counting, as explained above, but it isn't due to performance, it just sells better than explaining it was due to Objective-C inherited C memory model, which besides the memory corruption problems, it doesn't allow for anything better than a conservative garbage collector, with very bad performance.

https://hboehm.info/gc/

Re: A Tour of Safe Tracing GC Designs in Rust

#29

Post by celeritascelery »

devit wrote: post #27
celeritascelery wrote: post #24

Earlier quoted context omitted.

Until the virtual address space gets so big that there are no bits left at the top that are "free". As soon as you have a 64 bit virtual address space, pointer tagging the top bits no longer works. Your program is now broken on the new CPU.

Of course competent programmers using the top K bits of the pointer would make sure that the kernel and memory allocator operate so that they don't allocate memory outside a (64 - K)-bit address space, regardless of what the CPU supports (e.g. Linux mmap as one would expect won't allocate beyond 2^48 unless explicitly requested). And obviously any intelligent CPU architect, if they make a CPU that masks the upper bit…

> Of course competent programmers ... And obviously any intelligent CPU architect

Interesting to see the future is so "obvious" to you. You are correct however, that this is not a problem at the present because no architecture uses more then 48-bits of address space in practice. And since this is such a common practice now, there will have to allowances made in the future for when the address space is expanded.

Re: A Tour of Safe Tracing GC Designs in Rust

#30

Post by xfer »

tialaramex wrote: post #15
saurik wrote: post #6

Earlier quoted context omitted.

The concept of what a pointer "is" is somewhat language-dependent, particularly as people finally attempt to mitigate the waste of moving to 64-bit by using tagged pointers (which maybe could try to be modelled in LLVM also, but I think you will rapidly realize that LLVM just isn't modeling a lot of things that affect scanning).

> particularly as people finally attempt to mitigate the waste of moving to 64-bit by using tagged pointers It's very fraught to try to "mitigate the waste" at the top of the pointer. Everybody involved is clear that what you're doing there is saving up pain for yourself because periodically more of those "wasted" bits become significant and each time that happens if you've been using them now you've incurred a maint…

Isn't using bottom bit is how most runtimes represent their ints taking advantage of the fact that gc pointers are aligned? This is common practice afaiu.
Post reply on HN