3 ms·

> It's hard for me to imagine any sane architecture where using more memory and having if fragmented rather than contiguous is going to perform as well as using

by lispm 2y ago

> It's hard for me to imagine any sane architecture where using more memory and having if fragmented rather than contiguous is going to perform as well as using a contiguous block of memory. Yet many of the language runtimes are actually following the Lisp model. Just that it's there not the cons cell with two slots, but arrays and objects with slots. A Java program is a multitude of dynamically allocated objects with one or more slots, where many of the slots contain pointers to other objects. The memory management is done by the runtime (and, usually, its garbage collector). > Sometimes they aren't. That doesn't fit the narrative that Lisp is god's gift to McCarthy who then gifted it to humanity, but it is reality. Other than what you might think (and set up as a strawman), that's well known and the evolution of Lisp is also showing how the implementations had to deal with this problem. The LISP 1 implementation introduced mark&sweep garbage collection (-> McCarthy). As a reaction to it Collins proposed "reference counting" as another way to manage&reclaim allocated memory. Over time early Lisp programs (Macsyma is an example often mentioned) were problematic on multi-user time-shared machines. One reaction to that was to develop single user workstations for Lisp, where all the memory was available to a single user. There one then used large virtual memory, which still made memory access (for example during garbage collection) time consuming. A GC run of a large heap in VM could run for 30 minutes making the computer mostly unusable during that time. Vectors/Arrays and OOP objects then also used the model of dynamic allocation with many referenced objects (unless they were of some primitive types). Generational GCs, compacting GCs, hardware-supported GCs, etc. were invented and implemented. Full GCs through virtual memory heaps were rare then. The availability of cheaper RAM made it possible that more of the large heaps fit into RAM. Lisp implementations early on added vectors and other data structures. But they still often need pointers. A vector of records (called structures in Common Lisp) is usually a vector with pointers to records. For example Common Lisp implementations usually will not provide vectors of inline records. A vector of fixnums OTOH will be a vector without pointers -> the fixnums will be stored directly in the vector. In the end a Lisp heap is a huge graph of objects referencing other objects. This does not only effect CONS cells, but also vectors, arrays, records, ... -> they also reference other, non-primitive, objects via pointers. That's not very different from any other language runtime which uses dynamic memory allocation and a heap of linked objects (-> Java, JavaScript, ...). The problem of dealing/avoiding non-locality and pointer-chasing is there, too.

kerkeslager 2y ago
This is moving the goalposts. My critique was about list implementation, not about implementing the entire runtime. > Yet many of the language runtimes are actually following the Lisp model. This is frankly not true in any way relevant to this conversation. Using garbage collection is not equivalent to using the entire Lisp model. Java, JavaScript, Python, Lua, Ruby, C#, etc. do not make extensive use of linked lists in their standard libraries, instead preferring--you guessed it--vectors. Hashmaps in modern languages are implemented as... vectors again. And if you dig into how structs are implemented in say, C#, they are implemented as contiguous blocks of memory. Yes, there are some things contiguous blocks of memory can't do, so everyone has to support nested data structures, but by default, most languages push you toward contiguous memory in their standard libraries and idioms whenever possible, because it's just so obviously more performant for the vast majority of cases. > That's not very different from any other language runtime which uses dynamic memory allocation and a heap of linked objects (-> Java, JavaScript, ...). The problem of dealing/avoiding non-locality and pointer-chasing is there, too. Yes, and my point is that having cons cells as a ubiquitous data structure in your language greatly exacerbates this problem. The extremely common case of lists does not need to entail pointer chasing, and in the vast majority of cases it should not entail pointer chasing, and contrary to your claims here, in most languages it does not entail pointer chasing. Lisp-family languages are fairly unique in this problem. Ironically, higher order functions like map/reduce/etc. push you toward operating on lists as a whole which is exactly the case where vectors most outshine linked lists.
- lispm 2y ago
  > My critique was about list implementation, not about implementing the entire runtime. Linked lists are actually managed by the runtime. Example on a esoteric platform, a Lisp Machine, a real, but outdated, computer. But we still have Virtual Lisp Machines, which have a virtualized implementation (not as in a microcoded CPU, as the real ones were). If I cons a list via CONS, I get a linked list made of cons cells. But over the lifetime of the list, this may change. At some point in time the runtime may decide to copy the list (for example because it has a copying garbage collector). The effect then is that the list is allocated in contiguous memory. The program itself does not see a difference. First the list (1 2 3) is allocated as [1 | -> [2 | -> [3 | NIL]]], written in Lisp as (1 . (2 . (3 . NIL))) . At some point in time the runtime changes this transparently to [1][2][3], where the cells are tagged, such that the successor is in the next memory word and where the last element is tagged that it has no successor. That's called cdr-coding. Now If I copy a list, with COPY-LIST I always get a cdr-coded list as a result. Several list functions return cdr-coded lists, instead of linked lists. This cdr-coding method is not much used anymore, since there is not much of an advantage: either one uses linked lists (because they are easy to use and have useful properties, like that CONS does not need to copy its arguments) or other available data structures (vectors, structures, ...). What is still used are locality improving garbage collectors. > Using garbage collection is not equivalent to using the entire Lisp model. Java, JavaScript, Python, Lua, Ruby, C#, etc. do not make extensive use of linked lists in their standard libraries, instead preferring--you guessed it--vectors. Lisp also makes use of vectors, where necessary. These languages with managed memory like Java have the same object/reference model as Lisp and the same calling mechanisms. linked lists are only a special case (-> java.util.LinkedList). Say we have N cities. Each city is a an object of class CITY. Each city will have attributes, for example NAME and PEOPLE-NUMBER. Now we want to keep two "lists" of them one sorted by name and another one sorted by PEOPLE-NUMBER. We need two vectors and N city objects. In Lisp the city objects are not stored in the vectors. They are stored somewhere in the heap. -> there goes your "contiguous memory" to bust. The vectors are pointers into a heap. Every access to the nth city object through one of the nicely contiguous vectors, references an object which is stored somewhere else. That model is used in many languages implementations. It's the Lisp model of memory management, introduced with Lisp 1 -> dynamic memory management plus a garbage collector to reclaim unused space. > And if you dig into how structs are implemented in say, C#, they are implemented as contiguous blocks of memory. That's also the case in Lisp. But a struct (or list or vector) of structs usually points to those being somewhere on the heap. A struct/list/vector of structs is not a single contiguous block of memory. structs in slots are typically not inlined. Some languages inline data non-primitive structures, Lisp usually does not. > contiguous blocks of memory That's can be an illusion. In a virtual memory system, the memory is made from pages of a fixed size. Random pages are cached in RAM, influenced by their usage pattern over time. > in most languages it does not entail pointer chasing It does, see above. Just not tail pointers in the list. > Ironically, higher order functions like map/reduce/etc. push you toward operating on lists as a whole which is exactly the case where vectors most outshine linked lists. That's why in Common Lisp the functions MAP and REDUCE work over vectors, too. > Lisp-family languages are fairly unique in this problem. see Prolog and various functional languages, ... some even have basic strings implemented as linked lists of characters (which Common Lisp does not do). If we look at data structures, one tries do address quite a bit more than "contiguous memory", for example persistence, runtime updates and runtime lookups, ... see for examples: https://cstheory.stackexchange.com/a/1550 https://cstheory.stackexchange.com/a/1550

by lispm 2y ago

kerkeslager 2y ago

This is moving the goalposts. My critique was about list implementation, not about implementing the entire runtime. > Yet many of the language runtimes are actually following the Lisp model. This is frankly not true in any way relevant to this conversation. Using garbage collection is not equivalent to using the entire Lisp model. Java, JavaScript, Python, Lua, Ruby, C#, etc. do not make extensive use of linked lists in their standard libraries, instead preferring--you guessed it--vectors. Hashmaps in modern languages are implemented as... vectors again. And if you dig into how structs are implemented in say, C#, they are implemented as contiguous blocks of memory. Yes, there are some things contiguous blocks of memory can't do, so everyone has to support nested data structures, but by default, most languages push you toward contiguous memory in their standard libraries and idioms whenever possible, because it's just so obviously more performant for the vast majority of cases. > That's not very different from any other language runtime which uses dynamic memory allocation and a heap of linked objects (-> Java, JavaScript, ...). The problem of dealing/avoiding non-locality and pointer-chasing is there, too. Yes, and my point is that having cons cells as a ubiquitous data structure in your language greatly exacerbates this problem. The extremely common case of lists does not need to entail pointer chasing, and in the vast majority of cases it should not entail pointer chasing, and contrary to your claims here, in most languages it does not entail pointer chasing. Lisp-family languages are fairly unique in this problem. Ironically, higher order functions like map/reduce/etc. push you toward operating on lists as a whole which is exactly the case where vectors most outshine linked lists.

