3 ms·

...and a garbage collector is one of those. It's not magic fairy dust, it's still software that works on the same processing unit as your program, and obeys the

...and a garbage collector is one of those. It's not magic fairy dust, it's still software that works on the same processing unit as your program, and obeys the same rules. Computers are finite automata, they can't beget true randomness, so any software system that is isolated to a single machine is "deterministic", if you have enough context.

PaulDavisThe1st 4y ago
> Computers are finite automata, they can't beget true randomness Plenty of peripheral inputs that can be used to induce true randomness.
- nice_byte 4y ago
  ...of which the computer is not the source.
fluoridation 4y ago
>Computers are finite automata, they can't beget true randomness "Non-deterministic" in this context means that the behavior of the program is not deducible from the state of the current thread of execution, or more generally, from the state of the system being analyzed. If another thread modifies the current thread's memory, that modification is non-deterministic because you couldn't have foreseen it by following any pointer that's reachable by the current thread. If a cosmic ray hits a computer chip and flips a bit, that bitflip is non-deterministic; you couldn't have predicted that that bit would be flipped by looking at any part of the computer. In other words, an effect is non-determistic with respect to a causal chain if it's causally unrelated to it. A tracing GC is non-deterministic for two reasons. First, it causes effects (namely, pauses) in all threads, even those that never allocate any memory. Second, it makes the lifetime of objects unpredictable. Thread A can allocate an object and then drop it, and when that object will be destroyed depends on the behavior of the entire system, not just thread A's. RAII doesn't exist in GC'd languages (except through using or try-finally hacks). Reference counting is completely deterministic. If a thread holds the last reference to an object you can predict with certainty when that object will be released and which objects will also be released as a consequence, before actually releasing the object. You don't need to know what any other thread is doing to make this prediction. Crucially, if you find that sometimes a reference counting program spends too long releasing an object graph, all you need to do to debug it is to run the program again under the same conditions and break when it reaches that point. Try doing the same with a garbage collector.
- nice_byte 4y ago
  > Reference counting is completely deterministic. If a thread holds the last reference to an object you can predict with certainty when that object will be released and which objects will also be released as a consequence, before actually releasing the object. You don't need to know what any other thread is doing to make this prediction. You're contradicting your own definition of determinism here. Other threads may be holding references to the same object, and unless you know what the other threads are doing, you _cannot_ predict when an object is going to be released just by looking at the execution of a single thread. You need to look at the overall behavior of the application, with the complex object graph spanning multiple threads. > all you need to do to debug it is to run the program again under the same conditions this is much easier said than done.
  - fluoridation 4y ago
    >Other threads may be holding references to the same object Yes, other threads may be holding references to that object, except when the current thread holds the last one, which was the first thing I said in the statement you're responding to. But that aside, you seem to be making the assumption that threads sharing state and object graphs between each other is a given, but that's completely false. Reference counting lets you design your application such that threads don't need to interact with each other to manage their memory. So you have the option of completely deterministic behavior, if your problem is amenable to such a solution. On the other hand, tracing GC doesn't have that option. Threads affecting each other is mandatory, even when no object is reachable from two threads simultaneously. Between reference counting and tracing GC, only one permits deterministic object destruction. >this is much easier said than done. You're right, it's much better when your memory management system makes it completely impossible to debug stalls. Completely impossible is definitely better than difficult.

PaulDavisThe1st 4y ago

> Computers are finite automata, they can't beget true randomness Plenty of peripheral inputs that can be used to induce true randomness.

nice_byte 4y ago
...of which the computer is not the source.

fluoridation 4y ago

>Computers are finite automata, they can't beget true randomness "Non-deterministic" in this context means that the behavior of the program is not deducible from the state of the current thread of execution, or more generally, from the state of the system being analyzed. If another thread modifies the current thread's memory, that modification is non-deterministic because you couldn't have foreseen it by following any pointer that's reachable by the current thread. If a cosmic ray hits a computer chip and flips a bit, that bitflip is non-deterministic; you couldn't have predicted that that bit would be flipped by looking at any part of the computer. In other words, an effect is non-determistic with respect to a causal chain if it's causally unrelated to it. A tracing GC is non-deterministic for two reasons. First, it causes effects (namely, pauses) in all threads, even those that never allocate any memory. Second, it makes the lifetime of objects unpredictable. Thread A can allocate an object and then drop it, and when that object will be destroyed depends on the behavior of the entire system, not just thread A's. RAII doesn't exist in GC'd languages (except through using or try-finally hacks). Reference counting is completely deterministic. If a thread holds the last reference to an object you can predict with certainty when that object will be released and which objects will also be released as a consequence, before actually releasing the object. You don't need to know what any other thread is doing to make this prediction. Crucially, if you find that sometimes a reference counting program spends too long releasing an object graph, all you need to do to debug it is to run the program again under the same conditions and break when it reaches that point. Try doing the same with a garbage collector.

nice_byte 4y ago
> Reference counting is completely deterministic. If a thread holds the last reference to an object you can predict with certainty when that object will be released and which objects will also be released as a consequence, before actually releasing the object. You don't need to know what any other thread is doing to make this prediction. You're contradicting your own definition of determinism here. Other threads may be holding references to the same object, and unless you know what the other threads are doing, you _cannot_ predict when an object is going to be released just by looking at the execution of a single thread. You need to look at the overall behavior of the application, with the complex object graph spanning multiple threads. > all you need to do to debug it is to run the program again under the same conditions this is much easier said than done.
- fluoridation 4y ago
  >Other threads may be holding references to the same object Yes, other threads may be holding references to that object, except when the current thread holds the last one, which was the first thing I said in the statement you're responding to. But that aside, you seem to be making the assumption that threads sharing state and object graphs between each other is a given, but that's completely false. Reference counting lets you design your application such that threads don't need to interact with each other to manage their memory. So you have the option of completely deterministic behavior, if your problem is amenable to such a solution. On the other hand, tracing GC doesn't have that option. Threads affecting each other is mandatory, even when no object is reachable from two threads simultaneously. Between reference counting and tracing GC, only one permits deterministic object destruction. >this is much easier said than done. You're right, it's much better when your memory management system makes it completely impossible to debug stalls. Completely impossible is definitely better than difficult.