11 ms·

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

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?

openasocket 10y ago
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.
- pjmlp 10y ago
  This is called regions and was quite common a few decades ago.
  - Kristine1975 10y 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.
    - pjmlp 10y ago
      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.
      - fsloth 10y ago
        But are there any non-paywalled digital accesspoints to this?
        pjmlp 10y ago
        Lots of them. All research of Interlisp-D, Smalltalk and Mesa/Cedar at Xerox PARC: https://archive.org/details/bitsavers_xerox 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 http://stephane.ducasse.free.fr/FreeBooks.html Oberon at ETHZ: http://www.ethoberon.ethz.ch/books.html 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=compilers&type=tutorial 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://www.modula3.org/ http://ftp.labs.hp.com/ftp/pub/dec/SRC/ http://ftp.labs.hp.com/ftp/pub/dec/SRC/ http://www-spin.cs.washington.edu/ http://www-spin.cs.washington.edu/ Burroughs overview: http://www.smecc.org/The%20Architecture%20%20of%20the%20Burroughs%20B-5000.htm 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 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.
        fsloth 10y ago
        Cool, thanks!
- treerex 10y ago
  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.
- tehrei 10y ago
  Apache already does exactly this. (I wrote a small plugin to implement custom authentication for requests via custom headers). You have a hierarchy of memory pools and you can only allocate memory from the pool, or free the entire pool. Usually you just use e.g. the per-request pool and allocate what you need without having to manually free it, since apache frees it for you at the end of the request. If you free a pool, you also free all child pools.
- dfox 10y ago
  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.
ksherlock 10y ago
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-75/240158941 http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...
- joe_the_user 10y ago
  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.
  - dfox 10y ago
    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++).
    - joe_the_user 10y ago
      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).
chrisseaton 10y ago
How would it change the design of the language though, compared to a language with garbage collection?
- michaelfeathers 10y ago
  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.
sp332 10y ago
https://blogs.msdn.microsoft.com/oldnewthing/20100809-00/?p=13203 https://blogs.msdn.microsoft.com/oldnewthing/20100809-00/?p=... I don't know anyone who has practically implemented it though.
rm445 10y ago
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.
pjmlp 10y ago
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.
Tuna-Fish 10y ago
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.
- dfox 10y ago
  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).
kazinator 10y ago
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.
- foota 10y ago
  Good luck explaining that one in the code review :p
- PeCaN 10y ago
  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-75/240158941 http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...
  - kazinator 10y ago
    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.
    - ksherlock 10y ago
      Over a minute? At least it didn't take a few days... http://lists.gnu.org/archive/html/coreutils/2014-08/msg00012.html http://lists.gnu.org/archive/html/coreutils/2014-08/msg00012... https://news.ycombinator.com/item?id=8305283 https://news.ycombinator.com/item?id=8305283
- lloeki 10y ago
  > 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.
akkartik 10y ago
I'm exploring something similar in my project: https://github.com/akkartik/mu 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..
- foota 10y ago
  This is basically "leaky" reference counting, yeah?
  - akkartik 10y ago
    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.)
- dTal 10y ago
  >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.
Pxtl 10y ago
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.
TickleSteve 10y ago
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.
dumael 10y ago
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 http://www.elsman.com/pdf/retro.pdf or "Tauplin and Toft region based memory management retrospective" should lead you to the paper.
sedachv 10y ago
Hash consing is a 1970s Lisp technique for supporting this that was recently rediscovered as "string interning": https://en.wikipedia.org/wiki/Hash_consing 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.pdf 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-HowToReuseAWriteOnceMemory.pdf https://people.csail.mit.edu/rivest/RivestShamir-HowToReuseA... Linear types (http://home.pipeline.com/~hbaker1/LinearLisp.html 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.
e12e 10y ago
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-secure-software-chapter-7-safe-memory-management/ http://www.adacore.com/adaanswers/gems/gem-43-safe-and-secur...
- junke 10y ago
  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.625&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39....)
spdegabrielle 10y ago
Is that what individual Erlang processes do?

openasocket 10y ago

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.

pjmlp 10y ago
This is called regions and was quite common a few decades ago.
- Kristine1975 10y 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.
  - pjmlp 10y ago
    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.
    - fsloth 10y ago
      But are there any non-paywalled digital accesspoints to this?
      - pjmlp 10y ago
        Lots of them. All research of Interlisp-D, Smalltalk and Mesa/Cedar at Xerox PARC: https://archive.org/details/bitsavers_xerox 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 http://stephane.ducasse.free.fr/FreeBooks.html Oberon at ETHZ: http://www.ethoberon.ethz.ch/books.html 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=compilers&type=tutorial 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://www.modula3.org/ http://ftp.labs.hp.com/ftp/pub/dec/SRC/ http://ftp.labs.hp.com/ftp/pub/dec/SRC/ http://www-spin.cs.washington.edu/ http://www-spin.cs.washington.edu/ Burroughs overview: http://www.smecc.org/The%20Architecture%20%20of%20the%20Burroughs%20B-5000.htm 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 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.
        fsloth 10y ago
        Cool, thanks!
treerex 10y ago
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.
tehrei 10y ago
Apache already does exactly this. (I wrote a small plugin to implement custom authentication for requests via custom headers). You have a hierarchy of memory pools and you can only allocate memory from the pool, or free the entire pool. Usually you just use e.g. the per-request pool and allocate what you need without having to manually free it, since apache frees it for you at the end of the request. If you free a pool, you also free all child pools.
dfox 10y ago
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.

ksherlock 10y ago

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-75/240158941 http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...

joe_the_user 10y ago
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.
- dfox 10y ago
  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++).
  - joe_the_user 10y ago
    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).

chrisseaton 10y ago

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

michaelfeathers 10y ago
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.

sp332 10y ago

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

rm445 10y ago

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.

pjmlp 10y ago

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.

Tuna-Fish 10y ago

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.

dfox 10y ago
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).

kazinator 10y ago

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.

foota 10y ago
Good luck explaining that one in the code review :p
PeCaN 10y ago
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-75/240158941 http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...
- kazinator 10y ago
  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.
  - ksherlock 10y ago
    Over a minute? At least it didn't take a few days... http://lists.gnu.org/archive/html/coreutils/2014-08/msg00012.html http://lists.gnu.org/archive/html/coreutils/2014-08/msg00012... https://news.ycombinator.com/item?id=8305283 https://news.ycombinator.com/item?id=8305283
lloeki 10y ago
> 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.

akkartik 10y ago

I'm exploring something similar in my project: https://github.com/akkartik/mu 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..

foota 10y ago
This is basically "leaky" reference counting, yeah?
- akkartik 10y ago
  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.)
dTal 10y ago
>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.

Pxtl 10y ago

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.

TickleSteve 10y ago

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.

dumael 10y ago

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 http://www.elsman.com/pdf/retro.pdf or "Tauplin and Toft region based memory management retrospective" should lead you to the paper.

sedachv 10y ago

Hash consing is a 1970s Lisp technique for supporting this that was recently rediscovered as "string interning": https://en.wikipedia.org/wiki/Hash_consing 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.pdf 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-HowToReuseAWriteOnceMemory.pdf https://people.csail.mit.edu/rivest/RivestShamir-HowToReuseA... Linear types (http://home.pipeline.com/~hbaker1/LinearLisp.html 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.

e12e 10y ago

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-secure-software-chapter-7-safe-memory-management/ http://www.adacore.com/adaanswers/gems/gem-43-safe-and-secur...

junke 10y ago
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.625&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39....)

spdegabrielle 10y ago

Is that what individual Erlang processes do?