@keean thanks for your feedback:

pointer + offset addressing is slower, and uses more registers. It is not just slower, bit slower on every operation, so taking an in-place quicksort as an example, it can result in a significant reduction in performance. This kind of thing will result in people wanting to write critical sections (filter kernels etc) in 'C'.

As I wrote previously, the pointer + offset is only necessary for not having horrible performance with pointers to fields when the base pointer of the allocated object needs to be accessed. So that doesn’t need to be pointer + offset, unless we need to compress the shortage requirements (i.e. if offsets use much less space than pointers), because can just make that a tuple of (pointer-to-allocated-base, pointer-to-field).

Additionally, your performance criticism would not apply (even if employing pointer + offset) in a tight loop that was leveraging the ability to combine pointer + offset into a single-wide (i.e. no double pointers) temporary pointer.

Before reading your comment and immediately upon awakening, I had the following realization¹.

Where we can prove at compile-time that the lifetime of an interior pointer is contained within the lifetime of any other pointer to the base of the allocated object, then such interior pointers don’t need to be involved in the (referencing counting, generational, or mark-and-sweep) GC. Thus we can employ single-wide pointers for them, making them very fast. So presuming we will not be using double-wide pointers (such as for reference counted allocations) which would otherwise have negative impact cache locality, I propose we only allow interior pointers at the language level in the cases where they can be single pointers. For other cases, employ pointer + offset and/or pointer + pointer at the library level, such as for slices in the library implementations of arrays and strings and what not.

Thus I’m thinking that high-performance (performance critical path) libraries will require some lifetime analysis (or at least escape) analysis. Most (~80+%) of the code of the program doesn’t require this level of attention to detail and absolute maximum performance.

Separately there’s the possibility that eventually the typical way to implement a generational GC² is a separate young generation collector for each thread that can run simultaneously. So thus if escape analysis proves that an interior pointer (and if we’ve implemented my generational + RC idea, then the interior pointer must not point within a reference counted object) doesn’t leak to the caller and that function completes fast enough to not need to be interrupted by the generational GC (which perhaps is an annotation the programmer is allowed to make), then the interior pointer needs only a single pointer.

EDIT#2: I’m contemplating that with an Actor-like model all stack allocation will be safe and thus single-pointer pointers to fields for stack allocated objects will always be allowed.

I also wrote on Quora:

^{Another reason which I’m sure you aware of but didn’t mention is cache locality. Imagine an array of pairs of objects where each pair object has two pointers (references) for each of the pair instead of storing them in place. So walking the array is no longer contiguous in the cache lines so it will thrash the cache and add latency.}

^{Pointers to fields forces any automated GC to be slower. The alternatives to pointers to fields are copying or pointer+offset:}

^{Pointers · Issue #38 · keean/zenscript}

¹ _{But I am late to post it because of some distractionary drama with the n00bs.}

² _{Which Go apparently currently lacks and instead employs escape analysis for the young objects on the stack which is inferior given it’s not the complete Rust-like lifetime analysis so presumably many objects leak into the old generation mark-and-sweep collector.}

EDIT:
@keean was writing to me at LinkedIn about how if the future is parallelism with “a modern Intel processor has up to 180 instructions in flight at a time” to saturate it (and his thought that non-speculative CPUs will need 1440 non-superscalar³, non-speculative pipeling cores to perform on the same level as a 32 core AMD Threadripper) so we need memory to perform efficiently with many many threads. The point being that mark-and-sweep GC definitely does not work well with many cores. AMD Threadripper will have 32 cores with 64 hyperthreads and the GPU has even more.

I’m glad to see that @keean was also thinking about the GC issue with threads. Indeed the young generation compacting collector must typically have a separate instance for each thread. I wrote at Quora:

Páll Haraldsson wrote:

Another reason to not invest in Java is that we headed to massive parallelism and Java’s GC model is inherently incompatible.

What is it about the “GC model”? For Julia language wit GC it works very well. Your link about language that compiles to JS.

Must pause all the threads when compacting the young generation bump pointer, compacting collector, unless employ a separate young generation collector for each thread, which thus requires these objects to non-shared between threads. There is no such feature on the JVM to create such thread-cordoned objects. The young generation collector needs to be collected more frequently than the older generation(s). So imagine you have one thread that is slamming the young generational heap with allocations thus forcing all other 9999 of your threads to pause much more frequently.

Additionally automated GC (instead of Rust-like stack allocation) appears to be entirely incompatible with scaling of multi-core![1] Yikes!

[1] #41 (comment), c.f. footnote ² on the linked post

This is I think why Go apparently doesn’t have a young generation collector as I already stated above, because the M:N goroutines apparently have no way of dictating which groups of goroutines must not run simultaneously so they could run on the same young generation collector (and the use of the stack instead of young generation collection although maybe less efficient is thus able to accommodate M:N without any such groupings). The older generation (even incremental) mark-and-sweep collector which has one instance for all threads suffers from Amdahl’s law as the more simultaneously running threads, then the greater percentage of the performance budget that is lost to GC.

This is another reason I had offered my unique proposal to have a separation between programmer annotated young generation collected objects and annotated referencing counted collected objects. Referencing counting is more scalable for threading than mark-and-sweep, because the collections can be more localized. But not always as there can also be cascading dominoes of effects when reference count declines to 0 on an object which contains pointers to other objects, especially so if young generation objects escape from escape analysis and are allocated to the older generation collector instead of allocated on the stack. And cycles probing for reference counting also increases non-localized costs. These non-localized cascades can increase the synchronization overhead between threads given a global memory pool for the older generation objects.

The competitive alternative to having a separate young generation GC for each grouping of green threads which can’t run simultaneously, is the tsuris and inflexibility of Rust-like lifetime analysis which presumably enables more objects to be allocated to the stack than simplified escape analysis which Go does. This could potentially enable more threads to be eligible to run simultaneously since it is a more fine-grained proof of non-sharing of mutable references. Whereas, the separation of young generation collectors by grouping is a somewhat analogous but different proof of non-simultaneous sharing of mutable references. There are tradeoffs between the two paradigms.

³ _{Also superscalar is an independent instruction-level parallelism optimization from, out-of-order execution, pipelining and speculative pipelining of branches. Superscalar relies on independent, parallelizable instructions on multiple execution units. Whereas, instructions can be serially dependent in pipelining because the instructions are partially overlapped such that each instruction is executed in multiple steps, thus the result of an earlier instruction can complete before it needs to be used by a later instruction which is already in the pipeline and has partially executed. Thus pipelining by definition does not accommodate branches without speculative execution. Superscalar is not pipelining. Superscalar would not leak timing info nor waste power, and can achieve up to 8 instructions in parallel but typically only 2. So maybe only need 180 – 360 superscalar threads to match a fully speculative pipelining 32 core AMD ThreadRipper, although this superscalar-like instruction-level parallelism feature seems to be inherent in the “the SM more closely resembles

an eight-wide vector processor operating on 32-wide vectors” vectorization on the GPU so we would need on the order of ≈1440 GPU threads to match the AMD Threadripper. Also there’s some limited pipelining (aka arithmetic pipeline) on the Streaming Multiprocessors (SM) of the GPU but not speculative (presumably because branching is highly undesirable if it will cause divergence between threads in the same warp because threads in warps are context-switched contiguously) but there’s no out-of-order execution on the SMs of the GPU so there’s no register renaming. Instead the GPU exploits a much larger register file (RF) so that registers don’t have to saved and reloaded on context switches (and only one pointer/offset/warp-id into the RF for the registers context-switched for the warp not individually per thread because warps are context-switched contiguously) so that a much higher-level of algorithmic-level parallelism can be exploited to mask the relatively high latency of all forms memory on the GPU, e.g. 24 cycle write latency (archived) (c.f. also) for the registers as compared to less than 1 cycle on cores of a modern CPU.}

_{@keean often cites the Itanium as an example of explicit (i.e. compile-time determined) ILP that failed. But he is incorrect to conclude that the superscalar and non-speculative pipelining aspects of the Itanium totally failed. There was some parallelism gains, just not the 45 instructions per core in flight obtained on the modern Intel processors. The fact that the GPU exploits ILP in the SMs without any out-of-order speculation, is evidence that superscalar is not necessary tied to speculative and out-of-order.}

^{_{This link won’t archive so I’m copying the content below:}}

^{_{There is context switching, any time a warp scheduler switches from one thread to another. This thread-switching behavior is desirable as it is part of the latency-hiding process.}}

^{_{A large part of the a thread's state is contained in its associated registers (there is only a small amount of additional state, such as the instruction pointer, stack pointer, and flags). A thread's register state does not need to be moved during a context switch because there is enough register storage for all threads/warps that are currently resident and schedulable for execution. This is one of the reasons why GPUs have relatively large register files (e.g. 16K+ registers). Since there is a unique (physical/HW) register for each logical register for each (schedulable) thread, no movement of register data is required during a "context switch".}}

^{_{This is also why register usage can be a limiter to "occupancy". In general, we want as many warps/threadblocks as possible to be "resident", i.e. schedulable for execution, as this increases our ability to hide latency. But each additional schedulable warp carries with it a register "footprint" which must be provided for in the SM registers. When we run out of register storage, then no more warps/threadblocks can be scheduled on that SM, until some of the register usage is released by retiring warps/threadblocks. Therefore imposing limits on register usage per thread may help to drive up "occupancy", i.e. the number of schedulable warps/threadblocks that can be simultaneously resident on the SM. Since this helps with latency hiding, this may be a good thing. On the other hand, limiting register usage may lead to register "spilling" by the compiler, which will increase memory traffic. So there may be a tradeoff to this method of increasing "occupancy".}}

^{_{As a clarification to the above, warps cannot be individually made resident on a SM. The unit of residency on an SM is the threadblock, not the warp. No warps from a threadblock will become resident on an SM until there are sufficient resources for the entire threadblock. At that point, the entire threadblock (all of its warps) may become resident on that SM.}}

Pointers #38

Description

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions