Hacker News Reader

Comment by vvanders | Hacker News Reader

> The assumption is that the machine code of the C++ compiler is significantly faster than that emitted by a comparable dynamic language compiler. While this may hold true in general, it does not necessarily hold true with Lisp. Lisp is a programmable programming languages. If we are inclined to program it for speed, we can.

My Lisp-fu isn't as strong as my C++-fu so someone correct me if I'm wrong but isn't the GC an intrinsic part of Lisp? Do more modern Lisps allow you to mark value types so you can control memory access patterns(which is where the true speed of C/C++ comes from).

View on HN

Lisp does support more than just lists as data structures.

Arrays are also available, including specialized versions that hold value types.

https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node15.html

You can also stack allocate if required, via dynamic-extent, http://clhs.lisp.se/Body/d_dynami.htm

Also not all Lisps have a tracing GC, some variants had a RC with tracing GC for collecting cycles.

RAII like patterns can be achieved via the with-.... functions, or macros.

I don't know the actual performance of commercial Lisps like Allegro Common Lisp and LispWorks, but I imagine it is quite good, given that they stay in business.

On the other had, given the amount of money spent in C and C++ optimizers vs the lack of industry wide adoption of Lisp, probably still not as good as current leading C++ compilers.

Indeed, those with- macros.

In TXR Lisp, RAII is supported thusly:

This is GC finalization of a struct:

  This is the TXR Lisp interactive listener of TXR 172.
  Use the :quit command or type Ctrl-D on empty line to exit.
  1> (defstruct animal nil
       (:fini (me) (put-line `@me says good-bye`)))
  #<struct-type animal>
  2> (progn (new animal) nil) ;; make animal without referencing from REPL
  nil
  3> (+ 2 2)
  4
  4> (sys:gc)
  #S(animal) says good-bye
  t

OK, now with-objects macro:

   5> (with-objects ((a (new animal)))
       (prinl a))
   #S(animal)
   #S(animal) says good-bye
   #S(animal)

with-objects invokes finalizers explicitly, before objects become unreachable.

Also, what if a constructor throws? Let's derive animal to dog which bails at `new` time:

  6> (defstruct dog animal
       (:fini (me) (put-line `@me: woof woof`))
       (:postinit (me) (error "refuse to construct")))
  #<struct-type dog>
  7> (new dog)
  #S(dog): woof woof
  #S(dog) says good-bye
  ** refuse to construct
  ** during evaluation at expr-6:3 of form (error "refuse to construct")

The object instantiation logic catches exceptions and invokes finalizers on a partially constructed object (in the proper order as you can see: derived, then base).

The with-* style function do not replace RAII except for the limited case of lexically scoped resources. Not all resources are scoped lexically -- e.g. file handles you store in a map. What C++ programmers typically see as the most important guarantee is that RAII is prompt freeing -- that is, as soon as said example map goes out of its scope (or is freed by its owner), then those file handles will also be freed immediately.

Neither the gc-based nor with-* based solutions handle that.

Even on C++ RAII requires a lexical scope at some point in the program.

Somewhere in the whole workflow there must be a class allocated in the stack.

You can have destructor like behavior in Lisp as well, just register a file handle cleanup action by giving a cleanup lambda when creating the map instance.

The function that removes entries from the map will call the provided lambda.

I'm sure I must be missing something, but can you give a concrete example?

Of course instances of classes (not "classes", as you say, classes are an entirely compile-time construct in C++) must be allocated, but I mean... there's still heap storage. You know, shared_ptr<T> and all that...

What am I missing?

> You can have destructor like behavior in Lisp as well, just register a file handle cleanup action by giving a cleanup lambda when creating the map instance.

Well, except you don't know exactly when the map is going to get cleaned up...? And it could get reused across various sections of the program... Do you see what I'm talking about?

EDIT: That, and if the map exists for the entire duration of the program, but it's really important that entries have prompt cleanup when removed... what then?

