5 ms·

> Every lisp system that ever existed uses this technique, and it never hurt them any. Wasn't it part of the reason they ended up with poor "mechanical sympath

by lmm 3y ago

> Every lisp system that ever existed uses this technique, and it never hurt them any. Wasn't it part of the reason they ended up with poor "mechanical sympathy" on regular PCs, and got a bad performance reputation as a result?

db48x 3y ago
No. Their reputation for poor performance mostly arises because the default data structure is a singly–linked list. Although the language makes these lists extremely convenient for the programmer to use, linked lists invariably result in terrible cache locality. High–performance systems that are written in lisp (and they do exist), achieve that performance by avoiding lists and using vectors and arenas instead. Of course, it must be said that this performance penalty rarely matters in practice. For most programs, the limiting factor is not performance but the cost of implementation and maintenance. Lisp has has many powerful and convenient features that make implementation faster and surer than in any other language, and which usually greatly lower the cost of maintenance as well. Thus by writing a new program in Lisp you can get it off the ground and earning you money faster than you could in almost any other language. You can also add features more cheaply as time goes on, allowing you to keep up with your competitors. It is only when your system is nearing completion, and all necessary features have been invented and implemented, that you should think about rewriting select parts of that system in a systems language where more efficiency is possible. Not only will you only understand the system after it is written, but you can measure the actual performance of the system to figure out which parts you need to rewrite, and which parts have acceptable performance already and thus do not need to be rewritten.
- jxf 3y ago
  > For most programs, the limiting factor is not performance but the cost of implementation and maintenance. The limiting factor for what? Their commercial success, or something else?
  - db48x 3y ago
    Success, yes. It need not be direct commercial success; lots of programs are written purely for internal use within some larger organization. And even when there are known performance requirements, Lisp is often still a good choice because the performance is handled by specialized hardware. Consider games, for example. Time to market and rapid iteration are both paramount, while performance is taken care of not by writing a fast renderer but by sending everything to the GPU to be rendered on specialized hardware.
- pfdietz 3y ago
  Cache locality is improved if the Lisp has a compacting garbage collector, but you still need extra memory for the cdr links. Lisp Machines had cdr-coding that allowed those to be avoided but I don't think that's practical on stock architectures.
  - db48x 3y ago
    True, but don’t forget that one of the _other_ causes of performance problems in lisp programs is the creation and subsequent collection of garbage. If you know ahead of time which of your data needs to be accessed or created by the most performance–sensitive parts of your program, then you can put that data into vectors to start with and avoid all of the extra work.
    - pfdietz 3y ago
      Long-lived things end up in older generations and aren't traversed much during GC, which is the moral equivalent of being statically allocated. There's overhead if you mutate old objects in a GCed system due to card marking. Lisp vectors are vectors of pointers, so there's still an overhead of dereferencing through it. Presumably the objects being pointed to end up compacted together, eventually.
      - db48x 3y ago
        I should have been more clear; I meant using vectors as arena allocators, so that all of your data ends up stored contiguously with no extra indirection.
- mik1998 3y ago
  > linked lists invariably result in terrible cache locality With a compacting GC (ie most of the relevant ones) lists often provide better memory locality than arrays. They only lose at a large scale due to having +8 bytes of memory, which makes arrays occasionally cheaper for large sequences.
  - nequo 3y ago
    Why do lists provide better memory locality than arrays? The array already stores its elements next to each other in memory. The compacting GC helps arrange the elements of the list close to each other too, right? Then wouldn’t the compacting GC at best even out the performance difference for sequential traversal?
  - gpderetta 3y ago
    Even with perfect cache locality, a linked list will be significantly slower to traverse than an array because of worse pipelining and parallelization. Partially unrolled lists can help, but at the cost of additional complexity. Of course not all container accesses require traversal.
