4 ms·

TL;DR: Using dtrace to analyze the performance of AVL Trees in C vs BTreeMaps&HashMaps in Rust. Spoilers: Rust wins every time, and you should rewrite your soft

• dxhdr 8y ago
  I thought the tl;dr was: Implementing B-trees as an embeddable library in C is hard, therefore Rust is faster.
  • kenhwang 8y ago
    Rust makes hard problems easier, but easy problems harder. BTrees are a great example of that sentiment.
    • TheDong 8y ago
      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!
      • paulddraper 8y ago
        The problem that Rust makes hard: linked lists.
        • Animats 8y ago
          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.
          • Rusky 8y ago
            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."
            • nixpulvis 8y ago
              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.
            • acjohnson55 8y ago
              They're routine in CS classes. Curiously, I've never needed to use them in real life.
              • btmorex 8y ago
                Except really common things like LRU caches use them.
                • chousuke 8y ago
                  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
  • namibj 8y ago
    klib's kbtree header/macro library seems to provide rather nice B-trees in C. https://github.com/attractivechaos/klib/blob/master/kbtree.h https://github.com/attractivechaos/klib/blob/master/kbtree.h
  • kibwen 8y ago
    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.
    • igouy 8y ago
      So it's called "The relative performance of C and Rust" to put the emphasis on the data structures? :)
      • kibwen 8y ago
        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".
        • igouy 8y ago
          Obviously Why Rust BTreeMaps beat C AVL Trees is way too-long and misleading a title ;-)
  • igouy 8y ago
    Might there be a C library that could be used? https://old.reddit.com/r/programming/comments/9jsqb3/the_relative_performance_of_c_and_rust/e6umut4/?st=jmo70uic&sh=d3f0d1cf https://old.reddit.com/r/programming/comments/9jsqb3/the_rel...
• nostrademons 8y ago
  Note that the data structure is different: AVL trees vs. BTrees. The interesting part for me was that because of modern cache hierarchies, BTrees appear to be superior than AVL trees even for in-memory data structures, while before I'd thought of them as a special-purpose on-disk data structure for databases.
  • rdtsc 8y ago
    Makes total sense. The insight is that the memory acts like the disk used to and the caches act like the memory. BTrees worked well for spinning disk because they'd nicely load a whole array (node) of BTree child pointers in one disk read. But the same works for caches, they'd load the the whole array of into the cache when the first one is accessed. A silly idea I had, wonder if it would be possibly to auto-adjust the B factor of a BTree (the number of nodes) at runtime based the cache line size.
    • fulafel 8y ago
      Auto adjusting would be interesting, even better (though harder) would be to do it experimentally rather than based on cache line size. Cache line size only determines the minimum block size that doesn't waste cache capacity, after all.
  • klodolph 8y ago
    AVL trees were more competitive when memory was more shallow. These days an L1 cache hit is dirt cheap and a RAM fetch is ~200x as expensive, following a pointer creates a data dependency. B-trees give you more L1 cache hits and fewer pointers to follow. Back in the 1990s the cache hits and RAM fetches were much closer to parity and there weren't as many pipeline stages to fill so data dependencies weren't as important. Go back even farther and you have completely uniform memory that could be accessed in a fixed number of cycles no matter what the address. There are a lot of good books from these eras, and there are a lot of good books that teach with the uniform memory model. Most algorithms classes don't talk about the hierarchy at all (even though it distorts the true asymptotic runtime of many algorithms).