12 ms·
Fast linked lists
- ertucetin 2y ago7-8 years ago I created GlueList (https://github.com/ertugrulcetin/GlueList https://github.com/ertugrulcetin/GlueList) in order to build faster version of LinkedList + ArrayList. It was a fun effort.
- boxed 2y agoI believe that's called a "rope"
- amelius 2y agoIt was fun because you didn't write it in Rust :) https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/
- duped 2y agoIf I have this right, what you've built is this, storing M items in M / N nodes where N is the radix of the array? 0 1 M / Nth node [ N elem ] [.] -> [N elem] [.] -> .... -> [M - (M / N) elem] [null] And so if you want to index the `i`th element you chase the pointers index (node i) : acc = 0 while acc + N < i acc += N node = node.next return node.array[j - acc] Or something like that? You can do better using a B tree and exploit the fact that you don't need keys to just store pointers in the branch nodes. This reduces the number of pointer dereferences in large arrays. For example say you have N = 8 and there are 1024 elements in the list, you would need 127 pointer dereferences to reach the end of the array. In a B-tree you only have 3. (double check my math, I might be off by one). This is the typical implementation for immutable/persistent vector types. If you keep the links between leave nodes at the bottom of the tree, you've got a B+ tree and have fast iteration through it as well.
- ertucetin 2y agoYou're probably right, I was in college back then and wanted to work on something cool, this was my idea.
- twic 2y agoSimilar to an unrolled linked list: https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list But you size the nodes dynamically, rather than using a fixed size.
- kevingadd 2y agoI was hoping to see optimization of the actual linked list manipulation and traversal (pipelining? i'm not sure what you'd do), but this is still a neat post. It's cool to see thought put into various parts of the problem, like reallocation/preallocation, stack allocation, etc.
- cogman10 2y agoreallocation/preallocation actually does increase manipulation and traversal performance. The major slowness of linked lists is cache inconsistency. New nodes can be put all over the memory space. However, if you can make sure all or part of the list exists in contiguous blocks of memory, then there's a good chance that when the CPU loads up the next node it will also grab the next 3 nodes in a cache line. The closer these node addresses are in memory, the faster things will be.
- vlovich123 2y agoIntrusive linked lists might bring down the allocations further, reduce the memory footprint, & more importantly improve locality when doing pointer chasing (single predictable indirection vs double hard-to-predict indirection).
- kolbe 2y agoLinked list benchmarks are amazing.... if you don't thrash your cache on inserts so all its elements are contiguous. You get all the benefits of a vector and a linked list, without the reality that linked lists mostly don't get populated 100% consecutively, and thus can be anywhere in memory.
- bjoli 2y agoMost languages with linked lists as an important part (lisps mostly) all have well optimized linked lists that end up with a lot better memory locality.
- wavemode 2y agoHow does that work? I don't follow how any runtime or compile-time optimization can solve the problem of locality for a linked list. If the data wasn't allocated sequentially, then it's simply not going to be sequential (unless you move it).
- hayley-patton 2y agoSBCL tries its hardest to allocate sequentially, then moves lists to be sequential in GC.
- jkaptur 2y agoAnother cool aspect of this and (if I understand correctly), where Rust really helps you is that you can explore multiple branches in parallel, since the linked list is immutable.
- eimrine 2y agoWhat if the linked list is cycled or doubly-linked?
- amelius 2y agoThen Rust isn't the right tool for the job. Rust is great for tree-like structures which is 99% of what you encounter anyway. Unless you're writing a kernel or something.
- jkaptur 2y agoI was talking about this case in particular, where we know the list is basically isomorphic to the call stack.
- ComputerGuru 2y agoTo be fair, lack of concurrency safety never stopped C and C++ devs from boldly doing just that, anyway!
- ILoveQaWolf 2y agothis is interesting!
- evmar 2y agoThe "maybe you don't need a linked list" proposal at the bottom seems significantly better than the options presented in the post: - almost no cost in the non-erroring path - no extra data structures to manage - a lot less code I think the post would benefit from a better analysis of why this doesn't work for them.
- vouwfietsman 2y agoIndeed, also building a linked list over the stack like that is a crafty but very weird design. Keep it simple.
- dmitry_dygalo 2y agoIndeed, I agree with your points. This idea was added after I wrote the post and wasn't taken from my own optimization efforts in `jsonschema`. Originally, in `jsonschema` the output type is actually a badly composed iterator and I intended to simplify it to just a `Result<(), ValidationError>` for the article, but with this output, there are actually way better optimizations than I originally implemented. If I'd discovered this idea earlier, I'd probably spend more time investigating it.
- duped 2y agoIt strikes me the bottleneck for this problem isn't Vec or List, it's the serde_json Value type that needs to be used. This is useful for serializing/deserializing values into Rust types but if you're trying to validate JSON against a schema you don't actually need the JSON value data, just the types of the nodes (or more specifically, you only need some of the value data, and probably not much of it, so don't pay for it when you don't have to). If you implemented your own parser for the schema and the JSON and only used an AST to validate + span information (which can just be a pair of u16s for start/end of a token) then you can collect your error messages very, very quickly and generate the error message once validation is finished. Heavily optimized compilers will do this for semantic analysis and type checking, where the IR they use can be constructed quickly and then used with the input text to get helpful messages out, while the guts of the algorithm is only working with semantic information in a structure that's compact and easy to access/manipulate. All that said, serde_json is incredibly convenient and giving up to write your own parser is a big hammer for a problem that probably doesn't need it.
- EGreg 2y agoJust use capn’proto. No deserialization needed !
- aabhay 2y agoWhats your experience like using it? Is it ergonomic or does it require you to do lots of type gymnastics?
- cabronerp 2y agoThis repo has a nice pub/sub implementation based on capnp: https://github.com/commaai/cereal/blob/master/log.capnp https://github.com/commaai/cereal/blob/master/log.capnp
- ComputerGuru 2y ago> All that said, serde_json is incredibly convenient and giving up to write your own parser is a big hammer for a problem that probably doesn't need it. I had a thought in my reply [0] on this that actually might let him eat his cake and have it too in this regard. I think you can heavily abuse serde::de::Visitor to schema validate without actually parsing (or with less parsing, at any rate). I went into more detail in my comment but I wanted to ping you (@duped). [0]: https://news.ycombinator.com/item?id=40357159 https://news.ycombinator.com/item?id=40357159
- varispeed 2y ago[flagged]
- actionfromafar 2y agoI often think about this - my pet theory is that the kinds of smart people who can create new languages don't have a problem with a new syntax. While us plebes struggle, learning both new concepts and new syntax at the same time. :)
- dymk 2y agoOpposite for me; I can read C/C++ fine including messy template code, but Rust's syntax is overall easier for me to read, and has a much simpler grammar.
- thewakalix 2y agoWouldn't using push_back prevent the need to reverse the Vec at the end?
- sanjay_0508 2y ago[dead]
- ComputerGuru 2y agoNice post, Dmitry! Two suggestions: it’s not immediately obvious whether subsequent benchmark result tables/rows show deltas from the original approach or from the preceding one (it’s the latter, which is more impressive). Maybe call that out the first couple of times? Second, the “using the single Vec but mutating it” option would presumably benefit from a reserve() or with_capacity() call. Since in that approach you push to the vector in both erroring and non-erroring branches, it doesn’t have to be exact (though you could do a bfs search to find maximum depth, that doesn’t strike me as a great idea) and could be up to some constant value since a single block memory allocation is cheap in this context. (Additionally, the schema you are validating against defines a minimum depth whereas the default vec has a capacity of zero, so you’re guaranteed that it’s a bad choice unless you’re validating an empty, invalid object.) But I agree with the sibling comment from @duped that actually parsing to JSON is the biggest bottleneck and simply parsing to the minimum requirements for validation would be far cheaper, although it depends on if you’ll be parsing immediately after in case it isn’t invalid (make the common case fast, assuming the common case here is absence of errors rather than presence of them) or if you really do just want to validate the schema (which isn’t that rare of a requirement, in and of itself). (Edit: I do wonder if you can still use serde and serde_json but use the deserialize module’s `Visitor` trait/impl to “deserialize” to an enum { Success, ValidationError(..) }` so you don’t have to write your own parser, get to use the already crazy-optimized serde code, and still avoid actually fully parsing the JSON in order to merely validate it.) If this were in the real world, I would use a custom slab allocator, possibly from storage on the stack rather than the heap, to back the Vec (and go with the last design with no linked lists whatsoever). But a compromise would be to give something like the mimalloc crate a try!
- dmitry_dygalo 2y agoThanks! > Two suggestions: it’s not immediately obvious whether subsequent benchmark result tables/rows show deltas from the original approach or from the preceding one (it’s the latter, which is more impressive). Maybe call that out the first couple of times? Agree! > Second, the “using the single Vec but mutating it” option would presumably benefit from a reserve() or with_capacity() call. Since in that approach you push to the vector in both erroring and non-erroring branches, it doesn’t have to be exact (though you could do a bfs search to find maximum depth, that doesn’t strike me as a great idea) and could be up to some constant value since a single block memory allocation is cheap in this context. (Additionally, the schema you are validating against defines a minimum depth whereas the default vec has a capacity of zero, so you’re guaranteed that it’s a bad choice unless you’re validating an empty, invalid object.) Oh, this is a cool observation! Indeed it feels like `with_capacity` would help here > But I agree with the sibling comment from @duped that actually parsing to JSON is the biggest bottleneck and simply parsing to the minimum requirements for validation would be far cheaper, although it depends on if you’ll be parsing immediately after in case it isn’t invalid (make the common case fast, assuming the common case here is absence of errors rather than presence of them) or if you really do just want to validate the schema (which isn’t that rare of a requirement, in and of itself). My initial assumption was that usually the input is already parsed. E.g. validating incoming data inside an API endpoint which is then passed somewhere else in the same representation. But I think that is a fair use case too and I was actually thinking of implementing it at some point via a generic `Json` trait which does not imply certain representation. > (Edit: I do wonder if you can still use serde and serde_json but use the deserialize module’s `Visitor` trait/impl to “deserialize” to an enum { Success, ValidationError(..) }` so you don’t have to write your own parser, get to use the already crazy-optimized serde code, and still avoid actually fully parsing the JSON in order to merely validate it.) Now when I read the details, it feels like a really really cool idea! > If this were in the real world, I would use a custom slab allocator, possibly from storage on the stack rather than the heap, to back the Vec (and go with the last design with no linked lists whatsoever). But a compromise would be to give something like the mimalloc crate a try! Nice! In the original `jsonschema` implementation the `validate` function returns `Result<(), ErrorIter>` which makes it more complex to apply that approach, but I think it still should be possible.
- tomck 2y agoThis article is disingenuous with its Vec benchmark. Each call to `validate` creates a new Vec, but that means you allocate + free the vec for each validation. Why not store the vec on the validator to reuse the allocation? Why not mention this in the article, i had to dig in the git history to find out whether the vec was getting reallocated. This feels like you had a cool conclusion for your article, 'linked lists faster than vec', but you had to engineer the vec example to be worse. Maybe I'm being cynical. It would be interesting to see the performance of a `Vec<&str>` where you reuse the vector, but also a `Vec<u8>` where you copy the path bytes directly into the vector and don't bother doing any pointer traversals. The example path sections are all very small - 'inner', 'another', 5 bytes, 7 bytes - less than the length of a pointer! storing a whole `&str` is 16 bytes per element and then you have to rebuild it again anyway in the invalid case. --- This whole article is kinda bad, it's titled 'blazingly fast linked lists' which gives it some authority but the approach is all wrong. Man, be responsible if you're choosing titles like this. Someone's going to read this and assume it's a reasonable approach, but the entire section with Vec is bonkers. Why are we designing 'blazingly fast' algorithms with rust primitives rather than thinking about where the data needs to go first? Why are we even considering vector clones or other crazy stuff? The thought process behind the naive approach and step 1 is insane to me: 1. i need to track some data that will grow and shrink like a stack, so my solution is to copy around an immutable Vec (???) 2. this is really slow for obvious reasons, how about we: pull in a whole new dependency ('imbl') that attempts to optimize for the general case using complex trees (???????????????) You also mention: > In some scenarios, where modifications occur way less often than clones, you can consider using Arc as explained in this video I understand you're trying to be complete, but 'some scenarios' is doing a lot of work here. An Arc<[T]> approach is literally just the same as the naive approach but with extra atomic refcounts! Why mention it in this context? You finally get around to mutating the vector + using it like a stack, but then comment: > However, this approach requires more bookkeeping and somewhat more lifetime annotations, which can increase code complexity. I have no idea why you mention 'code complexity' here (complexity introduced by rust and its lifetimes), but fail to mention how adding a dependency on 'imbl' is a negative.
- thefaux 2y ago> how about we: pull in a whole new dependency ('imbl') that attempts to optimize for the general case using complex trees (???????????????) To me this is a self answering question.
- torusle 2y ago> Linked lists are taught as fundamental data structures in programming courses, but they are more commonly encountered in tech interviews than in real-world projects. I beg to disagree. In kernels, drivers, and embedded systems they are very common.
- ComputerGuru 2y agoReally only because they’re so goddamn easy. I find myself using linked lists a lot less since adopting rust for embedded code (even with no_std and no allocator, but especially when alloc-only std data structures are within reach).
- saghm 2y agoMost people who take data structures courses or perform tech interviews don't end up working on kernels, drivers, or embedded systems though. To me, it sounds like the point being made is that there are a large number of programmers who have learned about linked lists but haven't run into many cases where they needed them in the world world, and I think it's accurate.
- dmitry_dygalo 2y agoThis was my intention
- SoftTalker 2y agoAgree, I can't recall using anything more complicated than lists/arrays or hash tables (key/value stores) in practice, in many years of (mostly web application) programming. And even those I'm not coding from scratch, I'm using classes or functions that my programming language gives me. For anything more complicated than that, I'm using a database, which of course is using many data structures under the covers but I don't directly touch those.
- sumtechguy 2y agoI used to use them all the time. However, now? I would be hard pressed to not use one of the many built in vector/list/dict/hash items in many languages now. I would have to be truly doing something very low level or for speed to use one.
- sfink 2y agoLinked lists get a bum rap. Yes, if you have a simple choice between a vector and a linked list, then the vector is vastly superior due to locality and (for non-intrusive linked lists) allocations. So much so that vectors often win even when you're doing lots of O(n) deletions that would be O(1) with a linked list. But that doesn't mean that linked lists are useless! A vector gives you a single ordering. What if you need multiple? What if you need a free list, which you're never going to be iterating over but will just grab off an item at a time? I find it quite common to have one "natural" order, for which I will use a vector (or equivalently, a bump allocator of fixed-size items), and then one or several auxiliary orders like the entries belonging to a particular owner or the ones that will need to be visited for some sort of cleanup or an undo list or some sort of stack or queue of pending items to process. Your common iteration will be in memory order, but that doesn't mean you won't ever want to do different iterations. It annoys me that this is always omitted, with the attitude that linked lists are obsolete and useless because vectors be moar better faster gooder, to the point that it's a waste of time to learn how to manipulate linked lists anymore. I guess a lot of this is probably due to the popularity of high level languages, where you're just dealing with references to everything in the first place. But in those, the arguments in favor of vectors are often not valid because that blessed golden vector of Objects is giving you no more locality than giving your Object a `next` field: the vector of Objects is represented internally as a vector of pointers to the actual Object data, so your oh so nicely cached lookups are doing memory reads that are 100% pure overhead compared to following a `next` link from an Object that fits into a cache line. In both cases, your performance is going to be limited by the locality of your Object data, which is the same whether you have a vector of pointers or Object data with an intrusive pointer. Also, if you have an existing setup and need to introduce a new list, it is sometimes far easier to drop in a `next` (and maybe `prev`) field than to refactor everything to accommodate a new vector. Especially since the vector will move all of your data when resizing the vector, which invalidates any pointers you might be using for other purposes. If you'll be iterating that list frequently, then the vector may very well be a good idea. If it's just for error cases or slow paths, then linked lists really aren't bad at all. I'm not trying to argue for linked lists here so much as arguing against the blanket arguments against them. </rant>
- PartiallyTyped 2y ago
- osigurdson 2y agoLink lists can move items in O(1) but their O(N) search can be bad because of all of the cache line misses.
- hi-v-rocknroll 2y agoLinked lists are often the wrong choice because they're rarely performant or efficient when compared to vecs in the real world. In general, use vecs until you absolutely can't. Perhaps there are a few uses for LL's in limited circumstances.