9 ms·

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 re

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. Unless you claim that a C++ alloc/feee call is “garbage collection”. Which is not common terminology. It also (BTW) scales linearly the more cores you throw at it.

refulgentis 4y ago
I'm not sure whats being asserted here, could you explain more? This sounds like you're describing a non-stopping GC, and its well understood reference counting is garbage collection. I'm not sure how the rest applies, you're correct, it is possible to write software with just malloc and free.
- cakoose 4y ago
  Re: "it's well understood reference counting is garbage collection". I think this might just be a terminology thing. There appear to be two ways the terms are categorized: 1. "reference counting" and "garbage collection" are two types of automatic memory management/reclamation. 2. "reference counting" and "tracing garbage collection" are two types of garbage collection. I think mbrodersen is using #1. (Back in the 90s and 2000s I feel like #1 was much more prevalent. But #2 seems to have gained popularity since then. My theory is that whoever started writing the Wikipedia content for this stuff picked #2.)
  - rowanG077 4y ago
    I never understand why people refer to reference counting as garbage collection. It waters down the term so much it becomes essentially useless. Because under that assumptions basically every language has garbage collection in some shape or form.
    - jstanley 4y ago
      C doesn't have garbage collection. Furthermore, pretty much every language has I/O, but that doesn't make the term useless.
    - tsimionescu 4y ago
      They do it because they serve the same purpose, though with different trade-offs. Note that this mostly reflects automatic reference counting, like you have in Python or Swift, not so much manual reference counting like std::shared_ptr or Rc.
    - pjmlp 4y ago
      Because we have studied the literature instead of what a random dude in tells at a coffee https://gchandbook.org/ https://gchandbook.org/ https://www.sigplan.org/ https://www.sigplan.org/ https://ieeexplore.ieee.org/Xplore/home.jsp https://ieeexplore.ieee.org/Xplore/home.jsp
      - rowanG077 4y ago
        Nice appeal to authority instead of trying to engage in a meaningful way.
        pjmlp 4y ago
        When one is open to learning, the best path to enlightenment is to use the same books as the Wizards on the tower of knowledge.
  - tsimionescu 4y ago
    I think this is actually common in the literature, it has nothing to do with Wikipedia. Consider that Python is commonly described as a GC language, though it has always mostly relied on automatic reference counting to free objects (it does have a tracing GC as well to handle cycles, but I'm not sure if it always did).
    - int_19h 4y ago
      I would argue that what matters is the observable behavior. In Python, regardless of how the actual cleanup is distributed between ARC and GC, the behavior that programmer sees is that all unused memory gets cleaned up eventually. So, it makes sense to group it with languages that provide the same guarantee.
  - bjourne 4y ago
    I think it's more of an industry vs. academia kind of thing. In the mid-90's before Java was released automatic memory management was mostly unknown to the unwashed masses. So garbage collection became synonymous to whatever Java was doing. However, The Garbage Collection Handbook originally published in 1996 defines garbage collection as: "All garbage collection schemes are based on one of four fundamental approaches; mark-sweep collection, copying collection, mark-compact collection or reference counting." So that's an example of terminology #2.
  - mbrodersen 4y ago
    Yep. The compiler generates code that works the same way that an experienced C programmer would hand optimise alloc/free calls and manually keep track of shared data by increasing/reducing a reference counter. There is no separate mark/sweep or whatever step.
viraptor 4y ago
How do you collect cycles without a pause?
- eru 4y ago
  There are solutions to this one. Real time garbage collectors are a thing. You just might not be able to collect the cycle in one GC run. Or you can do what Erlang does: Erlang has neither mutation nor laziness, so you can't create cycles. The GC also lays out object in topological order in memory, so that you can detect garbage without tracing every life object.
  - omginternets 4y ago
    Where can I read about Erlang’s magic?
    - eru 4y ago
      Google suggests https://stackoverflow.com/questions/10221907/garbage-collection-and-memory-management-in-erlang https://stackoverflow.com/questions/10221907/garbage-collect...
  - viraptor 4y ago
    The comment claimed "There are zero GC pauses." Tbh, it's not clear how to interpret that. But real time simply means the pauses are guaranteed not to cross the realtime response budget. You still need to schedule the collection while the mutator is paused.
- dataflow 4y ago
  I'm gonna take a guess they dedicate a core to GC (or something along these lines).
  - viraptor 4y ago
    That's not enough. Imagine a circular linked list. GC looks at an outside pointer to item A in it. Now another thread removes A from the list and moves the outside pointer to the next item. After that, GC would see all items in the list not referenced by anything (apart from the cycle).
pclmulqdq 4y ago
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 will likely get a slightly better result than your GC algorithm.
- dataflow 4y ago
  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<T, your_deleter>(); 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 slower) in the case where cond is true. Moreover, the obvious way to avoid it is to write it "C-style": void bar2(bool cond) { .. auto p = new T(); if (cond) { return foo(p); } ... your_deleter()(p); } which can up being faster when cond is true. But this isn't something an expert would generally want to do, as now the C++ code becomes unidiomatic, fragile, and unmaintainable. In an ideal world, though, you could have an optimizer smart enough to do that transformation automatically. C++ compilers already do that in trivial cases, but they can't do it in general. My impression is that their Haskell compiler exploits the internal knowledge of what your_deleter does (i.e. reference counting) in order to optimize the code in various ways, like optimizing out such code, consolidating refcount updates, etc. And if I understand this correctly, there's no surprise at all that it can be faster than idiomatic C++ code written even by experts. The question for me isn't the expertise of their programmers. Perhaps in their case they genuinely do need to have lots of objects on the heap, have (say) tight loops where they (for whatever reason) nevertheless cannot avoid the heap allocations, and don't have much of a use for finalizers besides freeing memory. In which case, I'm not surprised their solution clearly delivers better results than the C++ equivalent. The question from me, instead, is how well they think that generalizes, such as to (a) well-written Haskell programs in general, (b) well-written C++ programs in general, and/or (c) other domains. It would be one thing if their solution delivers better results in Haskell than C++ for their use case; it would be another thing if they could claim their solution delivers better results in Haskell than C++ for most use cases.
