Hacker News Reader

Comment by michaelfeathers | Hacker News Reader

This makes me wonder whether it would be worthwhile to design languages with no garbage collection or manual deallocation. Non-stack memory can be allocated but never freed, and memory exhaustion would be fatal.

We might be at the point where this is an acceptable simplification for very fine grained processes and services. Has anyone explored this model?

View on HN

I'm exploring something similar in my project: https://github.com/akkartik/mu. Where C was designed as a more portable+expressive assembly language, Mu is designed as a more portable+safe assembly language. You have to manually manage memory, but you can't ever end up corrupting your heap or using pointers after free. I provide these guarantees by allocating a refcount with every single allocation. The only way to reclaim memory is to clear a pointer. If you happen to still have other pointers to the allocation you won't actually reclaim it.

Given this setup I can prototype programs without thinking about memory at all. When my program runs out of memory I start measuring allocations and insert the odd pointer clear at strategic places until I don't, then I continue on my merry way. 99.9% of programs we write don't require thinking of "no memory leaks" as a black-and-white cast-iron guarantee.

This setup also provides a really nice teaching experience where students can learn about pointers and write all sorts of programs without ever running into weird bugs due to use-after-free or overflowing bounds. However it adds some overhead akin to a realtime GC: everytime you copy a struct you have to increment refcounts of any pointers nested arbitrarily deep within it (Mu maintains a flattened bitmap for each type to make this not utterly suck). Sum types get even crazier, because you might have a pointer at offset x depending on the state of the tag at offset y, and so on. I'll try to measure the overhead at some point..

>The only way to reclaim memory is to clear a pointer. If you happen to still have other pointers to the allocation you won't actually reclaim it.

Elegant! It's funny though, on persistent storage we sort of invented this decades ago in the form of hard links. You can have as many hard links as you want to a file, and the file will only be deleted when all links are removed and all file handles are closed.

Yes, reference counting is one of those things that keeps coming up everywhere.

This is basically "leaky" reference counting, yeah?

