1. 66

  2. 36

    For example, in C I’d be tempted to reuse a buffer allocated for one purpose for another purpose later (a technique known as HEARTBLEED).

    Made me laugh.

    1. 2

      Me too, I think it’s a great article and some sprinkling of humor gave it a more personal touch.

    2. 6

      So this is just a small point, but it’s been bothering me.

      Any time the linked list thing is brought up, people always defending it by saying that “nobody should be using linked lists anyways and they’re slow”. However, don’t people use linked lists? It’s super common to have a tree structure with a parent pointer, is it not? That’s a linked list (except that a node can have multiple forward pointers), and thus, afaik, problematic in Rust. Don’t people see this? Or does Rust magically make doubly linked list OK if a node can have multiple forward pointers? Or do people just not use trees either “in the 21st century”?

      This also makes the argument that “Rust’s stdlib has linked list implementations so you don’t have to bother with it” moot. A “tree with a parent pointer” is almost never implemented as a generic datastructure; instead, you have a node struct with a children array and a parent pointer. That means you have to deal with the borrow checker’s limitations manually, right?

      1. 11

        I don’t find it particularly common, no. But the bias here is hard to dodge. Cyclic structures in Rust are mildly annoying, so Rust programmers tend to code in a way that doesn’t use them. Maybe by, for example, allocating things in contiguous storage and passing around indices into that storage as if those indices were pointers. That’s not to say that it can be used in all cases pointers can. Or that it has all of its benefits. But it’s pretty easy to do and works a lot of the time.

        I’m not a huge fan of the “shouldn’t be using linked lists” messaging, but there’s a kernel of truth to it. I mean, ripgrep uses a “linked list” for directory traversal for reusing gitignore matchers as it descends. I don’t think there’s any need for parent pointers there, so I just used reference counting. It wasn’t a big deal and it’s not in a hot path and it works really well.

        To a first approximation, “Rust discourages linked lists while C encourages them” is not that far off. I don’t think either is particularly wrong because not every use of a linked list is “wrong” from a performance perspective.

        1. 8

          Just as one isolated example, a few weeks ago, I was reviewing the source code of busybox’s grep implementation. It uses a linked list to store patterns from a file. There is assuredly no performance concern with using a linked list for this purpose, because, relative to other work that grep has to do, it’s almost certainly insignificant. That is to say, it doesn’t really matter what you do. Some kind of growable storage is just fine. In Rust code, the easiest thing to do here wouldn’t be a linked list, but rather a Vec of patterns. Does it matter? Nah, probably not.

          This example doesn’t cover parent pointers or anything like that. My only intention with showing this example is to show how different environments push us to do different things, and that my skew our perception of how prevalent certain data structures are. Linked lists are surely prevalent in C, but is that an inherent property of linked lists or a property of C and the environment provided to you?

          1. 1

            I think it’s one of the bits of folk wisdom that comes from repeating half-remembered facts. On modern hardware, pointer-chasing data structures are slow because cache misses can quickly dominate the access. That applies equally to random access in an array: replacing ‘pointer’ with ‘array index’ doesn’t make things any better and the requirement that you store things contiguously can also add copying overhead for resizes.

            Linked-list traversal is one of the worst things you can do on modern hardware, where a cache miss may cost hundreds of cycles and may occur on every node. Linear scanning of an array is vastly better because, even if it’s large and isn’t in the cache, the prefetcher will pull it all in for you. Using linked lists for stack-like things; however, is fine because you’re likely to keep the top few elements in the cache anyway and you can dynamically size whatever you’re doing.

            Anything that requires indirection eventually needs something pointer-like in it. Rust’s problem is that unique ownership is the only safe tool that they provide. For example, the Rust compiler’s control-flow graph representation uses an array of pointers to basic blocks and then stores indexes into that array for target blocks following a block’s terminator. You may choose to do something like that in C/C++ if you want a dense encoding (you’re unlikely to have more than 2^16 basic blocks in a function, so you can probably get away with a 16-bit index instead of a 64-bit pointer, if you want to optimise for memory size rather than performance), but it means that:

            • The Rust version is now effectively following two pointers instead of one, so has two opportunities for a cache miss. If the array is small, hopefully it will stay in L1, so you’re just burning a bit of cache.
            • There’s now no temporal memory safety. You can deallocate a block and allocate a new one at the same index in the array and now you have a use-after-free. It will be of the same type, so it’s equivalent to a UAF with a type-pooling allocator in C/C++, but would still generate the wrong output as the result of a memory-management bug.
          2. 2

            libc bends over backwards to make stdout and putc reasonably fast. Rust’s libstd has less magic, so I/O isn’t buffered unless wrapped in a BufWriter. I’ve seen people complain that their Rust is slower than Python, and it was because Rust spent 99% of the time flushing the result byte by byte, exactly as told.

            Huh, I experienced this when implementing writing to stdout for a rust program compiled to wasm. Every println call resulted in many calles to write with just a single byte each. I thought this was a quirk of the Rust wasm implementation not something more general.

            Although the print docs do indicate that “stdout is frequently line-buffered”.

            1. 8

              If println!("bar") does a write for each of b, a and r, then that sounds like a bug to me. It’s not doing that for me on Linux/x86_64. If you could get a small repro with WASM, then that might be a good bug report if you have the time!

              1. 2

                hey there burntsushi, this was over a year ago, still worth digging it up? if you’re not seeing the same might have just been early wasi/wasm build stuff.

                1. 5

                  Yeah to be honest, I’m not too knowledgeable about the wasi/wasm stuff, but if println! is doing a syscall for each byte in println!, that does seem like a serious bug.

                  1. 10

                    No dice

                    git clone git@github.com:maxmcd/single-bytes-poc.git
                    make run
                    docker build -t single-bytes-poc .
                    docker run -v $(pwd):/opt single-bytes-poc
                        Finished dev [unoptimized + debuginfo] target(s) in 0.01s
                    go: downloading github.com/bytecodealliance/wasmtime-go v0.24.0
                    called wasi_snapshot_preview1.fd_write()
                    Hello, world!

                    (that’s a single call to fd_write, not 14)

                    Might be misremembering (might have been a different language even) or it might just have been fixed.

                    1. 5

                      Great, thanks for checking in on it! Appreciate it.