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

Reference count, don't garbage collect

kevinlawler.com

Post reply on HN
Print view View original

371–380 of 415 posts

Re: Reference count, don't garbage collect

#371

Post by deterministic »

brabel wrote: post #248
deterministic wrote: post #132

Earlier quoted context omitted.

I am the maintainer of a very high-performance JIT compiler for a Haskell like rules programming language used by large enterprises around the world. It uses reference counting + a global optimisation step to reduce the reference count updates to an absolute minimum. The result is compiled code that runs faster than C++ code carefully hand optimised by C++ experts over a 10 year period. There are zero GC pauses. Unle…

You've gone from claiming reference-counting is faster than tracing GC to claiming it's even faster than hand optimized C++, which is quite honestly unbelievable - whatever the reference counting algorithm is doing can be emulated by the hand-optimised C++ code so that's just literally impossible. But anyway, it's a completely fruitless discussion here unless you provide data that we can look at and scrutinize. OP ha…

The code is not open source unfortunately so I can’t provide evidence. But I have nothing to sell or promote (unlike the V language guys who has a clear motivation to inflate what they are selling). What the compiler does differently is that it does a whole program optimisation pass where it minimises the code manipulating the reference counters to an absolute minimum. This is something you can’t do in a C++ compiler. Which is one of the reason why the resulting machine code is faster. Also, I am using LLVM as the backend. So I am getting the same low-level optimisations that C++ compilers get. However the most important optimisations are done before lowering the code to LLVM. Function specialisation for example is huge (generating multiple versions of the same function with the arguments unlined and optimised away). I am doing quite a few high level optimisations like that before even lowering it to LLVM.

Re: Reference count, don't garbage collect

#372

Post by mbrodersen »

staticassertion wrote: post #312
brabel wrote: post #248

Earlier quoted context omitted.

You've gone from claiming reference-counting is faster than tracing GC to claiming it's even faster than hand optimized C++, which is quite honestly unbelievable - whatever the reference counting algorithm is doing can be emulated by the hand-optimised C++ code so that's just literally impossible. But anyway, it's a completely fruitless discussion here unless you provide data that we can look at and scrutinize. OP ha…

> whatever the reference counting algorithm is doing can be emulated by the hand-optimised C++ code so that's just literally impossible. shared_ptr and unique_ptr have pretty significant overhead and are common practice, even for optimized codebases, so I wouldn't say it's impossible at all.

You are 100% right. At some point I measured smart_ptr to be 25x slower than raw pointers. The compiler I am maintaining is not using C++ style smart pointers. It is using a global whole program optimisation pass to reduce reference manipulation to a minimum. Basically what a world class C++ programmer with years of experience optimising performance would do. It is just done automatically.

Re: Reference count, don't garbage collect

#373

Post by mbrodersen »

yakubin wrote: post #304
deterministic wrote: post #132

Earlier quoted context omitted.

I am the maintainer of a very high-performance JIT compiler for a Haskell like rules programming language used by large enterprises around the world. It uses reference counting + a global optimisation step to reduce the reference count updates to an absolute minimum. The result is compiled code that runs faster than C++ code carefully hand optimised by C++ experts over a 10 year period. There are zero GC pauses. Unle…

What happens in your language when a linked list is freed? Doesn't running its destructor (or its equivalent) take a linear amount of time relative to the length of the list?

The compiler uses arrays not linked lists. One of the big mistakes that other functional compilers make (IMHO) is that they use linked lists. It is a huge performance problem. There is a reason why high-performance software written in C++ and C always use arrays and not linked lists. Memory access patterns is the #1 thing to optimise for on modern CPUs.

Re: Reference count, don't garbage collect

#374

Post by mbrodersen »

pclmulqdq wrote: post #147
deterministic wrote: post #132

Earlier quoted context omitted.

I am the maintainer of a very high-performance JIT compiler for a Haskell like rules programming language used by large enterprises around the world. It uses reference counting + a global optimisation step to reduce the reference count updates to an absolute minimum. The result is compiled code that runs faster than C++ code carefully hand optimised by C++ experts over a 10 year period. There are zero GC pauses. Unle…

The global optimization step is often what people commonly refer to as "garbage collection." Putting it inside a framework to RC as few times as possible is pretty cool. However, I doubt the efficacy of your C++ experts: most of the people I know who write C++ are actually really bad at optimizing code. They mostly use it for legacy reasons. If you get a team of experienced (and expensive) systems programmers, you wi…

