mozilla/rust — pull request #7652 by blake2-ppc (2013-07-08 20:33:36+00:00)
Title: RFC: Replace DList with an owned doubly-linked list

This is a new doubly-linked list using owned nodes. In the forward direction, the list is linked with owned pointers, and the backwards direction is linked with &'static Node pointers.

This intends to replace the previous extra::DList that was using managed nodes and also featured freestanding nodes. The new List does not give access to the nodes, but means to implement all relevant linked-list methods.

At the moment it supports pop_back, push_back, pop_front, push_front, peek_front, peek_back, iter, mut_iter, +more iterators, append, insert_ordered, and merge.

## RFC Topics

### Implementation

Using &'static Node pointers for backlinks creates an infinite loop when you use `fmt!("%?")`. Using raw pointers is just as easy, but Option<*Node> is 16 bytes while Option<&'static Node> is only 8.

### Replacing DLink

Do we want to throw out the old DLink? It's not very rustic anymore, and it's very slow (benchmarks at the end)

### extra or std?

I think the doubly-linked list should enter std under `std::list::List`, together with deque under `std::deque`.

### Container Method Names

I think we have two options

* Align with the existing methods on the vector. That would be `.push()`, `.pop()`, `.shift()`, `.unshift()`.
* Use the API described in https://github.com/mozilla/rust/wiki/Containers Obviously that's the way List is written right now.

### Benchmarks

Some basic bench numbers for List vs. Vec, Deque and *old DList*

This List implementation's performance is dominated by the allocation of Nodes required when pushing. The forward iterators are slower; they traverse a chain of `Option<~Node>`, the rev iterators traverse `Option<&'static Node>.`

Iterate (by-ref) collection of 128 elements

test test_bench::bench_iter ... bench: 298 ns/iter (+/- 0)
test test_bench::bench_iter_mut ... bench: 297 ns/iter (+/- 0)
test test_bench::bench_iter_rev ... bench: 201 ns/iter (+/- 0)
test test_bench::bench_iter_mut_rev ... bench: 204 ns/iter (+/- 3)

test test_bench::bench_iter_vec ... bench: 108 ns/iter (+/- 0)
test test_bench::bench_iter_deque ... bench: 581 ns/iter (+/- 0)
test test_bench::bench_iter_dlist ... bench: 9262 ns/iter (+/- 273)

Sequence of `.push(elt)`, `.pop()` or equivalent at the tail end

test test_bench::bench_push_back_pop_back ... bench: 74 ns/iter (+/- 0)

test test_bench::bench_push_back_pop_back_vec ... bench: 6 ns/iter (+/- 0)
test test_bench::bench_push_back_pop_back_deque ... bench: 15 ns/iter (+/- 0)
test test_bench::bench_push_back_pop_back_dlist ... bench: 234 ns/iter (+/- 0)