[reconstructed] WD-40 (for reducing Rust with the next mainstream language) #35

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issue-243345358
Original Date: July 17, 2017

⁣	⁣
	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.

EDIT: on the coding for readability point, “Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.”

@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.

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-315910415
Original Date: July 17, 2017

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 at deterministic, prompt finalization (which is required for non-main memory 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.

Has it ever been tried to combine reference counting with GC? Apparently so:

Edaqa Mortoray wrote:

Reference counting with cycle detection adds an interesting twist. I believe both D and Python do this. In order to eliminate memory loops objects are “sometimes” scanned for reference loops. This involves a lot more work than simply touching a reference count — though still not nearly as much as scanning all allocated memory. The impact of this loop detection depends heavily on how often it is scanned, and what the triggers are.

Given our single-threaded model, we do not need atomics on the reference counting and given the proposal of the OP to emphasize borrowing and RAII then we would not get the benefits of a generational GC scheme. So reference counting would give us determinism except in the case of cyclical references and then GC would kick in to break cycles. However, when we know the cyclical references are probable (e.g. any kind of non-acyclic graph such as the DOM or a doubly-linked list), then it is wasted overhead to employ reference counting, although that overhead could be very tiny (i.e. infrequent tracing) if we only want to catch unexpected cycles (i.e. as an insurance policy and we’d want to log these and consider them bugs).

I suppose we could rate-limit reference counting finalization, to prevent the rare aberrant high latency stall.

@fauigerzigerk wrote:

@rbehrends wrote:

It is well-known that the amortized cost of naive reference counting is considerably higher than that of a modern tracing garbage collector (regardless of whether you also support cycle collection). It is also well-known that non-naive RC-based approaches generally make it easier to achieve lower pause times (though cycle collection may throw a spanner in the works).

True, but I think these comparisons are often done under the assumption that memory utilisation remains fairly low. Tracing GCs react very badly to growing memory utilisation in my experience. This is of course ultimately an economic question and maybe it should be modelled that way.

@SKlogic wrote:

@jules wrote:

@jules wrote:

Tracing GC is not always faster. GC time is proportional to the size of the allocated memory, reference counting time is not.

It's not about running out of memory altogether, it's about the heap filling up with dead objects while the GC doesn't yet know that they are dead. Of course things are great when they are great and the GC can keep up with the mutator. Yet failure does happen whether or not you think it should happen, hence all the efforts that I mentioned that are trying to fix the issues.

As I said, in such a case RC would behave even worse.

@david-given wrote:

Regarding latency spikes: that's not entirely true. If you drop the last reference to an object, then freeing that object can cause the last reference to other objects to be dropped, etc.

So it's possible that dropping a reference can cause a large amount of work, which if it happens during a critical path can cause a latency spike. Particularly if finalisers are involved. If your object ownership graph is straightforward this isn't a problem, but if you have large objects with shared ownership it's very easy to be surprised here.

@SKlogic wrote:

It is really hard to get real time guarantees with RC - given that time for cleaning up depends on a size of a structure.

Just imagine it freeing a 10Gb linked list.

Real time pure mark and sweep GCs are easier.

@rbehrends wrote:

Just keep in mind the trade-offs that you are making.

For starters, you are adding a considerable performance overhead to local pointer assignments; you're replacing a register-register move (and one that can be optimized away in many situations by a modern compiler through register renaming, turning it into a no-op) with a register-register move plus two memory updates plus a branch. Even where you have cache hits and the branch can be predicted correctly almost always, you're dealing with cache and BTB pollution; these effects may not fully show up in micro-benchmarks, but only completely manifest in large programs.

@barrkel wrote:

There's no discussion of thread safety and how that affects reference counting. That's probably the biggest problem; you need to use memory barriers to make reference counting safe with multiple threads, and that can kill performance.

@vardump wrote:

Reference counting ~~is fast with one CPU core. But it~~ gets worse and worse as you add cores. Inter-CPU synchronization is slow and the buses can saturate. With enough cores, at some point that'll be all the system is doing

@iofj wrote:

@rbehrends wrote:

It is well-known that…

I submit this is only true for equivalent number of things to keep track of. In practice this is not the case. Languages with GC [typically] go completely overboard with GC, using it completely everywhere, even when not strictly necessary and certainly java does.

In C++, if you have a map with items, you use move semantics and you have have either 0 or 1 refcounts to keep track of, the one for the map itself. The rest is still "refcounted" but without ever touching any integer, by the normal scoping rules. Same goes for Rust code. That's ignoring the fact that a Java object is, at minimum, 11 bytes larger than a C++ object. Given java's boxing rules and string encoding, the difference in object sizes becomes bigger with bigger objects. Because out-of-stackframe RTTI is a basic necessity of tracing garbage collectors this is unavoidable, and cannot be fixed in another language. Bigger object sizes also mean more memory needed, more memory bandwidth needed, ... And Java's constant safety checks also mean

In Java, the same map will give the GC 3 items to keep track of (minimum) per entry in the map, plus half a dozen for the map itself. One for the object that keeps the key and the value, one of the key and one for the value. That's assuming both key and value are boxed primitives, not actual java objects. In that case, it'll be more.

@majke wrote:

Having that in mind, there are couple of problems with refcnt:

Cache spill. Increasing/decreasing a counter values in random places in memory kills cache. I remember one time I separated the "string object" data structure in python away from the immutable (!) string value (python has usually C struct object followed in memory by value blob). The python program suddenly went way faster - immutable (readonly) string values in memory were close to each other, mutated refcnts were close to another. Everyone was happier

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. If the number of available unused bits is insufficient to count all allocated objects, then perhaps each compiled object type could employ a separate array (i.e. a zero-runtime-cost compile-time array selection), presuming the cache thrashing issue is due to intra-page-size fragmentation, not lack of inter-page contiguity. Also then we do not need to create the array element until the second reference. This is applicable when mostly passing around objects and not accessing all the data of the object as frequently.

Weighted reference counting can be employed to reduce the accesses to the reference count by half (since the source pointer has to be accessed any way), but it requires some unused bits in the pointer to store the weight.

David Ireland wrote:

Don’t get me wrong, Apple must have had a good reason to choose reference counting for memory management. That reason is actually pretty obvious: Objective-C is not a safe language, so you can’t move objects. If you can’t move objects, You have to use something like malloc to minimise fragmentation: you pay a big up front cost to allocate an object in the right place. In most GC schemes, allocation is free – you just increment a pointer. This is fine, because you are going to iterate through all your objects every now and again, and it doesn’t cost a whole lot more to move some of them around at the same time. You get to compact away all the fragmentation this results in. This makes GC fairly miserly with memory too. In iOS , if you want to allocate something bigger than the largest free fragment, you die. With GC, you have to wait a while for the GC to compact everything, after which memory will be compacted 100% efficiently and there will be a single memory extent as big as all available memory. Objective-C can’t have any of these benefits, so Apple chose a different route for iOS, and put the best possible spin on it.
…
Mobile apps won’t be fast until browsers are re-written in a fast, safe programming language that can share a good GC with ECMAScript. Of course browsers won’t be secure until then either, but I’m not holding my breath. There is no such language that is sufficiently popular, and Google fluffed it’s lines with Go. Maybe ECMAScript implementations will gain so much in performance, that all code that manipulates the DOM will be written in ECMAScript, and we can finally use a high performance GC.

Edit Nov. 18, 2017 Distinguish between non-deterministic reference counting and deterministic RAII.

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-315958730
Original Date: July 18, 2017

⁣@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).

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-325094328
Original Date: August 26, 2017

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