Yes, the mechanism is exactly reference counting. However, the goal is totally different. Typically refcounting is used for automatic memory management. Here the goal is safe manual management. (The different goal means that refcounting's well-known inability to collect cycles is irrelevant, among other things.)

This is probably already possible in several language implementations just by telling them to turn off their garbage collector.

After all, the essential rule behind garbage collection is that all variables are available to a program for ever - yet the implementation is allowed to clear up memory if it can prove that a value can never be retrieved again (for instance, because all references to it have gone out of scope).

It has also crossed my mind that a large number of small, terminating programs might well be better off running to completion without any collection taking place. But language implementors are pretty smart - probably quite a lot of the small programs you have in mind already /do/ run right through without ever doing any garbage collection.

You could just use C (or any other non-GC language) and opt out of freeing your memory. That it is done sometimes (not always intentionally, of course). The DMD Compiler for example:

"DMD does memory allocation in a bit of a sneaky way. Since compilers are short-lived programs, and speed is of the essence, DMD just mallocs away, and never frees. This eliminates the scaffolding and complexity of figuring out who owns the memory and when it should be released. (It has the downside of consuming all the resources of your machine if the module being compiled is big enough.)"

http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...

The Qt C++ also allocates but never free a certain amount of memory. A lot of programs and libraries take the view that if you're going to allocate memory and keep using till the end, why bother freeing it?

The downside to this is it makes it difficult to use tools like Valgrind that trace memory allocation in one's own program.

There are two significant downsides to freeing blocks of memory that are in use when program exits: 1) it's completely wasted effort to track who should free some global structure that gets allocated and then exists until program ends (global singletons, various caches...) 2) freeing all objects when program exits puts completely unnecessary pressure on OS's VM subsystem (it's not so long ago that closing long-running firefox or openoffice caused linux desktop to just freeze and swap for few seconds)

Maybe I'm in minority but in C I tend to flag unnecessary free()'s before program exit in code reviews (There is not much that you can do about that in "safe" languages like C++).

I'm not saying this somewhat common method is necessarily bad.

I'd just mention it makes tracking memory allocation harder for an end-user of an application framework that does. In those instances, it might be nice to, say, disable this approach with compiler flag or something.

Edit: it also depends on how concerned you are with memory leaks. Making sure every single allocation has a delete attached is a simple rule. The rule of "every allocation has a delete, except the allocations we're sure will last for the life of the program", making sure that rule is followed seems a little harder and presents a "mental overhead". This kind of thing probably depends on how prone to memory leaks your program is (I've seen big, messy, memory leak prone programs where "oh this one isn't deleted 'cause of optimization" would make the leak-detective's job just that much harder).

Hash consing is a 1970s Lisp technique for supporting this that was recently rediscovered as "string interning": https://en.wikipedia.org/wiki/Hash_consing

In general copy-on-write schemes would be useful for this, and some persistent data structures can be as well.

JonL White wrote a paper about this idea in 1980: http://3e8.org/pub/scheme/doc/lisp-pointers/v1i3/p17-white.p... (favorite quote: "GC Once a Year: Enough?")

Rivest and Shamir wrote an interesting paper on write once memory in 1982 that I feel might have some non-obvious applications to this: https://people.csail.mit.edu/rivest/RivestShamir-HowToReuseA...

Linear types (http://home.pipeline.com/~hbaker1/LinearLisp.html) is a closely related idea in terms of avoiding garbage collection that has very useful concurrency properties. Most time-of-check-to-time-of-use and kernel/userspace race conditions would be prevented by using linear types for system call arguments. IMO linear types have enough benefits outside of memory management to make the trade-off of using them worth it vs the other techniques mentioned above.

Another interesting possibility for an immutable language would be a generational copying allocation with two young generations and no collection of the old generation. Immutability would guarantee that you only have to scan the young generations, two young generations would catch practically all of the ephemeral garbage, and so long as they are small enough to fit a close level of cache, collection would be really fast.

Immutable languages tend to produce more garbage in the old generation than mutable languages such that this approach is not going to work reasonably (easy to find useful piece of software written in mutable language that produces no garbage in the old generation, while any state changes in immutable languages will invariably produce garbage).

On the other hand, generational GC is almost trivial to implement for immutable languages, exactly because there is no need for write-barrier. BEAM's GC is perfect example of how trivial can well performing GC be in that case (and good study material that is perfectly relevant for runtimes with mutable objects).

I believe there was a comment here recently about someone writing software for airplanes, mentioning how after power up, and when the plane was in the air, no new allocations were allowed. So it's not unheard of.

Speaking of safe software, I came across a free chapter/snippet on memory and safety in Ada[1]:

"(...)Restrictions

There is a general mechanism for ensuring that we do not use certain features of the language and that is the pragma Restrictions. Thus if we write

   pragma Restrictions(No_Dependence =>
     Unchecked_Deallocation);

then we are asserting that the program does not use Unchecked_Deallocation at all – the compiler will reject the program if this is not true.

There are over forty such restrictions in Ada 2005 which can be used to give assurance about various aspects of the program. Many are rather specialized and relate to multitasking programs. Others which concern storage generally and are thus relevant to this chapter are

  pragma Restrictions(No_Allocators);
  pragma Restrictions(No_Implicit_Heap_Allocations);

The first completely prevents the use of the allocator new as in new Cell'( ... ) and thus all explicit use of the heap. Just occasionally some implementations might use the heap temporarily for objects in certain awkward circumstances. This is rare and can be prevented by the second pragma.

Hint: Ada is also a high level language that allows low-level programming, and might be fun for writing a lisp ;-)

[1] http://www.adacore.com/adaanswers/gems/gem-43-safe-and-secur...

See for example Structured Programming with Limited Private Types in Ada: Nesting is for the Soaring Eagles, by Henry G. Baker.

(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39....)

An aside:

Tolpin and Toft designed an extension to the functional language ML which used region based memory managed instead of traditional garbage collection for ML.

This lifted the lifetimes of variables into ML's type system (!!!) while the underlying implementation IIRC could achieve O(1) memory behaviour except when an exception occurred.

While this sounds amazing, there were draw-backs on the implementation / theory as certain optimisations were near necessary to get good performance. I.E. word sized integers had to live in the heap as opposed to registers. Another issue was that loops had to be restructured from idiomatic ML style to a slightly different one, other the region inference logic would cause O(N) allocations in a loop which would otherwise use O(1) allocations.

http://www.elsman.com/pdf/retro.pdf

or "Tauplin and Toft region based memory management retrospective" should lead you to the paper.

Just check Ada and Spark.

The main issue is that in most cases the complexity increase is not worth the trouble.

So such languages end up being used in embedded systems and high integrity deployments. Usually where human lifes are at risk.

Just because memory can be freed doesn't mean it has to; the programmers can choose not to.

The mode of not freeing has been explored in programs that are short-lived and run on top of an OS that reliably cleans up memory. For instance, system utilities and compilers and such.

Got a C program that crashes due to premature allocation, according to Valgrind, and it is hard to figure out why? It it just a short-lived utility that does some job and exits? Then just #define free(p) ((void) 0) and rebuild.

Or because it's considerably faster—if you don't have to deallocate, you can just reserve a bunch of pages on startup and use a stupid simple bump allocator.

Actually, D's compiler more or less works this way: http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...

I have seen a program, which meticulously freed everything on shutdown, take over a minute to actually do so under a large and complex test case involving lots of data. In production use, this would be a complete waste of CPU cycles.

Over a minute? At least it didn't take a few days...

http://lists.gnu.org/archive/html/coreutils/2014-08/msg00012...

https://news.ycombinator.com/item?id=8305283

> The mode of not freeing has been explored in programs that are short-lived

[fork, allocate, exit] is a very valid and robust pattern leveraging the OS as a garbage collector.

This kind of pattern reminds me of crash-as-an-operation-mode software.

That's a fine solution, but you're going to cause some weenie manager's head to explode.

Also, some hapless intern is going to copy a chunk of code out of your project in their new project and then give you hell because their program leaks memory like crazy.

Also, some mid level manager is going to decide that all code must be run through static analysis and come out cleanly and you're going to have a bad day.

Good luck explaining that one in the code review :p

https://blogs.msdn.microsoft.com/oldnewthing/20100809-00/?p=... I don't know anyone who has practically implemented it though.

This project uses reference counting to deallocate memory, so memory is being freed when it is no longer used.

However, the paradigm you're referring to is interesting. Short-living processes that allocate little memory could work. Also, servers could use this model: create a slab of memory for each request, and allocate memory on that slab when processing the request. When the request is completed, you can free the entire slab at once. I know the Ur language does something like this.

I did this 20 years ago. My allocator had multiple regions (slabs) that were tuned to specific allocation patterns and lifetimes, with different algorithms for managing block size, fragmentation handling, and freeing. We could turn on detailed allocation/free logging, which included the file/line the action took place. From this we could put the system under load and then identify allocation hotspots and build models on block size and lifetimes and tune the allocators from that. It was pretty cool.

Your take on the server usage of this idea is widely implemented. But the usual approach is not to allocate large block of memory and allocate from that, but to wrap malloc() with function that adds headers that track purpose of the allocated block and then free all still live blocks when the purpose ceases to exists. Both Apache and Samba uses generalized mechanisms for this (apr_pool and talloc, respectively), while PostgreSQL does the same thing in somewhat ad-hoc manner.

This is called regions and was quite common a few decades ago.

Which are used by Bone Lisp:

It uses explicit regions instead of garbage collection.

Explicit regions are both very simple and very fast, but how far can one get with them? I want to find out, so I am developing this interpreter.

So we've come full circle.

To come full circle we would need people to accept the great research done at Burroughs, DEC/Olivetti, Royal Navi, Xerox PARC, Genera, ETHZ, MSR... in what concerns safe systems programming.

But are there any non-paywalled digital accesspoints to this?

Lots of them.

All research of Interlisp-D, Smalltalk and Mesa/Cedar at Xerox PARC:

https://archive.org/details/bitsavers_xerox

Stéphane Ducasse also maintains the original Smalltalk manuals on his legacy books:

http://stephane.ducasse.free.fr/FreeBooks.html

Oberon at ETHZ:

http://www.ethoberon.ethz.ch/books.html

If you want to see how the latest incarnation of Oberon used to look like:

http://www.progtools.org/article.php?name=oberon&section=com...

For Modula-3 it is a bit harder, because of DEC/Olivetti being acquired by Compaq, which was then acquired by HP. So lots of sites are full with broken links.

So the older books are a better source than the Internet.

But still you can get some info here:

http://www.modula3.org/

http://ftp.labs.hp.com/ftp/pub/dec/SRC/

http://www-spin.cs.washington.edu/

Burroughs overview:

http://www.smecc.org/The%20Architecture%20%20of%20the%20Burr...

It lives on as Unisys MCP mainframes. There are some more informations when searching for it.

Algol-68RS used at Royal Navy:

https://en.wikipedia.org/wiki/ALGOL_68RS

This is just a small taste. If one cares about history of computing there are lots of other resources scattered around the web and libraries.

Cool, thanks!

Could probably do this in Lua or other embedding-oriented languages where it's easy to create and discard interpreters willy nilly in the host environment.

its been common practice in embedded/real-time systems to make everything static.

dynamic memory allocation is frowned upon... to many issues with fragmentation and non-deterministic behaviour.

How would it change the design of the language though, compared to a language with garbage collection?

I don't think it would. Implementation of the language would be easier, though, and I suspect that knowing that memory is not reclaimable might act as a beneficial constraint on design.

Is that what individual Erlang processes do?

Reply on news.ycombinator.com