Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Do we need to manually create a destructor for a linked list?

Tags:

rust

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
like image 321
kingluo Avatar asked Jul 01 '16 14:07

kingluo


1 Answers

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.

like image 86
JDemler Avatar answered Sep 25 '22 03:09

JDemler