(Btw, I do understand that in the general case with weak_ptr, shared_ptr, unique_ptr, etc. that things get decidedly less deterministic[1], but RAII is pretty well defined by scope or referenced-to-scope.)

[1] Basically almost as unpredictable as a general purpose GC. I can't recall the paper title, but I'm sure there is a paper out there detailing this.

TXR Lisp:

  This is the TXR Lisp interactive listener of TXR 173.
  Use the :quit command or type Ctrl-D on empty line to exit.
  1> (defstruct map nil
       (hash (hash :equal-based))
       (:method lambda (me key) (gethash me.hash key))
       (:method lambda-set (me key new-val)
         (let ((old-val (shift (gethash me.hash key) new-val)))
           (call-finalizers old-val)
           new-val))
       (:fini (me)
         (dohash (key val me.hash)
           (call-finalizers key)
           (call-finalizers val))))
  #<struct-type map>
  2> (defstruct widget nil
       id
       (:static counter 0)
       (:init (me) (set me.id (inc me.counter)))
       (:fini (me) (put-line `widget @{me.id} says bye`)))
  #<struct-type widget>
  3> (defvar map (new map))
  map
  4> (set [map "a"] (new widget))
  #S(widget id 1)
  5> (set [map "a"] (new widget))
  widget 1 says bye
  #S(widget id 2)
  6> (set [map "a"] (new widget))
  widget 2 says bye
  #S(widget id 3)
  7> (set [map "b"] (new widget))
  #S(widget id 4)
  8> (set [map "c"] (new widget))
  #S(widget id 5)
  9> (call-finalizers map)
  widget 3 says bye
  widget 4 says bye
  widget 5 says bye
  10> (with-objects ((m (new map)))
        (set [m "x"] (new widget))
        (set [m "y"] (new widget)))
  widget 6 says bye
  widget 7 says bye
  #S(widget id 7)

You can see in my example that non-lexically scoped resources are involved also.

Secondly, doing RAII into and out of a map container is largely a poor idea, and C++ programmers expend energy fighting it.

The assignment operation and constructors and destructors of the map element all have lexical scopes somewhere.

> You can see in my example that non-lexically scoped resources are involved also.

Please explain your example further then, because I don't see it.

> Secondly, doing RAII into and out of a map container is largely a poor idea, and C++ programmers expend energy fighting it.

Again, explain, please. Why is it a "poor idea"? Any links, at least? "Fighting it"... how, exactly?

(It's been a while since I was a professional C++ programmer, but I don't really recognize this characterization.)

> The assignment operation and constructors and destructors of the map element all have lexical scopes somewhere.

Well, yes, but what about the MAP itself? It could easily be heap allocated.

I'm sorry, I just don't see what you're on about.

The map being heap allocated somewhere means this, in its most basic form:

  {
    map<whatever> *ptr = new map<whatever> ;

    // forgotten delete
  }

If you don't want the heap allocated map to leak, and you want that management to be automated, you need some smart pointer type to reference it; map itself doesn't help.

All RAII-driven management of heap resources is tied to some scope somewhere. Anything not tied to scoping has to be treated explicitly: try to calculate the lifetime and explicitly dispose of the resource.

AFAICT you're saying that RAII = RC. Am I correct in thinking that?

"I don't know the actual performance of commercial Lisps like Allegro Common Lisp and LispWorks, but I imagine it is quite good, given that they stay in business."

It might be good or just OK on modern hardware. I imagine they stayed in business for their IDE's, libraries, commercial support, and decent compilers. Batteries included. Some success stories make me think performance is really good, though.

http://www.lispworks.com/success-stories/netfonds-primetrade...

http://www.lispworks.com/success-stories/ral-siglab.html

I found those while looking for one about a real-time implementation for telecom or something. Franz's success stories are mostly about doing complicated stuff easier. There was one that looked performance-critical:

http://franz.com/success/customer_apps/finance/ravenpack.lht...

Here is a another one, a Portuguese company specialized in Lisp based solutions, for timetables and fleet management.

