WD-40 (for reducing Rust with the next mainstream language)

I propose a (rough sketch for a) language design that I posit while attempting to maintain the most significant opportunities for performance (e.g. monomorphisation) would have superior tradeoffs  than Rust in the areas of complexity bloat, design freedom, and benefits versus inflexibility/tsuris of static code analysis. It would have the HLL feel of JavaScript with the LLL control of C++ without all the complexity and unnecessary abstractions (e.g. not the anti-patterns OOP subclassing and not shared_ptr as the default over GC).

GC Exclusion Axiom:
Afaics, presuming (enforcement of block scope lifetimes and) all functions input (mutable or immutable because we don’t care in a single-threaded model) borrows—i.e. don’t take lifetime ownership (note callbacks take lifetime ownership)—then GC is not required for provable use-after-free (aka dangling reference/pointer) safety. However, for dynamic data structures that share references (e.g. directed graphs with in-degree > 1), then GC references are much more convenient and performant than the alternative of representing the references with array indices. Note functions that would otherwise take ownership can take ownership of a (GC referenced or unboxed¹) deep copy/clone instead. However where deep cloning would be too costly in terms of performance and memory consumption, shared GC references may be preferred. Where GC is employed we have protection against memory leaks which Rust does not provide, except with an inferior except prompt/deterministic reference counting smart pointer paradigm Rc<T>.

Afaics, there are some marvelous simplifying implications of this axiom:

Presuming all functions adhere except where they declare references to be GC, afaics the compiler can automatically implement RAII (in try-finally blocks² with an equivalent finally concept for Promise callbacks) for deterministic memory deallocation (and automatically deterministically destruct instances of a type that have a destructor¹ which is a major feature lacking from GC languages and the with of Python being inferior because it is manual and object isn’t deallocated deterministically; noting that such types can not used with GC references directly or indirectly as a member of a data structure that is GC referenced).

Afaics, the same code will be sound and applicable whether the data structures are implemented by compiler unboxed without GC or boxed with GC. In other words, other than the aforementioned explicit GC references for algorithmic convenience and performance, the programmer never needs to indicate whether the data structures should be boxed or unboxed³. I want to strip away the noise/complexity of Ref<>, Box<>, etc.. For read-only inputs (i.e. the unannotated default) the programmer need not even think about whether the inputs are cloned-by-value (i.e. primitive type) or passed-by-reference; and cloned-by-value type inputs should never be allowed to be annotated as mutable on the function signature (although they can be mutated inside the function body unless they explicitly annotated read-only and the point being that the programmer never needs to think about whether the type is primitive or not and can see if there is a mutability implication by looking at the function signature). Although I presume an optimizing compiler will always strive for unboxed (because this will be more performant), if we start writing code in say TypeScript we can strive to adhere to this pattern (or have our compiler generate TypeScript) without all the unboxing mess if we so desire.

Goodbye to Rust’s lifetime parameters and 3 kinds of pointers noise/tsuris/complexity; and  due to the proposed single-threaded concurrency event model goodbye also to Rust’s mutability borrowing restrictions/complexity/tsuris.

When thinking about interfacing with ASM.js (or Webassembly aka WASM) with minimum (or no) marshaling overhead, then since (which IMO is a major paradigmatic flaw) there is no way yet to have those interact directly with GC references (ostensibly because since there is no static typing then JavaScript thinks these are unbounded polymorphic, i.e. Any aka Object), we can (until some future where we write our own VM) favor unboxed and mallocing these via Emscripten (or similar transpilation to ASM.js/WASM of our own C-like language features).

¹ But not cloning resources such as file handles.
² And Rust’s error handling has no try (panic! is doesn't throw an error up the stack call hierarchy) and instead forces all exceptions to be bubbled up as Result<T, E> return values which is excessive boilerplate noise/tsuris.
³ Even arrays of data structures that have variable sized members such as String can be cleverly implemented (by a library or the compiler) to use indices byte offsets into a second array which contains the variable sized values. This can even work with mutable variable size values, by creating a new value at the end of the second array growing the array as necessary and/or implementing a malloc and free on the second array, i.e. this second array heap is freed from the parent heap as a monolith. Note if the second array is encapsulated so it can never be referenced directly, then it can be repositioned in virtual address space as needed to minimize virtual address space fragmentation. Monomorphisation could make such libraries more efficient.
Note bounded polymorphism never absolutely requires boxing. Unbounded polymorphism would but we are refusing to support Any, i.e. all unbounded polymorphism in modules must be bounded when consumed by compiled/linked code.
Subsequent discussion in this thread will explain further the rough sketch so that readers can gain clarity. Let’s see what caveats and flaws are revealed via discussion. I look forward to @keean’s feedback and perhaps he will explain to what degree it corresponds to some features of the Ada PL.
I do not claim any of these ideas are novel inventions. @keean has alluded to for example cloning as an alternative to lifetimes and/or GC. What I am doing above is making a more holistic presentation of various ideas that have been floating around.
Of course typeclasses or ML functor/modules on top of this for HLL abstractions. If typeclasses, there is an option to go with implicit function arguments instead of requires, which makes it more readily implementable in TypeScript.
@shelby wrote:

My expectation is that in Rust the programmer will often need to resort to unsafe code to obtain the necessary freedom. My overriding concern is the K.I.S.S. principle and the amount of the complexity budget consumed for the benefits attained.

@shelby3 wrote:

…the goals that one justifies employing static typing (“better structure/abstraction, have more readable/maintainable code, and giving stronger guarantees about safety, lack of bugs, and lack of exploits”)…
A valid argument against static typing which I have made on these issues threads, is that no static abstraction can be 100% leak-free. Meaning that eventually we always end up having to violate the invariants of the abstraction, or moreover that it becomes very convoluted to maintain type safety and have complete degrees-of-freedom of expression. So then static typing becomes a negative factor for productivity instead of a positive one. This is why selecting which abstractions to enforce with a compiler is an engineering design challenge (arguably even perhaps an art) of matching to use cases.

@shelby3 wrote:

…there is diminishing return from static checking complexity because we can not statically check every clever algorithm and design paradigm that programmers will come up with. I think he had mentioned fighting with type systems.
I am interested to explore static typing that does not frustrate programmers.
…
Disagree that Rust’s balance of flexibility and tsuris is ideally suited to most apps.

@shelby3 wrote:

Additionally it’s the noise of extreme static checking such as the lifetime parameters (in addition to generic parameters and normal kinds of static types) on every function in Rust… GC is so much more elegant. I understand certain real-time use cases will not tolerate GC pauses (although we did also discuss V8’s incremental mark-and-sweep upthread) and more optimized by zero overhead abstractions (e.g. no runtime overhead for deciding which to deallocate)

@shelby3 wrote:

Perhaps we will eventually think of some low-complexity abstraction that gives us non-marshaled integration for tree data structures between HLL and LLL, and perhaps we can even prove borrowing and lifetimes statically. But I suspect we can not without heading towards the complexity of C++ and Rust.

@keean wrote:

I would not write a web service in 'C' or even 'Rust' ever, this is really ideal ground for a garbage collected language. I would use Node (TypeScript), Django(Python) or 'Go'.

@keean wrote:

My view is there needs to be a high-level-language and a low-level-language that share enough memory-layout and data-structure that data can easily be passed backward and forward.

@shelby3 wrote:

I am wanting to move away from such clusterfucks of never ending aggregation of complexity.

I am not going to try to argue that Rust has no use cases.
But I want to create a mainstream programming language used by millions of programmers.
Do you want to compete with Rust?

@keean replied:

@shelby3 wrote:

Once we start heading for Rust’s three different kinds of pointers, then I will think we have failed to make a clean high-level language for the masses.

Here we agree.

not shared_ptr as the default over GC

inferior except prompt/deterministic reference counting smart pointer paradigm

deterministically destruct instances of a type that has a destructor¹ which is a major feature lacking from GC languages … noting that such types can not used with GC references directly or indirectly as a member of a data structure that is GC referenced

We need optional GC and reference counting. The latter excels as deterministic, prompt finalization but has the trade-offs quoted below:
@shelby3 wrote:

However, reference counting deallocation is prompt and more deterministic than GC mark-and-sweep (although I rebutted there, “But please note that reference counting can’t break cyclical references but GC can. And reference counting can cause a cascade/domino effect pause that would not be limited to a maximum pause as hypothetically V8’s incremental mark-and-sweep GC.”). Incremental GC schemes when not overloaded with allocation that escapes generational GC, decrease high-latency stalls.

@anonymous wrote in private:

Progress on the language design is great to see.

I need progress on code, not language design, but I am trying to have paradigm I can be thinking about when structuring my code in TypeScript + C, so that it can be an easy transition if ever we complete a new PL and also to drive my insights on that potential language.
Concretely, I think it means I will write wrapper classes with getters and setters in TypeScript that take an ArrayBuffer for data and do my malloc in Emscripten and eliminate marshalling that way. Which will be a precursor to what a compiler can do automatically (and later with better integration by outputting ASM.js or WASM directly and maybe one day our own VM since the browser VMs have limitations).

Rust’s leadership may be falling into the political hell hole.

I wrote:

We need optional GC and reference counting. The latter excels at deterministic, prompt finalization (which is required for non-main memory finalization) but has the trade-offs quoted below:
[…]
Edit Nov. 18, 2017 Distinguish between non-deterministic reference counting and deterministic RAII.

Re-reading the prior linked comments…
First realization is that reference counting is non-deterministic and thus is inferior to GC in every facet (for the applicable use cases of non-deterministic resource management and thus the inherent lack of deterministic finalization).
Afaics, the only useful facility to add in addition to GC is the zero-cost1 abstraction of deterministic RAII block scope allocated/deallocated on the stack, because it (probably improves performance and) adds determinism of finalization (aka destructors).
To achieve such zero-cost resource management abstractions requires typing/tracking the lifetimes of borrows of references so the compiler can prove a resource has no live borrow when it goes out of block scope. I had proposed the “is stored” annotation on function inputs when an input will be (even transitively) borrowed beyond the lifetime of the function application. A separate concern from the issue of tracking borrows for the purpose of preventing concurrent race conditions access (which we discussed in depth in the Concurrency thread). This granular typing of the context of side-effects seems more straightforward than some grand concept of typing everything as a side-effect??2
One of the key advantages/requirements of GC is the ability to move objects so that memory can be periodically compacted (with the compaction being amortized over many implicit/delayed deallocation events which would otherwise be explicit/immediate/non-deterministic-latency with reference counting), which enables allocation to be as low-cost as incrementing a pointer to the end of allocated objects in a contiguous memory address space.
As an aside, for highly optimized low-level code to run at maximum performance, it must be possible to freeze the position of objects in the memory address space, else the objects must be copied. The former has the concurrency live and dead-lock issue w.r.t. the said compaction.
For RAII managed data structures that contain pointers to data (i.e. unboxed) which is not RAII managed at the current or containing block scope, these pointers have to be mutable by the compaction engine and have to be recorded in the list of references which the GC must trace. Thus to have full interoperability between GC instances and RAII instances without copying data, incurs either a performance penalty of reloading pointers on each access (in case they’ve been moved by the compactor) else the aforementioned concurrency live and dead-lock issue w.r.t. the said compaction.
1 Zero runtime cost because due to the compile-time determinism, we know at compile-time when the deallocation will occur.
2 How does Oleg’s insight conflict with @keean’s prior stance (in our discussions) against AST macros? I vaguely remember that you were against macros because they obfuscated debugging and the type system.
Is this the paper?  http://okmij.org/ftp/Computation/having-effect.html#HOPE
I can’t readily grok Oleg’s work because he communicates in type theory and Haskell, afaics he explains with details/examples instead of conceptually and generatively. And I do not have enough time to apply arduous effort.
Essentially all side-effects distill to the generative essence of shared state. If state is not shared, then there are no interactions of effects between those processes.
Afaics, a Monad controls the threading of access to an orthogonal context across application. That orthogonal context can be state in the State monad. Correct? That is why Monads can’t generally compose because they cordon orthogonal contexts.
But what is the goal to achieve? If we model higher-level concepts as imperative building blocks with contexts, we can do unlimited paradigms, but not only will our code become impossible to read because of the overhead of syntax and type system to allow for such generality, but we have an explosion of issues with the interaction of too many paradigms. Afaics, this isn’t headed towards a simple language.
There will not be a perfect language. Type theory will never be complete and consistent. Design is driven by goals.
Thoughts?

If i may :)
For me the main problem i would have with garbage collector is that they are harder to debug and test.
The nightmare i have is you will test the functionality on simple program, then it works, and you keep adding functions, race conditions, and two month latter you realize there is a memory leak or memory corruption somewhere, and you're good for days or weeks of debugging to trace the problem.
With reference counting, it's very easy to trace problem, because you know where the freeing must happen, the point where the last reference to an object is released can be tracked easily, and it make it very easy to track problems, either they are memory corruption due to memory being released prematurely , or memory leaks.
With garbage collector who will parse the whole tree every now and then, it will traverse thousands of pointer allocated over few minutes of running, and it can become much harder to track where the problem is if it free a memory that it shouldn't, or if it doesn't free a memory that it should.
Especially if you go for multi layered scope, with closures, and asynchronous code execution, it can become very hard to make sure the GC will catch everything right. And bugs will generally appear when the program start to become more complex rather than in easy vanilla cases when the program is small and simple.
And if you need to have a system of plugin, like code that are loaded at runtime that can manipulate references itself, it can become also impossible to track deterministically the reference tree at compile time, and the host program might have no clue at all of what the plugin is doing with the reference passed to it. And it's the same problem with distributed application.