tsimionescu 4y ago
free() calls that have to run for a data-dependent amount of time are more or less equivalent to GC pauses (assuming a concurrent GC that doesn't need to stop the world, like Java's). The most typical example is free()-ing a a linked list, which takes O(n) free() calls to free with a simple RC mechanism.
- kccqzy 4y ago
  If you are assuming GC does not need to stop the world, you can also assume that the freeing of memory (including the O(n) calls to free()) will not be done in a critical path; all memory could be handed off to a separate dedicated thread that actually calls free(). Or in a RPC or HTTP server all memory can be freed after the request has been served. It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so.
  - altfredd 4y ago
    > all memory could be handed off to a separate dedicated thread that actually calls free() That only works when you have infinite memory (or infinite CPU resources). > It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so. Only if by "not stopping the world" you mean your previous suggestion (leaking unbounded amount of memory to free() everything at some later point). When your memory is bounded, you will eventually have to stop/crash once you have run out of it. AFAIK, the best modern state of art garbage collectors have stop-the-world pauses, proportional to size of root set and/or thread count. I'd love to see an RC implementation, that does not have stop-the-world pauses at all, but that sounds as audacious as claims of perpetual motion machine.
    - andreareina 4y ago
      I don't think the gp is describing the null garbage collector, rather one that can work incrementally and concurrently with the program doing its thing. Whereas a concurrent tracing gc has the problem of data changing while it runs and so special care has to be taken not to corrupt memory.
Bolkan 4y ago
Pics or gtfo.
- bitcharmer 4y ago
  Yeah, GP's claim is completely bonkers. And they haven't provided any links or data to back up their nonsensical claim.
  - mbrodersen 4y ago
    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.