http://www.siscog.eu/

The last time I checked, the naive Lisp will be shorter than the typical C++, but usually much slower. Sometimes you can annotate your code to death for performance, resulting in something longer than the C++ with more parens, but you still can't trust the compiler to get it right. Fortunately, thanks to DEFMACRO, Lisp lets you write your own optimizing compiler, so as long as your implementation supports your full instruction set, you can do that and achieve better-than-C performance by generating Fortran IV's ugly cousin.

> I don't know the actual performance of commercial Lisps like Allegro Common Lisp and LispWorks, but I imagine it is quite good, given that they stay in business.

Performance is not one easy number. Applications have different performance requirements. In many benchmarks for typed or type inferred code SBCL tends to be slightly faster with less programming effort.

Fast can mean for example:

* fastest possible execution of optimized code

Then one might not care about code size, code safety, robustness, threading capability, interrupts, .

* fast execution of non-optimized robust, flexible, reflective, debuggable code.

Allegro CL and LispWorks integrate a lot of features. These features are provided over some amount of platforms, with only few restrictions. They provide relatively good performance of a native code compiler. Some robustness is needed for commercial applications, thus I would expect an advantage there.

Well, modern C++ discourages the programmer from doing manual memory management. There's a very strong push to use vector and string instead of arrays and C strings, references instead of pointers, or, if you really need them, smart pointers instead of raw pointers, etc. Any book or article on modern C++ will tell you to let the compiler and language run-time handle memory management. It's not quite GC, but it's similar.

On the other hand, the default in Lisp is always to let the compiler handle memory, but Common Lisp in particular gives the programmer a lot of flexibility and control over types, memory management, and other optimizations. It's been fighting the "Lisp is slow" stereotype for a long time, so there's been a lot of work done to optimize it and give the programmer optimization options.

For your specific question about memory access patterns, Common Lisp does allow some control over that via the "dynamic-extent" declaration: (declare (dynamic-extent variable-name)). It tells the compiler (or interpreter) that a variable in an inner scope (of a loop, for example) can be allocated once and the space reused each iteration instead of allocating fresh memory each time. It's not full blown C style control of memory, but it's similar and can have a big impact in some situations. The book "Common Lisp Recipes" has a section on it, and so does the hyperspec: http://www.lispworks.com/documentation/HyperSpec/Body/d_dyna...

The recently published "Common Lisp Recipes" is a great book that covers a ton of topics in this area. I think a lot of people would be surprised just how much control and flexibility is available in Common Lisp.

I wouldn't say Common Lisp is faster than C++ in general, and certainly not by default, but with a bit of work it's possible to get pretty close. Importantly, the optimized code will still look and feel like more or less idiomatic Lisp.

Yup, you don't want to be doing manual memory management until you've done the profiling and found your hot-paths.

However, the set of problems I can tackle is going to be bounded by the escape-hatches that are available to me. Much like Rust has `unsafe {}`, being able to drop down to the bare metal is an important tool to be used at the appropriate time.

It's possible to avoid allocations by, e.g. preallocating buffers and other such tricks.

Allocations are only half the story, you also want to control where those allocations are located so that your cache access patterns pull in the right chunks of memory.

That's what arrays are for. You can also do structure packing using implementation-specific tricks. SBCL's SB-ALIEN package has a nice interface for doing this: http://www.sbcl.org/manual/#Foreign-Types

A really cool example of SB-ALIEN in action is jiyunomegami's native type extensions for the Vacietis C-to-CL transpiler: https://github.com/jiyunomegami/Vacietis/commits/master (commits 5504079d63eb2745f6b8ef7ec1cf9bb3151994eb onward)

Nice, yeah arrays + structure packing looks like it would do the trick.

I'm not really an expert on high performance Lisp, but my impression is that the compilers can optimize things pretty well and that you can have a fairly low level of control over things like allocation patterns.

Edit: looks like I misread what you were saying. Yeah, if you want to pack two things next to each other in memory, that might be tricky in the language defined in the ansi standard. Although I think some implementations give you control over this sort of thing.