Look what Eric wrote about Rust:

http://esr.ibiblio.org/?p=7711&cpage=1#comment-1913931
http://esr.ibiblio.org/?p=7724#comment-1916909
http://esr.ibiblio.org/?p=7303
http://esr.ibiblio.org/?p=7294
http://esr.ibiblio.org/?p=7294#comment-1797560
http://esr.ibiblio.org/?p=7294#comment-1797743
http://esr.ibiblio.org/?p=7711&cpage=1#comment-1911853

They also argue (similar to a point I made to @keean) that type system complexity can kill the economics of a language (this complexity budget has to be minimized):

http://esr.ibiblio.org/?p=7724#comment-1912884

And everyone agrees OOP (virtual inheritance and subtyping) are anti-patterns:

http://esr.ibiblio.org/?p=7724#comment-1912640

Comments about where Rust has overdrawn it’s complexity budget:

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-345494394
Original Date: November 18, 2017

⁣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 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) except for interop with non-GC objects as explained below (but potentially at the cost of loss of compaction and loss of automatic cyclical references memory leak detection).

Afaics, a useful facility to add in addition to GC is the zero-cost¹ abstraction of deterministic RAII block scope allocated/deallocated on the stack, because it (probably improves performance and) adds determinism of finalization (aka destructors) and interacts with the optimization of low-level performance as explained below.

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 compile-time enforced “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 ^{_{(a la Rust’s total ordering which assumes multithreaded preemption everywhere or my proposed partial ordering in conjunction with singled-threaded event model)}} for the purpose of preventing concurrent race conditions access (which afair 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 (a cordoned context of imperative) side-effect??²

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 virtual memory address space, else the objects must be copied. The former has a 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 (i.e. for GC pointers since pointers to data RAII managed in a contained block scope would exhibit use-after-free errors), 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. To have full interoperability between GC instances and RAII (stack allocated data structure) 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 (which is an onerous, undesirable can-of-worms).

Thus, I’m leaning towards that stack allocated data structures should not interop with GC instances, except via copying because (other than deterministic finalization) performance is their primary raison d'être. And interop with GC would (as GC does) also encourage unboxed data structures, which are known to thrash caches and degrade performance. Additionally, I think it should be allowed to have GC instances which are unboxed data structures (e.g. transpiled to ArrayBuffer in JavaScript) so they can be most efficiently copied (i.e. no transformation overhead). One might ponder whether to also have reference counted allocation on the heap , so that these immovable objects would not need to be copied when accessed by low-level performant algorithms ^{_{(and note that the reason ASM.js didn’t allow very small ArrayBuffers is because there’s no presumption that what was compiled to ASM.js did bounds checking, although not a hindrance because our compiler could do static bounds checking in many cases and insert dynamic checks in the others)}}, but the loss of compaction and the lack of automatic cyclical references detection are onerous. Any attempt to overcome these onerous trade-offs with “stop the world” of the code that is operating on non-GC instances, would suffer from “a concurrency live and dead-lock issue” as well (because think about it that just stopping the threads is not sufficient as the state can be invalid when the threads are restarted, instead they must be stopped at points where the current thread state has no such dependencies).

However, is memory compaction even necessary on 64-bit virtual address spaces wherein the hardware can map the virtual address pages to compacted, available physical pages? Well I guess yes unless most objects are much larger than the ~4Kb page size.

However, afaics perhaps the compaction issue could be significantly mitigated by allocating same size objects from contiguous virtual address space significantly larger than ~4KB in reference counting algorithm. Thus allocations would be first applied to deallocated slots in the address space, if any, per the standard reference counting allocation and deallocation algorithm, which employs a linked-list of LIFO free slots.³

If compaction is required, then I contemplate whether to allow unsafe low-level code which manually employs malloc and free should still be allowed for cases where there’s no other way to achieve performance with dynamic memory allocation.

¹ _{Zero runtime cost because due to the compile-time determinism, we know at compile-time when the deallocation will occur.}

² _{How does Oleg’s insight conflict with @keean’s prior stance (in our discussions) against AST macros? I vaguely remember that he was against macros because they obfuscated debugging and the type system.}

_{Is this the paper? http://okmij.org/ftp/Computation/having-effect.html#HOPE}

_{I’m unable to readily grok Oleg’s work because he communicates in type theory and Haskell (neither of which am I highly fluent). Afaics he explains with details/examples instead of conceptually and generatively from ground level concepts. And I do not have enough time to apply arduous effort. So he limits his audience to those who are fluent in every facet of the prior art he builds on and/or who can justify the time and 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 function 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 the necessary syntax and type system to allow for such generality (which was essentially my complaint against trying to model everything, e.g. even subtyping, as typeclasses as you were proposing before), 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?

³ _{Richard Jones. Garbage Collection Algorithms For Automatic Dynamic Memory Management, §2.1 The Reference Counting Algorithm}

@NodixBlockchain

Original Author: @NodixBlockchain
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-345981613
Original Date: November 21, 2017

⁣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.

For me now when i want to add new feature, especially for memory management, my first concern is not only 'how to make it work', but also how easy it will be to detect problems, and to track what cause the problem.

With reference counting, it's easy to make a break point when reference get freed, and having the debugger to pause everything and inspect all the context at the moment where it happens.

With GC, the analysis is delayed, and all the context of execution that change the state of the object is lost, so it makes it very hard to debug.

For me to make GC programming easy, it needs something like android SDK where all the application is structured at macro level with activities, intents, special class for asynchronous/background execution, and making in sort that lifetime of all objects are predictible due to the structuring of the application, declaration of resources in XML etc.

https://developer.android.com/guide/components/activities/process-lifecycle.html

They have whole lot of classes to build the application on, to make resource management and lifecycle of object more deterministic.

It impose a certain structure to all application classes and component to make memory management fit in case that the GC can easily deal with.

Making general purpose GC to deal with complex language with multi layered scope and asynchronous execution without giving any hint to the pattern that the object is likely to follow by inheriting some class, and structuring the application with built class with predictible behavior seems very hard.

Reference counting is much easier to deal with for the general case.

@keean

Original Author: @keean
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346013299
Original Date: November 21, 2017

⁣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.

Edit: where this gets complicated is you then end up with two kinds of pointers "owning pointers" which must form a Directed-Acyclic-Graph, and non-owning (or reference) pointers (and links between data-structures). The simple solution is to make all 'references' weak-references, so that you have to null-test them when dereferencing to check if the resource they point to has gone away. Then we simply delete things when they go out of scope, removing all resources pointed to by owning-pointers in the DAG. No GC no Reference counting, and a simple non-zero check on dereference. Of cource 'nullable' pointers are not considered a good thing, so we can then look for static techniques where we do not allow references to outlive the object to they reference. This is where Rust's lifetimes come from.

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346107470
Original Date: November 21, 2017

⁣@NodixBlockchain (aka IadixDev @ BCT) wrote:

If i may :)

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 “Saluations! :)” 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) analyses was/is.

