8. Lisp-like lists

Lists in lisp and Scheme

A long time ago there was a programming language called Lisp or for you younger folks Scheme. Scheme might have been wrong, but it was great¹. The whole language centers around very simple linked lists which are based on three fundamental operations²:

1. cons: create a pair.
2. car: get first element of pair.
3. cdr: get second element of pair.

We’re not going to use these terms and we’re going to extend our vocabulary from 3 to 4. Lisp told us that there’s this wonderful thing, without which we cannot live, called garbage collection. We don’t want garbage collection for all the algorithms we want to use. So we are going to add a 4th operation:

 4. free: manually release/free a pair.

What we want to do is muck around with lists. Meaning you can insert items in the middle, change pointers, connect this and that. All of these operations are natural. If you don’t want to muck around, just use vectors.

But, we’re going to build it so it’s blindingly fast. How are we going to do that? You want to avoid memory fragmentation. If you have lists with nodes spread all over memory, every time you access one, it is a cache miss. Modern computer caches do not really help if you do long jumps. We have lots of nodes, but we want them to live in a little buffer even if we keep generating them back and forth. If they reside in a small space we will never get a cache miss.

Why is malloc so slow?

We’re also going to avoid malloc because it is evil. It used to be sort of alright, when I started working on STL in 1993. But, even then I realized it was too slow to be used with node based data structures. So for any data structure of nodes, such as list, I would keep a pool of nodes myself and manage them in a quick way.

A few people, such as Bill Plauger at Microsoft and others at GNU who followed their example, said that if they have a common pool and they just do pointer movement then if you have multiple threads you could have problems³. Instead of solving the problem for the multi-threaded case they decided to solve it in general. They said, “first we’re going to put locks on our malloc⁴. Then we’re going to throw Alex’s pool management away and we’re going to do full malloc.” Now malloc is function call with a lock, so it’s a very heavy operation.

Because of this decision, all our lists are going to be thread safe⁵. People like us, who do not use threads (you don’t use threads right?) pay for them. They violated a fundamental principle which Bjarne insists on. People should not pay for things they do not use. Everybody pays for the ability of multiple threads to do list allocations out of the same pool. Which actually nobody does, but everybody pays.

List pool

A list pool is an object with many outstanding lists inside. Internally we will use one vector to implement many, many, lists. These lists are not containers. A container guarantees that when the container is gone, the values are gone too. For these lists there is no guarantee like that. For example, you could split this list into two by setting a cdr. There is no ownership and this is why I recommend not viewing them as containers. STL containers are wonderful when you want them, but that’s not the case here.

We’re trying to get as close to Lisp as we can without building garbage collection⁶. If you want to build garbage collection you can extend this thing and build garbage collection too, but garbage collection is overrated.

We will implement list_pool as a class, with two types as template arguments. T will be the values we want to store, and N will be an index type.

#include <vector>
template<typename T, typename N>
// T is semi-regular.
// N is integral
class list_pool {
    typedef N list_type;

    struct node_t {
      T value;
      N next;
    };

    std::vector<node_t> pool;
    list_type free_list;

    // ...
};

What should N be? Why not size_t? Because it’s 64 bits. For our application we could probably use uint16_t so our whole node fits in 32 bits. But, we should define a default.

typename N = size_t;

Now we are going to implement cons, car, cdr, and free as member functions of list_pool, but we need appropriate names for a younger generation.

Value (car)

We will rename car to value. Note that because we can return value by reference, it can be both read and modified. So, it won’t just be car, it will also act as rplaca⁷.

T& value(list_type x) {
  return node(x).value;
}

const T& value(list_type x) const {
  return node(x).value;
}

Next (cdr)

Let’s rename cdr to next. Because of read and write it also acts as rplacd.

list_type& next(list_type x) {
  return node(x).next;
}

const list_type& next(list_type x) const {
  return node(x).next;
}

Free

Now let’s write free. The pool maintains a list of nodes which are available for reuse. This operation appends a node to the head of this list⁸.

list_type free(list_type x) {
  list_type cdr = next(x);
  next(x) = free_list;
  free_list = x;
  return cdr;
}

We make it somewhat more useful by returning next(x) instead of void. If it was not returned, the user would have to save it before freeing.

Allocate (cons)

Now we will write cons, it takes two arguments. Where do nodes come from? The free list, if it has room, otherwise we make a new node from the pool.

list_type allocate(const T& val, list_type tail) {
  list_type new_list = free_list;

  if (is_empty(free_list)) {
    new_list = new_node();
  } else {
    free_list = next(free_list);
  }

  // start with this part
  value(new_list) = val;
  next(new_list) = tail;
  return new_list;
}

So we need to write the public function is_empty.

bool is_empty(list_type x) const {
  return x == empty();
}

Dual to this function, is one which gives you the nil or empty list.

list_type empty() {
  return list_type(0);
}

You might think, what about the 0th item in the pool? We will just index everything at 1, so we don’t lose the first item. If you use -1 then our index type must be signed.

list_pool() {
  free_list = empty();
}

Now we write a few private node functions including new_node.

node_t& node(list_type x) {
  return pool[x - 1];
}

const node_t& node(list_type x) const {
  return pool[x - 1];
}

list_type new_node() {
  pool.push_back(node_t());
  return list_type(pool.size());
}

Our structure requires all lists in the pool to be const or all of them to be non-const. Typically const is just for handing someone something to read.

Free list helper

There is a simple rule to distinguish when you should write a method/member function and when to just make an outside function (free function). Implement the simplest possible thing. If you can do it outside, do it.

Let’s implement a function for freeing an entire list, not just a node.

template <typename T, typename N>
void free_list(list_pool<T, N>& pool,
    typename list_pool<T, N>::list_type x) {
  while (!pool.is_empty(x)) x = pool.free(x); 
}

Exercise: Before moving on, get familiar with these operations. Create a simple list inside a pool and print it by iterating through its contents (solved in test_list_pool.cpp at the end of the chapter).

List queue

We can use our list to implement a queue structure. The queue will be defined by a list node in the front, and one in the back.

typedef std::pair<list_type, list_type> pair_type;

We often want to detect empty queues and construct them:

bool empty(const pair_type& p) { return is_end(p.first); }
pair_type empty_queue() { return pair_type(end(), end()); }

You can add an element to the front, or the back of the queue:

pair_type push_front(const pair_type& p, const T& value) {
  list_type new_node = allocate(value, p.first);
  if (empty(p)) return pair_type(new_node, new_node);
  return pair_type(new_node, p.second);
}

pair_type push_back(const pair_type& p, const T& value) {
  list_type new_node = allocate(value, end());
  if (empty(p)) return pair_type(new_node, new_node);
  next(p.second) = new_node;
  return pair_type(p.first, new_node);
}

You can remove an element from the front of the queue⁹:

pair_type pop_front(const pair_type& p) {
  if (empty(p)) return p;
  return pair_type(next(p.first), p.second);
}

Now we can also free lists in constant time, simply by attaching the end of our list to the free list.

void free(const pair_type& p) { free(p.first, p.second); }

Code

• list_pool.h
• list_pool_iterator.h (included by list_pool.h, but not discussed until Chapter 9)
• test_list_pool.cpp