sycamore

SYCAMORE
========

Fast, purely functional data structures in Common Lisp.

API Documentation: http://ndantam.github.io/sycamore

Comprehensive Set Benchmarks: https://ndantam.github.io/sycamore/bench.html

Features
========
* Fast, purely functional Hash Array Mapped Tries (HAMT) [1,2].
  - https://en.wikipedia.org/wiki/Hash_array_mapped_trie
  - One simple-vector per layer (bitmap+children) reduces indirection.
  - SBCL VOPs (when available) enable single machine instructions for
    the POPCNT and CTZ operations commonly performed by HAMTs.
  - Generally higher-performance than WB-trees.
  - Requires hashing and test functions (defaults are CL standard
    SXHASH and EQL), but does not need the total ordering function
    required by trees.
* Fast, purely functional weight-balanced binary trees (WB-trees)
  [3,4,5].
  - http://en.wikipedia.org/wiki/Weight-balanced_tree
  - Leaf nodes are simple-vectors, greatly reducing tree height.
* Interfaces for tree Sets and Maps (dictionaries).
* Ropes [6]
  - http://en.wikipedia.org/wiki/Rope_(data_structure)
* Purely functional pairing heaps
  - http://en.wikipedia.org/wiki/Pairing_heap
* Purely functional amortized queue

Installation
============

* Sycamore uses ASDF (https://common-lisp.net/project/asdf/)
* See `INSTALL` file for details

Examples
========

See also `./example.lisp`

Hash Sets
---------

Create a set with default EQL test:

    CL-USER> (sycamore:make-hash-set)

    #<SYCAMORE:HASH-SET {}>

Create a set with default EQL test and initial elements from a list:

    CL-USER> (sycamore:list-hash-set '(1 2 -10 40))

    #<SYCAMORE:HASH-SET {40 1 -10 2}>

Create a set with EQUALP test:

    CL-USER> (sycamore:list-hash-set '(1 1.0 2.0 2) :test #'equalp)

    #<SYCAMORE:HASH-SET {1 2.0}>

Insertion:

    CL-USER> (sycamore:hash-set-insert (sycamore:list-hash-set '(1 2))
                                       0)
    #<SYCAMORE:HASH-SET {1 2 0}>

Lookup:

    CL-USER> (sycamore:hash-set-find (sycamore:list-hash-set '(0 1 2))

    0
    T

Removal:

    CL-USER> (sycamore:hash-set-remove (sycamore:list-hash-set '(1 2 0))
                                       0)

    #<SYCAMORE:HASH-SET {1 2}>

Union:

    CL-USER> (sycamore:hash-set-union (sycamore:list-hash-set '(1 2 0))
                                      (sycamore:list-hash-set '(1 0 3)))


    #<SYCAMORE:HASH-SET {3 1 2 0}>

Intersection:

    CL-USER> (sycamore:hash-set-intersection (sycamore:list-hash-set '(1 2 0))
                                             (sycamore:list-hash-set '(1 0 3)))

    #<SYCAMORE:HASH-SET {1 0}>

Difference:

    CL-USER> (sycamore:hash-set-difference (sycamore:list-hash-set '(1 2 0))
                                           (sycamore:list-hash-set '(1 0 3)))

    #<SYCAMORE:HASH-SET {2}>

Map set:

    CL-USER> (sycamore:map-hash-set 'list #'1+
                                    (sycamore:list-hash-set '(1 2 0)))

    (2 3 1)

Fold set:

    CL-USER> (sycamore:fold-hash-set (lambda (list item) (cons item list))
                                     nil
                                     (sycamore:list-hash-set '(1 2 0)))

    (1 2 0)

Tree Sets
---------

Define an ordering function:

    CL-USER> (defun compare (a b)
               (cond ((< a b) -1)
                     ((> a b) 1)
                     (t 0)))

    COMPARE

Create a set for integers:

    CL-USER> (sycamore:tree-set #'compare 1 2 -10 40)

    #<TREE-SET {-10 1 2 40}>

Insertion:

    CL-USER> (sycamore:tree-set-insert (sycamore:tree-set #'compare 1 2)
                                       0)
    #<TREE-SET {0 1 2}>

Lookup:

    CL-USER> (sycamore:tree-set-find (sycamore:tree-set #'compare 1 2 0)
                                     0)
    0
    T

Removal:

    CL-USER> (sycamore:tree-set-remove (sycamore:tree-set #'compare 1 2 0)
                                       0)
    #<TREE-SET {1 2}>

Union operation:

    CL-USER> (sycamore:tree-set-union (sycamore:tree-set #'compare 1 2)
                                      (sycamore:tree-set #'compare 1 0 3))

    #<TREE-SET {0 1 2 3}>

Intersection operation:

    CL-USER> (sycamore:tree-set-intersection (sycamore:tree-set #'compare 1 2)
                                             (sycamore:tree-set #'compare 1 0 3))

    #<TREE-SET {1}>

Difference operation:

    CL-USER> (sycamore:tree-set-difference (sycamore:tree-set #'compare 1 2)
                                           (sycamore:tree-set #'compare 1 0 3))

    #<TREE-SET {2}>

Map set:

    CL-USER> (sycamore:map-tree-set 'list #'1+
                                    (sycamore:tree-set #'compare 1 0 10 2))

    (1 2 3 11)

Fold set:

    CL-USER> (sycamore:fold-tree-set (lambda (list item) (cons item list))
                                     nil
                                     (sycamore:tree-set #'compare 1 0 10 2))

    (10 2 1 0)

Ropes
-----

Create a Rope:

    CL-USER> (sycamore:rope "Hello" #\Space 'World!)

    #<ROPE "Hello WORLD!">

Also works on lists:

    CL-USER> (sycamore:rope (list "Hello" #\Space 'World!))

    #<ROPE "Hello WORLD!">

And arrays:

    CL-USER> (sycamore:rope (vector "Hello" #\Space 'World!))

    #<ROPE "Hello WORLD!">

Rope to string:

    CL-USER> (sycamore:rope-string (sycamore:rope "Hello" #\Space 'World!))

    "Hello WORLD!"

Print a rope:

    CL-USER> (sycamore:rope-write (sycamore:rope "Hello" #\Space 'World!)
                                  :escape nil :stream *standard-output*)

    Hello WORLD!


What collection data structure should I use?
============================================

Concept of Operations
---------------------

- Two classes of set and map collections: hashes and trees.
- Hashes require a hash function and an equality function.  ANSI CL
  provides SXHASH and EQ/EQL/EQUAL/EQUALP/=.
- Trees require a total order (for any two elements A and B: does A
  come before B, does B come before A, or are A and B equal?)
- Hashes offer better asymptotic (big-O) and constant factor running
  times (O(1)) than trees (O(log(n))).
- In some less-typical cases (e.g., adversarial key selection, very
  large collections on 32 bit machines), hash collisions could reduce
  hash performance, while balanced trees guarantee consistent
  performance in such cases.

Q/A
---

- Q: Is your collection tiny or used outside a performance-critical
  path?

  - Yes: Use a list.  Or whatever you care to.  For collections that
    are small and/or not performance-critical, it probably won't much
    matter.

   - No: Let's discuss!

- Q: Are you very certain you will only ever have one version of your
  structure that you need? (no sharing between modules, no
  backtracking, maybe used only within a single, small function)?

  - Yes: A mutable structure such as ANSI CL hash-tables may offer the
    best performance.

  - No: Let's discuss!

- Q: Are your elements/keys hashable and equality-comparable (lisp
  primitives and lists are hashable/equality-comparable), and are keys
  not adversarially selected?

  - Yes: Hash Array Mapped Tries (HAMTs) could offer the best
    performance.

  - No, I either don't have a hashing function or my keys could be
    adversarially selected.

- Q: Are your keys adversarially selected but able to be
  cryptographically hashed?

  - Yes: In principle, HAMTs using a cryptographic hashing function
    would be robust to adversarially selected keys.  However, strong
    cryptographic hashes require >64 bits, while the current HAMT
    implementation in Sycamore assumes that hash-codes are FIXNUMs
    (aligning with ANSI CL SXHASH).  This limitation may be addressed
    in the future by adding support for larger (e.g., bit-vector)
    hash-codes, but for now WB-trees may be best for adversarial
    cases.

- Q: Are your keys not hashable but totally ordered (for any two
  elements A and B: you can decide if A and B are equal or if A comes
  before B, or vice versa)?

  - Yes: Weight-balanced trees could offer good performance.  They may
    be slighter slower than HAMTs, but require comparison rather than
    hashing functions.


Alternatives
============

There are many other Common Lisp data structure libraries.  Here are a
few alternatives and their trade-offs relative to Sycamore.

ANSI CL Hash Tables
-------------------

Mutable hash tables are very fast.  If you don't need persistence or
set operations (union, intersection, difference, subset), then a
mutable hash table could be a good choice.  Included benchmarks show
that SBCL's hash tables are around twice as fast as Sycamore HAMTs for
construction and lookup.

FSet
----
https://gitlab.common-lisp.net/fset/fset

FSet implements finite sets using (1) weight-balanced binary trees
similar to (and which in part inspired) Sycamore's WB-tree
implementation and (2) a HAMT variation based on Steindorfer's
Compressed Hash-Array Mapped Prefix-tree (CHAMP) [5].  FSet trees
support partial orders, whereas Sycamore trees assume a total order.
HAMTs don't require any order but do require a hashing function.  FSet
trees uses a single, global ordering for elements via a generic
function, while Sycamore orders elements with a per-collection COMPARE
parameter.  FSet HAMTs do not memoize hash codes, while Sycamore HAMTs
do.


[Benchmarks](https://ndantam.github.io/sycamore/bench.html) indicate
that Sycamore and FSet HAMTs are similar in performance for insert,
find, and remove operations, while Sycamore HAMTs are 1.3-4.5x faster
for new HAMT construction, union, intersection, and difference on the
tested sets.  Sycamore WB-trees are 1.2-3.8x faster than FSet,
depending on the operation and size, for the tested sets.

CL-HAMT
-------
https://github.com/danshapero/cl-hamt

CL-HAMT is an implementation of hash array mapped tries. Included
benchmarks show that Sycamore HAMTs are 10x faster than CL-HAMT.

CL-Containers
-------------
https://github.com/gwkkwg/cl-containers

CL-Containers is stateful/mutable/imperative, while Sycamore is
purely-functional/persistent.

Lisp Interface Library (LIL)
----------------------------
https://github.com/fare/lisp-interface-library

Lisp Interface Library (LIL) provides abstracted data structures using
Interface Passing Style, while Sycamore provides a few concrete data
structures. LIL's Interface Passing Style presumably improves
flexibility at the cost of runtime overhead and API complexity.
Sycamore's explicit data structures have low-overhead, optimized
implementations and a simple, documented API.


References
==========

[1] Bagwell, Phil. Ideal Hash Trees. EPFL Technical Report, 2001.

[2] Michael J. Steindorfer and Jurgen J. Vinju. 2015. Optimizing
    hash-array mapped tries for fast and lean immutable JVM
    collections. SIGPLAN Not. 50, 10 (October 2015),
    783–800. https://doi.org/10.1145/2858965.2814312

[3] Okasaki, Chris. "Purely Functional Data Structures." Cambridge
    University Press. June 1999. ISBN: 978-0521663502.

[4] Adams, Stephen., 1992. Implementing sets efficiently in a functional
    language. University of Southampton. Tech Report CSTR 92-10.

[5] OCaml Sets. [Documentation](https://ocaml.org/docs/sets).
    [Code](https://github.com/ocaml/ocaml/blob/trunk/stdlib/set.ml)

[6] Boehm, H.J., Atkinson, R. and Plass, M., 1995. Ropes: an
    alternative to strings. Software: Practice and Experience, 25(12),
    pp.1315-1330.

Name
====

http://en.wikipedia.org/wiki/Platanus_occidentalis

    Oh, the moonlight's fair tonight along the Wabash,
    From the fields there comes the breath of newmown hay.
    Through the sycamores the candle lights are gleaming,
    On the banks of the Wabash, far away.

        - Paul Dresser
          "On the Banks of the Wabash, Far Away"
          1897


alexandria

cl-ppcre

A fast, purely functional data structure library

Sycamore is a purely functional data structure library in Common
Lisp.  It include fast, weight-balanced binary trees, set and
map (dictionary) interfaces, pairing heaps, and amortized queues.

sycamore

Upstream URL

Author

License

sycamore

Version:

License:

Authors:

Dependencies:

Weakly Dependencies:

Dependencies (4)

Dependents (0)