My preference is to manage as much as possible from the stack as you can. There are some simple tricks that can make this work. If all allocation is RAII and you have proceedures not functions then to return some data you simply pass a collection (set/map/array etc) into the proceedure.

@NodixBlockchain (aka IadixDev @ BCT) wrote:

With reference counting, it's very easy to trace problem, because you know where the freeing must happen, the point where the last reference to an object is released can be tracked easily, and it make it very easy to track problems, either they are memory corruption due to memory being released prematurely , or memory leaks.

I wondering whether that is a superstitious, anecdotal belief (i.e. aliasing error) or an assertion you actually studied, measured, and verified to be the case. Because inherently reference counting doesn’t track the directed graph of memory allocation (i.e. all we have are reference counts and no back pointers to the references that comprise those counts); thus, there’s no feasible way to see which data structures have leaked because they’re no longer reachable from the untraced roots of the said graph— for example due to cyclical references. Whereas, in theory a tracing garbage collector could provide such a graph for debugging.
I previously mentioned the following disadvantages for reference counting to you (either in the Concurrency thread and/or the other thread you created). And note the first one below is a form of memory leak inherent in reference counting.
 And according to an expert book I’m reading there’s no known means of weak pointers or other paradigm which can reliably solve the problem of cyclical references in all scenarios.2 This makes sense because reference counting doesn’t contemplate the entire directed graph of objects holistically.
According to this expert book3, reference counting has significantly worse performance (except compared to the pathological asymptotic case for tracing GC) because of the significant additional overhead for ever pointer assignment. This overhead as a percentage is worse for highly optimized languages compared to interpreted languages which have high overhead any way. Additionally the adjustment of the reference counts on each pointer assignment thrashes the cache4 further reducing performance, except for optimizations which generally have to combined with a tracing GC any way (and they diminish the afaics mostly irrelevant claimed deterministic finality benefit).5 Additionally for multithreaded code, there is additional overhead due to contention over the race condition when updating reference counts, although there are potential amortization optimizations which are also potentially superior for parallelized and/or distributed paradigms6 (but they diminish the afaics mostly irrelevant claimed deterministic finality benefit). Additionally memory allocation management on the heap is non-deterministic, so the determinism of the immediacy of deallocation for referencing counting is afaics more or less irrelevant. Additionally reference counting (especially when executing destructors) can cause a dominoes cascade of latency (aka “stop the world”) and the amortization optimizations7 again diminish the afaics mostly irrelevant claimed deterministic finality benefit.
However, in my next post in this thread, I will propose a variant of deferred reference counting8 in conjunction with a clever generational GC scheme, for the avoiding the pathological asymptotic case of tracing GC.
1 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §1 Introduction, pg. 2.
2 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §3.5 Cyclic reference counting, pg. 56 – 62, §3.6 Issues to consider: Cyclic data structures, pg. 71.
3 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §2.1 The Reference Counting Algorithm, pg. 19 – 25, §3 Reference Counting, pp 43 – 74.
4 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §2.1 The Reference Counting Algorithm: The strengths and weakness of reference counting, pg. 22.
5 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §3.3 Limited-field reference counts, pp. 50 – 55, §3.3 Limited-field reference counts: One-bit reference counts, pg. 52, §3.6 Issues to consider: Space for reference counts & Locality of references, pg. 71.
6 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §8.4 Concurrent Reference Counting, pp. 200 – 201, §3.7 Notes, pg. 74, §4.1 Comparisons with reference counting, pg. 77.
7 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §3.1 Non-recursive freeing, pg. 44.
8 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §3.2 Deferred reference counting: The Deutsch-Bobrow algorithm, pg. 46.

@keean wrote:

My preference is to manage as much as possible from the stack as you can. There are some simple tricks that can make this work. If all allocation is RAII and you have proceedures not functions then to return some data you simply pass a collection (set/map/array etc) into the proceedure.

This is conceptually broadly analogous/related to deferred reference counting9 schemes which rely on compile-time deterministic tracing of the deallocation, such as via linear (aka uniqueness) types.
Although I was obviously also contemplating similarly to you in my prior posts in this thread (after you had reminded me about RAII in our previous discussions and my recollection of programming in C++ in the late 1990s), after reading a book on garbage collection and thinking more about the issues, I’m going to further argue against the compile-time deterministic memory mgmt language design strategy in my upcoming detailed post, because I believe it’s not as generally flexible, generally sound, nor highly comprehensible solution.
These stack memory mgmt paradigms you’re referring to, don’t handle the general case of non-deterministic heap management.
Afaics, it’s a special case methodology that leads to a very complex set of corner cases such as for C/C++ which tries to pile on a bunch of different sort of compile-time optimizations and keep as much memory mgmt on the stack, but lead to a brittle clusterfuck of a language with a 1500 page manual that virtually no one understands entirely (not even the C++ creator Bjarne Stroustrup nor the STL creator Alexander Stepanov).
And those stack paradigms don’t marry well holistically with a bolt-on tracing garbage collection appendage10 (i.e. was not design holistically with the language). To even attempt to apply these compile-time deterministic memory management holistically requires a complex typing tsuris akin to Rust’s total ordering of borrow lifetimes with lifetime annotation parameters for transitivity of borrows from inputs to outputs, and of course the programmer must violate the invariants and create unsafe code in order to handle non-deterministic (i.e. runtime randomized) memory mgmt, which defeats the entire point as then the total order is no longer checked and the unsafety can leak back into the code the compiler thinks is safe. I apply the 80/20 or 90/10 Pareto principle to prioritization. Although all that special case tsuris might be able to obtain an extra 10% of performance, it has the cost 90% more effort on debugging, readability of the code, maintenance of the code, complexity of the code, etc.. When you really need that 10% boost (or in the case where the more generalized GC paradigm is much slower for some reason), then go write a module in C++ or Rust. I see no need to invest my effort in trying to recreate (or improve upon) those languages, because there are millions of man-hours already in those ecosystems. Our only prayer of creating something useful in this decade with our resources, is to 90/10% prioritize on clean abstractions that are elegant and generalized and 90% performant with 10% of the effort and complexity.
Additionally, perhaps my GC design ideas (to be outlined in my next post) might possibly be compelling (if I haven’t made some errors in my thought process, which is entirely possible given I need to eat dark chocolate to even get my brain to ephemerally coax my brain out of the 105 IQ brain fog gutter and function non-lethargically presumably due to an ongoing TB infection). Note however, that the prior art for GC is apparently vast and seemingly exhaustive in terms of the low hanging fruit of obvious, simple variants11 (i.e. fertile ground presumably only in the realm of esoteric, high complexity, and/or obtuse). Thus, unlikely I discovered something (after a day of reading and contemplation) that hadn’t be considered previously in the prior art.
Total ordering compile-time paradigms (including attempting to type check everything) are afaics brittle paradigms that break because the programmer must necessarily break out of them because the entropy of the universe is not bounded.
My thought is we need to be circumspect about the benefits versus trade-offs of every paradigm and feature we choose in a programming language. And the target use cases (and acumen/preferences of the target programmers demographics) of the programming language will also factor into the decision process.
For example, Haskell programmers favor brevity and mathematical expression with trade-offs such as hidden (2nd, 3rd, and 4th order) details in the form of implicit typing (which the mathematically minded model in their mind without reading them explicitly in the code), which drastically reduces the demographics of programmers who can read the code and participate. Some snobbishly claim this is a good filter to keep the less intelligent programmers away. Haskell has other trade-offs (necessarily to enable the mathematical modelling) which we’ve discussed else where are outside the scope of this concise summary, including but not limited to (and my descriptions may not be entirely accurate given my limited Haskell fluency) the debugging non-determinism tsuris of lazy evaluation, the bottom type populating all types, a total ordering (or algebra) on implementation of each data type for each typeclass interface, a total ordering on the sequential (monadic) threading of I/O processing in the code (requiring unsafe code to fully accommodate the non-determinism of I/O), etc..
9 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §3.2 Deferred reference counting, pg. 45.
10 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §9 Garbage Collection for C, pg. 227.
11 Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, Preface: The audience, pg. xxiv, Preface: The Bibliography and the World-Wide Web, pg. xxv.

Kindle version of the book is available on Amazon for less then $20 if you don’t want to turn your monitor sideways to read the free pdf linked above.

The claims made about GC efficiency in those kind of books never turn out to be true in reality. Look at how JavaScript is slow yet emscripten can get within factor of 2 of native 'C', yet both run on the same VM. The difference is that asm.js and WebASM are strongly typed and manually manage the memory. In theory the JIT can make well typed JS code as fast as strongly typed code, so well typed TypeScript should be as fast as the compiled asm.js/WebASM, but its not. The remaining difference is mostly down to memory management in my opinion.

I wonder if this solution would work if the object instance referenced can change during the lifetime of the reference.
Because it would mean you might need to delete the referenced object before the reference get out of scope in case a new object is assigned to it during its lifetime.

You can see the efficiency of most GCs really easily: just look at % time
in GC. For programs designed with generational GC in mind, it won't be
above 10% and will more likely be < 2%. GC isn't the culprit for Javascript
running slower than webasm. Types are part of it, but it's more about
abstraction level. Higher abstraction means the runtime needs to perform
more work to get to machine code, and will be using generalisations (aka
baked in assumptions about trade-offs) to get there - and on a JIT time
budget too. Whereas webasm is designed to be efficiently and unambiguously
converted to machine code, so there will be fewer trade-offs, and the
compiler targeting webasm can spend much more time analysing the trade-offs
involved in reducing abstraction level.
I don't think there's any theory that JS would ever be as fast as webasm
under any reasonable  set of assumptions because of the time budgets need
to be taken into consideration. JIT means deadlines.
And that's without getting into the costs of semantic fidelity. You can't
simply pretend JS's prototype inheritance doesn't exist given typescript
source; all the work needs to be done anyhow, just in case, since the web
is a distributed system and thus non-deterministic.
On Tue, 21 Nov 2017, 18:14 Keean Schupke<EMAIL_ADDRESS>wrote:

The claims made about GC efficiency in those kind of books never turn out
to be true in reality. Look at how JavaScript is slow yet emscripten can
get within factor of 2 of native 'C', yet both run on the same VM. The
difference is that asm.js and WebASM are strongly typed and manually manage
the memory. In theory the JIT can make well typed JS code as fast as
strongly typed code, so well typed TypeScript should be as fast as the
compiled asm.js/WebASM, but its not. The remaining difference is mostly
down to memory management in my opinion.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/keean/zenscript/issues/35#issuecomment-346114141, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AAHypPkm1PWue63YbgWl4_-23tAvY5g4ks5s4xLugaJpZM4OZwjF
.

