4 ms·

A https://en.wikipedia.org/wiki/Tagged_architecture https://en.wikipedia.org/wiki/Tagged_architecture yes. Tags make life a bit easier for the CPU when it acces

by gwern 8y ago

A https://en.wikipedia.org/wiki/Tagged_architecture https://en.wikipedia.org/wiki/Tagged_architecture yes. Tags make life a bit easier for the CPU when it accesses objects and is deciding what to do with them, but the CPU is still doing all the work and walk the RAM to do the GC. (I vaguely recall stories about Lisp machine users who would turn off GC while working, and then let it run when they left work and returned the next day.) The idea here seems to be to have an entire separate chip, a specialized CPU, which walks RAM independently of the 'main' CPUs, whose only task is freeing up memory.

lispm 8y ago
> I vaguely recall stories about Lisp machine users who would turn off GC while working That was more in the early days when the GC was more primitive. The later GC was actually several different ones. A huge impact had the so-called 'Ephemeral GC', where the machine tracks changed RAM memory (it uses virtual memory in general) and where the EGC focuses on those areas with objects which were only very short-lived. That means, given a sufficient amount of memory, the machine stayed fast and responsive for a long time. The main problem was the low amount of RAM (20MB were common after the mid 80s), because RAM was very expensive, and the large amount of virtual memory (possibly hundreds of MB on slow disks). Thus what made the machines really slow was the GC over virtual memory with relatively slow disks. Thus the later mainly used GC was incremental&generational&copying&with areas and with support from the EGC - a full Mark&Sweep GC would keep the machine possibly busy for 15-40 minutes.
_old_dude_ 8y ago
There is a renaissance of that idea in ZGC [1]. You have a lot useless bits in a 64 bits pointers and thanks to the virtual memory, you can manage to have an untagged address and its corresponding tagged address referencing the same physical memory. This give you free bits that you can use to track the liveness/evacuation of a graph of objects. [1] https://wiki.openjdk.java.net/display/zgc/Main https://wiki.openjdk.java.net/display/zgc/Main
- p_l 8y ago
  Lisp Machines didn't use tags for tracking liveness/evacuation of objects, though. They used them for safety, which automatically gave them precise, as opposed to conservative, GC which always knew whether it was dealing with a pointer. They also had special, CPU-handled type of forwarding pointers, which when accessed "normally" would transparently redirect you to forwarded location.
  - _old_dude_ 8y ago
    The forwarding pointer you are describing is equivalent to a ZGC colored pointer with the evacuation bit set that a GC barrier (a load barrier) will rewrite to the evacuation address. and yes ZGC doesn't use colored pointer to track if a value is an integer or a pointer because Java unlike Lisp is typed so the VM derives those information from the bytecode.
    - p_l 8y ago
      Lisp is also typed - the tagging made for easier native code compilation vs. bytecoded approaches.
    - lispm 8y ago
      Most Lisp implementations use typed memory via tags. Lisp doesn't have pointers, but references and usually knows if something is an integer or a reference - because it's encoded in the tags.

by gwern 8y ago

lispm 8y ago

> I vaguely recall stories about Lisp machine users who would turn off GC while working That was more in the early days when the GC was more primitive. The later GC was actually several different ones. A huge impact had the so-called 'Ephemeral GC', where the machine tracks changed RAM memory (it uses virtual memory in general) and where the EGC focuses on those areas with objects which were only very short-lived. That means, given a sufficient amount of memory, the machine stayed fast and responsive for a long time. The main problem was the low amount of RAM (20MB were common after the mid 80s), because RAM was very expensive, and the large amount of virtual memory (possibly hundreds of MB on slow disks). Thus what made the machines really slow was the GC over virtual memory with relatively slow disks. Thus the later mainly used GC was incremental&generational&copying&with areas and with support from the EGC - a full Mark&Sweep GC would keep the machine possibly busy for 15-40 minutes.

_old_dude_ 8y ago

There is a renaissance of that idea in ZGC [1]. You have a lot useless bits in a 64 bits pointers and thanks to the virtual memory, you can manage to have an untagged address and its corresponding tagged address referencing the same physical memory. This give you free bits that you can use to track the liveness/evacuation of a graph of objects. [1] https://wiki.openjdk.java.net/display/zgc/Main https://wiki.openjdk.java.net/display/zgc/Main

p_l 8y ago
Lisp Machines didn't use tags for tracking liveness/evacuation of objects, though. They used them for safety, which automatically gave them precise, as opposed to conservative, GC which always knew whether it was dealing with a pointer. They also had special, CPU-handled type of forwarding pointers, which when accessed "normally" would transparently redirect you to forwarded location.
- _old_dude_ 8y ago
  The forwarding pointer you are describing is equivalent to a ZGC colored pointer with the evacuation bit set that a GC barrier (a load barrier) will rewrite to the evacuation address. and yes ZGC doesn't use colored pointer to track if a value is an integer or a pointer because Java unlike Lisp is typed so the VM derives those information from the bytecode.
  - p_l 8y ago
    Lisp is also typed - the tagging made for easier native code compilation vs. bytecoded approaches.
  - lispm 8y ago
    Most Lisp implementations use typed memory via tags. Lisp doesn't have pointers, but references and usually knows if something is an integer or a reference - because it's encoded in the tags.