bitwize 3y ago
I don't know what you mean. Maybe in the early early 80s that was the case, but PCs were still 16-bit back then, and would've been a poor fit for Lisp anyway. One of the reasons why the Lisp machines died out is that round about the mid-80s or so, compiler technology improved for generic 32-bit processors, and it became possible to run Lisp software on a VAX, 68k, or RISC CPU faster than it ran on the Lisp machines' bespoke architecture. Back during the first AI hypecycle, the makers of Golden Common Lisp introduced the Hummingboard to the market, billed as an inexpensive solution to have a "Lisp machine in a PC". It was just a 386 on an ISA card (predating Compaq's 386 PC by about a year) with gobs of memory on board; a special build of Golden Common Lisp allowed code to be run on that CPU rather than the main one.
- coldtea 3y ago
  >One of the reasons why the Lisp machines died out is that round about the mid-80s or so, compiler technology improved for generic 32-bit processors, and it became possible to run Lisp software on a VAX, 68k, or RISC CPU faster than it ran on the Lisp machines' bespoke architecture. I'd say Lisp machines died out because Lisp died out (commercially). Other languages got popular, the second AI winter didn't help at all either. If Lisp itself had fared better (even if it was on generic hardware), Lisp machines could have been saved too, they could still use a VAX, 68k, or RISC CPU underneath, and optimize for the developer experience. Or they'd have turned Lisp machines from hardware into a "Lisp machine" OS or IDE/REPL/etc environment for other OSes succeeding. But none of that took off.
  - zozbot234 3y ago
    > Or they'd have turned Lisp machines from hardware into a "Lisp machine" OS Emacs is that Lisp OS. But it's still lacking a good text editor.
    - pfdietz 3y ago
      Ok, that made me laugh.
  - bitwize 3y ago
lispm 3y ago
No, the reason for less than stellar performance of Lisp on the 32bit x86 CPUs were things like too few registers. On 64bit Intel CPUs this is much less of a problem and Lisp runs roughly twice as fast in 64bit mode. I would think that this even holds without taking advantage of wider data words. On other architectures this was less of a problem. 32bit CPUs had more registers on a RISC or some other CISC CPUs.
samatman 3y ago
It's not. Two counterexamples: LuaJIT's interpreter/VM, and Wren's, both use NaN boxing, and are among the fastest VMs out there (we're ignoring JITs as out of scope). It isn't tagging pointers that makes things (some Lisps are 'things', some are not) slow: it's pervasive abstraction and indirection. Doing some masking on a pointer is pipelined, out-of-order, one to three cycles, and is absolutely dwarfed by cache misses and conditional mispredictions, let alone the sort of pointer chasing which is common in idiomatic Lisp (or indeed Python) code.

by lmm 3y ago

db48x 3y ago

No. Their reputation for poor performance mostly arises because the default data structure is a singly–linked list. Although the language makes these lists extremely convenient for the programmer to use, linked lists invariably result in terrible cache locality. High–performance systems that are written in lisp (and they do exist), achieve that performance by avoiding lists and using vectors and arenas instead. Of course, it must be said that this performance penalty rarely matters in practice. For most programs, the limiting factor is not performance but the cost of implementation and maintenance. Lisp has has many powerful and convenient features that make implementation faster and surer than in any other language, and which usually greatly lower the cost of maintenance as well. Thus by writing a new program in Lisp you can get it off the ground and earning you money faster than you could in almost any other language. You can also add features more cheaply as time goes on, allowing you to keep up with your competitors. It is only when your system is nearing completion, and all necessary features have been invented and implemented, that you should think about rewriting select parts of that system in a systems language where more efficiency is possible. Not only will you only understand the system after it is written, but you can measure the actual performance of the system to figure out which parts you need to rewrite, and which parts have acceptable performance already and thus do not need to be rewritten.

jxf 3y ago
> For most programs, the limiting factor is not performance but the cost of implementation and maintenance. The limiting factor for what? Their commercial success, or something else?
- db48x 3y ago
  Success, yes. It need not be direct commercial success; lots of programs are written purely for internal use within some larger organization. And even when there are known performance requirements, Lisp is often still a good choice because the performance is handled by specialized hardware. Consider games, for example. Time to market and rapid iteration are both paramount, while performance is taken care of not by writing a fast renderer but by sending everything to the GPU to be rendered on specialized hardware.