TypeScript can force you to stick to classes for objects, allowing the JIT to efficiently optimise these. Really for JS where there are no allocations going on it is as fast as asm.js. GC hides all sorts of costs, like the extra level of pointer indirection.
Probably a major factor is that GC hides the cost of allocation and deallocation, so the programmer does not realise they are thrashing object creation.

For me ideally GC are better when they works well, but they are much harder to design correctly.
Ideally it's sure GC is better in theory, allocation is fast, you don't have to care about anything in the world, because the GC will catch everything for you, it will compact the memory and catch automatically all unused memory.
But as one's says, the devils is in the detail, and when it deals with complex program, in multi thread environment, and has to deal with complex object hierarchy it's not always as great as in the book.
I'm aware there are many downside from reference counting that are a given in naive implementation, compared to well working optimal/ideal garbage collector, but i don't think those downside are that bad.
The cache issue for me i don't think it's a problem as pointer and reference count are supposed to always be in the same cache line, and optimizing cache on modern SMP anyway is kinda impossible and useless, unless you are doing video encoding or image processing in mono thread, or optimizing GPU multipass algorithm, but for general global variable management it's not really much a problem.
And thread contention is not a problem for the moment as i don't aim to have that much high contention on reference count. With 1 thread per core, already if i have to run 8 thread or 16 that will be a maximum, and i always make in sort not to have too many contention on reference count, mostly one reference in main thread, then atomic CAS aquire for another thread. Atomics fetch add is supposed to be lock free for two threads. And i don't think there will be many case where more than two threads can access the same reference in the same time.
I'm aware of the potential downside, but for me they remain benign for the use case i have for the moment. And they have the merit to be very simple, the principle can be explained in one sentence, and will works everywhere for everything without any bother, outside of cyclic dependency, and yet with my system i don't use bare reference count, but an explicit hierarchy of object/nodes, so i believe cyclic graph can be dealt with, as children are released bottom to top using explicit object hierarchy.
In my case the reference count is only the first layer in the memory management, and the object hierarchy is handled explicitly in an higher level that manage object graph.

GC is even worse with multi threads, because it has to stop all the threads to do the collection. This leads to GC pauses, and bad user interface Jank, plus programs crashing due to fragmentation...

The cache issue for me i don't think it's a problem as pointer and reference count are supposed to always be in the same cache line

The reference count needs to be in the object reference, not the pointer, so it won't be in the same cache line as the pointer. When you have multiple pointers to the same object they all need to increment/decrement the same counter.

See: https://softwareengineering.stackexchange.com/questions/203745/demonstration-of-garbage-collection-being-faster-than-manual-memory-management
The key fact for me is that managed memory usage is always significantly worse than the managed. Yes GC can be fast providing you have twice the RAM available. Typically on a multi-tasking machine this means less RAM available for other processes. This results is real slowdown of things like the disk-caching layer because its losing pages to the application.
The end result is that the user experience of using a system with GC is significantly worse than using a system with manual allocation - providing the software does not crash due to bad memory management :-)

I mostly just butted in because accusing GC for JS / Typescript being
slower than webasm seemed a bit outlandish. GC overhead is directly
measurable; it's trivially disproved for anyone inclined to measure.

Actually the difference in performance between JS and WebASM is only about 10-20% anyway, so that is in the 2%-10% region you claimed for the GC, so for some algorithms it could account for 100% of the difference...

It cannot be with the pointer, because when you create a new pointer to the array you need to increment the reference count.

With the system i'm doing, first need to aquire a reference and then aquire the pointer. Once the reference is aquired, the pointer can be safely accessed.
Reference are manipulated independently from the pointer. Sometime a part of the program can be just holding a reference without needing to access the pointer directly at all.
It's a two step thing to access the actual data from the object tree, first need to aquire  a reference to the object, then fetching the pointer from the reference. Or pushing the reference to another list (which will increase the reference count), or passing it to another function.
The main program rarely make direct pointer access at all. It's more like a reference to a boxed monad.
Can't really get a reference pointer to an element of an array like this.
The array will always be manipulated via the reference, and aquiring the pointer from the reference won't touch the reference count.
Pointer are always weak references. But need to own a strong reference to the object first to get the pointer to it.
Most of the time, it's a reference to a boxed monad, so the actual pointer will only be used by a monomorphized function from the reference passed to it. And it won't touch the reference count to get the pointer and access the data. The caller need to have access to a strong reference before passing it to the monomorphized function who will do the access from a weak reference fetched from the strong one.
In the principle the basics is similar to this
http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting/implementation
Except for now there is only the 'outter counter', but the structure is similar, with a structure containing the reference count and pointer, and the main program manipulate objects through this structure.
In the ideal my implementation will lean to more or less this algorithm of differential reference counting, even if it's only a partial implementation for the moment.
But it's especially made to avoid direct pointer manipulation from main application as much as possible, unless it need fast access to the data without going through the monomorphized function.

What make me think that cyclic dependency are not a problem with the way i handle it, is that i have a case of cyclic dependency like this.
There the node object, who contain a list of scripts, and script contain a reference to the node object.
So that's a cyclic dependency.
What makes it not a problem is that all the function that traverse the tree recursively have a max depth parameter to limit to depth of recursion, either it's to copy a whole tree of objects, or dump it to output, or traversing it. I always put a limit to the number of recursion.
And for freeing, as there is already an equivalent of destructor at each level, when the root node is released, it first release its list of scripts, which release their reference to the node, before the node is actually released and freed, and it doesn't cause the problem with cyclic dependency if it's used in this context.
It wouldn't work if i barely decrement the last reference to the root node, but as it already contain a destructor who can logically be called explicitly and will recursively release all the reference to all it's descendant before releasing the reference to it, normally it takes care of cyclic references.
As long as each level of objects have a destructor that release all reference to it's child, and that each level is freed explicitly, normally it can free tree with cyclic references.
There are probably some cases where it wouldn't work, but for most sane configurations where each object have a destructor who is called explicitly to release it which take care of freeing all it's children references, it can deal with cyclic references.

@NodixBlockchain I asked you to please respect my thread and you are not doing what I asked.

I can’t speak for @keean (and this is his project area but this is my thread), but personally I’d prefer “please don’t” (or post once for every 10 posts by others in this thread, so as to keep the S/N ratio of the thread higher), i.e that you would comment in your thread instead (or at least not in this/my thread), unless you have something new+important+accurate+well-researched to point out which you have not written already in the past.
If you quote from this thread, and post in your thread, I will probably read (presuming I have time) and perhaps even reply there. I’m trying to avoid this thread becoming another 300+ posts that I can’t wade through when I want to refresh my own memory of what my (and @keean’s) analysis was/is.
@keean and I have been doing backtalking on LinkedIn to reduce clutter in theses issues thread. You’re welcome to add me there.

@keean wrote:

The difference is that asm.js and WebASM are strongly typed and manually manage the memory. In theory the JIT can make well typed JS code as fast as strongly typed code, so well typed TypeScript should be as fast as the compiled asm.js/WebASM, but its not. The remaining difference is mostly down to memory management in my opinion.

TypeScript transpiles to JavaScript (ES6), not ASM.js nor WASM.
Also C code which is transpiled to ASM.js/WASM, is employing different abstractions such as not boxing every damn thing, such as every element of every array.
Also I believe JS may be passing all function arguments on the heap (the prototype chain of objects which form the closures we talked about), and thus although the throughput and locality is similar, the volume of objects before a collection is much greater than for stack passed arguments and thus the cache may be getting thrashed.
C code rarely employs hashmap lookup, yet JS literally encourages it since all object properties and non-numeric array indices employ it.
There are many more details and we would need to study all the reasons:
https://news.ycombinator.com/item?id=7943303
https://www.html5rocks.com/en/tutorials/speed/v8/
https://blog.sessionstack.com/how-javascript-works-inside-the-v8-engine-5-tips-on-how-to-write-optimized-code-ac089e62b12e

Probably a major factor is that GC hides the cost of allocation and deallocation, so the programmer does not realise they are thrashing object creation.

Agreed, e.g. do not realize they boxing everything.
@barrkel wrote:

Types are part of it, but it's more about
abstraction level. Higher abstraction means the runtime needs to perform
more work to get to machine code, and will be using generalisations (aka
baked in assumptions about trade-offs) to get there - and on a JIT time
budget too. Whereas webasm is designed to be efficiently and unambiguously
converted to machine code, so there will be fewer trade-offs, and the
compiler targeting webasm can spend much more time analysing the trade-offs
involved in reducing abstraction level.
[…}
And that's without getting into the costs of semantic fidelity. You can't
simply pretend JS's prototype inheritance doesn't exist given typescript
source; all the work needs to be done anyhow, just in case, since the web
is a distributed system and thus non-deterministic.

+1.

I’m wondering whether that is a superstitious, anecdotal belief (i.e. aliasing error) or an assertion you actually studied, measured, and verified to be the case with in depth effort for comparing reference counting and tracing garbage collection. Because inherently reference counting doesn’t track the directed graph of memory allocation (i.e. all we have are reference counts and no back pointers to the references that comprise those counts); thus, there’s no feasible way to see which data structures have leaked because they’re no longer reachable from the untraced roots of the said graph in a reference counting GC system— for example due to cyclical references. Whereas, in theory a tracing garbage collector could provide such a graph for debugging.

If you consider reference as objects with a delete operators rather than only a pointer with a free, the destructor can release reference to childs before to release the reference.

@NodixBlockchain wrote:

If you consider reference as objects with a delete operators rather than only a pointer with a free, the destructor can release reference to childs before to release the reference.

