4 ms·

Nice ! But without GC I guess it’s just a nice hack and will have a hard time being actually useful

by Ecco 9y ago

amelius 9y ago
GC doesn't have to be complicated if performance isn't an issue. Also, escape-analysis could be used to run this without GC in trivial cases.
- DannyB2 9y ago
  Also if memory is fairly limited, then you don't get that much of a pause time from even a fairly simplistic GC implementation. I would also point out that modern micro controllers run faster than the old systems mentioned in TFA. (eg, Apple II, TI/99, etc.) There are already micro controller implementations of GC languages. MicroPython. Espruino (eg, JavaScript)
  - pjmlp 9y ago
    That is what gets old about arguing against GC languages on micro-controllers. Of course there are use cases using 8KB PIC micro-controllers and such. On the other hand something like ESP32, has a dual core with 512KB, way better than the Amstrad PCW 512 used to be.
- amelius 9y ago
  As a concrete example of the second point: if your program basically does: for(;;) do_shortlived_task(); Then even if do_shortlived_task() has a complicated memory allocation pattern, you can get away by just throwing away the entire heap after each iteration.
  - vvanders 9y ago
    That's assuming no statics/singletons.
    - vidarh 9y ago
      That's still easily solved by providing arenas or barriers: allocate anything that needs to persist first, then mark, do your shortlived task and throw away anything above the mark in memory.
      - vvanders 9y ago
        If your statics have containers(yes I know it's a bad idea, but not forbidden) then you can easily have invalid pointers now with that approach. Really you're going to have to go through so many gyrations that your GC code may start looking a lot like manual memory management.
        vidarh 9y ago
        No, you just need to know what you're allocating and accept that if you're using an approach like that you're very much responsible for ensuring you don't allocate anything that should live on past the mark. It's an old, well tested mechanism - the brk() syscall in Unix-like systems for getting memory does just that, for example (though today some get more convoluted and may or may not opt to use mmap() as well) And you'll find it used today even in systems with gc's too. E.g. mruby for example provides an API to do pretty much that for extensions that would otherwise leave a lot of garbage to explicitly allocate to an arena and throw away everything other than whatever you then explicitly register with the gc. If you have complications like what you describe, you'd probably want a proper gc, but as I outlined elsewhere, a simple gc is also easy if your heap is small enough that performance isn't an issue. But for many systems it's not necessary.
- vidarh 9y ago
  As an example of how simple, as I think people tend to see gc as complicated and scary, a simple tri-color mark and sweep gc in pseudo code: push_registers_to_stack() // Simplifies dealing with roots - you can now ignore registers // These are the roots: // (grey objects are directly referenced from a root, but have not yet been scanned for pointers) for_each_stack_value { mark_grey } for_each_bss_variable { mark_grey } // We then keep iterating over grey objects, scanning the values of those objects for further // pointers (which we mark grey), and mark "finished" objects black: while (ob = grey_list.shift) { for each pointer in ob { if white: mark_grey(pointer); mark_black(ob) } } // Now any objects you haven't touched are still white (and unreachable), and thus garbage: for_each_object { if white: free else: mark_white } The above is inefficient, but it takes very little space to implement. If you know precise object layout and takes it into account when scanning, it's also precise, if not it's conservative (it may leave garbage if values in memory looks like pointers). Downside is that it is "stop the world", so if your heap is big, it'll cause noticeable pauses. Simple GC's are easy.... Fast/good/efficient GC's on the other hand...
  - vvanders 9y ago
    The other downside is fragmentation(which is also why even embedded native tends to be static/up-front allocation based).
    - vidarh 9y ago
      That's true, and certainly if you can avoid dynamic allocations, do. But you can actually get "halfway" to a partially compacting gc very easily too if memory use is a bigger concern than performance and you want to avoid fragmentation: Set a (small) fixed size for all objects. It can be anything from a single pointer to any data that will be present in all objects. E.g. you might have class pointers and flags and a fixed number of bytes for auxiliary data. If any class needs more instance data, you make a pointer in that primary layout point to space in a secondary heap. Now compacting the secondary heap is easy: Just copy into new buffers and deallocate the old and update a single pointer per object. You can do that by a single pass through all allocated objects, or you can do something more complex. Compacting the primary heap is still messy (you'd need to identify all sites pointing to each object), but if you chose a small size for the primary objects there's less reason to do so, as while it is still possible to create pathological allocation patterns, unless the application reaches a high water mark and then frees a huge number of objects that it then never need again, any empty space left behind can always be perfectly filled by new primary object allocations, and hopefully each such object is fairly small. If you want to, though, you can also compact auxiliary data (the "secondary heap") into holes in the primary heap when there's a good enough fit. E.g. on top of the steps I outlined: For each object, if there's an auxiliary data pointer, check if there's a suitable hole (keep lists by "hole size" for example) in the primary heap. If so, move there. If not, copy to end of new secondary heap. Update source pointer.
