7 ms·

Common Lisp code optimisation

128 points by lokedhs 5y ago

podiki 5y ago
Should have a (2020) tag, though Common Lisp has a standard, these optimizations are done by specific implementations (compilers).
- lokedhs 5y ago
  True, although this particular simple optimisation is done by most Common Lisp compilers.
samsaga2 5y ago
The problem with that type of optimizations is that is too verbose to be useful. You have to type boring extra code.
- lokedhs 5y ago
  Modern compilers, and in particular SBCL is able to use type inference so that in many cases it is able to deduce these optimisations even without explicit type specifications. Or at least you can add the type specification in one place and then other functions will be able to take advantage of this. I should probably write a followup article that goes into more details on this.
  - dunefox 5y ago
    Please do!
  - spicybright 5y ago
    Also, I'd imagine you can get a lot of mileage with macros here, no?
  - User23 5y ago
    I've had no trouble getting SBCL to infer return types when calling other functions with the appropriate DECLARE or DECLAIM (as displayed with DISASSEMBLE and DESCRIBE), but so far I've not been able to verify that the compiler will infer the argument types in the same case. For example, if F takes two (signed-byte 8) and returns a (signed-byte 8) and I (defun g (a b) (f a b)) DESCRIBE will say that G takes two arguments of type T and returns a (signed-byte 8). Is this something you can please shed some light on? Without argument type inference it's hard to imagine how efficient code is going to be reliably generated without explicit declarations.
