Why writing a linked list in safe Rust is so damned hard

Re:Why writing a linked list in safe Rust is so damned hard by vvanders on Thursday February 22, 2018 @07:40PM (#16443079)

Option #3(indexed tree) looks non-ideal but it actually has some really cool properties if you do it right.

1. If you know traversal order you can get really great cache coherency. We used to do this all the time with animation DAGs and the like in gamedev.

2. If everything is an "offset"/index instead of a pointer you can do things like in-place loading where creating something is just a single read() call. No constructors or annoying allocations to slow down loading. If you want to take this even further you can mmap() the entire file on disk and use massive(500mb+) files without using much actual memory overhead through letting the kernel page it in/out for you.

[ Parent | on HN ]

Re:Why writing a linked list in safe Rust is so damned hard by Narishma on Thursday February 22, 2018 @09:08PM (#16443620)

> 1. If you know traversal order you can get really great cache coherency.

Cache locality, not coherency.

[ Parent | on HN ]

Re:Why writing a linked list in safe Rust is so damned hard by vvanders on Thursday February 22, 2018 @09:15PM (#16443656)

Sorry yes, had a brain fart there.

[ Parent | on HN ]

Re:Why writing a linked list in safe Rust is so damned hard by stjepang on Friday February 23, 2018 @06:49AM (#16445736)

Why does option #3 look non-ideal, what are your concerns with it?

[ Parent | on HN ]

Re:Why writing a linked list in safe Rust is so damned hard by vvanders on Friday February 23, 2018 @10:40AM (#16446934)

Well, non-ideal may be poor phrasing. I guess I meant to say it doesn't look like the "classic" linked list implementation.

[ Parent | on HN ]