What does “deterministic” mean in the context of memory management?

Question

At the time of writing, Wikipedia describes determinism as:

"a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states"

That aligns with my interpretation of determinism as a natural scientist.

If a program contains a benign race condition and its control flow varies depending upon the outcome of the race, is it deterministic? I would say not. However, many people describe thread-safe reference counting, such as shared_ptr in C++, as deterministic even though threads race to decrement the reference count to zero and the winner is responsible for executing the destructor.

The Wikipedia page about garbage collection lists determinism as an advantage of reference counting compared to tracing collection and determinism is also referred to here. On the other hand, people have blogged rants explaining why this is wrong.

So what does "reference counting is deterministic" mean, if anything?

Answer 1

So what does "reference counting is deterministic" mean, if anything?

It means it is deterministic in the absence of multiple threads. Threads almost always ruin this sort of determinism, with or without a race condition, memory collection or whatnot: in one run, thread A, can be scheduled first a bit, then another thread, B gets scheduled a bit; in a second run, the OS can schedule the threads to run in the opposite order, thus almost all threaded programs inherently lose this determinism.

Therefore "race condition" and "threads" usually put a procedure out of the scope of this use of this meaning of determinism.

Answer 2

Determinism is an absolute, objective concept — either a process always produces the same result, or it doesn't.

Well, no, it's not so simple. When people say that something is deterministic, they're often leaving out a precise specification of just what it means for the process to be executed in the same conditions. A deterministic process always produces the same result for a defined set of initial conditions. It matters what you consider part of the process and what you consider part of the initial conditions.

Concurrency is an extreme case of non-determinism. In pretty much any model of concurrency, scheduling introduces a source of non-determinism, and the most we can expect is that one thread or node behaves deterministically, if the behavior of the rest of the system is constant from its point of view. Any timing difference causes the thread to observe the rest of the system in a different way, which allows it to behave differently.

Input/output can cause a program to behave differently. Again, very much like a thread in a concurrent system, a program that performs I/O is only expected to behave deterministically if its interactions with the rest of the world are fixed. A sequential program that doesn't perform any I/O (including things like calls to random number generator) is expected to be deterministic. Its behavior is thus fully predictable and reproducible. Let's call such a program a pure program.

What this means for memory management is that a pure program is deterministic, no matter what memory allocation strategy is used.

Now as hinted above this statement needs to be qualified. What assumptions are hidden here?

An important assumption is of course that the memory allocation strategy is fixed, and non-randomized. A different memory allocation strategy could obviously lead to different behavior, including the memory being full or not full at different times in the program's execution.

Another assumption is that we're talking about a complete program, starting from a known initial state. As far as memory management is concerned, we're running the program starting with a fixed heap configuration.

But what if we were talking about a program fragment? We tend to like our notions about programs to be compositional, because we're forever building bigger programs from components. Depending on where and how a given program fragment is executed, it may be started from different heap configurations.

Garbage collection affects the heap globally. If a collection happens during the execution of the program fragment, it may also affect storage used by the rest of the program. Thus garbage collection exhibits a strong dependency on the program as a whole. An object that stops being used may or may not be collected because a collection may or may not be triggered at a particular point, or because the minor heap may fill up at a different time for a generational collector, etc.

Reference counting is more deterministic than garbage collection because there are fewer dependencies to the rest of the program. An object used solely by the program fragment is freed when its reference count reaches 0, and this does not depend on the what the rest of the program had been doing.

Reference counting, like most memory management strategies, is not fully deterministic from this point of view. The state of the heap when the fragment starts matters because of fragmentation. Even for a given amount of free memory when the fragment starts, a difference in size and layout of the free areas may lead to the program running out of memory, or not. The amount of time spent managing the data structures of the memory allocator may also vary depending on the shape of the free areas in the heap.

This is the case for any memory allocation strategy, including fully manual management, except for strategies guaranteed not to run out of memory (such as fully static allocation).

Just about any memory allocation strategy is non-deterministic in the sense that the behavior of a program fragment is affected by the surrounding program — both in terms of whether a given allocation will succeed (and at which address), and in terms of how much time is spent on memory management at any given point. The difference between reference counting and garbage collection is not one of nature but one of degree. Reference counting is more deterministic than garbage collection (under typical approaches). And that's without getting into concurrency, where pretty much anything is non-deterministic.

Arguing whether a strategy is “deterministic” without enough context to precisely specify what is meant is a matter of semantics. In the colloquial sense of “arguing about words and forgetting about their meaning”, not in the technical sense of “the study of the meaning of programs”.

Answer 3

As the other poster said, determinism is the idea that given initial conditions A and B a process will produce output C where the time used is part of the definition of C. Because of the evolution of computers many people have losses sight of the point at which the pre-conditions A and B no longer apply to a program but to the entire computer. Modern general purpose computers can never be deterministic due to entropy generate by the interaction of the clock with the kernel schedular and other issues. Hard realtime systems use dedicated chips (think car breaks) or FPGAs (think high speed trading) to ensure determinism.

OK regarding memory management, the idea of determinism can and should be broadened to a soft realtime concern. We want memory reclamation to happen within a known, bounded time. We also do not want the upper limit of that time to be too long (as determined during requirements gathering) and so make out program's non-function specification have an unacceptable upper time limit or jitter.

Shared_ptr is a poor choice because of its low over all performance and because of its large jitter. Thus (I wrote the rant) I don't think it should ever be used unless there is absolutely no other choice. Also, it does not work for memory management due to cycles. In general it is bad (ranting again).

By comparison, on most modern machines, assuming our process does not loose its quantum during reclamation, automatic (stack) memory is deterministic enough to be considered deterministic in the real world.

In financial low latency systems, any instruction which locks the memory (as shared_ptr does) must be avoided. Funnily enough, that is something I am currently involved with.

All the best - AJ