The C++ code I am referring to was hand optimised and maintained for 10+ years before the compiler I am maintaining was fast enough to take over. I never looked at the C++ code myself. I simply use it as the milestone to beat. When I took over the maintenance of the compiler it was 25x slower than the C++ code. It took a lot of work to finally make it faster. I also used the C++ code to compare the output of the compiler and the C++ code. I found quite a few bugs in the C++ code doing that by the way.

Re: Reference count, don't garbage collect

#375

Post by mbrodersen »

dataflow wrote: post #283
pclmulqdq wrote: post #147

Earlier quoted context omitted.

The global optimization step is often what people commonly refer to as "garbage collection." Putting it inside a framework to RC as few times as possible is pretty cool. However, I doubt the efficacy of your C++ experts: most of the people I know who write C++ are actually really bad at optimizing code. They mostly use it for legacy reasons. If you get a team of experienced (and expensive) systems programmers, you wi…

What I understood from their comment (which may not be correct) is the following. Say you have something like this: extern void foo(T *p); // some arbitrary function void bar1(bool cond) { .. auto p = std::make_unique (); if (cond) { return foo(p.release()); } ... } This requires the compiler to call your_deleter::operator() regardless of whether cond is true or false, even though it's unnecessary (and can thus be sl…

Yep you are quite right. The optimiser basically does what an experienced C++ optimisation experts would (tediously) do by hand: it carefully reduces the number of reference counter modifications to an absolute minimum by symbolically evaluating the full executing flow of the code. It is something that is doable in a pure functional language like this one. I am not sure if it is possible to do the same in C++ (because of the aliasing rules).

Re: Reference count, don't garbage collect

#376

Post by mbrodersen »

viraptor wrote: post #141
deterministic wrote: post #132

Earlier quoted context omitted.

I am the maintainer of a very high-performance JIT compiler for a Haskell like rules programming language used by large enterprises around the world. It uses reference counting + a global optimisation step to reduce the reference count updates to an absolute minimum. The result is compiled code that runs faster than C++ code carefully hand optimised by C++ experts over a 10 year period. There are zero GC pauses. Unle…

How do you collect cycles without a pause?

The language has zero data cycles by design. It turns out that we didn’t need it. Thinking about it, I can’t remember even a single situation in my 30+ years career where I needed a data structure with data cycles. There are usually better ways to do it in my experience.

Re: Reference count, don't garbage collect

#377

Post by mbrodersen »

dataflow wrote: post #169
viraptor wrote: post #141

Earlier quoted context omitted.

How do you collect cycles without a pause?

I'm gonna take a guess they dedicate a core to GC (or something along these lines).

No each thread does it’s own alloc/free. I reduce the locking to a minimum by using per-thread caching and memorisation. I had to implement that to make the code scale linearly with number of cores. Without per-thread caching it would only scale to about 3 cores. Now it scales very cleanly. Which is nice.

Re: Reference count, don't garbage collect

#378

Post by mbrodersen »

bitcharmer wrote: post #259
Bolkan wrote: post #222

Earlier quoted context omitted.

Pics or gtfo.

Yeah, GP's claim is completely bonkers. And they haven't provided any links or data to back up their nonsensical claim.

Yep the code is not open source so I can’t provide that. However I am happy to explain exactly how it works down to the lowest level details. Perhaps somebody gets inspired to implement it themselves as open source? That would be neat.

Re: Reference count, don't garbage collect

#379

Post by mbrodersen »

pclmulqdq wrote: post #147
deterministic wrote: post #132

Earlier quoted context omitted.

I am the maintainer of a very high-performance JIT compiler for a Haskell like rules programming language used by large enterprises around the world. It uses reference counting + a global optimisation step to reduce the reference count updates to an absolute minimum. The result is compiled code that runs faster than C++ code carefully hand optimised by C++ experts over a 10 year period. There are zero GC pauses. Unle…

The global optimization step is often what people commonly refer to as "garbage collection." Putting it inside a framework to RC as few times as possible is pretty cool. However, I doubt the efficacy of your C++ experts: most of the people I know who write C++ are actually really bad at optimizing code. They mostly use it for legacy reasons. If you get a team of experienced (and expensive) systems programmers, you wi…

Just to clarify: it is not a framework. It is a whole program optimisation pass done by the compiler before lowering the intermediate code to LLVM and then generating machine code.

Re: Reference count, don't garbage collect

#380

Post by mbrodersen »

pkolaczk wrote: post #253
viraptor wrote: post #141

Earlier quoted context omitted.

How do you collect cycles without a pause?

I simply don't do cycles. Software is simpler without them.

Agree. I can’t even come up with an example that couldn’t be done better without them.
Post reply on HN