brabel 4y ago
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 hasn't provided any. You haven't provided any (and I do believe you may think you're right, but I've been in the position of being very confident of something just to be proven completely wrong by giving all my data to others to scrutinize... it's disheartening but necessary to get to the bottom of what's real). It's like the V language saying it can do memory management magically and it's much faster than Rust or whatever when they don't even have a working system yet.
- fnord123 4y ago
  > 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. There is nuance here. They claimed that their project is faster than a specific hand optimized project. Not faster than a theoretical peak performance c++ program. I've run into similar situations where python reimplementation s are faster than java because python is easier to change and fixup algorithms. And %timeit in the ipython shell is way easier than the black magic involved in profiling and benchmarking java. You also have people on rust subreddit or discourse asking for optimization help when their rust is not as fast as a Go example they wrote. Often you get buffered IO going and it's on par. But to melt faces like ripgrep and friends you often need to drop pretences and work on Vec<u8>s.
  - brabel 4y ago
    > And %timeit in the ipython shell is way easier than the black magic involved in profiling and benchmarking java Unfair criciticm... first, Java has had a REPL for several years and you can time stuff like in Python as easily... second, profiling tools in Java are some of the best available, and are not blackmagic... quite simple to use, just attach them to the running process and hit "profile". With that said: yes, I've also seen Java programs that run faster than the Rust or C counterpart. I suspect what OP saw falls into this category: a rare example that you take as a rule (maybe I misinterpreted the claim, I admit, but it does sound OP meant his Haskell program and, I assume, others which you write in the same style, cannot be beaten by the equivalent C++).
naasking 4y ago
> There are zero GC pauses. Unless you claim that a C++ alloc/feee call is “garbage collection”. Alloc/free can introduce arbitrary pauses last I checked, so yes, there are pauses. Any time doing book keeping for resources rather than running your code counts as GC time.
- MaxBarraclough 4y ago
  > Any time doing book keeping for resources rather than running your code counts as GC time. Perhaps a nitpick: memory management time, yes, but not GC time. alloc/free is manual memory management, not garbage collection.
  - naasking 4y ago
    If you're using alloc/free in your GC, which is what was being implied, then that counts as GC time.
- aaaaaaaaaaab 4y ago
  On any OS which is not hard realtime, there could be arbitrary pauses with any syscall. This is just nitpicking.
  - dento 4y ago
    Nitpicking: arbitrary pauses can occur even without syscalls, when the OS preempts the program. More nitpicking: on x86-64, SMI interrupts can cause arbitrary pauses even without any software control involved. Hard realtime on x86-64 is not possible.
    - staticassertion 4y ago
      More nitpicking: Your computer might turn off, cosmic rays might blow fuck up your RAM/CPU, Capital G God could reach down and pause the system, there's a universal quantum pause every 5.391247 × 10^-44 so that the universe can reboot, etc etc etc Orrrrr, GC pause just means pauses caused by the GC as part of its implementation's work to manage memory.
yakubin 4y ago
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?
- afiori 4y ago
  My guess is that this could be done concurrently and/or in parallel. It still take time linear in length, but dead nodes are by definition stable so it does not really matter when you free them.
  - yakubin 4y ago
    So just like with tracing GCs. You do have a pause, which you may avoid with parallelism, or smear out incrementally. If you do it in parallel, your reference counting needs to be atomic, which adds further overhead. You still need to perform all the reference counting operations for each element of the list, not just free them, because part of the list may be shared. E.g. in SML: fun replace_head_with_1 (_::xs) = 1::xs; val a = [2, 3, 4]; val b = replace_head_with_1 a; Now a and b share the tail. And a linked list is only a simple demonstration of a chain of pointers. It occurs spontaneously outside of containers, when you just write e.g. classes which have objects of other classes as their fields. In Haskell that would be records, or just an algebraic data type. Or just closures.
- mbrodersen 4y ago
  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.
  - GrumpySloth 4y ago
    So, as I understand it, you avoid pauses by avoiding data structures with long chains of pointers. The same will work equally well in a language with a GC. It's also not the case that reference-counting itself doesn't result in pauses itself, but that the user is responsible for using such data structures that they do not result in pauses. Which I think is the only way when you care about performance, no matter whether you use manual memory management, reference counting or a tracing GC, so that's by no means a criticism of you or your language, I think it's very sensible. But I think that describing it as a no-pause memory management mechanism is a mischaracterisation.