For example, the standard itself gives you some control over code generation via compiler macros and individual implementations often give you much more:

https://www.pvk.ca/Blog/2014/03/15/sbcl-the-ultimate-assembl...

That depends on the implementation.

This is LispWorks 64bit from http://lispworks.com . It uses a generational GC, and each generation has several memory segments. You can tell LispWorks how much generations it should use, how large these segments should be and in which generation/segment to allocate.

    CL-USER 12 > (room t)
     > Generation 7: 33904936 (0x2055928)
           Cons               4774352 (0x48D9D0)
           Non-Pointer        3213752 (0x3109B8)
           Other              8048192 (0x7ACE40)
           Symbol             2881680 (0x2BF890)
           Function           14569120 (0xDE4EA0)
           Non-Pointer-Static 5528 (0x1598)
           Mixed-Static       411600 (0x647D0)
           Weak               712 (0x2C8)
     -- Segments:
           Cons               40C0038800 - 40C04C9000
           Non-Pointer        40D0000800 - 40D0314000
           Other              40E0038800 - 40E07E8000
           Symbol             40F0038800 - 40F02FB000
           Function           4100038800 - 4100E20000
           Non-Pointer-Static 40B0000800 - 40B000D000
           Mixed-Static       400004E800 - 40000C8000
           Weak               4110038800 - 4110039000
    ================================
     > Generation 6: 0 (0x0)
     > Generation 5: 0 (0x0)
     > Generation 4: 0 (0x0)
     > Generation 3: 206544 (0x326D0)
           Non-Pointer        69648 (0x11010)
           Other              5040 (0x13B0)
           Symbol             131856 (0x20310)
     -- Segments:
           Non-Pointer        4070000800 - 4071001000
           Other              4170018800 - 4171019000
           Symbol             4080018800 - 4080819000
    ================================
     > Generation 2: 8768024 (0x85CA18)
           Cons               1960288 (0x1DE960)
           Non-Pointer        2531584 (0x26A100)
           Other              2720024 (0x298118)
           Symbol             5088 (0x13E0)
           Function           700184 (0xAAF18)
           Non-Pointer-Static 850152 (0xCF8E8)
           Mixed-Static       64 (0x40)
           Weak               640 (0x280)
     -- Segments:
           Cons               41B0010800 - 41B1011000
           Non-Pointer        4180000800 - 4181001000
           Other              41C0010800 - 41C1011000
           Symbol             41D0010800 - 41D0811000
           Function           41E0010800 - 41E0811000
           Non-Pointer-Static 4040000800 - 4040136000
           Mixed-Static       4090010800 - 4090013000
           Weak               41F0010800 - 41F0051000
    ================================
     > Generation 1: 732480 (0xB2D40)
           Cons               160240 (0x271F0)
           Non-Pointer        170344 (0x29968)
           Other              398200 (0x61378)
           Function           3248 (0xCB0)
           Weak               448 (0x1C0)
     -- Segments:
           Cons               4200008800 - 4200301000
           Non-Pointer        4210000800 - 4210411000
           Other              4220008800 - 42203F1000
           Symbol             4230008800 - 423001B000
           Function           4240008800 - 424003B000
           Weak               4250008800 - 4250009000
    ================================
     > Generation 0: 1956832 (0x1DDBE0)
           Cons               630224 (0x99DD0)
           Non-Pointer        361232 (0x58310)
           Other              923816 (0xE18A8)
           Function           41560 (0xA258)
     -- Segments:
           Cons               4010000800 - 401040B000
           Non-Pointer        4030000800 - 403041B000
           Other              4020000800 - 402040B000
           Symbol             4150000800 - 4150101000
           Function           4060000800 - 4060101000
           Weak               4190000800 - 4190041000
    ================================

    Total allocated 45568816 (0x2B75330), total size 178085888 (0xA9D6000) 

    NIL

Reply on news.ycombinator.com