Version 6 (modified by schiptsov, 10 years ago) ( diff )


To keep it simple, we can think of data structures in terms of its shape. There are

  • list - a sequence of the values of the same type (an array or vector) or of any type (a dynamic list or a fixed set)
  • table - of the values of the same type (matrix or multi-dimensional array) or of mixed types an associative list (alist) or an associative array or a hash table.
  • tree - trees of any kind, such as binary trees, binary-search trees, red-black trees, etc.
  • net - a graph or a network with any kind connections between its nodes.

They all are abstract data types, because deep down there is nothing but pointers and numbers.

We should use annotations for the compiler to choice appropriate built-in primitives and hardware-supported types of values.

We should forget all space optimizations because memory is cheap, and use partitioning and pool-based pre-allocation instead. There is a pool for pointers, another one for indexes, another one for data, etc.

The goal is to keep the most clear symbolic notation and and to transform it to simple immutable data structures based on pointers, 64-bit x96-64 Long mode and SSE4.2+ instruction set.

cons: a pair of pointers - the basic building block

(a . b)

list: a sequence (could be annotated as a set, one-dimension array, etc)

(1 "two" 3 (4 5))

vecror: an array with a shape, which is actually just a pointer to a sequence of chunks of memory of the same size.


matrix: multi-dimension array, which is a flat sequence of memory chunks in memory.

((1 2 3)
 (3 4 5)
 (6 7 8))

associative array: two linked sets of pointers

(("a" . 1)
 ("b" . 2)
 ("c" . '(1 2 3)))

hash table: set of slots plus a hash-function to produce an offset in the index.

(("apple" . 1)
 ("orange" . 2)
 ("grapes" . 3))

a table could be "called" by sending a message to it: (t "orange") => 2

Note: See TracWiki for help on using the wiki.