Spartns

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.

Latest version: 1.4.3 - 09 Oct 2009   changelog

Features:

One simple example: two dimensional matrix multiplication. First, define a type for 2-dimensional matrices:
(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)))))

The file spartns.tar.gz contains the Spartns library. The files t.cpp, timer.cpp and timer.h 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:

NOTE: THE C++ VERSION IS A NAIVE IMPLEMENTATION! I'm comparing what I'd quickly and easily do in C++ to what I'd quickly and easily do in Common Lisp with Spartns. This is NOT the best C++ code that could be used.

		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!)

The benchmarks are in the file benchmark.lisp (you should check the file so you can understand the table above).

(Thanks Aaron Sloman for the help with Poplog)

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