walkingolof 9y ago
Most of the machines on the list have a 16 bit address range (65536 bytes without paging) and usually less than that in free memory, GC or no GC, does not matter.
- dfox 9y ago
  Original PARC Smalltalk implementations had 32k (16b) word heaps (object pointers were 15b + one tag bit distinguishing SmallInteger and everything else). You could write quite complex systems with just that. Edit: this is true for the canonical ST80 VM described in Blue book, ST80 VM on Alto AFAIK had some indirection mechanism (ie. not 32k words, but 32k heap objects) and did paging.
  - pjmlp 9y ago
    Also the Lisp implementations in the 60 and 70's were even more constrained on IBM mainframes.
xfer 9y ago
Look into javacard spec, it doesn't require a GC, but it is used everywhere(your credit card, SIM card etc.). The secure processors used here implement this spec.
- nickpsecurity 9y ago
  JavaCard is also one of the few areas where high-assurance security use commercially. Names that come to mind are Kesterel Institute and Gemalto with EAL7-style VM's with formal verification. Examples: https://www.commoncriteriaportal.org/iccc/9iccc/pdf/B2404.pdf https://www.commoncriteriaportal.org/iccc/9iccc/pdf/B2404.pd... http://www.kestrel.edu/home/projects/jcapplets/ http://www.kestrel.edu/home/projects/jcapplets/

Nice ! But without GC I guess it’s just a nice hack and will have a hard time being actually useful

by Ecco 9y ago

Nice ! But without GC I guess it’s just a nice hack and will have a hard time being actually useful

GC doesn't have to be complicated if performance isn't an issue. Also, escape-analysis could be used to run this without GC in trivial cases.

DannyB2 9y ago
Also if memory is fairly limited, then you don't get that much of a pause time from even a fairly simplistic GC implementation. I would also point out that modern micro controllers run faster than the old systems mentioned in TFA. (eg, Apple II, TI/99, etc.) There are already micro controller implementations of GC languages. MicroPython. Espruino (eg, JavaScript)
- pjmlp 9y ago
  That is what gets old about arguing against GC languages on micro-controllers. Of course there are use cases using 8KB PIC micro-controllers and such. On the other hand something like ESP32, has a dual core with 512KB, way better than the Amstrad PCW 512 used to be.
