Spartns is a *SPARse TeNSor representation library* (if you don't know what
a tensor is, think of it as a matrix with any number of dimensions, not just
two).
Spartns is distributed under the LLGPL license.

Get the latest version on GitHub

Features:

- No external dependencies (no BLAS or any other C/Fortran library needed). Just plain Common Lisp;
- Represents mappings from one dimension onto another using any scheme you want (there are three built-in schemes: array, hash and compressed-vector, but you can roll your own and plug it);
- Flexible: works with any data type;
- Heavily optimized: traversing the tensor can be extremely fast (in one specific situation -- traversing the tensor -- it was 10 times faster than a naive implementation in C++);
- Fairly portable: works with SBCL, ABCL, OpenMCL, CMUCL, Clisp, ECL, GCL, XCL, Poplog, LispWorks, and
Allegro Common Lisp. But it looks like Spartns does
**not**work with Corman Common Lisp; - Spartns is never released without going through regression tests (if a platform breaks and can't be supported, it will be clear in the release announcement);
- ASDF installable (thanks Slobodan Blazeski!);
- Easy to use, with introductory documentation (not only on-line);
- Comes with description of the internals of the library.

(defspartn 2dmatrix :representation (spartns:hash spartns:cvector) :non-zero (3 4) :element-type long-float :sparse-element 0L0)The Spartn type "2dmatrix" is then defined as the type for sparse tensors that map indices onto long-floats using a hashtable of compressed vectors. When they are created, the hashtables start with :size 3, and the compressed vectors with :size 4. Now, create three matrices, X Y and Z, and multiply them:

(let ((X (make-2dmatrix)) (Y (make-2dmatrix)) (Z (make-2dmatrix))) (set-2dmatrix X 0 0 5L0) (set-2dmatrix Y 0 1 6L4) ;; set non-zeros in the rest of the matrices X and Y ;; and now multiply them: (w/fast-traversals ((2dmatrix X i j val-x) (2dmatrix Y j k val-y)) (set-2dmatrix Z i k (+ (get-2dmatrix Z i k) (* val-x val-y)))))

Download the Spartns Library on Github. From this site you can download the files t.cpp, timer.cpp and timer.h, which are the implementation of the benchmark using std::map. The file utils.lisp has a bunch of utilities (not all necessary for Spartns). You probably want to install using ASDF, though...

Silly micro-benchmarks:

SBCL GCL Poplog Clozure Clisp ABCL ECL XCL ---------------------------------------------------------------------------- ARRAY GET 0.16 0.38 7.68 0.01 3.83 2.88 4.12 3.1 ARRAY SET 0.16 0.07 2.68 0.77 8.53 4.00 4.6 3.2 CVECTOR GET 4.38 34.81 321.74 52.11 541.70 83.01 77.27 21.23 CVECTOR SET 4.84 36.13 335.92 52.31 541.78 83.18 66.67 21.6 TR-CVECTOR-GET 0.72 0.97 9.66 1.49 24.65 3.34 3.60 1.89 TR-CVECTOR-SET 0.73 0.97 9.91 1.19 7.16 3.09 6.14 1.9 HASH-GET 2.32 9.87 12.61 11.24 43.45 10.44 21.29 4.33 HASH-SET 6.93 9.15 15.78 12.1 39.88 11.2 24.21 4.67 TR-HASH-GET 6.9 20.48 17.91 15.2 49.68 9.19 22.8 4.9 TR-HASH-SET 0.4 20.3 17.68 11.73 48.27 11.51 21.68 5.2 ---------------------------------------------------------------------------- C++ STL GET 5.80 C++ STL SET 5.86

A graph with the running times (in seconds):

**THIS IS NOT A REAL BENCHMARK!** It just helps a bit to understand how Spartns can be fast, and
also how faster it is to use traversals instead of using get/set functions. Even real benchmarks
can have serious usefulness limitations, so this one is not meant to back any statements about
the speed of languages, algorithms or anything else. Speed really depends a lot
on your Lisp implementation and the method used (and obviously, on your workload -- do not
underestimate the impact of memory/cache/garbage collection issues!)

- This is on an Athlon(tm) 64 X2 Dual Core 3600+ (1900MHz) with 2Gb RAM; g++ 4.2; SBCL 1.0.30.40; GCL 2.7.0 (CVS, Jan 8 2008); CLisp 2.48; Poplog 15.6101; Clozure Common Lisp 1.6-dev-r13705M-trunk; ABCL 0.17.0-dev (2009/10/29); ECL 9.10.2; XCL 0.0.0.290; Debian GNU/Linux (sid);
- The "plain array" numbers are just for reference. A plain array would not work for very large sparse tensors;
- The g++ implementation of std::map uses red-black trees (with O(log(n)) time to access and modify -- comparable to the O(log(n)) time for CVECTOR-GET/SET). For HASH-* and CEVCTOR-TRAVERSE, the access time is always O(1);
- CMUCL was not tested because it doesn't run on Linux/AMD64

(Thanks Aaron Sloman for the help with Poplog)

My email is j_p (put a @ sign here) aleph0 (here goes a dot) info