rwmj 6 years ago

I'm impressed that they seem to have managed to get a mark-sweep GC to work with only 2K of RAM. Or does it use a special non-GC mode with small amounts of RAM?

  • vardump 6 years ago

    Lots of computers did garbage collection in the seventies and eighties.

    Commodore VIC-20 with 4kB of RAM is not far off the mark, for example, but AFAIK the BASIC could handle strings and DIM declared 1D/2D arrays.

    Ok, it was not mark and sweep, but the difference isn't much.

    Linearly scanning heap is fast when you have just 2 kB of RAM.

    When the heap is compacted, next object can be allocated after the last address. If there's not enough room after last address, just scan until a large enough deleted area is found. If even that fails just compact the heap.

    To save memory, each the first byte of allocation should be sufficient metadata for most allocations.

    For example, values 1-126 could be reserved for object length. The highest bit can used for MARK bit. 127 could mean object is longer than 127 bytes.

    0 could mean deleted, next byte contains original length, so that it's possible to scan forward past deleted objects.

    So scan through all heap objects, setting MARK to 0. Mark the reachable objects. Scan again, delete all unmarked objects.

    Of course updating all the references to objects that moved due to compacting will be slow, but it's just 2 kB one needs to scan. If that is too inefficient, one can always maintain a handle mapping instead of direct references at cost of some RAM.

  • pjc50 6 years ago

    They've used the classic technique of the bottom bit of the car pointer. The code is easy enough to read: https://github.com/technoblogy/ulisp/blob/master/ulisp.ino

        #define mark(x)            (car(x) = (object *)(((uintptr_t)(car(x))) | MARKBIT))
    #define unmark(x)          (car(x) = (object  *)(((uintptr_t)(car(x))) & ~MARKBIT))
    #define marked(x)          ((((uintptr_t)(car(x))) & MARKBIT) != 0)
    #define MARKBIT 1
    • rwmj 6 years ago

      Marking isn't the problem. It's fitting a minor + major heap into 2K. In my (small, but not very optimized) ML implementation a useful minor heap is probably min 64K.

bibyte 6 years ago

I have always wanted something like this. I can't really build this myself because I have no hardware skills.

  • russh 6 years ago

    If you have the desire, there has never been a better time to learn!

microspino 6 years ago

Enjoyed the introduction to uLisp a lot. The author is also a very good teacher and writer.