amelius 9y ago
As a concrete example of the second point: if your program basically does: for(;;) do_shortlived_task(); Then even if do_shortlived_task() has a complicated memory allocation pattern, you can get away by just throwing away the entire heap after each iteration.
- vvanders 9y ago
  That's assuming no statics/singletons.
  - vidarh 9y ago
    That's still easily solved by providing arenas or barriers: allocate anything that needs to persist first, then mark, do your shortlived task and throw away anything above the mark in memory.
    - vvanders 9y ago
      If your statics have containers(yes I know it's a bad idea, but not forbidden) then you can easily have invalid pointers now with that approach. Really you're going to have to go through so many gyrations that your GC code may start looking a lot like manual memory management.
      - vidarh 9y ago
        No, you just need to know what you're allocating and accept that if you're using an approach like that you're very much responsible for ensuring you don't allocate anything that should live on past the mark. It's an old, well tested mechanism - the brk() syscall in Unix-like systems for getting memory does just that, for example (though today some get more convoluted and may or may not opt to use mmap() as well) And you'll find it used today even in systems with gc's too. E.g. mruby for example provides an API to do pretty much that for extensions that would otherwise leave a lot of garbage to explicitly allocate to an arena and throw away everything other than whatever you then explicitly register with the gc. If you have complications like what you describe, you'd probably want a proper gc, but as I outlined elsewhere, a simple gc is also easy if your heap is small enough that performance isn't an issue. But for many systems it's not necessary.
vidarh 9y ago
As an example of how simple, as I think people tend to see gc as complicated and scary, a simple tri-color mark and sweep gc in pseudo code: push_registers_to_stack() // Simplifies dealing with roots - you can now ignore registers // These are the roots: // (grey objects are directly referenced from a root, but have not yet been scanned for pointers) for_each_stack_value { mark_grey } for_each_bss_variable { mark_grey } // We then keep iterating over grey objects, scanning the values of those objects for further // pointers (which we mark grey), and mark "finished" objects black: while (ob = grey_list.shift) { for each pointer in ob { if white: mark_grey(pointer); mark_black(ob) } } // Now any objects you haven't touched are still white (and unreachable), and thus garbage: for_each_object { if white: free else: mark_white } The above is inefficient, but it takes very little space to implement. If you know precise object layout and takes it into account when scanning, it's also precise, if not it's conservative (it may leave garbage if values in memory looks like pointers). Downside is that it is "stop the world", so if your heap is big, it'll cause noticeable pauses. Simple GC's are easy.... Fast/good/efficient GC's on the other hand...
- vvanders 9y ago
  The other downside is fragmentation(which is also why even embedded native tends to be static/up-front allocation based).
  - vidarh 9y ago
    That's true, and certainly if you can avoid dynamic allocations, do. But you can actually get "halfway" to a partially compacting gc very easily too if memory use is a bigger concern than performance and you want to avoid fragmentation: Set a (small) fixed size for all objects. It can be anything from a single pointer to any data that will be present in all objects. E.g. you might have class pointers and flags and a fixed number of bytes for auxiliary data. If any class needs more instance data, you make a pointer in that primary layout point to space in a secondary heap. Now compacting the secondary heap is easy: Just copy into new buffers and deallocate the old and update a single pointer per object. You can do that by a single pass through all allocated objects, or you can do something more complex. Compacting the primary heap is still messy (you'd need to identify all sites pointing to each object), but if you chose a small size for the primary objects there's less reason to do so, as while it is still possible to create pathological allocation patterns, unless the application reaches a high water mark and then frees a huge number of objects that it then never need again, any empty space left behind can always be perfectly filled by new primary object allocations, and hopefully each such object is fairly small. If you want to, though, you can also compact auxiliary data (the "secondary heap") into holes in the primary heap when there's a good enough fit. E.g. on top of the steps I outlined: For each object, if there's an auxiliary data pointer, check if there's a suitable hole (keep lists by "hole size" for example) in the primary heap. If so, move there. If not, copy to end of new secondary heap. Update source pointer.

walkingolof 9y ago

Most of the machines on the list have a 16 bit address range (65536 bytes without paging) and usually less than that in free memory, GC or no GC, does not matter.

dfox 9y ago
Original PARC Smalltalk implementations had 32k (16b) word heaps (object pointers were 15b + one tag bit distinguishing SmallInteger and everything else). You could write quite complex systems with just that. Edit: this is true for the canonical ST80 VM described in Blue book, ST80 VM on Alto AFAIK had some indirection mechanism (ie. not 32k words, but 32k heap objects) and did paging.
- pjmlp 9y ago
  Also the Lisp implementations in the 60 and 70's were even more constrained on IBM mainframes.

xfer 9y ago

Look into javacard spec, it doesn't require a GC, but it is used everywhere(your credit card, SIM card etc.). The secure processors used here implement this spec.

nickpsecurity 9y ago
JavaCard is also one of the few areas where high-assurance security use commercially. Names that come to mind are Kesterel Institute and Gemalto with EAL7-style VM's with formal verification. Examples: https://www.commoncriteriaportal.org/iccc/9iccc/pdf/B2404.pdf https://www.commoncriteriaportal.org/iccc/9iccc/pdf/B2404.pd... http://www.kestrel.edu/home/projects/jcapplets/ http://www.kestrel.edu/home/projects/jcapplets/