refulgentis 4y ago

I'm not sure whats being asserted here, could you explain more? This sounds like you're describing a non-stopping GC, and its well understood reference counting is garbage collection. I'm not sure how the rest applies, you're correct, it is possible to write software with just malloc and free.

cakoose 4y ago
Re: "it's well understood reference counting is garbage collection". I think this might just be a terminology thing. There appear to be two ways the terms are categorized: 1. "reference counting" and "garbage collection" are two types of automatic memory management/reclamation. 2. "reference counting" and "tracing garbage collection" are two types of garbage collection. I think mbrodersen is using #1. (Back in the 90s and 2000s I feel like #1 was much more prevalent. But #2 seems to have gained popularity since then. My theory is that whoever started writing the Wikipedia content for this stuff picked #2.)
- rowanG077 4y ago
  I never understand why people refer to reference counting as garbage collection. It waters down the term so much it becomes essentially useless. Because under that assumptions basically every language has garbage collection in some shape or form.
  - jstanley 4y ago
    C doesn't have garbage collection. Furthermore, pretty much every language has I/O, but that doesn't make the term useless.
  - tsimionescu 4y ago
    They do it because they serve the same purpose, though with different trade-offs. Note that this mostly reflects automatic reference counting, like you have in Python or Swift, not so much manual reference counting like std::shared_ptr or Rc.
  - pjmlp 4y ago
    Because we have studied the literature instead of what a random dude in tells at a coffee https://gchandbook.org/ https://gchandbook.org/ https://www.sigplan.org/ https://www.sigplan.org/ https://ieeexplore.ieee.org/Xplore/home.jsp https://ieeexplore.ieee.org/Xplore/home.jsp
    - rowanG077 4y ago
      Nice appeal to authority instead of trying to engage in a meaningful way.
      - pjmlp 4y ago
        When one is open to learning, the best path to enlightenment is to use the same books as the Wizards on the tower of knowledge.
