9 ms·
Modern C++ and Lisp Programming Style
- vvanders 10y ago> 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).
- fiddlerwoaroof 10y agoIt's possible to avoid allocations by, e.g. preallocating buffers and other such tricks.
- vvanders 10y agoAllocations 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.
- fiddlerwoaroof 10y agoI'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.
- fiddlerwoaroof 10y agoFor 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-assembly-code-breadboard/ https://www.pvk.ca/Blog/2014/03/15/sbcl-the-ultimate-assembl...
- sedachv 10y agoThat'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 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 https://github.com/jiyunomegami/Vacietis/commits/master (commits 5504079d63eb2745f6b8ef7ec1cf9bb3151994eb onward)
- vvanders 10y agoNice, yeah arrays + structure packing looks like it would do the trick.
- lispm 10y agoThat depends on the implementation. This is LispWorks 64bit from http://lispworks.com 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
- pjmlp 10y agoLisp 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 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 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.
- nickpsecurity 10y ago"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-primetrader.html http://www.lispworks.com/success-stories/netfonds-primetrade... http://www.lispworks.com/success-stories/ral-siglab.html 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.lhtml http://franz.com/success/customer_apps/finance/ravenpack.lht...
- pjmlp 10y agoHere is a another one, a Portuguese company specialized in Lisp based solutions, for timetables and fleet management. http://www.siscog.eu/ http://www.siscog.eu/
- username223 10y ago
- jlarocco 10y agoWell, 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_dynami.htm 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.
- vvanders 10y agoYup, 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.
- deleted 10y ago[deleted]
- turnipping 10y agoWhat is Stepanov's beef with AI's week foundation?
- leshow 10y agoI don't see the relation to Lisp, if anything that quote about noticing the semigroup property of parallel fold algorithms speaks to Haskell or ML more than anything else.
- sedachv 10y agoA lot of early research into parallel algorithms and exploiting associativity for parallelism started at Thinking Machines, a Lisp supercomputer company. Hillis and Steele's 1986 paper in CACM is still one of the best introductions to the subject: http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-data-parallel-algorithms.pdf http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-d...
- lispm 10y agoThere was quite a lot research into parallel, concurrent and distributed Lisps beginning in the 80s. Thinking Machines with its SIMD computer was just one approach. At some point in time there was a lot of money available for that stuff, including custom hardware. In the US the DoD paid and you can bet that some military/intelligence applications were based on exotic multiprocessor machines running Lisp. http://www.softwarepreservation.org/projects/LISP/parallel http://www.softwarepreservation.org/projects/LISP/parallel Often parallel computers had also a Lisp implementation. Much more than listed above. Parallel Computation and Computers for Artificial Intelligence http://link.springer.com/book/10.1007/978-1-4613-1989-4 http://link.springer.com/book/10.1007/978-1-4613-1989-4 Parallel Lisp: Languages and Systems http://link.springer.com/book/10.1007/BFb0024148 http://link.springer.com/book/10.1007/BFb0024148 Parallel Symbolic Computing: Languages, Systems, and Applications http://link.springer.com/book/10.1007/BFb0018643/page/1 http://link.springer.com/book/10.1007/BFb0018643/page/1
- cjhanks 10y agoC++ programmers using a lot templates have a lot in common with Haskell programmers. Often I will write static methods like.. template<typename Scalar, typename Functor> auto DoSomething(Scalar value, std::size_t k) -> decltype(Functor(Scalar(0)) { ... Functor(value / Scalar(k)); ... } Even though it will probably only be used once. Simply because I don't know what types I am going to need yet... but I know it might need a few operators `+`, `-`, `*`, `/`. Once I figure that out, the code is ready to go and is as fast as anything hand written. If somebody could ever write a great 'Haskell for C++ MetaProgrammers' book describing how you are supposed to understand binary layout, IO, and wtf those hundreds of operators mean... you would probably have a bunch of programmers saying "Oh, I guess I know Haskell". It's also no surprise that a bunch of the STL algorithms structures were easily made parallel in C++17. A lot of developers using the STL correctly could basically change a few lines of code and switch their program from sequential to parallel.
- Animats 10y ago"Modern C++ has shifted focus from an emphasis on type (objects) which accommodate algorithm to an emphasis on algorithms parametrized over types." That may be a bug, not a feature. The Boost crowd won the battle, making extremely complex templates an essential part of the language. But they may have lost the war, as C++ loses market share. LISP backed into typing, and it shows. Both typed variables and objects are painful in LISP. By the time LISP got both, the era of LISP was over. LISP is really dead now; there hasn't been a release of GNU Common LISP ("clisp") in 7 years.
- sedachv 10y agoPlease quit trolling. Allegro CL 10.0 released on 2015-10-05 ABCL 1.4.0 released on 2016-10-08 CCL 1.11 released on 2015-11-06 ECL 16.1.3 released on 2016-12-19 Lispworks 7.0 released on 2015-05-05 MKCL 1.1.10 released on 2017-01-18 SBCL 1.3.15 released 2017-02-28
- e40 10y agoAnd the Allegro CL 10.1 release is imminent.
- papaver 10y agoexcept clojure is one of the most powerful languages around atm? which is a lisp??
- hughw 10y agoI recently came back to write a small experiment in C++. I programmed it professionally for a decade, ending in 2002, and was pretty good at it. After the last 16 years working in Java, Scala, Clojure, and Javascript, I have two observations on C++ 11: a) Grateful for the extensive access to algorithms, lambdas, type inference; b) Astounded at the complexity of template meta programming. I imagine I'll get better at it with practice. But I'm operating at about 15% of the time efficiency of, say, Scala.
- AstralStorm 10y ago
- nkozyra 10y ago“Yes. STL is not object-oriented. I think that object orientedness is almost as much of a hoax as Artificial Intelligence.“ Is hoax a placeholder for "hype" or am I missing something?
- sqeaky 10y agoThat confused me too, both clearly work unless there is some definition of work that excludes things which have earned many people many billions of dollars. Hoaxes don't create sustainable businesses.
- zwieback 10y agoThe quote is probably 20 years old now, at the time people were pretty disillusioned about AI and OO was a craze. Stepanov had other ideas. Here's more context: http://www.stlport.org/resources/StepanovUSA.html http://www.stlport.org/resources/StepanovUSA.html
- _delirium 10y agoIf you're thinking of the recent boom in machine learning specifically, there are plenty of people in ML, even people making lots of money from it, who think the concept of "artificial intelligence" is a recurring hoax, or at best an overselling aimed at people who've read more sci-fi than science. Of course plenty of people think otherwise, too, but it's not a rare view within the field.
- rurban 10y agoI cannot say much about the C++ code, but the lisp examples are very bad style. One does not write like this. One writes ordinary generic functions, and then optimized typed methods in lisp like this: (defgeneric xplusone (x) (1+ x)) (defmethod xplusone ((x integer)) (1+ x)) (defmethod xplusone ((x double-float)) (1+ x)) The sbcl compiler (called python) even creates the typed methods by itself, so mostly the defgeneric line is enough. The type hints for args and return types are purely optional, as the compiler figures it out by itself. He is right that algorithms, methods, trump data structures, objects. You always write methods with specializations on objects. Not the other way round, classes with specific methods.
- xrange 10y ago> (defgeneric xplusone (x) (1+ x)) > The sbcl compiler (called python) even creates the typed methods by itself, so mostly the defgeneric line is enough. Is this some new SBCL extension you are talking about? That `defgeneric` line is an error in CLOS.
- nuntius 10y agoVery much a part of the standard. i.e. not specific to SBCL. Think of defgeneric as the function signature and defmethod as the template specialization. Not sure why you say this is an error in CLOS. Looks fine to me. That said, most implementations try to auto-infer the generic function metaobject when you use defmethod without defgeneric. SBCL raises a warning. Good reads on the topic: http://www.gigamonkeys.com/book/object-reorientation-generic-functions.html http://www.gigamonkeys.com/book/object-reorientation-generic... https://mitpress.mit.edu/books/art-metaobject-protocol https://mitpress.mit.edu/books/art-metaobject-protocol http://mop.lisp.se/ http://mop.lisp.se/
- juki 10y agoThe DEFGENERIC line is wrong. It can't have a body like that. It should be something like (defgeneric xplusone (x) (:method (x) (+ 1 x))) Also, generic functions are slower than regular functions (due to dynamic dispatch), so using them for type optimization would be rather counterproductive.
- psyc 10y agoUnless I'm missing something, generic algorithms that work across types, and algos that work on type internals are just two separate things. And the latter probably still wants to be encapsulated in the type.
- lorenzhs 10y agoThe addone function in C++14 would look something like this: auto addone = [](auto x) { return x+1; }; That monstrosity at the top of the article is needlessly complex because C++11 didn't support generic lamdbas.
- photon-torpedo 10y agoFor terseness, it's probably hard to beat Julia: addone1(x) = x+1 Completely generic with type inference, and compiles to optimal machine code. But it also suffers from the "latent type errors deferred to the user" that the article discusses. Calling it with a type that does not support adding 1 will raise an error for a non-existing "+" method: addone1("0") ERROR: MethodError: no method matching +(::String, ::Int64) This is pretty understandable in this case, but we may prefer annotating the addone function so that it can only be called with types that support adding 1. Using the (very conservative) notion that only numbers can have 1 added to them, we could use Julia's type hierarchy to restrict the types for which addone may be called: addone2(x::T) where T<:Number = x+1 Calling it with an incompatible type now properly points to the outer level: addone2("0") ERROR: MethodError: no method matching addone2(::String) But this type of dispatch restrictions rely on a type hierarchy, causing similar problems as class hierarchies in OO languages. For example, the user might have defined their own type that supports addition but not multiplication. Using addone on this type makes sense, but the type shouldn't be a subtype of Number. Such more flexible dispatch scenarios can be achieved with traits. Although Julia currently doesn't have direct language support for traits, they can be implemented inside the language, with macros for syntactic sugar. With traits, the previous example becomes: using SimpleTraits @traitdef CanAddOne{T} @traitimpl CanAddOne{T} <- issubtype(T,Number) @traitfn addone3{T; CanAddOne{T}}(x::T) = x+1 Still relatively straight-forward to write and read, and the trait-restricted addone has the same performance as the original one. For incompatible types, the error message still points to the outer level: addone3("0") ERROR: MethodError: no method matching addone3(::Type{SimpleTraits.Not{CanAddOne{String}}}, ::String) Importantly, the user can extend the CanAddOne trait (with additional @traitimpl lines) to cover their own type, without being forced to make it a subtype of Number.
- 10y ago
- vkazanov 10y agoCan't say Common Lisp is intuitive but in comparison with C++ it looks... Cleaner.
- cassowary 10y agoAs I was reading some of the illustrations, I began to wonder why anyone would prefer to use Lisp instead of Haskell. Can anyone mention a few advantages? Mostly, I find Haskell attractive because of the fantastic type system which allows me to write code that will fail when I'm writing or changing code. But I worry that I'm overlooking something because I can't understand why some people prefer Lisp.
- sodawater 10y agoExploratory Programming. When solving a problem, I don't always know what adt would work the best apriori. So being forced to tie myself down with "this is an X" is restrictive.
- keymone 10y agoEver since i learned lisp i feel very annoyed by languages having so much syntax. Just yesterday i was looking at tiny piece of Haskell code and it gave me headaches. Once you realize how much more productive you can be without cognitive load of juggling dozens of syntactic constructs in your head - it's hard to go back. and then you have benefits of homoiconicity on top of that.
- ue_ 10y agoI personally find macros and metaprogramminv nicer and more powerful than Template Haskell. I like the regularity of all the syntax too.