@@@ tweak

[xyla] / README.org

#+TITLE: Xyla -- a fast, hard-mode binary tree library
#+AUTHOR: Mark Wooding
#+EMAIL: <mdw@distorted.org.uk>
#+LaTeX_CLASS: strayman
#+LaTeX_HEADER: \usepackage[greek, english]{babel}

* Sales pitch

Xyla is a C library which implements a number of binary trees.  A binary
trees is a versatile data structure which maintains a sequence of
/nodes/ and, when properly used, allow operations such as search,
insertion, deletion, splitting, and concatenation, in $O(\log n)$ time.

** Implemented trees

Xyla currently implements four kinds of binary trees:

  + /Adelson-Velsky and Landis/ (`AVL') trees, which maintain a fairly
    rigid height balance and offer good deterministic behaviour;

  + /red-black/ trees, which maintain a slightly looser height balance
    than AVL trees, but are otherwise fairly similar;

  + /splay/ trees, which provide excellent /amortized/ performance, but
    restructure the tree during searches, which makes them unsuitable
    for concurrent access, and can offer poor performance for
    /individual/ operations; and

  + /treaps/, which provide good /expected/ performance, but require a
    source of random bits which is independent of the data, and may
    behave poorly with small but finite probability in any particular
    instance.

** Hard mode implementations

Xyla implements these trees in /hard mode/.

  + Textbook search structures need to repeat a search to insert or
    delete a node.  In practice, it's common to want to want to update a
    matching node if one exists, or create a new one if it doesn't, or
    to have to example a node before taking the decision to remove it.
    Xyla provides /probe/ operations, which search a tree and captures
    the /path/ taken.  The path from a failed search can be used to
    insert a new node; the path from a successful search can be used to
    remove the node found.

  + Xyla places no requirements on node contents.  For example, it
    doesn't assume that nodes are sorted in any particular way.

  + Xyla is written in obsessively portable C.  The build system is
    Unix-biased, but compiling Xyla is essentially trivial.  Except for
    the check/walk framework, intended for diagnostic purposes, Xyla
    makes minimal demands on the C library, so it's suitable for use in
    embedded environments.  It uses only memory provided by the
    application.  By default, it makes use of only =memcpy= and
    =assert=, but even these can be removed.  See [[Freestanding build]]
    below.

  + Xyla's algorithms are all nonrecursive.

  + Xyla supports maintenance of arbitrary application-defined /summary
    data/ for nodes, i.e., anything which can be computed efficiently
    from a node itself and the summaries of its children.  Summary data
    can be used, for example, to implement determining the ordinal
    position of a node within the tree (given its path), and search by
    ordinal index.

  + Xyla implements join and split operations for all of its trees.
    Trees can be joined with or without an explicit middle node; trees
    can be split at any path, whether resulting from a successful or
    unsuccessful search.  It also implements set operations -- union,
    intersection, and difference -- for trees which are ordered by a
    search key.

** Performance

Xyla is /fast/.  This was kind of an accident: I was aiming at
`acceptable' performance and overachieved.  In my testing, splay trees
offered speeds competitive with (i.e., closely behind, or actually
faster than) Rust's state-of-the-art =HashMap=; AVL trees and treaps
were somewhat slower, but still faster than Rust's =BTreeMap=,
competitive with GNU =libstdc++='s =std::unordered_map= (and
significantly faster on large data sets) and consistently faster than
=std::map=.  Xyla's trees are consistently and significantly faster
than those in GNU =libavl=, and generally provide a more versatile,
capable, and flexible interface.  Xyla's trees also compared favourably
with other less versatile search structures, such as QP tries.


* Downsides

I'm not actually selling anything here.  I don't gain anything other
than a sense of personal satisfaction if you end up using Xyla in your
project.  So why should you /not/ use Xyla?

** Hash tables are fine, actually

Good hash tables are really fast.  If your application can work with a
hash table and you have a good one lying about, you should totally use
that.  That means that you don't care about maintaining elements in any
particular order; that you can tolerate an occasional long pause while
the hash table grows; and that you have a suitable hash function.  This
last is not so easy: it needs to be fast, well distributed, and --
because everything needs more cryptography nowadays -- unpredictable by
adversaries.

** Concurrency

Xyla isn't thread-safe.  It doesn't have any global state or anything,
but you'll have to use read/write locks or something if you want to
access a Xyla tree from multiple concurrent threads.  If you anticipate
enough contention that locking is a problem, or the thought of having to
slow down the read-only happy path by a couple of atomic operations
makes you sad, then use a data structure that's purpose-designed for the
job.

Splay trees are particularly inappropriate for concurrent access,
because you'd need a fully exclusive lock even for read operations in
order to restructure the tree; otherwise, you don't get the good
amortized performance.

** Some cool tricks are still out of reach

