Hacker News Reader

Hacker News

Comment by dxhdr | Hacker News Reader

Parent Full thread

dxhdr

I thought the tl;dr was: Implementing B-trees as an embeddable library in C is hard, therefore Rust is faster.

View on HN

Rust makes hard problems easier, but easy problems harder. BTrees are a great example of that sentiment.

Let's look at some problems in C which should be easy:

1. Storing an array and its length together and always checking it correctly such that you don't have a buffer overrun.

2. Freeing memory, not leaking memory.

3. Using a union correctly, e.g. always accessing the right variant.

4. Printing unicode characters.

5. Macros which dont' conflict with their scope (are hygenic)

All of those problems seem like they should be easy, are incredibly easy in rust, and are not fully solved problems in C.

I don't think rust makes easy problems harder just because its type-system and macro system and such are all so good compared to C.

It turns out having proper sum types instead of C's garbage unions, and having proper string support, and so on make easy problems easy too!

The problem that Rust makes hard: linked lists.

Doubly linked lists. Singly linked lists and one-way trees work fine with the single ownership model.

As I've said before, the two places where Rust has problems with expressive power are backlinks and partially initialized arrays. Those are routine cases which are forced to unsafe code.

One of the places you most often need to use backlinks and other unsafe code in Rust is implementing fancy data structures. Unfortunately that happens to be what a lot of people think of as "programming" because they come up a lot in computer science classes... Fortunately most production code seldom needs new fancy data structures; maps, sets, tuples, structs and reference counting take you a very very long way. For less common things like graphs there are usually crates you can use off the shelf.

Please, these are not interesting or useful talking points. You always get the same responses:

Partially initialized arrays are a solved problem- anything more would just be baking `Vec` into the language.

And backlinks are nowhere near "routine."

Backlinks ARE a very interesting point about Rust. Just because you don't find yourself using them all that often doesn't mean it's not interesting to the design and expresivity of the language.

The issue is a direct consequence of Rust's strict aliasing rules, which I feel any programmer would benefit from groking.

They're routine in CS classes. Curiously, I've never needed to use them in real life.

Except really common things like LRU caches use them.

I think it's important to note that in the case of most data structures, you only need to do the hard work of verifying your unsafe code once, after which you can package it up in a crate.

I guess many C programmers might be used to reimplementing data structures for their programs, but I don't think it's useful in a majority of cases

Why would libraries be more common in Rust than C?

Use of libraries may be more common in rust than c because of many possible factors:

1. Rust's standard library is large and contains data structures. People are good at centralizing on one thing if it's the standard one, if there are 10 competing string libraries, people might say "ah well, let's write our own". That also sometime means using one dependency will pull in others (e.g. in C you might want someone's regex library, but it might be incompatible with your string library because it uses a different one. A stdlib helps ensure libraries have a standard set of types to talk about, and C barely has that).

2. Rust's package manager (cargo) and registry (crates.io) are really good and making finding and adding dependencies much easier. If I want to add a random library on github to my rust project, it's 1 line in my Cargo.toml (whether it's on crates or not). In C, I have to figure out if they're using cmake, meson, autotools, or any of a dozen other things, and possibly vendor the code into a third_party folder, and possible spend several hours hacking on my build system to link against it.

3. Rust's community has made an effort to standardize on certain crates and include their use. See the rustlang nursery. The closest to this in C is stuff like the gnulib I think, which is an ancient effort pushing garbage code that suffers from the lack of good dependency management severely. I know of no recent similar efforts for C.

4. Rust has generics and a better type system in general which makes it much easier to implement generally usable libraries.

It's important to remember that C also predates the internet, and many c codebases also predate modern package management. Legacy practices have a habit of propagating themselves.

No, it's not harder than in C++. Compare: https://gist.github.com/stjepang/07fbf88afa824e11796e51ea2f6... , https://gist.github.com/stjepang/fc20ea97030a2153148117dddeb... . In Rust, it even works faster (with array bounds check!).

Please just use an `Option<usize>`, not that wonky NULL thing.

If you're worried about the slightly more memory that uses, you can use `Option<NonZeroUsize>` and subtract 1 for all indexing operations.

klib's kbtree header/macro library seems to provide rather nice B-trees in C.

https://github.com/attractivechaos/klib/blob/master/kbtree.h

I think that TL;DR misses lots of nuance; I'd suggest a better TL;DR would be "the features and idioms of different languages can lead to different preferred solutions to the same problems, which means that we should be careful not to unnecessarily restrict our perception of new languages in terms of the familiar idioms of old ones." Or maybe: "performance benchmarks are hard, and even carefully-crafted comparisons can miss the point if they paper over important practical implementation concerns; an apples-to-apples comparison can unintentionally mislead if it precludes the consideration that perhaps what you actually wanted was an orange after all". Importantly, the article explains why Rust is faster on this specific benchmark, but goes out of its way to note that benchmarks should always be interpreted with appropriate caution, and that nobody should come away with the notion that this implies any sort of strict dominance of Rust over C.

So it's called "The relative performance of C and Rust" to put the emphasis on the data structures? :)

As suggested in the introduction, one would think it was called "the relative performance of C and Rust" because this article is a corollary to a previous article and conceived as a response to an inquiry regarding that previous article--specifically, to answer the question "in your given benchmark, what explains the relative performance of C and Rust?" :P The basic answer: "data structures"; the insightful answer: "data structures that were originally chosen to play to the different strengths and weaknesses of their respective implementation languages, giving us food for thought as to how language design can shape the solutions that users of that language will tend to arrive at, and the performance implications thereof".

Obviously Why Rust BTreeMaps beat C AVL Trees is way too-long and misleading a title ;-)

Just because that would indeed focus on the specific sub-portion of the article that you think is most important, doesn't necessarily make it better than a title that meant to encompass the issues surrounding whole act of benchmarking, specifically between languages that might encourage different idiomatic solutions, and then drills down to what that means in this specific instance.

In other words, what you took away from the article might not have been what other people did, or what the author meant to express. It surely wasn't what I thought was important (but neither was "rust is faster/slower than C").

Might there be a C library that could be used?

https://old.reddit.com/r/programming/comments/9jsqb3/the_rel...

Reply on news.ycombinator.com