Learn Rust with entirely too many linked lists (2019) • Hacker News Board

Re: Learn Rust with entirely too many linked lists (2019)

#51

Post by aw1621107 » Sat, Feb 22, 2020, 6:14 PM UTC

zozbot234 wrote: post #31

nicoburns wrote: post #28

Earlier quoted context omitted.

You can't turn off the borrow checker for references, but Rust also provides raw pointers which are not subject to borrow checking (these are exactly like pointers in C, and can be cast to and from references (this is a no-op at runtime since they share the same memory representation)). https://doc.rust-lang.org/1.30.0/book/first-edition/raw-poin... You can create and manipulate raw pointers in safe code, but derefer…

AIUI, there are some hardware architectures where even creating a wild pointer might be undefined behavior, regardless of whether that pointer is subsequently dereferenced, and C inherits these requirements. This means that it might be desirable to restrict creation and manipulation of raw pointers to unsafe code in Rust as well, if this can be done without introducing undue incompatibilities. (Rust editions would na…

> AIUI, there are some hardware architectures where even creating a wild pointer might be undefined behavior, regardless of whether that pointer is subsequently dereferenced

Would you be able to point me to some references for such hardware? Im not sure how that would work (at least based on my admittedly limited amount of experience). Wouldn’t a pointer look like any other integer right up until it’s used as a memory operand? Or would said architecture have some way to distinguish pointers and a “regular” integer in registers?

Re: Learn Rust with entirely too many linked lists (2019)

#52

Post by staticassertion » Sat, Feb 22, 2020, 6:15 PM UTC

varjag wrote: post #45

Tuna-Fish wrote: post #42

Earlier quoted context omitted.

Yes. For the vast majority of uses, you should probably use a hash table instead. There are still niche uses for both linked lists and trees, but the sad fact is that the relative time it takes to chase a random pointer compared to doing literally anything else keeps getting worse, and is already at the point where frequently linearly copying kilobytes of arrays is almost always faster than using a linked list.

If your data/algorithm calls for a certain dynamic structure, let's say a red-black tree, replacing it with array is pointless. Last time I looked, kobjects in Linux kernel were still dynamically linked in a bunch of ways, and tree-like data structures are widely used.

I think it's probably fair to call kernel development niche? And the fact that Linux uses linked lists a lot is not necessarily a strong case for linked lists, but just a matter of very specific constraints - like perhaps not wanting to optimize too much for underlying hardware?

Re: Learn Rust with entirely too many linked lists (2019)

#53

Post by adrianN » Sat, Feb 22, 2020, 6:16 PM UTC

varjag wrote: post #45

Tuna-Fish wrote: post #42

Earlier quoted context omitted.

Yes. For the vast majority of uses, you should probably use a hash table instead. There are still niche uses for both linked lists and trees, but the sad fact is that the relative time it takes to chase a random pointer compared to doing literally anything else keeps getting worse, and is already at the point where frequently linearly copying kilobytes of arrays is almost always faster than using a linked list.

If your data/algorithm calls for a certain dynamic structure, let's say a red-black tree, replacing it with array is pointless. Last time I looked, kobjects in Linux kernel were still dynamically linked in a bunch of ways, and tree-like data structures are widely used.

Sure, but algorithms that explicitly need a linked structure for performance are very few compared to algorithms that have the same or better asymptotic with a hash and a vector or for which the input sizes are such that the large constants pointer chasing causes don't make up for worse asymptotics.

Re: Learn Rust with entirely too many linked lists (2019)

#54

Post by caconym_ » Sat, Feb 22, 2020, 6:17 PM UTC

A while ago now, this was the tutorial that got me to the point where I could implement linked structures in Rust. Highly recommended.

Re: Learn Rust with entirely too many linked lists (2019)

#55

Post by kybernetikos » Sat, Feb 22, 2020, 6:19 PM UTC

Dylan16807 wrote: post #49

varjag wrote: post #40

Earlier quoted context omitted.

Seriously? Are trees also niche?

What kind of tree? A binary tree isn't great for many uses, and doesn't excel at much. But a nice fat B+ tree removes the vast majority of pointer-chasing latency.

I've got quite keen on B+ trees. It seems like the world where we had fast main memory and slow drive storage is not very different to the world where we have fast cache memory and slow main memory.

Re: Learn Rust with entirely too many linked lists (2019)

#56

Post by Dylan16807 » Sat, Feb 22, 2020, 6:21 PM UTC

zozbot234 wrote: post #31

nicoburns wrote: post #28

Earlier quoted context omitted.

You can't turn off the borrow checker for references, but Rust also provides raw pointers which are not subject to borrow checking (these are exactly like pointers in C, and can be cast to and from references (this is a no-op at runtime since they share the same memory representation)). https://doc.rust-lang.org/1.30.0/book/first-edition/raw-poin... You can create and manipulate raw pointers in safe code, but derefer…

AIUI, there are some hardware architectures where even creating a wild pointer might be undefined behavior, regardless of whether that pointer is subsequently dereferenced, and C inherits these requirements. This means that it might be desirable to restrict creation and manipulation of raw pointers to unsafe code in Rust as well, if this can be done without introducing undue incompatibilities. (Rust editions would na…

Maybe. Or maybe you'd just change it so 'wild pointers' created in safe code are stored as ints on that architecture.

Re: Learn Rust with entirely too many linked lists (2019)

#57

Post by staticassertion » Sat, Feb 22, 2020, 6:22 PM UTC

varjag wrote: post #48

saagarjha wrote: post #46

Earlier quoted context omitted.

What’s an adjustable array? A vector?

A vector is a one-dimensional array. Adjustable arrays can have arbitrary number of dimensions, although am not sure if it's a thing in Rust.

That just sounds like a graph.

Re: Learn Rust with entirely too many linked lists (2019)

#58

Post by kybernetikos » Sat, Feb 22, 2020, 6:23 PM UTC

I really value this guide.

Writing data structures in a language is one of the standard ways that I convince myself that I understand it. Rust really messes hard with that mindset.

This guide talked me through all the things I'm not used to worrying about in garbage collected languages, showed me the error messages that I'd been banging my head against, explained what they meant, and did so with humor.

Re: Learn Rust with entirely too many linked lists (2019)

#59

Post by Dylan16807 » Sat, Feb 22, 2020, 6:25 PM UTC

xlap wrote: post #50

Basically anything published about Rust is turning me away from the language. It could be unfair though: Technical writing (and that includes humorous opinionated pieces) has declined dramatically in the last 10 years. Or perhaps writing as a whole has declined.

It wouldn't hurt to be specific.

Re: Learn Rust with entirely too many linked lists (2019)

#60

Post by Hello71 » Sat, Feb 22, 2020, 6:30 PM UTC

aw1621107 wrote: post #51

zozbot234 wrote: post #31

Earlier quoted context omitted.

AIUI, there are some hardware architectures where even creating a wild pointer might be undefined behavior, regardless of whether that pointer is subsequently dereferenced, and C inherits these requirements. This means that it might be desirable to restrict creation and manipulation of raw pointers to unsafe code in Rust as well, if this can be done without introducing undue incompatibilities. (Rust editions would na…

> AIUI, there are some hardware architectures where even creating a wild pointer might be undefined behavior, regardless of whether that pointer is subsequently dereferenced Would you be able to point me to some references for such hardware? Im not sure how that would work (at least based on my admittedly limited amount of experience). Wouldn’t a pointer look like any other integer right up until it’s used as a memor…

Allegedly, some platforms have pointer trap representations, where a certain pointer can be created, but may not be used in any operations of that type. No modern systems have such trap representations for pointer types, but the C standard inherits their legacy, and, more importantly, C compilers use it as justification for certain types of optimizations. Since it's not a hardware limitation, Rust can perfectly well take the opposite path and say that the compiler may not use it for those optimizations.

https://stackoverflow.com/questions/6725809/trap-representat...