6

I'm reading Learning Rust With Entirely Too Many Linked Lists and I'm confused about why the linked list (stack) needs a destructor.

I think when the list value is out of the scope, the list itself, and all nodes would be clean up. Is it just for demonstration?

I benchmarked the version with and without a manual destructor and I found the "without destructor" one has better performance:

for _ in 1..30000000 {
    let mut list = List::new();
    list.push(1);
    assert_eq!(list.pop(), Some(1));
}

With manual destructor:

real    0m11.216s
user    0m11.192s
sys     0m 0.020s

Without manual destructor:

real    0m9.071s
user    0m9.044s
sys     0m0.004s
Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
kingluo
  • 1,679
  • 1
  • 13
  • 31

2 Answers2

11

You are correct. The list would clean itself up. As the author stated:

All that's handled for us automatically... with one hitch.

They then explain why the automatic handling is bad: The automatic destruction process calls drop for the head of the list, which in turn calls drop for the first element. And so on and so on.

This is a function calling a function calling a function (with infinite possible repetitions) which will blow up your stack sooner or later.

This test causes such a stack overflow:

#[test]
fn build_really_big_stack() {
    let mut stack = List::new();
    for i in 0..1_000_000 {
        stack.push(i);
    }
}

If you build with --release for both versions, it shows that they perform nearly equally:

#[bench]
fn bench_auto_destructor(b: &mut Bencher) {
    b.iter(|| {
        let mut list = List::new();
        for i in 0..1000 {
            list.push(i);
        }
        assert_eq!(list.pop(), Some(999));
    });
}

#[bench]
fn bench_man_destructor(b: &mut Bencher) {
    b.iter(|| {
        let mut list = ManualDestructorList::new();
        for i in 0..1000 {
            list.push(i);
        }
        assert_eq!(list.pop(), Some(999));
    });
}

test bench_auto_destructor ... bench:      81,296 ns/iter (+/- 302)
test bench_man_destructor  ... bench:      85,756 ns/iter (+/- 164)

With only one element, like in your benchmarks:

test bench_auto_destructor ... bench:          69 ns/iter (+/- 1)
test bench_man_destructor  ... bench:          67 ns/iter (+/- 2)

Read the article to the end, its explanation is better than mine.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
JDemler
  • 1,246
  • 14
  • 22
  • I still cannot understand what it means. The default clean up way by rust compiler is bad? – kingluo Jul 01 '16 at 14:42
  • For each function call, the compiler needs to introduce some overhead for storing registers. (see https://en.wikibooks.org/wiki/X86_Disassembly/Functions_and_Stack_Frames for example). This allocates memory on the stack. If it happens too often, the stack overflows: https://en.wikipedia.org/wiki/Stack_overflow – JDemler Jul 01 '16 at 14:48
  • Yes, I know the recursion function calls consume resources. But by default, the list and nodes has no associated destructor. It just release memory. So by default, no function call happens for destruction, isn't it? In fact, you could try to benchmark the list operations with and without explicit destructor, and you could see the default one (without destructor) has better performance. So that's why I ask for the reason to associate destructor to the list. – kingluo Jul 01 '16 at 14:52
  • "list and nodes has no associated destructor" This is not a correct statement. They do have a destructor, namely, the one which calls `Drop` on the `Box` instance. Also, there is no "just releasing memory"; memory deallocation is still a function call. – Vladimir Matveev Jul 01 '16 at 14:57
  • The Box has destructor? provided by rust? But anyway, why when I remove the "impl Drop for List" and do some benchmark, it has better performance? – kingluo Jul 01 '16 at 15:01
  • The fact that there is no destructor in your code, does not mean, there is no destructor. There is always a default destructor which is automatically added by the compiler. It calls drop on self and then on the children, as the written out code in the article shows. See https://doc.rust-lang.org/nomicon/destructors.html – JDemler Jul 01 '16 at 15:02
  • Then how to explain the benchmark result? (see my edit in my question) It's conflicted with what the author said "The automatic handling is going to be bad.". – kingluo Jul 01 '16 at 15:06
  • In my tests I get said stackoverflow. I added the example test in the answer. – JDemler Jul 01 '16 at 15:18
9

The reason the author is making you implement your own drop for Link is that calling the destructor on the linked list is not tail recursive, and so if a very large List (i.e. a List whose node count is greater than the number of stack frames allowed by the Rust compiler) goes out of scope and is thus deallocated, then you'll get a stack overflow error when all those drop functions are called recursively. Go read the link I gave above to understand what tail recursion is, but replace the recsum() function with the Link's drop function, and you'll understand why the author made you write your own destructor.

Imagine a List with 1_000_000 Node's. When that List gets deallocated your stack will look like

(Stack Frame #1) List.drop();    // all work is done in this frame, so no need to save stack frame
(Stack Frame #2) self.ptr.drop(); self.ptr.deallocate(); // uh oh! stack frame must be preserved throughout all recursive calls because deallocate must be called after self.ptr.drop() returns
(Stack Frame #3) self.ptr.drop(); self.ptr.deallocate();
...
(Stack Frame #1_000_000) self.ptr.drop(); self.ptr.deallocate(); // we'll never reach here, because a stack overflow error would have been occurred long ago
almel
  • 7,178
  • 13
  • 45
  • 58
  • 1
    I finally got to understand the reason behind the destructor in that example. I've noticed an increasing number of blunt answers here in SO, most doesn't provide the foundation required to understand the problem as a whole and what led to its solutions. Thanks, mate. – Miere Dec 10 '20 at 03:25