- tsimionescu 4y ago
  I think this is actually common in the literature, it has nothing to do with Wikipedia. Consider that Python is commonly described as a GC language, though it has always mostly relied on automatic reference counting to free objects (it does have a tracing GC as well to handle cycles, but I'm not sure if it always did).
  - int_19h 4y ago
    I would argue that what matters is the observable behavior. In Python, regardless of how the actual cleanup is distributed between ARC and GC, the behavior that programmer sees is that all unused memory gets cleaned up eventually. So, it makes sense to group it with languages that provide the same guarantee.
- bjourne 4y ago
  I think it's more of an industry vs. academia kind of thing. In the mid-90's before Java was released automatic memory management was mostly unknown to the unwashed masses. So garbage collection became synonymous to whatever Java was doing. However, The Garbage Collection Handbook originally published in 1996 defines garbage collection as: "All garbage collection schemes are based on one of four fundamental approaches; mark-sweep collection, copying collection, mark-compact collection or reference counting." So that's an example of terminology #2.
- mbrodersen 4y ago
  Yep. The compiler generates code that works the same way that an experienced C programmer would hand optimise alloc/free calls and manually keep track of shared data by increasing/reducing a reference counter. There is no separate mark/sweep or whatever step.

viraptor 4y ago

How do you collect cycles without a pause?

eru 4y ago
There are solutions to this one. Real time garbage collectors are a thing. You just might not be able to collect the cycle in one GC run. Or you can do what Erlang does: Erlang has neither mutation nor laziness, so you can't create cycles. The GC also lays out object in topological order in memory, so that you can detect garbage without tracing every life object.
- omginternets 4y ago
  Where can I read about Erlang’s magic?
  - eru 4y ago
    Google suggests https://stackoverflow.com/questions/10221907/garbage-collection-and-memory-management-in-erlang https://stackoverflow.com/questions/10221907/garbage-collect...
- viraptor 4y ago
  The comment claimed "There are zero GC pauses." Tbh, it's not clear how to interpret that. But real time simply means the pauses are guaranteed not to cross the realtime response budget. You still need to schedule the collection while the mutator is paused.
dataflow 4y ago
I'm gonna take a guess they dedicate a core to GC (or something along these lines).
- viraptor 4y ago
  That's not enough. Imagine a circular linked list. GC looks at an outside pointer to item A in it. Now another thread removes A from the list and moves the outside pointer to the next item. After that, GC would see all items in the list not referenced by anything (apart from the cycle).

pclmulqdq 4y ago

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 will likely get a slightly better result than your GC algorithm.

dataflow 4y ago
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<T, your_deleter>(); 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 slower) in the case where cond is true. Moreover, the obvious way to avoid it is to write it "C-style": void bar2(bool cond) { .. auto p = new T(); if (cond) { return foo(p); } ... your_deleter()(p); } which can up being faster when cond is true. But this isn't something an expert would generally want to do, as now the C++ code becomes unidiomatic, fragile, and unmaintainable. In an ideal world, though, you could have an optimizer smart enough to do that transformation automatically. C++ compilers already do that in trivial cases, but they can't do it in general. My impression is that their Haskell compiler exploits the internal knowledge of what your_deleter does (i.e. reference counting) in order to optimize the code in various ways, like optimizing out such code, consolidating refcount updates, etc. And if I understand this correctly, there's no surprise at all that it can be faster than idiomatic C++ code written even by experts. The question for me isn't the expertise of their programmers. Perhaps in their case they genuinely do need to have lots of objects on the heap, have (say) tight loops where they (for whatever reason) nevertheless cannot avoid the heap allocations, and don't have much of a use for finalizers besides freeing memory. In which case, I'm not surprised their solution clearly delivers better results than the C++ equivalent. The question from me, instead, is how well they think that generalizes, such as to (a) well-written Haskell programs in general, (b) well-written C++ programs in general, and/or (c) other domains. It would be one thing if their solution delivers better results in Haskell than C++ for their use case; it would be another thing if they could claim their solution delivers better results in Haskell than C++ for most use cases.

tsimionescu 4y ago

free() calls that have to run for a data-dependent amount of time are more or less equivalent to GC pauses (assuming a concurrent GC that doesn't need to stop the world, like Java's). The most typical example is free()-ing a a linked list, which takes O(n) free() calls to free with a simple RC mechanism.

kccqzy 4y ago
If you are assuming GC does not need to stop the world, you can also assume that the freeing of memory (including the O(n) calls to free()) will not be done in a critical path; all memory could be handed off to a separate dedicated thread that actually calls free(). Or in a RPC or HTTP server all memory can be freed after the request has been served. It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so.
- altfredd 4y ago
  > all memory could be handed off to a separate dedicated thread that actually calls free() That only works when you have infinite memory (or infinite CPU resources). > It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so. Only if by "not stopping the world" you mean your previous suggestion (leaking unbounded amount of memory to free() everything at some later point). When your memory is bounded, you will eventually have to stop/crash once you have run out of it. AFAIK, the best modern state of art garbage collectors have stop-the-world pauses, proportional to size of root set and/or thread count. I'd love to see an RC implementation, that does not have stop-the-world pauses at all, but that sounds as audacious as claims of perpetual motion machine.
  - andreareina 4y ago
    I don't think the gp is describing the null garbage collector, rather one that can work incrementally and concurrently with the program doing its thing. Whereas a concurrent tracing gc has the problem of data changing while it runs and so special care has to be taken not to corrupt memory.

Bolkan 4y ago

Pics or gtfo.

bitcharmer 4y ago
Yeah, GP's claim is completely bonkers. And they haven't provided any links or data to back up their nonsensical claim.
- mbrodersen 4y ago
  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.

brabel 4y ago

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 hasn't provided any. You haven't provided any (and I do believe you may think you're right, but I've been in the position of being very confident of something just to be proven completely wrong by giving all my data to others to scrutinize... it's disheartening but necessary to get to the bottom of what's real). It's like the V language saying it can do memory management magically and it's much faster than Rust or whatever when they don't even have a working system yet.