- remexre 5y ago
  Also, the "hot loop hypothesis" still tends to hold in CL; you only end up needing to annotate the crap out of the small number of functions that end up being most of your runtime. (It can sometimes be worth it to declare types for other functions, but that's as much for error checking as performance.) Being able to set the compiler flags on a per-function level is also really helpful for this, since these hot functions can be compiled for run-time speed rather than safety, debuggability, or compile-time speed (once one's sure they're correct, of course!).
  - guenthert 5y ago
    > It can sometimes be worth it to declare types for other functions, but that's as much for error checking as performance. And readability!
- romero-jk 5y ago
  That's a big problem in clojure too, were you have to write lots of javaish clojure to get decent performance.
- mpfundstein 5y ago
  i maintain two big projects. i only ever annotate code after i know i am really done with it. and also not every code. its a dynamic language after all. its quite nice though that I can do it when I want and omit when not
  - lispm 5y ago
    The big difference between SBCL (and related implementations like CMUCL) compared to other Common Lisp implementations is that SBCL uses type declarations and type inference for compile time checks -> thus it can be less dynamic.
- jlarocco 5y ago
  I don't really agree with that. It's hardly "too verbose to be useful" when a handful of type declarations can result in a significant runtime speed up. In practice only a relatively small amount of code will need type declarations and optimizations enabled, and type declarations double as safety checks when using "(declaim (optimize (speed 0) (safety 3)))" instead of "(declaim (optimize (speed 3) (safety 0)))", so it's a win for more than just performance reasons. It's not an optimization panacea, but it's low hanging fruit to get started.
- epolanski 5y ago
  That’s your definition of “too verbose”?
bluefox 5y ago
If you want to declare that the function takes a fixnum and returns a fixnum, you can use a function type declaration: (declaim (ftype (function (fixnum) (values fixnum &optional)) foo)) Of course, if you pass a fixnum and the result cannot actually be stored in a fixnum, that's no good. So you need to either handle that case or not make such a declaration.
- lispm 5y ago
  for a specific expression on can also specify the return type using THE: (the fixnum (+ a b))
  - twoodfin 5y ago
    That’s a hilarious but perfect piece of syntax. Do you know where it originated?
    - Jtsummers 5y ago
      Per: https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node106.html https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node106.html > Compatibility note: This construct is borrowed from the Interlisp DECL package; Interlisp, however, allows an implicit progn after the type specifier rather than just a single form. The MacLisp fixnum-identity and flonum-identity constructs can be expressed as (the fixnum x) and (the single-float x).
    - vindarel 5y ago
      agreed^^ there are macros and libraries to bring a nicer syntax (of course). Exple: https://github.com/lisp-maintainers/defstar https://github.com/lisp-maintainers/defstar (defun* (sum -> real) ((a real) (b real)) (+ a b))
    - nerdponx 5y ago
      There is DECLARE, PROCLAIM, and DECLAIM. I always interpreted the latter to be a portmanteau of the former two.
  - 5y ago

128 points by lokedhs 5y ago

Should have a (2020) tag, though Common Lisp has a standard, these optimizations are done by specific implementations (compilers).

lokedhs 5y ago
True, although this particular simple optimisation is done by most Common Lisp compilers.

samsaga2 5y ago

The problem with that type of optimizations is that is too verbose to be useful. You have to type boring extra code.

lokedhs 5y ago
Modern compilers, and in particular SBCL is able to use type inference so that in many cases it is able to deduce these optimisations even without explicit type specifications. Or at least you can add the type specification in one place and then other functions will be able to take advantage of this. I should probably write a followup article that goes into more details on this.
- dunefox 5y ago
  Please do!
- spicybright 5y ago
  Also, I'd imagine you can get a lot of mileage with macros here, no?
- User23 5y ago
  I've had no trouble getting SBCL to infer return types when calling other functions with the appropriate DECLARE or DECLAIM (as displayed with DISASSEMBLE and DESCRIBE), but so far I've not been able to verify that the compiler will infer the argument types in the same case. For example, if F takes two (signed-byte 8) and returns a (signed-byte 8) and I (defun g (a b) (f a b)) DESCRIBE will say that G takes two arguments of type T and returns a (signed-byte 8). Is this something you can please shed some light on? Without argument type inference it's hard to imagine how efficient code is going to be reliably generated without explicit declarations.
remexre 5y ago
Also, the "hot loop hypothesis" still tends to hold in CL; you only end up needing to annotate the crap out of the small number of functions that end up being most of your runtime. (It can sometimes be worth it to declare types for other functions, but that's as much for error checking as performance.) Being able to set the compiler flags on a per-function level is also really helpful for this, since these hot functions can be compiled for run-time speed rather than safety, debuggability, or compile-time speed (once one's sure they're correct, of course!).
- guenthert 5y ago
  > It can sometimes be worth it to declare types for other functions, but that's as much for error checking as performance. And readability!
romero-jk 5y ago
That's a big problem in clojure too, were you have to write lots of javaish clojure to get decent performance.
mpfundstein 5y ago
i maintain two big projects. i only ever annotate code after i know i am really done with it. and also not every code. its a dynamic language after all. its quite nice though that I can do it when I want and omit when not
- lispm 5y ago
  The big difference between SBCL (and related implementations like CMUCL) compared to other Common Lisp implementations is that SBCL uses type declarations and type inference for compile time checks -> thus it can be less dynamic.
jlarocco 5y ago
I don't really agree with that. It's hardly "too verbose to be useful" when a handful of type declarations can result in a significant runtime speed up. In practice only a relatively small amount of code will need type declarations and optimizations enabled, and type declarations double as safety checks when using "(declaim (optimize (speed 0) (safety 3)))" instead of "(declaim (optimize (speed 3) (safety 0)))", so it's a win for more than just performance reasons. It's not an optimization panacea, but it's low hanging fruit to get started.
epolanski 5y ago
That’s your definition of “too verbose”?

bluefox 5y ago

If you want to declare that the function takes a fixnum and returns a fixnum, you can use a function type declaration: (declaim (ftype (function (fixnum) (values fixnum &optional)) foo)) Of course, if you pass a fixnum and the result cannot actually be stored in a fixnum, that's no good. So you need to either handle that case or not make such a declaration.

lispm 5y ago
for a specific expression on can also specify the return type using THE: (the fixnum (+ a b))
- twoodfin 5y ago
  That’s a hilarious but perfect piece of syntax. Do you know where it originated?
  - Jtsummers 5y ago
    Per: https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node106.html https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node106.html > Compatibility note: This construct is borrowed from the Interlisp DECL package; Interlisp, however, allows an implicit progn after the type specifier rather than just a single form. The MacLisp fixnum-identity and flonum-identity constructs can be expressed as (the fixnum x) and (the single-float x).
  - vindarel 5y ago
    agreed^^ there are macros and libraries to bring a nicer syntax (of course). Exple: https://github.com/lisp-maintainers/defstar https://github.com/lisp-maintainers/defstar (defun* (sum -> real) ((a real) (b real)) (+ a b))
  - nerdponx 5y ago
    There is DECLARE, PROCLAIM, and DECLAIM. I always interpreted the latter to be a portmanteau of the former two.
- 5y ago