20 ms·

Shouldn't [2012] be appended to the title? I've seen the article discussed on HN before. [1] [1] https://news.ycombinator.com/item?id=3830867 https://news.ycom

Shouldn't [2012] be appended to the title? I've seen the article discussed on HN before. [1] [1] https://news.ycombinator.com/item?id=3830867 https://news.ycombinator.com/item?id=3830867

falcolas 12y ago
Meta: does the date really matter, when we're discussing concepts and theory which change infrequently, if at all?
- PaulHoule 12y ago
  Things change. LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies. The car/cdr list is just about the worst way to represent lists in terms of performance on modern CPUS. Conceptually it is really clean, but about the only application it makes sense for is first order theorem proving, or in languages that support pattern matching. If you actually want to use lists as lists something like the Java ArrayList makes more sense.
  - davexunit 12y ago
    >LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies. Yeah, let's just forget about decades of Lisp development since. >something like the Java ArrayList makes more sense. Except you lose the most important detail of Lisp pairs: persistence.
    - dasmoth 12y ago
      And in practice, compromise is possible. E.g. Clojure's vectors which are unashamedly LISP-like to work with, but still avoid much of the pointer-chasing of a linked list.
      - davexunit 12y ago
        Yes, there are various implementations of persistent vector-like lists, Clojure's being one of them. They are extremely useful, however, they are far more complex than a cons cell. Most of the time, I want simple cons cells.
        gsg 12y ago
        There are schemes to "unroll" conses, too. CDR-coding, Appel's paper (although IIRC that requires immutable conses), etc.
    - PaulHoule 12y ago
      Persistence has some good properties, particularly if you are writing compilers. Just about every language that promises an advance in parallelism (other than solidly "worse is better" approaches such as Hadoop and Pig) is selling some kind of snake oil, and immutability is one of the worst of them. Immutability has benefits in terms of correctness, but not in terms of scalability to more processors or total throughput. With modern memory hierarchies a lot revolves around never letting two threads touch the same cache line and this happens at all you lose at least an order of magnitude in performance. Garbage collection involves global properties of the system, so there will always be some "stop the world" element of GC, so GC itself becomes a scaling bottleneck when you allocate lots of memory and throw it all behind your rear.
      - davexunit 12y ago
        >Immutability has benefits in terms of correctness, but not in terms of scalability to more processors or total throughput. I'll take correctness over raw performance any day.
        pjmlp 12y ago
        I am with you, specially since we all know where languages obsessed with performance over correctness lead to. http://web.nvd.nist.gov/view/vuln/search-results?query=&search_type=all&cves=on http://web.nvd.nist.gov/view/vuln/search-results?query=&sear...
        hga 12y ago
        Although the funny thing is, as the 2nd oldest surviving computer language after FORTRAN, and at least back then used for very difficult problems, to be competitive let alone justifiable on extremely scarce and expensive hardware, "Lisp" has always been "obsessed" with performance. ADDED along with a bit before: It first ran on the IBM 704, a vacuum tube computer. It was derived from the IBM 701, which initially used Williams tubes for memory (https://en.wikipedia.org/wiki/Williams_tube https://en.wikipedia.org/wiki/Williams_tube). Scare quotes because "anyone" can program up a Lisp "in a week". High performance LISPs not surprisingly require very roughly the same amount of effort as any other high performance language implementation. Lisp got its first compiler in 1962, 4 years after its launch (and it was the first self-hosting compiler, i.e. written in itself). As the inventor of garbage collection, it's long been a major driver of innovations in GC (although of course much less so now that Java etc. gave GCed languages mainstream cred). But by and large, except for strictness of dynamic type checking (often a tunable variable), sacrificing correctness for speed has never been part of Lisp's DNA.
  - lispm 12y ago
    > LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies. You mean like in the 80s with very little RAM, larger virtual memory to very slow disks, paging files of networks, booted images from network servers over 10Mbit links, ... A time when commercial Lisp did a lot to be memory efficient (like cdr coding of Lisps, compacting GCs, incremental GCs, ephemeral GCs, generational GCs, ...). > The car/cdr list is just about the worst way to represent lists in terms of performance on modern CPUS. Actually modern CPUs are really fast with these list operations. For a lot of operations linked lists are fully sufficient. You might also want to note that Lisp has data structures like vectors, multi-dimensional arrays, records, instances of Classes, hash tables and all kinds of fancy stuff, including access to 'foreign' memory which is accessible with pointers and manual memory management. Currently optimized Lisp code is as fast as F#, OCaml, Java, Haskell or similar...
  - weland 12y ago
    That's... basically not even wrong. Lisp implementations that run well on, and take advantage of, architectures with caches, branch prediction and complex memory hierarchies are well-known, and have been well-known for, literally, decades. http://pt.withy.org/publications/VLM.html http://pt.withy.org/publications/VLM.html is an example from 1994. More importantly though, even the earlier Lisp machines (at least since 1983!) implemented a form of instruction caching, and had hardware-aided garbage collection. > The car/cdr list is just about the worst way to represent lists in terms of performance on modern CPUS. Conceptually it is really clean, but about the only application it makes sense for is first order theorem proving, or in languages that support pattern matching. If you actually want to use lists as lists something like the Java ArrayList makes more sense. The car/cdr list is not the only data structure in Common Lisp.
    - RodgerTheGreat 12y ago
      The car/cdr list is the only data structure described in cute metacircular interpreters, and even then only when supported by a substantial amount of implied runtime code.
      - pjmlp 12y ago
        This doesn't look like a substantial runtime code. http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
        RodgerTheGreat 12y ago
        That doesn't look like sufficient runtime code. That paper quite explicitly avoids implementing a garbage collector, among other things.
        pjmlp 12y ago
        A simple reference counted implementation with cycle collector is not a big deal to implement, nor a substantial effort. It might perform like a dog, but that is another matter.
  - pjmlp 12y ago
    Although it is called List Processing, it does support other types of data structures, including arrays. https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node158.html#SECTION002110000000000000000 https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node158.html#... Don't blame the language for lack of programmer knowledge.
    - PaulHoule 12y ago
      Retrocomputing (such as the Cult of Knuth) seeds programmers with obsolete knowledge which displaces useful knowledge. If you learn anything about binary search you should learn to avoid it. Even computer science books have a wrong implementation of it more than 50% of the time and, that, together with all the algorithms based on total ordering, tends to blind people to the fascinating world of algorithms that are based on partial orderings. 99% of the time you are better off using the hashtables that come with your language than you are to look into a "data structures and algorithms" book we're you'll probably pick something that performs worse and you'll screw up the implementation of. (I recently wasted a few days coding up something that was "kinda like" binary search, but the analogy with binary search led me to think about it the wrong way.) Today people still read the stuff on Random Number generators from Knuth, which was obsolete by 1985. It's very likely that the rand() function in your language comes out of Knuth, even though his stuff was completely superceded but what was in Numerical Recipes (Knuth never did scientiic computing) and the stuff in NR was obsolete by 1990. They're removing rand() from the C++ standard library because they can't burn all the copies of Knuth fast enough to stop standard library implementers from reimplementing all the bad algorithms.
_lce0 12y ago
I thought HN wont allow to re-post the exact same url, so to bypass people add noise to the url. is date of post also considered?
- phowat 12y ago
  Yes, after some time has passed, HN will allow the same link to be resubmitted.
- andyjohnson0 12y ago
  As far as I know, re-posts are allowed after some period of time has elapsed. I don't think this is documented anywhere though.
  - samatman 12y ago
    I've always figured the URLS just fall off a queue, so there's no absolute period of time involved. No actual knowledge, just a guess.
    - _lce0 12y ago
      sweet, so we could attempt to find out the queue size!!

Shouldn't [2012] be appended to the title? I've seen the article discussed on HN before. [1] [1] https://news.ycombinator.com/item?id=3830867 https://news.ycombinator.com/item?id=3830867

falcolas 12y ago

Meta: does the date really matter, when we're discussing concepts and theory which change infrequently, if at all?

PaulHoule 12y ago
Things change. LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies. The car/cdr list is just about the worst way to represent lists in terms of performance on modern CPUS. Conceptually it is really clean, but about the only application it makes sense for is first order theorem proving, or in languages that support pattern matching. If you actually want to use lists as lists something like the Java ArrayList makes more sense.
- davexunit 12y ago
  >LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies. Yeah, let's just forget about decades of Lisp development since. >something like the Java ArrayList makes more sense. Except you lose the most important detail of Lisp pairs: persistence.
  - dasmoth 12y ago
    And in practice, compromise is possible. E.g. Clojure's vectors which are unashamedly LISP-like to work with, but still avoid much of the pointer-chasing of a linked list.
    - davexunit 12y ago
      Yes, there are various implementations of persistent vector-like lists, Clojure's being one of them. They are extremely useful, however, they are far more complex than a cons cell. Most of the time, I want simple cons cells.
      - gsg 12y ago
        There are schemes to "unroll" conses, too. CDR-coding, Appel's paper (although IIRC that requires immutable conses), etc.
  - PaulHoule 12y ago
    Persistence has some good properties, particularly if you are writing compilers. Just about every language that promises an advance in parallelism (other than solidly "worse is better" approaches such as Hadoop and Pig) is selling some kind of snake oil, and immutability is one of the worst of them. Immutability has benefits in terms of correctness, but not in terms of scalability to more processors or total throughput. With modern memory hierarchies a lot revolves around never letting two threads touch the same cache line and this happens at all you lose at least an order of magnitude in performance. Garbage collection involves global properties of the system, so there will always be some "stop the world" element of GC, so GC itself becomes a scaling bottleneck when you allocate lots of memory and throw it all behind your rear.
    - davexunit 12y ago
      >Immutability has benefits in terms of correctness, but not in terms of scalability to more processors or total throughput. I'll take correctness over raw performance any day.
      - pjmlp 12y ago
        I am with you, specially since we all know where languages obsessed with performance over correctness lead to. http://web.nvd.nist.gov/view/vuln/search-results?query=&search_type=all&cves=on http://web.nvd.nist.gov/view/vuln/search-results?query=&sear...
        hga 12y ago
        Although the funny thing is, as the 2nd oldest surviving computer language after FORTRAN, and at least back then used for very difficult problems, to be competitive let alone justifiable on extremely scarce and expensive hardware, "Lisp" has always been "obsessed" with performance. ADDED along with a bit before: It first ran on the IBM 704, a vacuum tube computer. It was derived from the IBM 701, which initially used Williams tubes for memory (https://en.wikipedia.org/wiki/Williams_tube https://en.wikipedia.org/wiki/Williams_tube). Scare quotes because "anyone" can program up a Lisp "in a week". High performance LISPs not surprisingly require very roughly the same amount of effort as any other high performance language implementation. Lisp got its first compiler in 1962, 4 years after its launch (and it was the first self-hosting compiler, i.e. written in itself). As the inventor of garbage collection, it's long been a major driver of innovations in GC (although of course much less so now that Java etc. gave GCed languages mainstream cred). But by and large, except for strictness of dynamic type checking (often a tunable variable), sacrificing correctness for speed has never been part of Lisp's DNA.
- lispm 12y ago
  > LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies. You mean like in the 80s with very little RAM, larger virtual memory to very slow disks, paging files of networks, booted images from network servers over 10Mbit links, ... A time when commercial Lisp did a lot to be memory efficient (like cdr coding of Lisps, compacting GCs, incremental GCs, ephemeral GCs, generational GCs, ...). > The car/cdr list is just about the worst way to represent lists in terms of performance on modern CPUS. Actually modern CPUs are really fast with these list operations. For a lot of operations linked lists are fully sufficient. You might also want to note that Lisp has data structures like vectors, multi-dimensional arrays, records, instances of Classes, hash tables and all kinds of fancy stuff, including access to 'foreign' memory which is accessible with pointers and manual memory management. Currently optimized Lisp code is as fast as F#, OCaml, Java, Haskell or similar...
- weland 12y ago
  That's... basically not even wrong. Lisp implementations that run well on, and take advantage of, architectures with caches, branch prediction and complex memory hierarchies are well-known, and have been well-known for, literally, decades. http://pt.withy.org/publications/VLM.html http://pt.withy.org/publications/VLM.html is an example from 1994. More importantly though, even the earlier Lisp machines (at least since 1983!) implemented a form of instruction caching, and had hardware-aided garbage collection. > The car/cdr list is just about the worst way to represent lists in terms of performance on modern CPUS. Conceptually it is really clean, but about the only application it makes sense for is first order theorem proving, or in languages that support pattern matching. If you actually want to use lists as lists something like the Java ArrayList makes more sense. The car/cdr list is not the only data structure in Common Lisp.
  - RodgerTheGreat 12y ago
    The car/cdr list is the only data structure described in cute metacircular interpreters, and even then only when supported by a substantial amount of implied runtime code.
    - pjmlp 12y ago
      This doesn't look like a substantial runtime code. http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
      - RodgerTheGreat 12y ago
        That doesn't look like sufficient runtime code. That paper quite explicitly avoids implementing a garbage collector, among other things.
        pjmlp 12y ago
        A simple reference counted implementation with cycle collector is not a big deal to implement, nor a substantial effort. It might perform like a dog, but that is another matter.
- pjmlp 12y ago
  Although it is called List Processing, it does support other types of data structures, including arrays. https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node158.html#SECTION002110000000000000000 https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node158.html#... Don't blame the language for lack of programmer knowledge.
  - PaulHoule 12y ago
    Retrocomputing (such as the Cult of Knuth) seeds programmers with obsolete knowledge which displaces useful knowledge. If you learn anything about binary search you should learn to avoid it. Even computer science books have a wrong implementation of it more than 50% of the time and, that, together with all the algorithms based on total ordering, tends to blind people to the fascinating world of algorithms that are based on partial orderings. 99% of the time you are better off using the hashtables that come with your language than you are to look into a "data structures and algorithms" book we're you'll probably pick something that performs worse and you'll screw up the implementation of. (I recently wasted a few days coding up something that was "kinda like" binary search, but the analogy with binary search led me to think about it the wrong way.) Today people still read the stuff on Random Number generators from Knuth, which was obsolete by 1985. It's very likely that the rand() function in your language comes out of Knuth, even though his stuff was completely superceded but what was in Numerical Recipes (Knuth never did scientiic computing) and the stuff in NR was obsolete by 1990. They're removing rand() from the C++ standard library because they can't burn all the copies of Knuth fast enough to stop standard library implementers from reimplementing all the bad algorithms.

_lce0 12y ago

I thought HN wont allow to re-post the exact same url, so to bypass people add noise to the url. is date of post also considered?

phowat 12y ago
Yes, after some time has passed, HN will allow the same link to be resubmitted.
andyjohnson0 12y ago
As far as I know, re-posts are allowed after some period of time has elapsed. I don't think this is documented anywhere though.
- samatman 12y ago
  I've always figured the URLS just fall off a queue, so there's no absolute period of time involved. No actual knowledge, just a guess.
  - _lce0 12y ago
    sweet, so we could attempt to find out the queue size!!