fnord123 4y ago
> 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. There is nuance here. They claimed that their project is faster than a specific hand optimized project. Not faster than a theoretical peak performance c++ program. I've run into similar situations where python reimplementation s are faster than java because python is easier to change and fixup algorithms. And %timeit in the ipython shell is way easier than the black magic involved in profiling and benchmarking java. You also have people on rust subreddit or discourse asking for optimization help when their rust is not as fast as a Go example they wrote. Often you get buffered IO going and it's on par. But to melt faces like ripgrep and friends you often need to drop pretences and work on Vec<u8>s.
- brabel 4y ago
  > And %timeit in the ipython shell is way easier than the black magic involved in profiling and benchmarking java Unfair criciticm... first, Java has had a REPL for several years and you can time stuff like in Python as easily... second, profiling tools in Java are some of the best available, and are not blackmagic... quite simple to use, just attach them to the running process and hit "profile". With that said: yes, I've also seen Java programs that run faster than the Rust or C counterpart. I suspect what OP saw falls into this category: a rare example that you take as a rule (maybe I misinterpreted the claim, I admit, but it does sound OP meant his Haskell program and, I assume, others which you write in the same style, cannot be beaten by the equivalent C++).

naasking 4y ago

> There are zero GC pauses. Unless you claim that a C++ alloc/feee call is “garbage collection”. Alloc/free can introduce arbitrary pauses last I checked, so yes, there are pauses. Any time doing book keeping for resources rather than running your code counts as GC time.

MaxBarraclough 4y ago
> Any time doing book keeping for resources rather than running your code counts as GC time. Perhaps a nitpick: memory management time, yes, but not GC time. alloc/free is manual memory management, not garbage collection.
- naasking 4y ago
  If you're using alloc/free in your GC, which is what was being implied, then that counts as GC time.
aaaaaaaaaaab 4y ago
On any OS which is not hard realtime, there could be arbitrary pauses with any syscall. This is just nitpicking.
- dento 4y ago
  Nitpicking: arbitrary pauses can occur even without syscalls, when the OS preempts the program. More nitpicking: on x86-64, SMI interrupts can cause arbitrary pauses even without any software control involved. Hard realtime on x86-64 is not possible.
  - staticassertion 4y ago
    More nitpicking: Your computer might turn off, cosmic rays might blow fuck up your RAM/CPU, Capital G God could reach down and pause the system, there's a universal quantum pause every 5.391247 × 10^-44 so that the universe can reboot, etc etc etc Orrrrr, GC pause just means pauses caused by the GC as part of its implementation's work to manage memory.

yakubin 4y ago

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?

afiori 4y ago
My guess is that this could be done concurrently and/or in parallel. It still take time linear in length, but dead nodes are by definition stable so it does not really matter when you free them.
- yakubin 4y ago
  So just like with tracing GCs. You do have a pause, which you may avoid with parallelism, or smear out incrementally. If you do it in parallel, your reference counting needs to be atomic, which adds further overhead. You still need to perform all the reference counting operations for each element of the list, not just free them, because part of the list may be shared. E.g. in SML: fun replace_head_with_1 (_::xs) = 1::xs; val a = [2, 3, 4]; val b = replace_head_with_1 a; Now a and b share the tail. And a linked list is only a simple demonstration of a chain of pointers. It occurs spontaneously outside of containers, when you just write e.g. classes which have objects of other classes as their fields. In Haskell that would be records, or just an algebraic data type. Or just closures.
mbrodersen 4y ago
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.
- GrumpySloth 4y ago
  So, as I understand it, you avoid pauses by avoiding data structures with long chains of pointers. The same will work equally well in a language with a GC. It's also not the case that reference-counting itself doesn't result in pauses itself, but that the user is responsible for using such data structures that they do not result in pauses. Which I think is the only way when you care about performance, no matter whether you use manual memory management, reference counting or a tracing GC, so that's by no means a criticism of you or your language, I think it's very sensible. But I think that describing it as a no-pause memory management mechanism is a mischaracterisation.