pfdietz 3y ago
Cache locality is improved if the Lisp has a compacting garbage collector, but you still need extra memory for the cdr links. Lisp Machines had cdr-coding that allowed those to be avoided but I don't think that's practical on stock architectures.
- db48x 3y ago
  True, but don’t forget that one of the _other_ causes of performance problems in lisp programs is the creation and subsequent collection of garbage. If you know ahead of time which of your data needs to be accessed or created by the most performance–sensitive parts of your program, then you can put that data into vectors to start with and avoid all of the extra work.
  - pfdietz 3y ago
    Long-lived things end up in older generations and aren't traversed much during GC, which is the moral equivalent of being statically allocated. There's overhead if you mutate old objects in a GCed system due to card marking. Lisp vectors are vectors of pointers, so there's still an overhead of dereferencing through it. Presumably the objects being pointed to end up compacted together, eventually.
    - db48x 3y ago
      I should have been more clear; I meant using vectors as arena allocators, so that all of your data ends up stored contiguously with no extra indirection.
mik1998 3y ago
> linked lists invariably result in terrible cache locality With a compacting GC (ie most of the relevant ones) lists often provide better memory locality than arrays. They only lose at a large scale due to having +8 bytes of memory, which makes arrays occasionally cheaper for large sequences.
- nequo 3y ago
  Why do lists provide better memory locality than arrays? The array already stores its elements next to each other in memory. The compacting GC helps arrange the elements of the list close to each other too, right? Then wouldn’t the compacting GC at best even out the performance difference for sequential traversal?
- gpderetta 3y ago
  Even with perfect cache locality, a linked list will be significantly slower to traverse than an array because of worse pipelining and parallelization. Partially unrolled lists can help, but at the cost of additional complexity. Of course not all container accesses require traversal.

bitwize 3y ago

I don't know what you mean. Maybe in the early early 80s that was the case, but PCs were still 16-bit back then, and would've been a poor fit for Lisp anyway. One of the reasons why the Lisp machines died out is that round about the mid-80s or so, compiler technology improved for generic 32-bit processors, and it became possible to run Lisp software on a VAX, 68k, or RISC CPU faster than it ran on the Lisp machines' bespoke architecture. Back during the first AI hypecycle, the makers of Golden Common Lisp introduced the Hummingboard to the market, billed as an inexpensive solution to have a "Lisp machine in a PC". It was just a 386 on an ISA card (predating Compaq's 386 PC by about a year) with gobs of memory on board; a special build of Golden Common Lisp allowed code to be run on that CPU rather than the main one.

coldtea 3y ago
>One of the reasons why the Lisp machines died out is that round about the mid-80s or so, compiler technology improved for generic 32-bit processors, and it became possible to run Lisp software on a VAX, 68k, or RISC CPU faster than it ran on the Lisp machines' bespoke architecture. I'd say Lisp machines died out because Lisp died out (commercially). Other languages got popular, the second AI winter didn't help at all either. If Lisp itself had fared better (even if it was on generic hardware), Lisp machines could have been saved too, they could still use a VAX, 68k, or RISC CPU underneath, and optimize for the developer experience. Or they'd have turned Lisp machines from hardware into a "Lisp machine" OS or IDE/REPL/etc environment for other OSes succeeding. But none of that took off.
- zozbot234 3y ago
  > Or they'd have turned Lisp machines from hardware into a "Lisp machine" OS Emacs is that Lisp OS. But it's still lacking a good text editor.
  - pfdietz 3y ago
    Ok, that made me laugh.
- bitwize 3y ago

lispm 3y ago

No, the reason for less than stellar performance of Lisp on the 32bit x86 CPUs were things like too few registers. On 64bit Intel CPUs this is much less of a problem and Lisp runs roughly twice as fast in 64bit mode. I would think that this even holds without taking advantage of wider data words. On other architectures this was less of a problem. 32bit CPUs had more registers on a RISC or some other CISC CPUs.

samatman 3y ago

It's not. Two counterexamples: LuaJIT's interpreter/VM, and Wren's, both use NaN boxing, and are among the fastest VMs out there (we're ignoring JITs as out of scope). It isn't tagging pointers that makes things (some Lisps are 'things', some are not) slow: it's pervasive abstraction and indirection. Doing some masking on a pointer is pipelined, out-of-order, one to three cycles, and is absolutely dwarfed by cache misses and conditional mispredictions, let alone the sort of pointer chasing which is common in idiomatic Lisp (or indeed Python) code.