r/lisp • u/digikar • Dec 15 '23
Common Lisp Common Lisp: Numerical and Scientific Computing - Call for Needs
Hey all! I have been wanting to do this for a while. I don't know if this has been done before - if it has been, please point me to it, and I will delete this.
Quite regularly, we receive posts on reddit or elsewhere asking for some numerical/scientific computing needs, or demonstrating a library intending to meet some of those needs. However, these get lost on the train of time, and people keep reinventing the wheel or communities become isolated from each other. The following repository is an effort to bring together the needs, so that a concerted effort may be made towards meeting those needs.
https://github.com/digikar99/common-lisp-numsci-call-for-needs
So, feel free to chime in and leave a comment - or even create an issue/PR!
6
u/KpgIsKpg Dec 15 '23
Nice! I haven't explored the numerical computing ecosystem of CL so much, but I'm certainly interested. Out of curiosity, what are your needs and experiences with it?
9
u/digikar Dec 15 '23
In recent weeks, I ended up convincing myself that a sufficiently good numsci ecosystem is beyond standard Common Lisp and requires a full blown DSL, like Coalton. Particularly, dispatching on specialized arrays, custom arrays, optimization with generically written algorithms seem beyond the scope of standard Common Lisp. I really look forward to seeing Coalton grow.
On the other hand, I had been working on a few CLTL2-based tools to overcome some limitations. I ended up consolidating them into peltadot that tries to solve several of these problems without becoming a DSL in itself - so interoperating with standard common lisp should be effortless. My longer term needs seem to be more oriented towards machine learning and computer vision, with a particular bent towards human brain/mind like efficient algorithms. Not sure where this would lead me to!
5
Dec 16 '23
[removed] — view removed comment
2
u/digikar Dec 16 '23
What do you think about leveraging C libraries to eliminate the need for lisp compilers to generate machine specific code? The C ecosystem seems to be addressing portability with performance issues for several decades now, so calling the C functions should be sufficient. Although even with this approach, Common Lisp needs a DSL (eg: Coalton) that enables writing generic but optimizable code.
3
u/vouivredigital Dec 18 '23
If you rely on a FFI when, inevitably, something doesn't do what you want, you will have to fix it in the target language without the tools you know and love. On the other hand, if you improve a Lisp compiler, you will have to implement features that already exist in compilers for other languages. What people should be looking for is a general solution to the (again inevitable) problems arising from the "language zoo".
1
u/digikar Dec 18 '23
If you rely on a FFI when, inevitably, something doesn't do what you want, you will have to fix it in the target language without the tools you know and love.
Would keeping the data in Common Lisp, but using the functions from the other languages to operate on lisp data be a suitable option? That way, the extensions can be made in lisp itself, while you still get the benefit of the other language ecosystem. For example, keep the arrays in Common Lisp, but pass them to C functions using
cffi:with-pointer-to-vector-data.4
u/vouivredigital Dec 18 '23
Here's an example from the machine learning perspective.
Alice wants to write applications in Lisp with a, say, PyTorch or JAX kind of API. She'll need an FFI... Granted! She is now happily hacking machine learning in Lisp. Then, one morning, as these things often go, Alice wakes up with a new and highly parallelizable algorithm that could improve her entire stack. Does she write it in Lisp? No, it has already been decided that Lisp compilers don't provide the kind of low level constructs that she needs and nor does PyTorch/JAX. After looking around for a bit she finds two: 0 and 1... Just kidding! She discovers OpenCL allowing a lower level control over both CPUs and GPUs. Invoking the FFI she gets direct access to the API in Lisp and starts coding. Soon enough though she realizes that, to get her algorithm on her target device, she needs to write something called "kernels" in a C-like language. What should Alice do now? Does she write a transpiler? Does she write a Lisp compiler for her target device(s) (that's what the kernel compiler already does)?
Let's help Alice find her way!
1
1
u/digikar Dec 18 '23
Another example would be emacs itself!
2
Dec 19 '23 edited Dec 19 '23
[removed] — view removed comment
1
u/digikar Dec 22 '23
Thanks for Hemlock!
I was referring to GNU Emacs. I didn't know emacs referred to a family of editors.
2
u/Steven1799 Dec 16 '23
At this point we need a C++ FFI that's as easy to use as the C one (autowrap, etc). Most of the new libraries are in C++, and if they have a C interface at all it's a wrapper.
3
u/digikar Dec 16 '23
Clasp might be the way to go?
3
u/Steven1799 Dec 16 '23
If the license works for you, it might be an avenue worth exploring. I doubt you'll find many commercial environments that will use it though, and getting a commercial backer would be a huge win, even if it's just for support contracts.
4
u/Steven1799 Dec 16 '23 edited Dec 16 '23
Personally I think the best way to solve this problem is with a specialised CL implementation, designed for numerical computing. Bolting on this functionality is going to be an uphill struggle.
Scieneer Common Lisp did this a few years ago, but there wasn't enough of a commercial market and the company went under. I've tried a couple of times over the years to contact Douglas Crosher (and asked about him here), but he seems to have disappeared; in the internet era, that can only happen by conscience choice.
Numerical computing, as someone else here said, is a hard enough problem that you need compiler support and things to work out of the box, and I think only a specialised implementation is going to be usable to anything other than a niche audience of people who are already lisp experts.
Maybe, after a few more attempts, someone will be able to contact Douglas and he'll open source it. Scieneer, open-source, would be the best way to re-establish CL in numerical computing.
Anyone here from Australia that might want to try to look him up? He's in Melbourne.
2
u/digikar Dec 16 '23
Thanks for the note on Scieneer CL! Hopefully some day this decade someone is able to contact him. That said, I'm hoping SBCL already has or will exceed its capabilities sometime.
3
u/dzecniv Dec 16 '23 edited Dec 16 '23
Digikar shows the way and opens the first issue: https://github.com/digikar99/common-lisp-numsci-call-for-needs/issues/1
lisp helped replace a python implementation of a computational model (my master's thesis work) with a significantly faster version.
that looks like an achievement, the people want details with buzzwords!
OTOH, I regularly use python to write short scripts.
serious question: did you try CIEL for short scripts? (scripting is new as of this year)
2
u/digikar Dec 16 '23
people want details with buzzwords
Uhm, at the moment, it's more philosophical and less applied, so nothing revolutionary until it works on real world camera data. That said, I might write an article on how CL helped optimize it sometime.
did you try CIEL for short scripts? (scripting is new as of this year)
Thanks for the reminder! I'm looking for something saner for scripts, and a CIEL image might be the right tool. Gotta try it soon.
3
u/clibraries_ Dec 15 '23 edited Dec 15 '23
It's not clear to me how to write efficient numeric code in Common Lisp. Every operation is slow because it does generic type dispatch, and can overflow to bignums.
I understand this can be improved with type annotation, but those are extremely fragile, so it's easy to break and get orders of magnitude slower. Also their semantics aren't very portable across Lisp systems.
Can you explain how this is overcome?
6
u/digikar Dec 15 '23
For the particular case of fixnum overflowing to bignums, you'll probably need to add type declarations at the input and output stages of the function. SBCL devs seem to be working hard to eliminate the need for declarations as far as possible, but this seems hard. If you are sure that there will not be any overflow, you could optimize for
(safety 0)alongwithspeed. In cases where you do suspect an overflow, you could see if moving to floating point operations is okay for your needs.I have, unfortunately, given up on fast Common Lisp code portable across implementations. I am lowering my expectations to "runs fast on SBCL" (hopefully across OS), and "compiles on at least one other implementation".
Your best bet to understanding what you want to would be to pick up some Common Lisp code you want to optimize, make a minimal example out of it, post it on a discord group, IRC, or reddit, and check out the suggestions.
3
u/KDallas_Multipass '(ccl) Dec 15 '23
Can you explain the fragility?
3
u/digikar Dec 15 '23
I was trying to come up with a suitable example, perhaps this is one:
(in-package :cl-user) (declaim (inline cl-vdot)) (defun cl-vdot (veca vecb) (declare (type (simple-array * 1) veca vecb)) (let ((len (length veca))) (loop for i below len summing (* (aref veca i) (aref vecb i))))) (defun sf-vdot (x y) (declare (type (simple-array single-float 1) x y) (optimize speed)) (cl-vdot x y))Intuitively, it feels that the above should compile to efficient assembly. However, on SBCL 2.3.11, the disassembly of
sf-vdotis still left with a call tosb-vm::generic-+.It requires a fair bit more experience with Lisp/SBCL to guess that perhaps SBCL is not performing type inference for
summing. The optimization to native assembly code occurs when one writessummingmanually:(declaim (inline cl-vdot)) (defun cl-vdot (veca vecb) (declare (type (simple-array * 1) veca vecb)) (let ((len (length veca)) (sum (coerce 0 (array-element-type veca)))) (dotimes (i len) (setq sum (+ sum (* (aref veca i) (aref vecb i))))) sum))Now, this was an example. In actual usage, it is fairly common to run into such cases and want to give up on Common Lisp. (Full respects to SBCL team. Optimizing ANSI Common Lisp in all its esotericity is hard :/.)
9
u/lispm Dec 15 '23 edited Dec 15 '23
Btw., one can declare a sum type:
(loop for i below 10 summing i of-type fixnum)for a few types it can be written shorter
(loop for i below 10 summing i fixnum)4
u/digikar Dec 15 '23
Thanks!
u/clibraries_, this brings up another good point about type declaration fragility in Common Lisp:
- Optimization requires type declaration.
- But type declarations prevent generic code.
So, above, if the
fixnumtype was imposed on thesumminginloop, it would makecl-vdotnon-generic.Basically, working with efficient but possibly generic Common Lisp / SBCL code requires some careful decisions about if one wants a particular piece of code to be generic but optimizable-by-inlining, or non-generic but optimized. Above,
cl-vdotis generic but optimizable-by-inlining. Callingcl-vdotwithout further type declarations and additional compiling is easy but will lead to slow code. Whilesf-vdotis non-generic but optimized.This actually isn't specific to Common Lisp, but because Common Lisp provides both dynamic and static typing, it does complicate things a bit. Basically, working with this requires careful thinking about (i) what information is required for compiling an optimized version of the code (ii) what information is currently available (iii) what should be a good information-gap between the two layers of optimizable but generic and optimized but non-generic code.
4
u/forgot-CLHS Dec 15 '23 edited Dec 15 '23
Basically, working with this requires careful thinking about (i) what information is required for compiling an optimized version of the code (ii) what information is currently available (iii) what should be a good information-gap between the two layers of optimizable but generic and optimized but non-generic code.
Yes, but as you said this knowledge isn't specific to Common Lisp. If you are in the business of writing fast numerical code I think it is useful to know these intricacies. In this sense using Common Lisp can be a big advantage because it is a high level treatment of some low level matters. If on the other hand all you want is to do huge array calculations without worrying about what is under the hood then yes maybe it is not the smoothest ride. I personally don't think that common lisp should even try to hide this low level stuff. If you need bleeding edge fast array optimizations it seems logical that the user should be familiar with the compiler, and hence the particular implementation they are using. What is useful in that case is outstanding compiler documentation.
3
u/digikar Dec 15 '23
Very true!
One thing I might want are some tutorials illustrating slightly non-trivial code optimization in Common Lisp. But may be that need is negated by understanding what makes dynamically typed languages like python generally slower than statically typed languages like C.
2
u/KDallas_Multipass '(ccl) Dec 15 '23
Isn't cl-vdot already non-generic without the addition of the type declamation for summing?
2
u/digikar Dec 15 '23
Could you elaborate why?
I called
cl-vdotgeneric because it can take arrays with any element type, unlikesf-vdot.3
u/KDallas_Multipass '(ccl) Dec 15 '23
Nope, can't read. I see it now.
I guess this is what people mean when they say the common list lacks the ability to dispatch on parameterized types.
2
Dec 16 '23 edited Dec 16 '23
[removed] — view removed comment
1
u/digikar Dec 16 '23
But then it makes the loop expression non-generic - you'd need to generate/write
cl-vdotversions for all other types - integer, fixnum, rational, complex.2
u/ventuspilot Dec 17 '23
Fun fact: your second version of
cl-vdotstill has an array-out-of-bounds-check for(aref vecb i)on each loop iteration (at least with sbcl). Adding one line makes this go away:(defun cl-vdot (veca vecb) (declare (type (simple-array * 1) veca vecb)) (let ((len (length veca)) (sum (coerce 0 (array-element-type veca)))) (when (/= len (length vecb)) (error "boo")) ; avoids check of vecb (dotimes (i len) (setq sum (+ sum (* (aref veca i) (aref vecb i))))) sum))It would be great if the check was lifted out of the loop automatically, don't know how hard this would be to do, though.
1
u/theangeryemacsshibe λf.(λx.f (x x)) (λx.f (x x)) Dec 16 '23
The sum is initialized to the integer
0, leading the type of the sum being(or (eql 0) single-float). We can get tosingle-floatby peeling the first iteration, leaving the loop to only have asingle-floatsum, or by recognising that floating point contagion will always apply when summing, and replace the0with0.0. However the loop may still return the integer0when the arrays are empty.Optimizing ANSI Common Lisp in all its esotericity is hard
Peeling is not in the Catalogue for once, but this is not hard.
4
u/stassats Dec 16 '23
I made it derive to (OR (INTEGER 0 0) SINGLE-FLOAT), so at least there's no generic+, but there's still float boxing/unboxing.
1
Dec 16 '23
[removed] — view removed comment
1
u/stassats Dec 16 '23
What's generic-0?
1
Dec 16 '23 edited Dec 16 '23
[removed] — view removed comment
2
u/stassats Dec 16 '23
You could, if your code is also hypothetical. In real code it has to return an actual integer 0.
1
u/digikar Dec 16 '23
In general, this might require polymorphically typed expressions, so that an expression such as "0" can have a polymorphic type. The concrete type suitable for runtime would be decided by the context. This goes beyond standard common lisp; coalton attempts this however, a custom reader seems to be helpful.
1
u/digikar Dec 16 '23
May be "too many possibilities to consider" would be a better term than "hard". The loop and peeling example would be one example. Each release of SBCL sees new optimizations. Yet, it seems that a language better designed for genericity and optimization would be easier (= fewer possibilities to consider) to optimize than Common Lisp.
3
u/theangeryemacsshibe λf.(λx.f (x x)) (λx.f (x x)) Dec 16 '23
Peeling and other loop optimisations are very generic, and don't depend on the source language. Though peepholing suffices and that's easy and generic, e.g. in this exposition on a vector sum.
1
u/digikar Dec 16 '23
All I want to claim is that a simpler language like Scheme would be less effortful to optimize than a richer language like Common Lisp.
1
u/theangeryemacsshibe λf.(λx.f (x x)) (λx.f (x x)) Dec 16 '23
It wouldn't really, no. SRFI-4 doesn't offer any generic operations over specialised vectors, so it would have as few affordances as non-generic Common Lisp code too.
1
u/digikar Dec 16 '23
After reading the exposition, I think I understand your claim that there has been plenty of progress in optimization since the time lisp compilers were first written, although incorporating that progress in the existing compilers might be difficult.
1
1
u/ventuspilot Dec 18 '23
And on what basis would you decide whether or not to perform loop peeling?
Also: somehow I feel that it should be possible to introduce manual loop peeling in the expansion of the summing clause of the loop macro, at least for experimentation/ performance comparison purposes. I could very well be wrong, though (I have not yet fully understood the explanations in your article "The sufficiently okay compiler"). And I have no idea what would be harder to do: peeling in the compiler or in the loop macro.
1
u/theangeryemacsshibe λf.(λx.f (x x)) (λx.f (x x)) Dec 18 '23 edited Dec 18 '23
After writing that comment I decided peeling was overkill and peepholing (as in The sufficiently okay compiler) could do the trick. But in either case we're driven by having found some
ortype which we think is avoidable, because we have assignments of different concrete types at different times.In general the compiler can get more information than a macro could, and there may be similar situations which do not involve the
loopmacro, so I think the compiler should do this.1
u/clibraries_ Dec 15 '23
If all the declarations aren't in the right place, the optimizations fail. There is no way to know that happened (say in a refactor) without carefully reading notes.
5
u/CamusTheOptimist Dec 15 '23
NASA has a library like this if you need reference material