lispm 2y ago
> My critique was about list implementation, not about implementing the entire runtime. Linked lists are actually managed by the runtime. Example on a esoteric platform, a Lisp Machine, a real, but outdated, computer. But we still have Virtual Lisp Machines, which have a virtualized implementation (not as in a microcoded CPU, as the real ones were). If I cons a list via CONS, I get a linked list made of cons cells. But over the lifetime of the list, this may change. At some point in time the runtime may decide to copy the list (for example because it has a copying garbage collector). The effect then is that the list is allocated in contiguous memory. The program itself does not see a difference. First the list (1 2 3) is allocated as [1 | -> [2 | -> [3 | NIL]]], written in Lisp as (1 . (2 . (3 . NIL))) . At some point in time the runtime changes this transparently to [1][2][3], where the cells are tagged, such that the successor is in the next memory word and where the last element is tagged that it has no successor. That's called cdr-coding. Now If I copy a list, with COPY-LIST I always get a cdr-coded list as a result. Several list functions return cdr-coded lists, instead of linked lists. This cdr-coding method is not much used anymore, since there is not much of an advantage: either one uses linked lists (because they are easy to use and have useful properties, like that CONS does not need to copy its arguments) or other available data structures (vectors, structures, ...). What is still used are locality improving garbage collectors. > Using garbage collection is not equivalent to using the entire Lisp model. Java, JavaScript, Python, Lua, Ruby, C#, etc. do not make extensive use of linked lists in their standard libraries, instead preferring--you guessed it--vectors. Lisp also makes use of vectors, where necessary. These languages with managed memory like Java have the same object/reference model as Lisp and the same calling mechanisms. linked lists are only a special case (-> java.util.LinkedList). Say we have N cities. Each city is a an object of class CITY. Each city will have attributes, for example NAME and PEOPLE-NUMBER. Now we want to keep two "lists" of them one sorted by name and another one sorted by PEOPLE-NUMBER. We need two vectors and N city objects. In Lisp the city objects are not stored in the vectors. They are stored somewhere in the heap. -> there goes your "contiguous memory" to bust. The vectors are pointers into a heap. Every access to the nth city object through one of the nicely contiguous vectors, references an object which is stored somewhere else. That model is used in many languages implementations. It's the Lisp model of memory management, introduced with Lisp 1 -> dynamic memory management plus a garbage collector to reclaim unused space. > And if you dig into how structs are implemented in say, C#, they are implemented as contiguous blocks of memory. That's also the case in Lisp. But a struct (or list or vector) of structs usually points to those being somewhere on the heap. A struct/list/vector of structs is not a single contiguous block of memory. structs in slots are typically not inlined. Some languages inline data non-primitive structures, Lisp usually does not. > contiguous blocks of memory That's can be an illusion. In a virtual memory system, the memory is made from pages of a fixed size. Random pages are cached in RAM, influenced by their usage pattern over time. > in most languages it does not entail pointer chasing It does, see above. Just not tail pointers in the list. > Ironically, higher order functions like map/reduce/etc. push you toward operating on lists as a whole which is exactly the case where vectors most outshine linked lists. That's why in Common Lisp the functions MAP and REDUCE work over vectors, too. > Lisp-family languages are fairly unique in this problem. see Prolog and various functional languages, ... some even have basic strings implemented as linked lists of characters (which Common Lisp does not do). If we look at data structures, one tries do address quite a bit more than "contiguous memory", for example persistence, runtime updates and runtime lookups, ... see for examples: https://cstheory.stackexchange.com/a/1550 https://cstheory.stackexchange.com/a/1550