Hi Marc,

Interesting! Thanks for taking the time to describe this.

Find here some more questions, only the first three have practical importance though.

(Aha below by computer processor you mean CPU core.)

How is the parallell heap and GC model fit for different memory coherency models e.g. that of AMD64 (strong) and ARM (weak)?

(I guess those are the two extremes and that other architectures like IBM Power, Sparc, Mips, you name it, land between those.)

What is the execution model for Gambit threads, is the default mode that execution is spread across all GVM processors?

If I will run code in Gambit that will be blocking, e.g. blocking system calls such as DNS lookup on open-tcp-client, and C code, can I devote a given number of GVM processors to that?

Would there be some way for me to run blocking C code and GVM processors in the same OS thread conveniently, so that when I go into the C world I make some kind of "stamp out" so that a GC not would block until that OS thread would return to the Scheme world? How expensive will such a "stamp out" be?

2016-11-10 21:00 GMT+08:00 Marc Feeley <feeley@iro.umontreal.ca>:

> On Nov 9, 2016, at 10:28 PM, Adam <adam.mlmb@gmail.com> wrote:
>
> From now and on, "processor" will mean "an OS thread that's running a GVM", right?

Sort of… A GVM (Gambit virtual machine) is actually a set of “processors” running a Gambit program. Typically a GVM “processor” is mapped to an OS thread. This choice of vocabulary is to abstract the implementation details and impress the idea that conceptually the VM is running on a set of processors, in parallel. In a “on the bare metal” implementation these “processors” would be actual hardware processors. But when running on top of a traditional OS, where it is not possible to access hardware processors directly, then each “processor” is implemented with an OS thread, and it is expected that the OS will be intelligent enough to assign different hardware processors to all these OS threads (with posix threads and Windows the thread affinity is used to help the OS achieve a one-to-one mapping).

> 2016-11-08 12:31 GMT+08:00 Marc Feeley <feeley@iro.umontreal.ca>:
> ..
> The barrier synchronizations are implemented using a binary tree like structure and time-limited spin-barriers to synchronize a parent processor with its 2 children. So a barrier takes logarithmic time.
>
> Cool!
>
> Just out of curiosity for nitty-gritty details:
>
> Which processor is the ultimate parent, is this generated at processors initialization, or at each GC? Is it the processor that trigs the GC?

When the Gambit process starts, the current thread is considered “processor 0”. After the Scheme library is initialized, the VM is resized to N processors (where N is supplied by the -:pN runtime option). So processor 0 is initially running the primordial Scheme thread. Note however that threads can migrate to another processor to balance the load.

All processors run the Scheme code in parallel and each processor has a heap section in which it does its memory allocations independently from the other processors (so allocation requires no locking, except when a heap section is full and a new heap section needs to be obtained from the pool of free heap sections, but that is relatively infrequent and there is very low contention for the lock). When the pool of free heap sections is exhausted, the processor that is doing the allocation will trigger a GC (so any processor can trigger a GC, and it is possible that more than one processor simultaneously trigger a GC).

Just curious, where are the malloc():s done (to increase the total heap space available for use for live objects)?

Also, is there relevance in changing memory block size to the page size e.g. 4096 bytes from the previous 512 bytes, as to minimize the possibility that two processors would write to memory addresses within the same page, hence congesting the memory coherence logics on AMD64?

(I.e. the performance difference on AMD64 between core1 and core2 doing writes to the same memory page concurrently, and doing writes to different pages concurrently, is enormous. If I recall right this paper "What Every Programmer Should Know About Memory" by Ulrich Drepper https://www.akkadia.org/drepper/cpumemory.pdf showed some measurements with like 10000x performance differences.)

Not sure if malloc() tends to be aligned to page limits, anyhow I guess that would be a healthy assumption.

At that point all processors are interrupted (by raising a flag that is polled regularly) to execute the GC in parallel. This is done using a barrier synchronization (so that the GC starts only after all processors have transitionned from the execution of the main program to the execution of the GC, to avoid that some processors start the GC while others are still allocating or modifying objects). Then, within the GC, barrier synchronizations are also performed to separate each phase of the GC (initialization, assignment of stack and heap sections, marking using strong references, …).

> What's the motivation for a tree-like propagation at all, compared for instance with that the processor that trigs GC would do the sync with all other processors, all by itself?

That would take linear time. Logarithmic is faster.

Wait. Doing a loop from 0 to N cores (which is generally below 100 or 1000 anyhow) to set a memory address, would be negligible speed on all architectures.

for (i = 0; i < processors; i++) { processor[i]->going_into_gc = true; }

Is this propagation used not only for signalling that you're going into a synchronous operation/GC, but also for complex operations like workload within the marking process?

Also, it is necessary to have a synchronization mechanism that will tolerate simultaneous triggering of the GC and only do one GC regardless of how many processors triggered a GC. So using a predefined barrier synchronisation primitive is not sufficient. The mechanism implemented in the runtime system allows processors to request a synchronous service (such as garbage collection, or resizing the VM) and the mechanism will sort out which service “wins” (in the case where there are conflicting services requested).

Is the "resizing the VM" about changing total heap size, or changing the number of processors, or either?

Are more synchronous services coming up?

Ensuring that the GC only is triggered once, how do you do that - say the GC trigging logic in one processor is if (gc found to be needed) { workup; go into gc; }, if that trigs in more processors at exactly the same time, just very approximately how do you make it go into gc exactly once?