@keean and I have been doing backtalking on LinkedIn to reduce clutter in these issues thread. You’re welcome to add me there.

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’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.

With reference counting, it's easy to make a break point when reference get freed, and having the debugger to pause everything and inspect all the context at the moment where it happens.

With GC, the analysis is delayed, and all the context of execution that change the state of the object is lost, so it makes it very hard to debug.

You can’t see which/where are all the references to the shared object that had it’s reference count decremented, because it’s the implicit nature of non-deterministic memory allocation to not know which pointers would be the candidates and the reference counting scheme provides no back pointers from the said object to said sharing pointers (as aforementioned).

I agree it wouldn’t normally be possible to set a runtime breakpoint on the change in number of references to a specific object with a tracing GC, because the assignment of pointers doesn’t touch the referenced object (although write-guards for generational GC might get you as close as the virtual page but that might not be helpful). Thus, there’s no way to know which assignment to set a breakpoint on for testing the address of the said shared object. Yet comparably, the more optimized variants of reference counting also have the same debugging problem because they don’t even update the said common object (as explained below) because they keep the reference count in the pointers (and additionally there is the Weighted Reference Counting). In both cases, a sophisticated debugger and language could in theory be designed to set such conditional breakpoints on all pointer assignments (conditionally breaking only if the said shared object address is encountered), if such a facility is helpful for debugging memory leaks. And the tracing GC would have more information about the memory allocation graph.

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