I already told you that explicitly asking the programmer to remember to break cycles is off-topic (i.e. the destructor will not be automatically fired if there is a cyclic reference preventing the parent most object's reference count from going to 0):

This is off-topic. Explicit, unchecked (i.e. “unsafe”) manual mgmt is not what we are interested in here. The topic was about automatic (or compiler checked deterministic) mgmt. As you know, both @keean and I are significantly into compiler-assisted checking.

Although you’ve deleted (or moved to your thread?) those numerous prior off-topic posts I asked you to (thank you), you want to repeat the same points of off-topic noise. I understand you think you have something important to say, but you apparently did not even pay attention or grok that I had already stated that it (i.e. the same point you’re repeating again) was/is off-topic.

It's not anecdotal, i have fully working application server with it's own memory management, object oriented script language, which deal with thousands of objects and i never spent more than 1h on tracking memory leak in the whole development cycle because i have clear methodology to track them.

How many times am I going to have to repeat myself that I am not interested in discussing further the anecdotal claims of your low-level framework. You’re missing the more holistic point that:

We’re (or at least I’m) not interested in your manual “unsafe” (i.e. not checked by compiler not runtime enforced) paradigm. Been there, done that in the 1980s and early 1990s. In late 1990s I adopted simplistic reference counting with C++ for CoolPage. Now I’m advancing further. IMO, you’re a dinosaur.

My reasons for not being interested are detailed in my prior response to @keean and @barrkel.
You’re preferences and experience with your framework are not indicated of the development costs for the community with such a paradigm, i.e. your arguments are anecdotal. When you have a large community and a lot of research/surveys/metrics amongst many general purpose applications refuting the exposition I have made based on more extensive sources, then we can discuss yours.

If you’re interested in your paradigm in spite of the convincing exposition in my prior posts, then please feel free of course to discuss in a different thread. I may occasionally read there. If you make your best arguments there (not in this thread) and if I see anything I agree with, then I will quote it over here (and invite/entice you to discuss here). Please do not pollute my thread (at least respect the one post for every 10 others request, or 7 if all the posts are lengthy and infrequent) with what I currently perceive to be off-topic discussion. I do not want a interactive chat style discussion in this thread. We can chat back-and-forth realtime in private. I wanted focused, carefully thought out discussion that is easy to re-read and condense enough for others to follow.

@keean wrote:

The reference count needs to be in the object referenced, not the pointer, so it won't be in the same cache line as the pointer. When you have multiple pointers to the same object they all need to increment/decrement the same counter.

Agreed, but note in my prior post with the many footnotes about GC, I cited some research (Weighted Reference Counting) that places the count in the pointers for allocation and only has to decrement the shared count on deallocation. Also cited research about employing the reference counting only for a single-bit stored in the pointer in a reference counting generation scheme. Also in an earlier post I suggested to pulling all the counts closer together in contiguous locality to minimize cache line and virtual page faults.

The thing is my paradigm is the basics for high level language, which is fully working with JS/Json, can generate binary data for webGL apps, or other kind of dynamic application.
Even Node.js or javascript VM use this kind of code internally. You can't have any kind of high level language without this kind of code underlying it.
And for the moment it give more feature than javascript as it work in multi threaded environment and memory can be freed safely when it's not used directly.
The script language can already process HTML data, including form variable, query variable, and interact 100% with js app, and i think it's still cleaner than PHP.
for  example https://github.com/NodixBlockchain/nodix/blob/master/export/web/nodix.site#L555
It can parse POST variable, including files, generate js variable and code with live variable from the node etc.
The low level mechanism is only to be seen as a minimalistic VM to run the script language, which either handle network events, or generate html page with dynamic data.
Any kind of advanced high level language will need this sort of code to manage memory, references, multi threads etc

@NodixBlockchain, you’re repeating the same points I already discussed with you in the Concurrency and your other thread. I refuse to repeat my explanations again to you as to why what you think is applicable, is not applicable to what I am doing.
Please stop. Please.

@keean wrote:

Interestingly I am about to port a bunch of asm.js to typescript, as the memory allocation for asm.js / webasm does not work well with the main JS garbage collector, and allocating the heap for the webasm is causing fragmentation of the JS heap. In the end it turns out that the better memory usage, keeping all them memory managed by the GC is better for the application stability than the small performance gain of having the code in asm.js.

Edit: its probably worth pointing out that this application uses a lot of memory, and has some periods when it is performing rapid allocations. This leads to memory usage for a single tab of about 1GB (even though memory buffers are 16mb so with manual allocation it would get nowhere near that level). Frequently when usage gets more than 1GB the web-browser crashes, even though most of that memory is probably free, and just waiting to be collected.

Has something to do with the fact that most browsers are limited to 32-bit virtual address space and this gets very complicated as to how they split this up between processes. They also have to protect against writing outside of bounds efficiently. I dug a little bit into the issues (c.f. links in quoted text below) but did not completely climb down the rabbit hole.
@shelby3 wrote:

For this last quoted issue, I am contemplating the ability to employ the unused bits (c.f. also) of 64-bit pointers (64-bit also provides a huge virtual memory space and c.f. also) would enable storing an index into a contiguous array which has the reference counts as array elements so they would be in contiguous pages.

I had mentioned to you in private discussion my idea about storing older generation objects in same sized objects memory pages in order to minimize fragmentation with a 64-bit virtual address space.
I agree that the memory allocation seems to have corner cases around the interaction of the GC in JS and the allocation of the ArrayBuffer for ASM.js/WASM.
I’m contemplating whether I can design my own programming language which models what I want, will tolerably to transpile to JS/TypeScript (or something else) easily enough to allow me to use it now, and then rewrite the VM and compiler later to optimum. This is what I’m analysing now and the reason I’m doing research on GC.
@keean wrote:

Following this argument to its logical conclusion, the better memory usage of manually managed memory for the whole application would be better overall.

How do you arrive at this conclusion? Have the posts I have made since you wrote that, changed your mind?
Afaics, the optimum solution is to better design the GC and VM with the low-level coding in mind. JavaScript was designed by Brendan Eich in 10 days.

Sometimes I ponder if the trolls at BCT paid you to come and disrupt me.

Just have to comment on this, you're paranoiac dude lol

How do you arrive at this conclusion? Have the posts I have made since you wrote that, changed your mind?

Because I am good enough to get the manual memory management right, and it will use a lot less memory, which will result in less fragmentation, and less crashes and therefore a better user experience.
I am still convinced that static analysis and region based memory management is a sweet spot for high performance languages.
I think GC is useful for simple coding, but there are some big problems:

it encourages object thrashing
it suffers from fragmentation
it causes user-interface jank due to the 'stop-the-world' nature of GC.

If you have a system with all three of the above problems, there is nothing you can do as a programmer within the language to solve the problem.
You can however solve problems (2) and (3) if you can avoid (1) by limiting object creation. If you can force pre-allocation of resources, and then use effects to restrict new object creation, so that the compiler will prevent you using idioms that thrash the GC then it could be acceptable. The problem is that you need all the library APIs to respect this too, and provide a way for the user to pass the result buffer into the function/procedure. As we know if you give people multiple ways to solve a problem they will probably pick the wrong way.
This is why I am interested in a language that forces people to do things the right way, so that then library APIs will always be written the correct way. Of course this might not make the language very popular, but I think it is an interesting approach to explore.

@NodixBlockchain wrote:

Sometimes I ponder if the trolls at BCT paid you to come and disrupt me.

Just have to comment on this, you're paranoiac dude lol I don't have anything to do with anyone on BCT lol

It’s half-joke and half observing that the trolling of BCT seems to follow me over here. However, it must be stated that you’re not insincere. You truly believe (or believed) your work is applicable to what I want (or to the balanced presentation for other readers/participants here). I just don’t know how much verbiage I have to put out in order to get you to understand my side. Seems like perhaps you understand now. Again I am very much willing to read anything you write in the thread you created on @keean’s repository, if I have time. But I hope you will understand my point in this thread. I suggest re-reading the thread, as I made so many edits to my posts over the past 8+ hours, including my prior responses to you in this thread.
Again thank you for cooperating on my request. That was very honorable. I’ll try to be mutually respectful in your thread.

@keean wrote:

Because I am good enough to get the manual memory management right, and it will use a lot less memory, which will result in less fragmentation, and less crashes and therefore a better user experience.

That appears to ignore the arguments @barrkel and I have made about the 80/20 rule of nature.
That appears to be the hubris of anecdotal experience not backed by a sound analysis of the factors involved: which I will revisit below since apparently my prior writings in this thread are being ignored.
No one should dictate to you which programming language you should use. Likewise, you can’t dictate to the rest of the world, what it prefers in terms of trade-offs in costs and outcomes for choice of paradigms in the programming languages. Java, JavaScript, Python, PHP, Haskell are very popular programming languages which all use tracing GC (and apparently not even the state-of-the-art GC):
@shelby3 wrote:

Even Google’s JavaScript V8’s GC is only incremental, generational with a standard pathological asymptotics mark-sweep for the older generation.

C/C++ are also popular, but afaik they do not match the aggregate market share of the others. As well, C/C++ these days is typically is limited to programs which require low-level control.
My quest in @keean’s repository has to been to get the advantage of GC and perhaps some other aspects of FP such as first-class functions and closures in a simple language that also can do some low-level things such as unboxed data structures. To further erode the use cases where C/C++ would be chosen, to relegate that clusterfucked C++ language (and perhaps Rust also but the jury is still out on that) more and more to the extreme fringe of use cases. For example, It is ridiculous that I must employ a cumbersome Node.js Buffer library to build an unboxed data structure.
Also I think you may be underestimating the trade-offs (at many different levels such as development time, maintenance, worst case failure modes, scalability, etc) of avoiding the assistance of runtime algorithms. Essentially since non-deterministic resource mgmt is an invariant of programming, you’ll end up writing a runtime GC algorithm to handle it, so I can’t see how your stance makes any sense whatsoever:
@shelby3 wrote:

Yes the choice is between static or runtime checking. The best is to use the stack, so there is no need for checking, but that does not work for all scenarios.

Generational GC is very efficient nearly as much as the stack (as I explained) and I am going to propose an algorithm that I am thinking might make it even more efficient.

What he fails to realise is that 2-10% is only true when you have enough memory.

It is true that the asymptotic computational complexity (i.e. performance) of tracing GC is pathological both as live memory usage approaches/exceeds the bound of physical memory and as total memory consumption increases for computers with more GBs (or TBs) of DRAM. That is why I cited that research for footnote16 in my prior post—which btw my independently derived idea seems to be roughly analogous to—for removing the pathological asymptotics by leveraging an optimized form of RC for the older generations. I will write my detailed post about this soon.
And that is why I allude in my response to @barrkel to the time vs. space trade-off approaching parity between automated GC and manual/stack/compile-time deterministic paradigms for memory management. The reason that the deterministic paradigms you espouse will not exceed the space vs. time trade-offs for the throughput (nor maximum latency pauses) of state-of-the-art automated GC in general is because I repeat that memory allocation mgmt is inherently non-deterministic (thus requires runtime management)!
Also there is research1 (which I haven’t read yet) which seems to indicate that as the number of (perhaps also non-deterministic) factors (e.g. power and energy management issues) that need to be managed increases, then automatic algorithms may become the most plausible (reasonable cost, time-to-market, stability, maintenance) for most applications with hand-tuning being further, further relegated to the esoteric that demand extreme tuning (e.g. the NASA space shuttle).
[…]
1 T. Cao, S. M. Blackburn, T. Gao, and K. S. McKinley, "The Yin and Yang of Power and Performance for Asymmetric Hardware and Managed Software," in ISCA ‘12: The 39th International Symposium on Computer Architecture, 2012. Originally found on Steve Blackburn’s website. Also T. Cao’s master’s thesis prior art.

@barrkel wrote:

The argument in favour of GC isn't speed of execution, it's speed of
development at very low costs - an extra 2 to 10% or so. Speed of
development in memory safe languages is significantly higher

+1.
Also it is about consistency of memory mgmt, i.e. avoiding the pitfalls of the average programmer or rushed development team.

Yes, GC scales because it trades space for time. If you're running on a
small embedded device, it can be a poor tradeoff; if you're trying to
maximize compute throughput across multiple machines, it can cost real
dollars. But these are extremes, and most people aren't on the extremes.

Well yes, but as I mentioned above in my reply to @keean, and I presume you’re also alluding to, that the differences in space vs. time tradeoffs between automatic and manual memory mgmt are getting closer to low double digit (or even single digit) percentages (i.e. “extremes” of optimization) and thus heavily favoring automatic GC for most use cases. Note I’m not conflating this metric with the 2 - 10% figure for throughput differences that you asserted.

In my prior post, I had alluded to how attempting to have the compiler check memory mgmt is forcing it into a deterministic, total order, which will necessarily cause the programmer to violate the compiler checks and leads to bugs (unless perhaps that compile-time paradigm is somehow limited to only deterministic instances, but from my study thus far it appears that the cross-pollution/interopt between young and older generation allocation makes non-deterministic, runtime automated algorithm interop with a deterministic young generation have worse characteristics than a runtime, automated generational non-deterministic collector for the younger generation):

To even attempt to apply these compile-time deterministic memory management holistically requires a complex typing tsuris akin to Rust’s total ordering of borrow lifetimes with lifetime annotation parameters for transitivity of borrows from inputs to outputs, and of course the programmer must violate the invariants and create unsafe code in order to handle non-deterministic (i.e. runtime randomized) memory mgmt, which defeats the entire point as then the total order is no longer checked and the unsafety can leak back into the code the compiler thinks is safe.
[…]
Total ordering compile-time paradigms (including attempting to type check everything) are afaics brittle paradigms that break because the programmer must necessarily break out of them because the entropy of the universe is not bounded. I commented on this previously numerous times in these issues threads. The non-determinism (i.e. unbounded randomness and entropy) of the universe (i.e. the real world in I/O) can’t be statically modeled.

@keean wrote:

I am still convinced that static analysis and region based memory management is a sweet spot for high performance languages.

For the highest quality software (i.e. mission critical stuff) yes, but I see already from my study of the research that gradually (even suddenly) state-of-the-art GC will continuously improve and cannibalize most of it until you’re relegated to programming languages that most people have no interest in. You always knew I was interested in mainstream programming languages. So if you remain glued to that stance then we're likely headed in different directions. I thought I was going to be supporting static memory allocation analysis for Lucid, until I realized that generational allocation can be as performant as compile-time stack based for the frequent young objects (and I have a new algorithm in mind to make it more so by eliminating most of the copying, i.e. “sudden” may be about to happen in a few hours).
Btw, I’m known for writing prophetic predictions. There’s some hubris back at ya. :kissing_heart:

I think GC is useful for simple coding, but there are some big problems:
it encourages object thrashing
it suffers from fragmentation
it causes user-interface jank due to the 'stop-the-world' nature of GC.

This has all been solved as of today.

This is why I am interested in a language that forces people to do things the right way, so that then library APIs will always be written the correct way. Of course this might not make the language very popular, but I think it is an interesting approach to explore.

You mean @keean’s way. I will prove to you that is not the right way.

If we are targeting JavaScript, this is irrelevant, as we have to live with the web-browsers GC. Mozilla's work with their Rust browser has shown you get better performance by bringing the DOM into the JavaScript GC, rather than having it reference counted.
I think if you have GC the best model is to have everything managed by the GC, otherwise there seem to be more corner cases. For example mixing JavaScript and WebAsm seems to bad for memory performance.
So either we compile to web-assembly and manage the memory ourselves, or we should use the web-browsers GC. If we have any interaction with GC manages systems we are probably better off using the web-browsers GC.
However when compiling to native, it would be nice to have a static analysis so you don't need a runtime for the binary. I would really like it if a program to add two numbers consisted of a couple of loads and add and a store and nothing else.
As stated above, the benefit of GC is easy development, and freedom from some errors. Unfortunately people don't seem to realise you can still leak memory with GC, it eliminates some simple error cases, but you can still write programs that leak memory like a sieve until they crash.
In my experience it is much harder to debug memory leaks with GC than it is with manual allocation, because it is invisible to the programmer. So GC makes some easy coding easier, and some hard coding harder, but the easy cases are common and the hard ones rarer.

@keean wrote:

If we are targeting JavaScript, this is irrelevant, as we have to live with the web-browsers GC.

I’m considering abandoning JS because of its crappy GC which doesn’t interop with low-level programming. Working on the detailed analyses now.

I think if you have GC the best model is to have everything managed by the GC, otherwise there seem to be more corner cases. For example mixing JavaScript and WebAsm seems to bad for memory performance.

That seems to agree with what I’ve learned thus far.

So either we compile to web-assembly and manage the memory ourselves

This is the direction I’m more strongly considering now based on the aforementioned realization. But I want to use an automated GC running on WASM.

If we have any interaction with GC manages systems we are probably better off using the web-browsers GC.

No.  Must be replaced.

However when compiling to native, it would be nice to have a static analysis so you don't need a runtime for the binary.

That is no relevance in the mass market use cases I’m targeting.

As stated above, the benefit of GC is easy development, and freedom from some errors.

And avoiding maintenance hairballs, and many other things I have already explained. You’re understating the massive, pervasive benefits.

Unfortunately people don't seem to realise you can still leak memory with GC, it eliminates some simple error cases, but you can still write programs that leak memory like a sieve until they crash.

Irrelevant. “Programming languages can have bugs” is not an argument.
The problem GC solves is a fundamental and massive problem in programming. That it does not eliminate all programming bugs is irrelevant.

In my experience it is much harder to debug memory leaks with GC than it is with manual allocation, because it is invisible to the programmer.

Create better analysis tools then. Refer to the response I already made to @NodixBlockchain on that issue.
It’s a confirmation bias to find excuses to argue for an inferior programming paradigm.

I think you missed my point, I was suggesting exactly the same program could be compiled for a GC target or a statically managed target. There is a clear subset where this is easy to to (stack based RAII), and if you change target and something cannot be solved without GC then you would get a compile time error.

@keean wrote:

GC is even worse with multi threads, because it has to stop all the threads to do the collection. This leads to GC pauses, and bad user interface Jank, plus programs crashing due to fragmentation...

It’s understandable why you might think this, but in the context of the new BG-RC design which that 2003 paper describes and which is my ideas were very similar to and I have some additional innovations I can add to theirs, I realize that multithreading can be accommodated very efficiently if we are adopting JavaScript’s single-threaded event queue model, i.e. each thread is more or less isolated except for read-only shared object accesses.
JS’s current BG-MS garbage collector has huge asymptotic pause times for the MS collection of the old generation objects, thus they must not allow even read-only shared references between old generations.
But with the very low pause times of BG-RC because most of the old generation is RC due to very low mutation rates, thus this is the read-only shared objects that have very low contention because they are rarely collected and collected incrementally as they occur.
The BG (generational young generation) portion runs separately in each thread and the non-RC portion of the old generation (which is a small minority of the old generation for highly mutated objects) is separate for each thread.
So all threads STW (stop-the-world) for the very low pause times and very low contention as they coordinate their very minimal collesced updates to the RC.
It's all about clever amortization.
BG-RC changes everything. I have no idea why Java 9’s new GC1 collector is apparently not BG-RC. Perhaps constraints of the JVM (Hotspot et al) preclude it.
I will explain all of this in more detail soon. Need to get some sleep.

The results are never as good in reality. See: https://goo.gl/images/vi6pce as you can see BG-RC performed worse than BG-MS, and that in turn was worse than simple mark-sweep. For general use nothing beats the mark-sweep garbage collector, but it still has all the problems we discussed. You can make the worst-cases for GC less bad, but that always makes the common-cases less good. There's no such thing as a free lunch as they say.

So GC makes some easy coding easier, and some hard coding harder, but the
easy cases are common and the hard ones rarer.

The pb for me is even if there is one hard case in the whole program that's
enough to kill the whole thing.
Le 22 nov. 2017 23:24, "Keean Schupke"<EMAIL_ADDRESS>a écrit :

The results are never as good in reality. See:
https://goo.gl/images/vi6pce as you can see BG-RC performed worse than
BG-MS, and that in turn was worse than simple mark-sweep. For general use
nothing beats the mark-sweep garbage collector, but it still has all the
problems we discussed. You can make the worst-cases for GC less bad, but
that always makes the common-cases less good. There's no such thing as a
free lunch as they say.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/keean/zenscript/issues/35#issuecomment-346489276, or mute
the thread
https://github.com/notifications/unsubscribe-auth/Ab61I0ilNM_6K47wMsS2AmOtV_hG2EW-ks5s5J8dgaJpZM4OZwjF
.

@keean wrote:

The results are never as good in reality. See: https://goo.gl/images/vi6pce as you can see BG-RC performed worse than BG-MS, and that in turn was worse than simple mark-sweep.

Why are you attempting to lie? That slideshow doesn’t conclude that BG-MS outpeforms BG-RC on throughput nor maximum pause times.
All that it says that is that when heap size declines, BG-RC performance degrades faster than BG-MS.
This is because of the hokey cyclic collection algorithm they chose. I told you I have an improvement which I think will correct that. I have a new design for incremental MS to correct the cyclic detection problem.
I was shocked when I saw they were using a localized algorithm to search for cyclic references, which has at worst an exponential asymptotics.
Even “manual memory mgmt” will not be able to do any better on the time vs. space tradeoff.
You’re grasping at straws.

Another perspective, which matches my experience of fighting the garbage collector: http://prog21.dadgum.com/134.html
Also I re-read the paper, and I did get those performance metrics backwards. If it's as good as the paper says, I wonder why nobody is using it.

But there is nothing perfect, not even manual memory mgmt. At least a reproducible automated >algorithm that includes all the wisdom and profiling of a huge investment in perfecting automated GC, >is going to get us as close as possible to optimum in general and on average. Of course there will >always be corner cases in any programming system.

It's not to do my linus, but in a way there is no 'gray area', there is no easy case, hard case, and corner case, there are just cases. If the GC can deal with all the cases properly then it's broken period.
And this article get quite to what i see with most GC language. If the program is small and simple it will work fine, but once you need to handle loads of data, have big list of potentially complex references, it still need some sort of assisted memory management to get things right.
https://samsaffron.com/archive/2011/10/28/in-managed-code-we-trust-our-recent-battles-with-the-net-garbage-collector
It's not like you can go ball out allocating millions of object with reference without a care in the world about how to optimize memory in sort that objects that are short lived can easily be detected as such, and that GC will always function in optimal manner without some form of manual optimization.
In a way GC just make the manual optimization that will always be needed somehow more tricky and more complex. But it's not like you can completely forget about memory allocation at all and only rely on the GC for everything without any care for how it will work, and some form of manual management of object lifetime and how they are represented in the GC etc.

@NodixBlockchain wrote:

https://samsaffron.com/archive/2011/10/28/in-managed-code-we-trust-our-recent-battles-with-the-net-garbage-collector

Have many times am I going to have to explain that the BG-PC of the 2003 research paper eliminates the long collection pauses because it doesn’t have to mark-sweep (MS) the entire old generation.
 You’re being disrespectful to my thread. I asked you to wait at least 6 long posts by others between your posts. And 10 if any of the others are short.

If the GC can't deal with all the cases properly then it's broken period.

Nothing, not even manual mgmt, can deal with all possible cases.
The entire point is the GC can do about as well as manual memory mgmt can do with the same resources.
If you want to expend all that extra effort on manual memory mgmt for an obtuse case, then go ahead. No one is stopping you. In the meantime, please stop shitting on my thread. I hope this is the last time I have to ask you.

I wrote:

I don’t understand how a generational garbage collector is going to have a problem with the volume of data allocations in young generations, unless it is exceeds what any form of memory mgmt could handle with non-deterministic allocation order.
[…]
There are going to be cases where one will have to try to devise a deterministic allocation scheme in order to get the performance they want. When deterministic is feasible, then yes higher performance than a non-deterministic algorithm is possible. But compare apples-to-apples. Don’t compare deterministic to non-deterministic allocation, because they’re not the same code base, algorithm, and problem set.
The reason I propose to not provide facilities in the compiler for static linear-typing and region analysis (a la Rust), is because I think the use cases are exceptional  and in that case the programmer should devise some very specific/customized deterministic allocation solution for his needs. And because for a programming language design we have to stay within a complexity budget.

Examples of deterministic allocation that would overload the automated non-deterministic GC, are assignment of a new instance either exclusively to a block scoped pointer (aka pointer stored locally on stack) in a loop, or as in @keean’s image buffering example allocating a new 16MB buffer each time his code needs one:
p = new Object

So in the first case, the young generation allocator is slammed with an new allocation for each iteration of the loop, and in the latter case the old generation allocator accumulates 16 MB allocations which have to be collected (and with a MS collector that is going to be very costly).
Both of those can be structured as deterministic allocation strategies and made much more efficient. In the first case, the static analysis of the compiler can determine that the newly allocated object is only ever referenced (beyond a single iteration of the loop) by the one pointer it is assigned to and thus the allocated space for the object can be used (i.e. the newly allocated object can replace the prior allocated one in the same memory location). For the latter case, assuming the 2003-invented BG-PC allocator is employed (which apparently no languages yet employ), then the programmer can reuse the same pointer always for the buffer so the compiler can check that the reference count on the prior allocated 16 MB object/buffer is going to zero when the newly allocated object/buffer will be assigned, and thus allocate the new object/buffer replacing the object/buffer that is being freed in the same memory location. Afaik, @keean wasn’t recycling his 16 MB buffers instead of reallocating them because of some flaw in the standard APIs of the WWW.

So Rust has lifetimes which apply both to data races mutable memory safety (which also applies to multithreaded data races) and escape analysis optimization which prevents use-after-free while enabling deterministic resource (not just memory) deallocation (thus proving safety for stack-based memory allocation). And non-deterministic resource deallocation in Rust is handled by explicit reference counting, which is an explicit pointer type, thus complicating the type system with 3 different types of pointers (complexity that @keean and I agreed is not desirable).
All the non-deterministic younger generation deallocation is inefficiently pushed into reference counting explicitly. So an improvement might be to combine Rust’s lifetimes with that aforementioned year 2003 invented BG-PC automated garbage collector, possibly to gain the efficiency of fast generational collection of the young objects which escape deterministic lifetimes and potentially eliminate the need to statically declare the type of each pointer. The compiler could I presume detect from lifetime analysis which pointers can be deterministically allocated on the stack. Pointers that escape lifetime analysis thus could be delegated to the generational GC which for older generation objects employs efficient PC + cyclical references deallocation with low pause times.
My prior post in this thread gave an example of the sort of deterministic optimization I hoped the compiler could do, but I realize such optimizations require escape analysis and the compiler would still need use to annotate lifetime parameters because otherwise:

the computational complexity might explode
APIs would not be stable
non-monomorphized dependency injection (e.g. typeclasses) and higher-ranked callbacks couldn’t be escaped analyzed (analogous to the method overloading problem)

Tangentially, how can the Rust lifetime parameter be declared for a function input which is also an output where the input state has a different lifetime than the output state? I presume this is not currently supported by Rust. Because afaics, non-reference counted references in Rust are always immutable (only the object they point to can be mutated). So I presume Rust forces the use of reference counted pointer for mutable pointers.

@keean wrote:

Ada has statically safe pointers (called access types) without all the complex lifetimes of Rust. This is the kind of model I was thinking about.

So access typed pointers are presumably deallocated when the block scope in which the type was defined is exited.
But that is much less flexible and less optimized than generalized escape analysis.

When upthread while studying GC, I basically independently thought of the design for BG-PC before discovering the year 2003 prior art for it, I had thought of some potential improvements to the prior art. The two ideas of mine which have survived thus far, are both pertaining to a generational collector:

The option of promoting younger generation objects to the mature space instantly when the write-bound detects their asssignment to a mature object’s pointer, instead of deferring them to a young generation copy-collection phase. This I suppose eliminates the overhead for tracking which objects to promote at the copy-collection phase and I would think simplifies integration with (when promotion is to) a RC collected mature space. Perhaps the reason this isn’t done is to retain economies-of-scale and locality optimizations.

Generational copy-collectors have a trade-off between duration of period between collections (which impacts how many objects leak to mature collection when they could have been collected more efficiently with a period longer than their allocation lifespan), the frequency of collection (for space and locality efficiency), and the amount of duplicate copying due to copy-collecting numerous times before promotion in order to increase said frequency.
Instead of copy-collecting the entire younger generation monolithically and tagging the object with the number of times it has been copy-collected (with promotion occurring when said count reaches a threshold), I propose to divide the young generation into separate copy-collected regions, one for each copy-collected count required for said threshold. Then perform each copy-collection only twice on each region: once for its first count and again on the last count before promotion. After each copy-collection phase promote the surviving objects in oldest region and bump the count of each region.
We can make things better by having value semantics, and storing values directly on the stack (providing they are under a certain size to prevent stack overflows), and by having object pools that re-use objects, and mutating object in-place.

As I have developed my understanding in this thread, I have come to the conclusion that the language I want needs:

static analysis of lifetimes with lifetime parameters annotation, but without the unnecessary tsuris of Rust’s exclusivity of mutual borrowing. Lifetimes which do not escape static/compile-time analysis, can be managed deterministically, with small enough objects on the stack and larger ones on the heap. Ada’s access types are much less powerful.

The lifetime analysis will aid an optimizing compiler in automatically mutating object in-place, because the compiler can detect which lifetimes don’t overlap and can reuse space. There would need to be some other manual facility for reusing object space for objects that escape compile-time lifetime analysis. Lifetime analysis can be applied to non-memory resources also a la Rust.

Reference counting (with the Bacon test deletion method of avoiding cyclical reference memory leaks) could be employed for all objects which escape static lifetime analysis. Future work: not sure if we’d need some mark-sweep heap for objects that would otherwise have their reference counts modified too frequently, and whether the runtime could automatically and dynamically manage which objects to put in the MS heap or whether the programmer would need to manually indicate which objects need this optimization.

Linked-lists of free space memory allocators fragment the memory space too much and exhibit poor locality for cache and memory paging faults performance. Allocating in blocks which are multiples of the virtual memory page size will enable less fragmentation because the virtual fragmentation can be mapped to contiguous physical memory, especially viable with a 64-bit address space so that virtual address space isn’t depleted by fragmentation. The optimum solution appears to be for small objects a bump-pointer style monotonic allocation within multiple of page size blocks wherein none of the freed space in the block is reused and the entire block is not freed until every object in the block is freed (c.f. “§<IP_ADDRESS> Mark Region”). That enables fast allocation by bumping a pointer and fast deallocation by decrementing a counter. Fragmentation induced by delayed freeing of blocks is in virtual memory space thus mostly irrelevant given a 64-bit address space. The MMTk segregated free space allocator seems to employ some variant of this strategy.

I had been averse to the tsuris and noise of Rust’s lifetime parameter annotations.

Today I had added an edit to my significant motivations for creating a new programming language (Lucid) to reflect the my direction in this thread. Then someone reminded me to go read ESR’s recent blogs. That said linked edit corresponds nearly precisely with some recent blogs by Eric S. Raymond:
ESR wrote:

My last post (The long goodbye to C) elicited a comment from a C++ expert I was friends with long ago, recommending C++ as the language to replace C.
[…]
My problem with the [C++] language, starkly revealed by that adventure, is that it piles complexity on complexity upon chrome upon gingerbread in an attempt to address problems that cannot actually be solved because the foundational abstractions are leaky. It’s all very well to say “well, don’t do that” about things like bare pointers, and for small-scale single-developer projects (like my eqn upgrade) it is realistic to expect the discipline can be enforced.
Not so on projects with larger scale or multiple devs at varying skill levels (the case I normally deal with). With probability asymptotically approaching one over time and increasing LOC, someone is inadvertently going to poke through one of the leaks. At which point you have a bug which, because of over-layers of gnarly complexity such as STL, is much more difficult to characterize and fix than the equivalent defect in C.
[…]
There were two directions a successor language to C might have gone. One was to do what C++ did – accept C’s leaky abstractions, bare pointers and all, for backward compatibility, than try to build a state-of-the-art language on top of them. The other would have been to attack C’s problems at their root – fix the leaky abstractions. That would break backward compatibility, but it would foreclose the class of problems that dominate C/C++ defects.
The first serious attempt at the second path was Java in 1995. It wasn’t a bad try, but the choice to build it over a j-code interpreter mode it unsuitable for systems programming. That left a huge hole in the options for systems programming that wouldn’t be properly addressed for another 15 years, until Rust and Go.
[…]
This is in many ways a bad situation. It was hard to really see this because of the lack of viable alternatives, but C/C++ has not scaled well. Most of us take for granted the escalating rate of defects and security compromises in infrastructure software without really thinking about how much of that is due to really fundamental language problems like buffer-overrun vulnerabilities.
So, why did it take so long to address that? It was 37 years from C (1972) to Go (2009)
[…]
Over time, there’s been a gradual shift from languages that require manual memory management to languages with automatic memory management and garbage collection (GC). This shift corresponds to the Moore’s Law effect of decreasing hardware costs making programmer time relatively more expensive. But there are at least two other relevant dimensions.
One is distance from the bare metal. Inefficiency low in the software stack (kernels and service code) ripples multiplicatively up the stack. This, we see machine-centric languages down low and programmer-centric languages higher up, most often in user-facing software that only has to respond at human speed (time scale 0.1 sec).
Another is project scale. Every language also has an expected rate of induced defects per thousand lines of code due to programmers tripping over leaks and flaws in its abstractions. This rate runs higher in machine-centric languages, much lower in programmer-centric ones with GC. As project scale goes up, therefore, languages with GC become more and more important as a strategy against unacceptable defect rates.
When we view language deployments along these three dimensions, the observed pattern today – C down below, an increasing gallimaufry of languages with GC above – almost makes sense. Almost. But there is something else going on. C is stickier than it ought to be, and used way further up the stack than actually makes sense.
[…]
Not so the new wave of contending systems-programming languages, though. Rust and Go are both explicitly responses to increasing project scale. Where scripting languages got started as an effective way to write small programs and gradually scaled up, Rust and Go were positioned from the start as ways to reduce defect rates in really large projects. Like, Google’s search service and Facebook’s real-time-chat multiplexer.
I think this is the answer to the “why not sooner” question. Rust and Go aren’t actually late at all, they’re relatively prompt responses to a cost driver that was underweighted until recently.
OK, so much for theory. What predictions does this one generate? What does it tell us about what comes after C?
Here’s the big one. The largest trend driving development towards GC languages haven’t reversed, and there’s no reason to expect it will. Therefore: eventually we will have GC techniques with low enough latency overhead to be usable in kernels and low-level firmware, and those will ship in language implementations. Those are the languages that will truly end C’s long reign.
There are broad hints in the working papers from the Go development group that they’re headed in this direction – references to academic work on concurrent garbage collectors that never have stop-the-world pauses. If Go itself doesn’t pick up this option, other language designers will. But I think they will – the business case for Google to push them there is obvious (can you say “Android development”?).
Well before we get to GC that good, I’m putting my bet on Go to replace C anywhere that the GC it has now is affordable – which means not just applications but most systems work outside of kernels and embedded. The reason is simple: there is no path out of C’s defect rates with lower transition costs.

ESR is conflating and/or oversimplifying a bit here though. Buffer overruns and other forms of programmer errors aren’t related to GC (aka memory allocation mgmt), but rather to static or runtime checking.
He’s really intending to drive at the general concept of the sweet spot in balancing programmer productivity, lower defect rates, easy adoption, and adequate performance for the use case (including large projects and some systems programming), as he explained further in his follow-up blog:
ESR wrote:

An increase in praxeological understanding of technology can reframe it, leading to tremendous increases in human productivity and satisfaction, not so much because of changes in our tools but because of changes in the way we grasp them.
In this, the third of my unplanned series of posts about the twilight of C and the huge changes coming as we actually begin to see forward into a new era of systems programming, I’m going to try to cash that general insight out into some more specific and generative ideas about the design of computer languages, why they succeed, and why they fail.
In my last post I noted that every computer language is an embodiment of a relative-value claim, an assertion about the optimal tradeoff between spending machine resources and spending programmer time, all of this in a context where the cost of computing power steadily falls over time while programmer-time costs remain relatively stable or may even rise. I also highlighted the additional role of transition costs in pinning old tradeoff assertions into place. I described what language designers do as seeking a new optimum for present and near-future conditions.
Now I’m going to focus on that last concept. A language designer has lots of possible moves in language-design space from where the state of the art is now. What kind of type system? GC or manual allocation? What mix of imperative, functional, or OO approaches? But in praxeological terms his choice is, I think, usually much simpler: attack a near problem or a far problem?
“Near” and “far” are measured along the curves of falling hardware costs, rising software complexity, and increasing transition costs from existing languages. A near problem is one the designer can see right in front of him; a far problem is a set of conditions that can be seen coming but won’t necessarily arrive for some time. A near solution can be deployed immediately, to great practical effect, but may age badly as conditions change. A far solution is a bold bet that may smother under the weight of its own overhead before its future arrives, or never be adopted at all because moving to it is too expensive.
[…]
The failure modes of near designs are uglier. The best outcome to hope for is a graceful death and transition to a newer design. If they hang on (most likely to happen when transition costs out are high) features often get piled on them to keep them relevant, increasing complexity until they become teetering piles of cruft. Yes, C++, I’m looking at you. You too, Javascript.
[…]
That said, there is a grand strategy expressed in the Go design that I think is right. To understand it, we need to review what the near problem for a C replacement is. As I noted in the prequels, it is rising defect rates as systems projects scale up – and specifically memory-management bugs because that category so dominates crash bugs and security exploits.
[…]
Of course, the proboscid in the room when I say that is Rust. Which is, in fact, positioning itself as the better far bet. I’ve explained in previous installments why I don’t think it’s really ready to compete yet.
[…]
Where Rust will be in five years is a different question, of course. My advice to the Rust community, if they care, is to pay some serious attention to the transition-cost problem. My personal experience says the C to Rust energy barrier is nasty. Code-lifting tools like Corrode won’t solve it if all they do is map C to unsafe Rust, and if there were an easy way to automate ownership/lifetime annotations they wouldn’t be needed at all – the compiler would just do that for you. I don’t know what a solution would look like, here, but I think they better find one.

Well in this thread we discovered that Go’s design strategy is sub-optimal, because Rust’s lifetimes could be unbundled for 99% of the tsuris which is the total order on mutable borrowing, providing more optimal static memory allocation at a very low tsuris, enabling automatic reference counting (RC) with automatic circular reference probing to provide a more performant result with less tsuris, given that the systems programmer will fight with the MS (concurrent or otherwise) GC otherwise.
The key insight was mine that the total order on borrowing is the Achilles heel of Rust.

@shelby3 wrote:

And the exclusive mutability is not really that important for single-threaded code […] Exclusive mutability isn’t even always the desired or even plausible algorithm for multithreading (or out-of-order access) such as when mutating a shared resource, although […] Instead minimizing the shared mutables between threads (or out-of-ordered access) is typically the desired design strategy.1

Rust’s total order exclusive mutability borrowing restriction can be too restrictive and is not the one-size-fits-all solution that Rust proponents may think it is.
For example, in the single-threaded case of shared writable access, even when order-of-order preemption is allowed by waiting on more than one callback, there are cases where there isn’t a critical section as would be the case for preemptive multithreading. An example of such a case is reading the value, computing a new value, and writing the result back before providing an opportunity for another callback to run in the same thread. If single-threaded code has a critical section on a mutable which is shared externally, it could opt to insure it doesn’t provide an opportunity for another callback to run within that critical section. Thus the soundness is a local affair and doesn’t require the tsuris+inflexibility of a total (aka entire program/universe) order on mutable borrowing.
Rust proponents imply that exclusive mutable borrowing is even necessary in single-threaded code to prevent data races such as use-after-free, which occur when the code obfuscates that it erroneously modifies some invariant which the programmer or static lifetime checker assumed, such as iterator invalidation or presumed lifetime invalidation.
In the latter linked example, Rust’s lifetime analysis presumes the exclusivity of mutable borrows, yet instead a compiler could disallow returning a lifetime tracked reference that is itself (not what it references) mutable, so the programmer would need to either make said reference immutable, or have fn get_text return an immutable doubly-indirected pointer (i.e. an immutable reference to the mutable reference), or replace fn get_text with a function that does some operation on the referenced text. Alternatively to allow the said reference to be mutable yet still avert a total order on exclusive mutable borrowing, for the single-threaded case that protects the critical section (i.e. no out-of-order callbacks can run within it and no preemptive multithreading), the exclusive mutability borrowing could be enforced but would only be necessary to enforce within the said critical section which in that example is the lifetime of the my_text reference.

@shelby3 wrote:

[…] such as iterator invalidation or invalidation of the presumed lifetime.

Another example where Rust prevents localized reasoning is where the lifetime analysis is unable to infer invariants that are obvious to the programmer.

The above cases in addition to demonstrating that Rust can’t (and not elegantly) model all possible optimized algorithms statically (no static typing ever can!), also exhibit that Rust's lifetimes and exclusive mutable references are interdependent, because Rust has to insure that the all the heap allocations (e.g. String) are statically tracked and deallocated at the correct stack frame expiration. References to stack allocated objects don’t need to remember to deallocate the objects assigned to them (because stack allocated objects are deallocated in bulk by the stack frame expiration) and thus only lifetimes need to be enforced. Whereas, where assigning a different heap allocated object to a reference that already references a heap allocated object, the former object must be deallocated at that instant, because the eventual stack frame destructor of the said reference can only remember to deallocate the last object it’s referencing:

If you are coming from languages like Java or Objective-C you might be wondering why do you have to deal with lifetime in Rust. There are very good reasons. In Java the use after free problem is solved through the use of Garbage Collection. GC will not destroy the String as long as any variable points to it. Objective-C will employ reference counting to solve this problem. In our example there will be two references – one by the text member variable and the other by my_txt. The String will be destroyed only when the reference count goes to 0. In other words when both text and my_txt stops existing.
GC requires a heavy runtime and may incur awkward pauses. Reference counting has extra overhead and simply not reliable in all cases. Rust’s lifetime provides an elegant solution with zero runtime overhead.

Thus exclusive mutable references are necessary (combined with lifetimes) for static tracking of the allocation of heap allocated objects. Yet for the static tracking of stack allocated objects, then only lifetimes are required.
Rust presumably considers the extra burden/inflexibility/tsuris/non-optimality of maintaining a total order on exclusive mutable references to be a freebie because Rust presumes that constraint is required any way because instantaneous preemption is assumed everywhere (i.e. multithreading everywhere). However, I’ve proposed we consider single-threaded models and thread pools.
It occurs to me that the generational portion of an automated GC is essentially as runtime performant (or perhaps even more so due to bump pointer allocation of the generational allocator) as Rust’s static heap allocation lifetimes, excepting the need for a BG-MS or BG-RC garbage collector to have a write-barrier to detect when assigned to a RC (reference counted) reference. Rust’s statically deterministic deallocation frees the space of the objects sooner but not necessary sooner to the usable memory pool due to fragmentation issues and if there’s no destructors on those objects then the additional immediacy is irrelevant. Remember most of the generational objects die before the collection cycle so they have no overhead when freed, less fragmentation, and lower overhead to allocate.
So it occurs to me that with a single-threaded and thread pool model wherein we don’t always need exclusive mutability everywhere, the model that may be both more runtime performant and more efficient, elegant, less hassle, and give the programmer more control, would be to have the programmer declare which references will live a long time and these will be statically known to be RC. Other heap allocated objects stay in the generational GC until all non-RC references to each of them disappear or until the object is assigned to an RC reference (which promotes the object to the RC collector). I think programmers know quite well which objects will live a long time or not, even if they don’t know each how long. Also RC references could be employed for any head allocated objects that have a destructor, e.g. file handle objects that have to close the file.
So this means that non-RC references might be pointing to an object which has been promoted to RC. Such objects can’t actually be deleted by RC decrements until all non-RC references have died, i.e. promoted objects have to be flagged, and the flag not remove until the tracing of the generational collector no longer has any reference to the object.
I will want to write some more thoughts I have on this such as other optimizations for low-level code in conjunction with this design. Perhaps this combination of design choices may be superior to both Go and Rust.

I think it's interesting, but I feel you have underestimated the importance of memory space (rather than time). With manual memory management most time is spent on reliability and performance, with GC I spend as much time on reducing memory usage and performance. Most GC does not seem to reclaim on failed allocation as far as I can tell. Software should be robust, and to me there is only one really robust way to do things - make sure you have the memory available before you start an operation, and reserve the space necessary to suspend the computation before starting. A reasonable compromise might be to do a GC on failed allocation, and a de-fragment on double fail, and suspend the thread on triple fail. Reference counting on the stack might be worth it for robustness (maybe that's why Apple likes it).

