ATerm SAF: A High Performance Streamable Format

This document contains the technical documentation of the (Semi-) Streamable ATerm Format, otherwise known as SAF. This document is mainly intended for the developers and users of the ATerm library. If you do not understand what ATerms are you’d better stop reading now ;).

SAF is intended to be a high performance format, capable of exchanging ATerms in an fast, efficient and platform independent way. The main reason for its development emerged from the wish to transmit terms across network connections in a ‘streamable’ way with the option to suspend this process at any point in time to enable multiplexing, while keeping (de-)serialization memory usage constant. The currently available ATerm formats (BAF, TAF and the ASCII ATerm format) do not supply any of these functionalities.

The most important requirements for this format and its implementation(s) are:

The serial representation of the format is fairly simple. Every term has a header containing general information about the term. After this header the serial representation of the term itself is present; the way this serial representation is layed out is type specific.

SAF is a (semi-)streamable format, so reading and writing it goes a little different then usual. It works in a block-wise way. A SAF writer can be requested for the following X bytes of the serial representation of a term, which can contain partially serialized elements. When reading SAF you will need information about how large those blocks were to be able to reconstruct the term. For this purpose we propose to emit a two byte unsigned integer value before every block, which specifies its size. This is, for example, the case for SAF file I/O; thus you will always need a buffer of 2^16 (65536) bytes when reading from a 'standard' SAF file. (Note that a 0 block length value indicates a block of 65536 bytes, since 0 length blocks can't exist). Custom ‘shielded’ I/O implementations for SAF are allowed to use their own values and / or protocol (by shielded we mean implementations that are not intended to interface with any implementations other then themselfs, since compatibility can not be guaranteed in these cases).

This block-wise writing and reading method enables us to suspend the (de-)serialization process at fixed intervals, without the need to assign a different thread to each process. This enables us to interleave the simultaineous construction of multiple trees of terms in a single threaded environment.

As noted before compression, generally speaking, incurs computational overhead. In this particular case computational overhead is something we want to avoid or at least restrict as much as possible. Also the streamability and portability requirements limit our options in terms of compression techniques. For this reason we decided to stick the to sharing of 'elements'. With elements we mean terms / sub trees and function symbols. We can achieve fairly good compression rates with this, because it is a type of compression that is specifically meant for ATerms; we know what the data and composition look like and can use that knowledge to our advantage.

We use a LZW like compression technique to handle the sharing. What we do is, every time we encounter an element we have not seen before we add it to a table and assign it the next 'identifier' (which is an unsigned integer; the first identifier is 0, which represents the root of the tree). If we encounter an element that is already present in the table, we set the with the element’s type corresponding 'shared?' flag in the header and emit the associated identifier. During the deserialization process we do the exact opposite, every unique element that is encountered is added to an array in the order in which we find them in the SAF stream; when we run into a shared element, we read the associated id and replace it by the value that is present at that index in the array. We use separate tables and arrays for both shared terms / sub trees and shared function symbols.

The current SAF (de-)serialization implementation in both C and Java is multiple times faster then that of any of the other ATerm formats (BAF, TAF and the ASCII ATerm format).

Here are some benchmarks that illustrate the performance difference between the current C and Java implementations of the different formats:

(The benchmarks were performed on a AMD 64 3500+ with 1 GB DDR-400 dual-channel RAM. It shows the 'best of five runs' execution time, measured inside the code (user time spend). Keep in mind that these measurements are subject to change and are merely an indication).

Memory usage of the current SAF (de-)serialization implementations scale linearly with the amount of unique elements in the tree. This is because a reference to every unique element in the tree is stored in a hashtable or array during both the serialization as the deserialization process. Also the depth of the tree influences the memory usage, since that determains the size of the stack that keeps track of the parent to child relations of the terms in the tree; the size of this stack scales linearly with the depth of the tree.

The worst case memory usage can be calculated in the following way:

Serialization memory usage: (the number of unique terms in the tree * 4 * 4) + (the number of unique function symbols in the tree * 4 * 4) + (the depth of the tree * 4 * 4).

Deserialization memory usage: (the number of unique terms in the tree * 2 * 4) + (the number of unique function symbols in the tree * 4) + (the depth of the tree * 8 * 4).

Calculating the exact amount of memory usage is possible, but largely depends on the layout of the tree. The above calculations serve as a guideline to indicate the maximal memory usage for the (de-)serialization of a certain term.

The following term:

line(box(rect(2), rect(5), square(4, 3)), circle(10), circle(10))

Will look like this in the binary format:

0x01 0x03 0x04 line 0x01 0x03 0x03 box 0x01 0x01 0x04 rect 0x02 0x02 0x41 0x03 0x02 0x05 0x01 0x02 0x06 square 0x02 0x04 0x02 0x03 0x01 0x01 0x06 circle 0x02 0x0a 0x80 0x06

Which in bits looks like this (the indent and lines were added to show the child-parent relationship):

|00000001  appl
|00000011  arity = 3
|00000100  fun-length = 4
|01101100  fun-bytes = line
|01101001
|01101110
|01100101
|---|
    |00000001  appl
    |00000011  arity = 3
    |00000011  fun-length = 3
    |01100010  fun-bytes = box
    |01101111
    |01111000
    |---|
    |   |00000001  appl
    |   |00000001  arity = 1
    |   |00000100  fun-length = 4
    |   |01110010  fun-bytes = rect
    |   |01100101
    |   |01100011
    |   |01110100
    |   |---|
    |   |   |00000010  int
    |   |   |00000010  value = 2
    |   |
    |   |01000001  appl with shared function symbol
    |   |00000011  shared function symbol identifier = 3
    |   |---|
    |   |   |00000010  int
    |   |   |00000101  value = 5
    |   |
    |   |00000001  appl
    |   |00000010  arity = 2
    |   |00000110  fun-length = 6
    |   |01110011  fun-bytes = square
    |   |01110001
    |   |01110101
    |   |01100001
    |   |01110010
    |   |01100101
    |   |---|
    |       |00000010  int
    |       |00000100  value = 4
    |       |
    |       |00000010  int
    |       |00000011  value = 3
    |
    |00000001  appl
    |00000001  arity = 1
    |00000110  fun-length = 6
    |01100011  fun-bytes = circle
    |01101001
    |01110010
    |01100011
    |01101100
    |01100101
    |---|
    |   |00000010  int
    |   |00001010  value = 10
    |
    |10000000  shared term
    |00000110  shared term identifier = 6