It seems you’re presuming that reference counting models deterministic memory allocation, but that is not generally the case and (per my reply to @keean below), if that were generally the case then in theory it could be replaced by zero-runtime-cost compile-time deterministic allocation mgmt (albeit with tsuris of a complex compile-time typing system). Afaics, you continue to repeat this belief system of yours (presumably confirmation biased by your presumed preference for your low-level framework you discussed in your thread “Saluations! :)” and per my comments to @keean about C/C++ below) without refuting the points that have been made to you numerous times previously. I’ll recap and augment… (and hoping you’ll keep the not-so-thoroughly-contemplated-studied noise to a minimum in this/my thread please).

https://developer.android.com/guide/components/activities/process-lifecycle.html

They have whole lot of classes to build the application on, to make resource management and lifecycle of object more deterministic.

I don’t see how the process lifecycle has anything to with the generalized problem that in general memory allocation is non-deterministic.

It impose a certain structure to all application classes and component to make memory management fit in case that the GC can easily deal with.

Programming paradigms for avoiding memory leaks are useful regardless of the memory allocation scheme chosen.

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.

Reference counting (aka ARC, which technically is a form of “direct”¹ garbage collection) can’t garbage collect cyclical references. 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.² This makes sense because reference counting (RC) doesn’t contemplate the entire directed graph of objects holistically. Thus only “indirect, tracing”¹ garbage collection which deals with the entire directed graph will reliably detect and garbage collect cyclical references. However, note that probabilistic, localized tracing combined with RC decrements is comparable to mark-sweep (MS)³ for (even apparently asymptotic) throughput computational complexity costs, yet with an upper bound (“6 ms”) on pause times due to locality of search. Yet presumably pause times are eliminated with a concurrent MS (and as cited below, RC has less throughput than BG-MS).