@keean wrote:

but I feel you have underestimated the importance of memory space (rather than time)

Virtual memory is practically free on 64-bit address space. I think I mentioned upthread I’m not designing for 32-bit address space. Some trade-offs have to be made in design and I think that’s an acceptable one since there will still be Rust for specialty and anarchic use cases.
Additionally, I’m contemplating that it's not entirely meaningful for you to compare your experience with JavaScript’s concurrent MS collector to my proposal for programmer dictated RC collector combined with a BG generational collector. You haven’t even tried a BG-RC collector because apparently has not been adopted by any language yet.

Most GC does not seem to reclaim on failed allocation as far as I can tell.

Please share an example? I would like to analyse this.

Software should be robust, and to me there is only one really robust way to do things - make sure you have the memory available before you start an operation

Generally speaking this is an impossible requirement. You’re expecting the universe to be bounded. You can design some API to return an error if the memory is not available, but then you caller may fail. If you caller (who may be an external service) has to poll everything it needs downstream before it starts, then it needs to be a future teller and know the future of all its future input.
You’re wanting to enumerate the universe of possible inputs, i.e. you must be designing for 999 sigma for the Space Shuttle. Most programming can’t be done to that level of precision realistically nor even desirable to waste such effort on it. Programs work fine by having sufficient extra memory to deal with unexpected spike, preferably physical memory so that virtual memory page swapping to disk doesn’t cause errors due to unexpected timeouts.

I was contemplating whether there's any justifiable need for supporting stack allocation and lifetimes in addition to the proposal I made for a statically demarcated variant of BG-RC.
Lifetime checking is only required when references (aka pointers) to stack allocated would be allowed. Note that then would require another distinct static type for references to objects allocated on the stack versus those that will be collected by the runtime GC (of which those have two types to demarcate those which employ RC or not). So I'd much prefer we didn't need this. K.I.S.S. coherent is preferred design. Good design should maximize the benefits with the least number of concepts/complexity.
Afaics, the main performance boost gained from static stack allocation as compared to copy compacting, bump pointer allocation GC (for short-lived objects, with in my proposal the long-lived objects statically typed as RC to avoid the write-barrier performance cost), is that the objects on the stack can be accessed via offsets on the single stack pointer register (e.g. SP on Intel) and they are typically clustered in memory address space to aid in cache coherency performance. The deallocation of objects on the stack by changing the value of the SP isn't a significant performance boost compared to not copy compacting untraced objects in the runtime GC. The runtime GC tracing is amortized over many function/procedure calls which typically leave nothing to trace nor copy compact.
But that performance benefit for stack allocation can be mostly eliminated, because for those pass-by-value arguments of a function/procedure which would have been passed on the stack, they could be passed on contiguous region of bump pointer allocated heap of the GC, and then function can be provided a pointer to said region, so that all said objects can be accessed through said single pointer with offsets. For pass-by-reference arguments, the reference will be stored in the said contiguous region and the object will be stored somewhere in the heap, which is again analogous (also in performance) to passing the reference on the stack. for stack allocation. IOW, bump pointer allocation with tracing copy compacting deallocation is akin to amortized stack rewinding. We utilize one additional register of the CPU since we still need to keep the SP separately pointing to the call stack. CPU registers aren't as scarce of a resource these days.
I'm failing to find any significant justification for supporting the tsuris of static (i.e. compile-time) stack allocation and lifetimes. I think this proposal of mine will defeat both Rust and Go as the next mainstream, general purpose programming language.

The main advantages of stack allocation are, fast allocation (just decrement a pointer), fast deallocation (just increment the pointer), no indirection (we can hold pointers directly into the stack), no pausing (no mark/sweep phase), and zero fragmentation.

fast allocation (just decrement a pointer)

I explained in my prior post that my proposal is the same. My reading is that is what "bump pointer" allocation means in the literature.

fast deallocation (just increment the pointer)

I explained in my prior post that essentially the same performance in the case that the objects die young, because they rarely traced (amortized) nor copy compacted. The key difference is that with stack deallocation, the timing of the deallocation is more immediate and deterministic. However, if such immediacy is desired in my proposal (e.g. if there's a destructor), then use the RC point type.

no indirection (we can hold pointers directly into the stack)

I already explained the same can be done in my proposal. But there are many cases even in stack allocation where you're going to be passing-by-reference to a function/procedure, thus you'll still have indirection on the stack allocation.

no pausing (no mark/sweep phase)

There's no pause on the tracing on the nursery because most objects die young. My proposal replaces mark-sweep (MS) for the older objects with reference counting (RC). The programmer dictates which objects live long and thus marks them with a RC type, so that no runtime write-barrier is needed on assigning references (aka pointers).

and zero fragmentation

The tracing, copy compacting nursery doesn't generate any fragmentation either.
Thus I repeat:

I'm failing to find any significant justification for supporting the tsuris of static (i.e. compile-time) stack allocation and lifetimes. I think this proposal of mine will defeat both Rust and Go as the next mainstream, general purpose programming language.

The tracing, copy compacting nursery doesn't generate any fragmentation either.

It generates fragmentation, then fixes it by copying. The cost is much higher. Copying is slow compared to just incrementing/decrementing a pointer. You have to double indirect for the heap because the data can move, and you have to pause when moving data between the nursery and other spaces, because you cannot be allowed to access the data mid copy.

It generates fragmentation, then fixes it by copying. The cost is much higher. Copying is slow compared to just incrementing/decrementing a pointer.

Incorrect. I already stated that rarely are any of the objects still around when the tracing+copy compacting  occurs. The cost is amortized away to negligible. I think this is the 3rd time I have stated this in the past few posts.

You have to double indirect for the heap because the data can move

Incorrect. My understanding from reading that book about GS, is the pointers are updated when they're traced. But again this rarely happens for objects in the nursery, so the cost is negligible.

you have to pause when moving data between the nursery and other spaces

Incorrect. Seems you're totally ignoring my proposal even though I have reexplained it more than once. In my proposal, no objects ever get moved from the nursery1, and instead the programmer marks which objects are long-lived with a RC type.

because you cannot be allowed to access the data mid copy.

Any copying will induce a pause, but for that thread only because the nursery will be per thread (whereas the RC objects will be multithreaded access), but since the amount of copying in the nursery will be small, you're looking at microsecond pauses, which is irrelevant. In my proposal, the programmer will be entirely in control of whether he is overloading the nursery will longer-lived objects.
Seems you have not yet wrapped your mind around my proposal and what is different about it.
1 Except when the programmer assigns a nursery object to a reference in a RC object, but the compiler can display which these are, so the programmer is in control of the cost.

Even short lived objects in the nursery will have different lifetimes, so it will fragment. Before dealing with the other points, explain why there is no fragmentation?

There is one clear situation.where having no stack is better, and that is in an asynchronous language where you want a 'cactus' stack.
In these circumstances, allocating a variable frame for a function would be a heap allocation, with a pointer to the previous frame. There will be fragmentation still.
Nurseries work to prevent fragmentation because they get defragmented when copying the long lived objects out. If you mark objects as long-lived, it does not mean that you do not need to defragment the nursery.

Nurseries work to prevent fragmentation because they get defragmented when copying the long lived objects out. If you mark objects as long-lived, it does not mean that you do not need to defragment the nursery.

The RC typed object instances never go into the nursery. They're allocated on the long-lived heap, which employs the methodology I mentioned upthread to mitigate fragmentation of the long-lived heap.
Comparing apples-to-apples, stack deallocation should not typically pertain to long-lived objects (at least that's not the use case we're trying to optimize with stack allocation) because for example if I tried to put the entire UTXO (unspent transaction outputs) of a blockchain on the stack, the stack would overflow (as well I think the lifetime analysis would be unwieldy). Thus if we're correctly comparing stack allocation/deallocation to nursery allocation/deallocation, then the latter has no long-lived objects and thus no fragmentation either.

There is no fragmentation with a stack because there is a total order of object lifetimes. Any object appended to a stack has a lifetime less than or equal to the lifetime of the current top-of-stack object. This is why they don't fragment.
The same is not true of a heap, even one with a nursery. As soon as you place any object on the heap that has a shorter lifetime than the next object you will get fragmentation. Consider:
f =>
   let x = 1
   let y = 2
   let z = 3
   let w = x + y
   // GC runs now
   return w - z

As the GC is asynchronous, it can run at any time. If we consider GC running where indicated, we allocate x, y, z and w on the stack, but we have no references to x or y any more, but we need z and w, so after GC, x and y will be freed. If we imagine the heap as a simple array we have.
[...]
[x, y, z, w, ...]
[(), (), z, w, ...]

You can see the fragmentation starting as we have two empty slots separated from the 'empty space'. If we consider objects may be different sizes, this would make it worse.

@keean I already explained why there will be no more than negligible performance cost of fragmentation for short-lived objects in the nursery of my proposed design (and I already explained why so just reread the prior posts), which essentially equivalent to the lack of fragmentation for stack allocation (which I stated is most applicable to short-lived objects).
Your response belies an understanding of what I have written. Obviously I know about fragmentation in the long-lived heap if it's not copy compacted (because upthread I even presented the ways to minimize such fragmentation), but that's irrelevant because we're comparing apples-to-apples meaning stack allocation for short-lived objects and the nursery for short-lived objects. Long-lived objects won't be put on the stack any way.

@shelby3 I think you are misunderstanding, if your heap has zero fragmentation, then is must be a stack. A stack is a name for a heap where there is no fragmentation. There is simply no other way to manage a block of memory and have no fragmentation. Its either a stack, or it fragments. As fragmentation accumulates over-time a heap needs de-fragmentation whereas a stack does not. These are facts, and not opinion.

@keean, generational GC doesn't defragment what is no longer allocated when the tracing and copy collection runs, which will be the usual case for most that is allocated. Thus, you're incorrect. Yet I'm repeating myself.

Some advantages of a stackless design: no arbitrary limit on stack size (no stack overflow, just out-of-memory), can run many more threads as each one does not need to reserve a stack. However not having a stack means having an assembly language runtime on every platform. It would be much easier to get portability of the languages compile target was 'C'.

I specifically wrote upthread that a stack would still be employed for the call stack.

@shelby3 wrote:

generational GC doesn't defragment what is no longer allocated when the tracing and copy collection runs, which will be the usual case for most that is allocated. Thus, you're incorrect. Yet I'm repeating myself.

This discusses nursery fragmentation in a generational garbage collector:
http://www.mono-project.com/docs/advanced/garbage-collector/sgen/

You could eliminate fragmentation in the nursery by not allowing pinned objects, and completely cleaning out the nursery on a GC run. This has the disadvantage of copying some short lived objects into the second generation that should not be there, which will increase the fragmentation of the second generation, as these objects would be discarded soon after, it also wastes time copying objects that are likely to be discarded soon.

@keean if you refuse to understand my proposal, what's the point of repeating myself 5 more times. Please review my prior posts.
There's no 2nd generation in my proposal. Apparently you keep forgetting (or refusing to digest) salient facts of my proposal that I've already explained numerous times. I think we should take private into LinkedIn for a while. The discussion is getting repetitive and noisy due apparently to lack of effort applied to comprehension.

How many times do I have to repeat that the nursery will be periodically copy compacted and nothing will ever be promoted out of the nursery. The negligible defragmentation cost is negligible, because the copy collector runs infrequently enough that most allocated objects are already deallocated when it the copy collector runs, thus the percentage of objects actually defragmented is negligible. IOW, as I had explained before, the cost of the running the copy collector can be conceptualized as amortized over many, many stack frames with most stack frames having come and gone during each said period. I am sure you understand what the word negligible means. I've repeated several times in my prior explanations.

Which means you are agreeing with me that the nursery will suffer from fragmentation, and that you are periodically de-fragmenting it (which is what a copy compactor does). It appears we have a differing opinion about the cost of this. Its hard to be specific about the cost without implementing and benchmarking.

@keean wrote:

Which means you are agreeing with me that the nursery will suffer from fragmentation, and that you are periodically de-fragmenting it (which is what a copy compactor does).

This is not a political contest. This is engineering. I already explained that you're incorrect. I will quote again (this is very frustrating):
@shelby3 wrote:

@keean, generational GC doesn't defragment what is no longer allocated when the tracing and copy collection runs, which will be the usual case for most that is allocated. Thus, you're incorrect in the sense that defragmentation implies a cost. Yet I'm repeating myself.

For a copy collector to be performing non-negligible defragmentation then there must be a non-negligible cost of copy collecting, otherwise the claim of fragmentation is vacuous:

The negligible defragmentation cost is negligible, because the copy collector runs infrequently enough that most allocated objects are already deallocated when it the copy collector runs, thus the percentage of objects actually defragmented is negligible. IOW, as I had explained before, the cost of the running the copy collector can be conceptualized as amortized over many, many stack frames with most stack frames having come and gone during each said period. I am sure you understand what the word negligible means.

@keean wrote:

It appears we have a differing opinion about the cost of this. Its hard to be specific about the cost without implementing and benchmarking.

If you wanted to challenge my claim that the cost of the copy collector is non-negligible, you could have done that very far upthread when I first mentioned it and employed the term 'amortized'. That would have relieved of us of a lot of noise such as you implying I do not know what fragmentation is (geez). The apparent fact is you weren't paying attention otherwise you could have gone straight to the point of challenging the specific claim.
It's inarguable that the copy collector's cost will be negligible, because the longer-lived objects of the nursery will get stuck at the compacted end and won't need to be repeatedly compacted. Thus the only ones that can get defragmented are the short-lived ones, but by definition of the fact that the copy collector's period will be much longer than the average life of the short-lived objects, then the cost must be negligible.

most allocated objects are already deallocated

This seems wrong, if the rate of object allocation is the same as the rate of object deallocation there will always be plenty of objects in the nursery.
The idea that a bunch of objects get allocated then deallocated cleanly without overlapping other allocations is wrong. There will be allocations every time a function is entered, and the scope of the calling function will still be current.

Its probably worth pointing out that we are discussing details, I think we are in agreement about the big-picture.

@shelby3 This is interesting, and matches my experience:
http://wiki.c2.com/?MemoryLeakUsingGarbageCollection
a couple of key quotes:

As time goes, I consider more and more the GarbageCollector as something that turns freed pointer crash into memory leaks. And yes, I'm hunting Java memory leaks more frequently than C/C++ memory leaks, but I'm hunting C/C++ crashes due to freed references much more than NullPointerExceptions in Java.

But the problem you describe certainly has the same effect, so I guess I'll have to widen my definition slightly to "failure to free memory that will no longer be referenced by the running program". It's certainly true that, in the presence of globals or long-lived locals, the explicit act of freeing memory has to be replaced by the explicit act of nulling a reference.

So is GC actually a solution? With manual memory management we have to free references to heap storage (but not all references, because of RAII). With GC we have to null references that are no longer part of the running-set of the program. Both of these lead to bugs, its just that with GC you might get away with it because the program is too short lived to run out of memory, but the delay makes it much harder to track down and debug.

Reference counting with immutable objects is an interesting point in the design space, as you cannot create circular references with immutable objects, so reference counting becomes a complete solution.

The Python GC is interesting:
http://arctrix.com/nas/python/gc/
They basically sacrificed performance for portability. In the end of the widely available GCs JavaScript is not that bad, its more the APIs provided by JS do not allow memory re-use.

When watching things from the angle of performance and time / bother to
write programs gc is better.
When watching things from the angle of memory use, and tracking memory
bugs, RC is better.
gc will make leaks less obvious as memory use always grow. With manual
management or RC, if memory use keep increasing, its an obvious sign of a
leaks.
What make the problem even more accute is that using a gc imply the
programmer doesnt have to know anything about memory management at all, or
what the gc handle well or not, and can encourage to write programs with
sloppy memory management, without even realizing it's sloppy or trigger
bugs in the gc. And many times the programmer can't (or is not supposed to)
know how the garbage collection works.
And most of time using a stack and proper program structure doesnt cost a
lot of time for manual memory management.
Le 21 déc. 2017 10:08, "Keean Schupke"<EMAIL_ADDRESS>a écrit :

The Python GC is interesting:
http://arctrix.com/nas/python/gc/
They basically sacrificed performance for portability. In the end of the
widely available GCs JavaScript is not that bad, its more the APIs provided
by JS do not allow memory re-use.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/keean/zenscript/issues/35#issuecomment-353297593, or mute
the thread
https://github.com/notifications/unsubscribe-auth/Ab61I5lsZND8H3sJXxSXqInvGnWKq5eZks5tCiAQgaJpZM4OZwjF
.

In all methods we have to do something with references, as with GC we must still null references to avoid leaking memory, without GC we have to free them. RC has the same reference problem as MS, but it also has the cycle-memory leak problem.
An example may make this clearer. Imagine I have a ring-buffer, which contains references to other data. I can 'clear' the ring-buffer efficiently by setting "start = end". With manual memory management, I leak all the data referred to in the buffer because I did not free the memory pointed to. With GC (RC or MS) I leak the memory because the references still exist in the ring buffer memory which is still in scope, even though I have cleared it by setting (start = end)

This sort of things is the reason why i wanted to avoid all direct pointer
manipulation, and avoiding holding pointer to inside a buffer or an object
as a strong reference.
If references are always to the start of an object or buffer, and
offset/size are kept separately, it make reference use more obvious.
List containing references to other objects can be marked as such if the
language recognize a list primitive, and release references to objects in
the list automatically when there no reference to the list.
So only need to manage the list reference life time.
If a reference is assigned to the start of the list, it can only be a
reference to another buffer, and make the release of the reference to the
buffer  ( and all references inside of it) obvious.
Le 21 déc. 2017 14:06, "Keean Schupke"<EMAIL_ADDRESS>a écrit :

In all methods we have to do something with references, as with GC we must
still null references to avoid leaking memory, without GC we have to free
them. RC has the same reference problem as MS, but it also has the
cycle-memory leak problem.
An example may make this clearer. Imagine I have a ring-buffer, which
contains references to other data. I can 'clear' the ring-buffer
efficiently by setting "start = end". With manual memory management, I leak
all the data referred to in the buffer because I did not free the memory
pointed to. With GC (RC or MS) I leak the memory because the references