Xyla is hard-mode, but it's `taxing' rather than `mayhem'.  It can't do
tricks like copy-on-write.  (The reason it's difficult is that it
introduces a failure point into the middle of the fiddly tree
restructuring algorithms, which then need a recovery strategy.  See
Tatham's [[https://www.chiark.greenend.org.uk/~sgtatham/tweak/btree.html][/An Efficient Data Structure for a Hex Editor/]] for why you
might want to do it anyway.)

** You might hate the interface

If you like your interfaces abstract, high-level, type-safe, sealed up,
and pre-packaged, then Xyla isn't for you.  Implementation details are
exposed all over.  The interface makes use of =void *= arguments; I've
tried to minimize them, but type casts are necessary in some places.
Overall, I've found that this approach improves the interface
ergonomics, improves speed, keeps bloat down, and avoids potential
points of failure.


* Building

** Building on Unix

Xyla uses a traditional Autotools build system.

If you're building from Git, you'll need GNU Autoconf, Automake, and
Libtool, and the Autoconf Archive; even ancient versions of these will
be fine.  To prepare the working tree, run

: autoreconf -fis

If you're building from a source tarball, then this has already been
done.

The soak test needs Python.  Even Python 2.7 will work.

The quick version is

: mkdir build
: (cd build && ../configure)
: make -j12 -Cbuild/
: make -j12 -Cbuild/ check
: make -j12 -Cbuild/ install

The included =INSTALL= file explains how drive the =configure= script
and =Makefile= if you're unfamiliar with this.

This will install header files, static and dynamic libraries, and a
=pkg-config= file, which is the preferred way for applications to find
the library.

** Building on other systems

A fairly basic CMake-based build system is provided for non-Unix
targets.  This doesn't get as much love and attention as the primary
Autotools system, though it is capable of building the library and
running most of the tests.

There is a booby-trap which prevents the CMake-based system from working
on Unix-like systems.  Disarming the trap is left as an easy exercise.

** Freestanding build

Xyla supports building for /freestanding/ C environments which lack a
run-time library; for example, embedded systems, or operating system
kernels.  To make this work, the following steps are needed.

  + Build Xyla with the preprocessor symbol =XYLA_FREESTANDING= defined
    (to any value).  This will omit the checking framework, and replace
    the calls to =memcpy= with simple loops.  Don't try to compile the
    =*-check.c= files containing the checking routines, which require
    memory allocation and I/O.

  * Optionally, define =XYLA__ASSERT= to be an =assert=-like macro,
    i.e., a macro of a single argument which will abort the program if
    its argument is zero or null.  If you don't provide a definition,
    then Xyla will run without assertions.

  + If you want to use treaps, then define a function
    =xyla__treap_boundfail= (with no arguments), which will abort the
    program.  This is used in the extremely unlikely event that a
    treap's height exceeds the calculated bounds; unfortunately, a
    treap's structure is rigidly determined by the order of its elements
    and their weights, so rebalancing is impossible and the situation is
    unrecoverable.


* Future directions

  + I'm thinking about a =touch= node operation to be called before a
    node is changed.  It would be able to return a replacement node to
    act on instead, to be be spliced into the tree.  This could be used
    to implement copy-on-write, for example.

  + Additional kinds of trees.

      - I'm considering a Bayer tree -- essentially, an encoding of 2-3
        trees as binary trees in the same way that red-black trees
        encode 2-3-4 trees.  I think I'd make these asymmetric, in the
        same way that Andersson trees are asymmetric.  The differences
        from an actual Andersson tree are that each node only records a
        single bit rather than a height, and that updates is much more
        similar to a red-black tree than the `split' and `skew'
        operations that Andersson describes.  The nice feature of such
        trees is that the first element has the shortest path from the
        root of any leaf or semileaf, which is nice for some kinds of
        priority queues.


* Compatibility policy

Xyla is still stabilizing.  There are a small number of issues which I
still want to nail down before I declare release 1.0.0.  I don't expect
this to take more than a month or so.

Once 1.0.0 does drop, I'm committed to retaining source and binary
compatibility indefinitely.  The cool kids seem to like removing things
all the time, but that's just not the way I roll.


* Name

The ancient Greek word `\foreignlanguage{greek}{ξύλον}' (`xulon')
doesn't have a direct English equivalent.  Pretty much any woody thing
is a \foreignlanguage{greek}{ξύλον}.  A thing made out of wood, like a
table or chair, a plank, or a club, is a \foreignlanguage{greek}{ξύλον},
but so is a naturally woody thing, like a tree.  The (nominative and
accusative) plural is `\foreignlanguage{greek}{ξύλα}' (`xula').

The initial `x' is a `ks', not a `z' like the word's descendants have
ended up with in English.  The `u' is fronted, like French `u', or
German `ü'.  When the Romans started borrowing Greek vocabulary, they
realized that they didn't have a way to represent this sound, so they
added a new letter `y' for it.  Hence, the Latin transliterations would
have been `xylon' and `xyla'.

The accent is on the first syllable, but ancient Greek had a pitch
accent, not the stress accent that English has, so the first syllable is
higher pitched than the second.

There's a more specific word `\foreignlanguage{greek}{δένδρον}'
(`dendron') which just means `tree', but \foreignlanguage{greek}{ξύλον}
is just an intrinsically better word.


* Licence

Xyla is free software.  You can modify and/or redistribute it under the
terms of the GNU Lesser General Public License, version 3, as published
by the Free Software Foundation, or, at your option, any later version.


* COMMENT Emacs cruft

# LocalWords: Adelson autoreconf AVL BTreeMap Cbuild cd CMake fis Landis
# LocalWords: libavl libstdc memcpy mkdir pre QP rebalancing treap's treaps
# LocalWords: Velsky xyla Xyla's Andersson