According to this expert book⁴, reference counting has significantly worse throughput (except compared to the pathological asymptotic huge heap case for tracing GC which can be avoided¹⁵, ^{_{and perhaps multi-threaded/multi-core/parallelism but I think need to study that more}}) because of the significant additional overhead for every pointer assignment. This overhead as a percentage is worse for highly optimized, low-level languages (e.g. C/C++) compared to interpreted languages which have high overhead any way. Note that a claimed throughput parity for RC with MS⁵ (and it’s just culling young generation overhead similar to prior art¹⁶) is not parity with generational GC combined with MS (BG-MS).⁶ Additionally the adjustment of the reference counts on each pointer assignment thrashes the cache⁷ 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)}}.⁸ 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 paradigms⁹ ^{_{(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 optimizations¹⁰ 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 counting¹¹ in conjunction with a clever generational GC scheme (apparently similar to prior art¹⁶), for the avoiding the pathological asymptotic case of tracing GC. See my further comments about this in my reply to @keean below.

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.

In general, more complexity in the code will increase the probability of semantic memory leaks, even semantic leaks of the form that automatic garbage collection can’t fix because the error is semantic. Reference counting (a form of automated GC) will also suffer these semantic memory leaks. The issue of complexity of semantics, is more or less not peculiar to the type of automatic GC scheme chosen. Thus I don’t view this as a valid complaint against tracing GC in favor of reference counting.

¹ _{Richard Jones (1996). Garbage Collection Algorithms For Automatic Dynamic Memory Management, §1 Introduction, pg. 2.}

² _{Richard Jones (1996). 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.}

³ _{D. F. Bacon and V. T. Rajan (2001). Concurrent cycle collection in reference counted systems. In J. L. Knudsen, editor, Proceedings of 15th European Conference on Object-Oriented Programming, ECOOP 2001, Budapest, Hungary, June 18-22, volume 2072 of Lecture Notes in Computer Science, pp. 207–235. Springer-Verlag, 2001.}

⁴ _{Richard Jones (1996). Garbage Collection Algorithms For Automatic Dynamic Memory Management, §2.1 The Reference Counting Algorithm, pg. 19 – 25, §3 Reference Counting, pp 43 – 74.}

⁵ _{R. Shahriyar, S. M. Blackburn, X. Yang, and K. S. McKinley (2012), "Taking Off the Gloves with Reference Counting Immix," in OOPSLA ‘13: Proceeding of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications, 2013. Originally found on Steve Blackburn’s website.}

⁶ _{Stephen Blackburn; Kathryn McKinley (2003). "Ulterior Reference Counting: Fast Garbage Collection without a Long Wait". Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications. OOPSLA 2003, Table 3 on pg. 9.}

⁷ _{Richard Jones (1996). Garbage Collection Algorithms For Automatic Dynamic Memory Management, §2.1 The Reference Counting Algorithm: The strengths and weakness of reference counting, pg. 22.}

⁸ _{Richard Jones (1996). 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.}

⁹ _{Richard Jones (1996). 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.}

¹⁰ _{Richard Jones (1996). Garbage Collection Algorithms For Automatic Dynamic Memory Management, §3.1 Non-recursive freeing, pg. 44.}

¹¹ _{Richard Jones (1996). 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 procedures not functions then to return some data you simply pass a collection (set/map/array etc) into the procedure.

This is conceptually broadly analogous/related to deferred reference counting¹² 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, have narrow applicability because they 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, as they both admitted).

And those stack paradigms don’t marry well holistically with a bolt-on tracing garbage collection appendage¹³ (i.e. was not design holistically with the language), although I have not yet read a more recent research paper on combining tracing GC with Rust.¹⁴ 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 of 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.

EDIT: on the coding for readability point, “Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.”

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 variants¹⁶ (i.e. fertile ground presumably only in the realm of esoteric, high complexity, and/or abstruse). Thus, unlikely I discovered something (after a day of reading and contemplation) that hadn’t be considered previously in the prior art, although there appears to be potential prior art similar to my ideas¹⁶ that have appeared later than the book I read. Note I independently arrived at my ideas (after about a day of contemplating the 1996 book) and have not yet read that 2003 research paper¹⁶ to compare.

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.

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 (although the requirement for lazy evaluation is disputed), 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..

Edit: where this gets complicated is you then end up with two kinds of pointers "owning pointers" which must form a Directed-Acyclic-Graph, and non-owning (or reference) pointers (and links between data-structures). The simple solution is to make all 'references' weak-references, so that you have to null-test them when dereferencing to check if the resource they point to has gone away. Then we simply delete things when they go out of scope, removing all resources pointed to by owning-pointers in the DAG. No GC no Reference counting, and a simple non-zero check on dereference. Of cource 'nullable' pointers are not considered a good thing, so we can then look for static techniques where we do not allow references to outlive the object to they reference. This is where Rust's lifetimes come from.

Human managed weak references are an incomplete and human-error prone strategy. Also as you noted then you leak the non-determinism from deallocation to how to handle error conditions of null pointers, leaking the non-determinism into program logic! That is horrible. Whereas, a provably sound weak pointer algorithm has exponential asymptotics and thus is no better or worse than tracing GC mark-sweep.²

¹² _{Richard Jones (1996). Garbage Collection Algorithms For Automatic Dynamic Memory Management, §3.2 Deferred reference counting, pg. 45.}

¹³ _{Richard Jones (1996). Garbage Collection Algorithms For Automatic Dynamic Memory Management, §9 Garbage Collection for C, pg. 227.}

¹⁴ _{Y. Lin, S. M. Blackburn, A. L. Hosking, and M. Norrish (2016), "Rust as a Language for High Performance GC Implementation," in Proceedings of the Sixteenth ACM SIGPLAN International Symposium on Memory Management, ISMM ‘16, Santa Barbara, CA, June 13, 2016, 2016.}

¹⁵ _{Richard Jones (1996). Garbage Collection Algorithms For Automatic Dynamic Memory Management, Preface: The audience, pg. xxiv, Preface: The Bibliography and the World-Wide Web, pg. xxv.}

¹⁶ _{Stephen Blackburn; Kathryn McKinley (2003). "Ulterior Reference Counting: Fast Garbage Collection without a Long Wait". Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications. OOPSLA 2003. I originally found this on Wikipedia’s page for Reference Counting.}

_{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” (copyright violation theft) pdf linked above.}

EDIT: a more concise overview resource:

@NodixBlockchain wrote:

https://openresearch-repository.anu.edu.au/bitstream/1885/9053/1/02WholeThesis_Garner.pdf

This papper cover it all :D

@keean

Original Author: @keean
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346114141
Original Date: November 21, 2017

⁣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.

@NodixBlockchain

Original Author: @NodixBlockchain
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346116255
Original Date: November 21, 2017

Edit: where this gets complicated is you then end up with two kinds of pointers "owning pointers" which must form a Directed-Acyclic-Graph, and non-owning (or reference) pointers (and links between data-structures). The simple solution is to make all 'references' weak-references, so that you have to null-test them when dereferencing to check if the resource they point to has gone away. Then we simply delete things when they go out of scope, removing all resources pointed to by owning-pointers in the DAG. No GC no Reference counting, and a simple non-zero check on dereference. Of cource 'nullable' pointers are not considered a good thing, so we can then look for static techniques where we do not allow references to outlive the object to they reference. This is where Rust's lifetimes come from.

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.

@barrkel

Original Author: @barrkel
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346119442
Original Date: November 21, 2017

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.

@keean

Original Author: @keean
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346122168
Original Date: November 21, 2017

⁣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.

What is the fastest garbage collected language?

@keean

Original Author: @keean
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346126086
Original Date: November 21, 2017

⁣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...

@keean

Original Author: @keean
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346126913
Original Date: November 21, 2017

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 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.

@keean

Original Author: @keean
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346128500
Original Date: November 21, 2017

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 :-)

@keean

Original Author: @keean
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-346131548
Original Date: November 21, 2017

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

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647668285
Original Date: Jun 22, 2020

Inserted:

IOW, memory has no more life if it can’t be referenced anymore and it continues to have a life for as long as any reference can access it. Whereas non-memory resources live on beyond (or need to die before) the life of the reference to the handle to the resource. The reference to the file handle is not isomorphic with the life of the resource referred to by the file handle.

@sighoya

Original Author: @sighoya
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647669696
Original Date: Jun 22, 2020

@shelby3

You can't require the compiler to detect in interior when to release/finalize a resource, only in terminus. But the latter can't be required for dynamic cases, too, i.e. a finalization must be either aborted if some other entity is blocking your resource or you enforce to disrupt the access to that resource and cause the other entities to possibly fail in their obligations.

@thickAsABrick

Original Author: @thickAsABrick
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647670179
Original Date: Jun 22, 2020

Hello: I'll confirm that I, @thickAsABrick, did not post anything to, or contribute to, this conversation. Not sure why I am receiving these notifications.

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647670826
Original Date: Jun 22, 2020

@thickAsABrick

Hello: I'll confirm that I, @thickAsABrick, did not post anything to, or contribute to, this conversation. Not sure why I am receiving these notifications.

Hahaha. Sorry I did not check to see you really exist. I guess I should have taken the visual cue when it was bolded in the comment. Apologies. I will not do it again. I hope you are not offended if I find this to be funny.

Hey I wish I had thought of that username before you did.

And @Ichoran thought I was chasing away new community, lol. (He is correct)

(as I try to scurry off stage hoping nobody will notice )

@thickAsABrick

Original Author: @thickAsABrick
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647672022
Original Date: Jun 22, 2020

No problem. Just making sure my account was not hacked. Quite honestly, I do not know much about the subject matter that you are discussing.

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647673108
Original Date: Jun 22, 2020

@thickAsABrick

No problem. Just making sure my account was not hacked. Quite honestly, I do not know much about the subject matter that you are discussing.

Thanks for the understanding. And your last sentence fits perfectly then — not that you should be expected to jump into an esoteric 601+ comments issues thread about highly obscure, abstruse programming language design topics and be able to assimilate it.

I actually like the Jethro Tull song even though it received poor reviews.

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647687433
Original Date: Jun 22, 2020

@sighoya

You can't require the compiler to detect in interior when to release/finalize a resource, only in terminus. But the latter can't be required for dynamic cases, too, i.e. a finalization must be either aborted if some other entity is blocking your resource or you enforce to disrupt the access to that resource and cause the other entities to possibly fail in their obligations.

If there is only one reference (or at least only one strong reference) to the resource handle then the compiler should be able to reason (by tracking the implicit linear type) when that reference dies either upon exit from its terminal stack scope or assignment of null, i.e. Rust does this but hopefully it can be accomplished without lifetime annotations? (If not, then @Ichoran may be correct to cite that as a utility advantage for Rust’s borrow checker) With multiple strong references to the same resource handle I presume the static analysis required by the compiler would require total, dependent type knowledge a la Coq and thus wouldn’t be viable for a general purpose PL. For multiple strong references I think only a conflation with ARC would be viable, but I have posited that comes with other meta-level baggage.

I was not proposing to track only in the interior (to stack frame scope) when to release. I was proposing to track in interior whether any code paths don’t escape the stack frame scope and thus make sure the programmer has been explicit about whether to release those automatically or has explicitly released them — or alternatively we could discuss whether the compiler should just release them implicitly by default without any using-like explicit intent from the programmer. I argued that being explicit has some advantages. I will think that over again and decide if I have changed my mind about the worth of those posited advantages in light of the discussion that has occurred since I made that claim.

@shelby3

Original Author: @shelby3
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647730310
Original Date: Jun 22, 2020

Note the edit:

@keean

Even your map example is being explicit because it assigns null to the reference to resource handle object.

No it does not. My example language has non-nullable references.

I see you alluded to move semantics for C++ but that is still being explicit. You move the reference out of the map (and what do you leave in its place except a null in the linked-list for the bucket or you decrement the size of the bucket array and move all the buckets?) then the block or stack frame scope deconstructs the reference you moved (i.e. assigned) it to. That is entirely semantically equivalent to assigning to null for the context of my point. ~~What is the point of this needless verbiage?~~[Actually I see a valid point, which is that by moving out the implicit ARC action happens at the stack frame scope rather than at the assignment of a null, and thus in some sense does not conflate the removal from the map with the implicit destruction of the handle. Note though that your example did not take this reference as an output from the map.delete thus the implicit conflation remained in your example. However, I find this point interesting because it seems to indicate how to facilitate explicit resource lifetimes per what I am advocating.]

@keean

Original Author: @keean
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647732299
Original Date: Jun 22, 2020

@shelby3 I can find a few references to automatic memory management and GC vs ARC, but it seems not widespread. To avoid confusion we should probably use MS (mark sweep) and RC (reference counting) are forms of AMM (automatic memory management), and avoid use of GC altogether.

Whereas non-memory resources live on beyond (or need to die before) the life of the reference to the handle to the resource. The reference to the file handle is not isomorphic with the life of the resource referred to by the file handle.

You can always refactor so the life of the handle is the life of the resource. If the resource needs to be shorter lived you can use a Weak reference. If the resource needs to be longer lived you can store it in a global container (global array, hash map, singleton object etc).

ARC is for freeing access to a reference (thus it follows that the memory resource can be freed because no reference can access it anymore), not optimally semantic congruent with freeing (non-memory) resources that reference used to know about. They are not semantically equivalent.

There is no reason for them not to have the same scope. If I have access to the handle, I should be able to read from the file. If I don't need access any more destroy the handle. There is no need to have a handle to a closed file.

Even GC + implicit if we use static escape analysis with a single strong reference.

No, because a strong reference must never be invalid, so you cannot close a strong reference to a file. A strong reference to a file must be RAII. Basically with a strong reference you must always be able to call read on the handle without an error.

By definition, if you want to be able to explicitly close the handle, it is by definition a weak reference to a file. So with GC the close is explicit, the weakness of the handle is implicit. You have no choice over this (unless you want unsoundness).

Well we could even have a single explicit strong reference (thus any weak references are implicit by default) with implicit (or explicit) destructors and make it work with either ARC or non-ARC, GC

To repeat above you should not use a strong reference to the resource with GC, because that would rely on finalizers to release the handle, and that can lead to resource starvation. It's not safe.

Basically mark-sweep = weak resource handle
ARC = strong or weak are possible.

Edit: Regarding C++, yes you are right you would swap a null there, but that's C++, which is not an ARC language. This would imply that "Weak" is defined:

type Weak<T> = T | null

And therefore Weak would be a billable reference to the strong file handle. However you would not be allowed to just write a null. Weak is an abstract datatype, so the value is private, and you would have to call weak.delete() which calls the destructor on the object contained, and then replaces with a null.

@keean

Original Author: @keean
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647735836
Original Date: Jun 22, 2020

@shelby3

Edit: Regarding C++, yes you are right you would swap a null there, but that's C++, which is not an ARC language. This would imply that "Weak" is defined:

type Weak<T> = T | null

And therefore Weak would be a nullable reference to the strong file handle. However you would not be allowed to just write a null. Weak is an abstract datatype, so the value is private, and you would have to call weak.delete() which calls the destructor on the object contained, and then replaces with a null.

@Ichoran

Original Author: @Ichoran
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647744776
Original Date: Jun 22, 2020

@shelby3 - Um, your supposed code counterexample isn't a counterexample. In fact, the disproof of it being a counterexample was in my Rust example! Here it is again:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2baade67d8ce2cc9df628de2b753f0e6

Here is the code, in case you want to see it here instead of run the runnable example there:

struct Str {
    string: String
}
impl Drop for Str {

fn drop(&mut self) { println!("Dropping!"); }

}
fn main() {

let mut s = String::new();

s.push_str("salmon");

let ss = Str{ string: s };

let l = ss.string.len();

std::mem::drop(ss);

println!("I was size {}", l);

}

Rust drops at block closure, but it resolves lifetimes to last use when needed ("non-lexical lifetimes"), so it could do it automatically at the point where it says std::mem::drop.

So your first example would magically just work. If not, the explicit drop with move semantics (so you can't use it again) would non-magically work.

Note that

using(new Handle){ handle =>
  somethingThatSecretlyBlocksForever()
}

also ties up resources forever. Because the blocking is secret (forgotten), it doesn't look like a problem.

But

let handle = Handle::new();
useHandle(handle);
somethingThatSecretlyBlocksForever();

with automatic dropping of handle when it can no longer be accessed, is safe.

You don't even have to know the secret. It just works. It's just correct.

So using is an antipattern.

Here's another problem with using--the requirement to nest scope.

using("textures".path.stream){ stream =>
  val textures = readSomeTextures(stream)
  using(new GraphicsResource){ g =>
    g.load(textures)
    if (userWantsMoreTextures()) {
      val moreTextures = readMoreTextures(stream)
      g.load(moreTextures)
    }
    g.doThings()
    g.doMoreThings()
  }
}

The problem? You've still go that file handle because you needed it live when you acquired some other resource.

In contrast, RAII handles this flawlessly.

Having to remember to deal with resources is a pain. If the compiler can figure out that they need to be closed, they should just plain be closed. If you need help understanding why your life is so easy now, then an IDE could help you out.

@thickAsABrick

Original Author: @thickAsABrick
Original URL: https://github.com/keean/zenscript/issues/35#issuecomment-647751447
Original Date: Jun 22, 2020

My apologies for asking: is there something I can do at my end to stop these emails? I tried unsubscribe, but it does not seem to be helping?

@NodixBlockchain

Huge thanks to @NodixBlockchain for coding and running the script to recover this thread (appending to what I had manually recovered from my backup) which was accidentally deleted by @keean.

Note the thread has been continued in a new issue, so I am going to close this thread so that new comments are not added:

WD-40 Issues thread was accidentally deleted by @keean

@NodixBlockchain

Thanks @NodixBlockchain

Navigation Menu

Repository navigation

[reconstructed] WD-40 (for reducing Rust with the next mainstream language) #35 #50

574 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

[reconstructed] WD-40 (for reducing Rust with the next mainstream language) #35 #50

Description

Activity

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

shelby3 commented on Jun 25, 2020

574 remaining items

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

NodixBlockchain commented on Jun 26, 2020

shelby3 commented on Jun 30, 2020

sighoya commented on Jun 30, 2020

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions