Fast linked lists

It strikes me the bottleneck for this problem isn&#x27;t Vec or List, it&#x27;s the serde_json Value type that needs to be used. This is useful for serializing&#x2F;deserializing values into Rust types but if you&#x27;re trying to validate JSON against a schema you don&#x27;t actually need the JSON value data, just the types of the nodes (or more specifically, you only need <i>some</i> of the value data, and probably not much of it, so don&#x27;t pay for it when you don&#x27;t have to).<p>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&#x2F;end of a token) then you can collect your error messages very, very quickly and generate the error message once validation is finished.<p>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&#x27;s compact and easy to access&#x2F;manipulate.<p>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&#x27;t need it.

The &quot;maybe you don&#x27;t need a linked list&quot; proposal at the bottom seems significantly better than the options presented in the post:<p>- almost no cost in the non-erroring path<p>- no extra data structures to manage<p>- a lot less code<p>I think the post would benefit from a better analysis of why this doesn&#x27;t work for them.

Nice post, Dmitry!<p>Two suggestions: it’s not immediately obvious whether subsequent benchmark result tables&#x2F;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?<p>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 <i>guaranteed</i> that it’s a bad choice unless you’re validating an empty, invalid object.)<p>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 <i>isn’t</i> 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).<p>(Edit: I do wonder if you can still use serde and serde_json but use the deserialize module’s `Visitor` trait&#x2F;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.)<p>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!

7-8 years ago I created GlueList (<a href="https:&#x2F;&#x2F;github.com&#x2F;ertugrulcetin&#x2F;GlueList">https:&#x2F;&#x2F;github.com&#x2F;ertugrulcetin&#x2F;GlueList</a>) in order to build faster version of LinkedList + ArrayList. It was a fun effort.

Intrusive linked lists might bring down the allocations further, reduce the memory footprint, &amp; more importantly improve locality when doing pointer chasing (single predictable indirection vs double hard-to-predict indirection).

&gt; 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.<p>I beg to disagree.<p>In kernels, drivers, and embedded systems they are <i>very</i> common.

Linked list benchmarks are amazing.... if you don&#x27;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&#x27;t get populated 100% consecutively, and thus can be anywhere in memory.

Another 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.

I was hoping to see optimization of the actual linked list manipulation and traversal (pipelining? i&#x27;m not sure what you&#x27;d do), but this is still a neat post. It&#x27;s cool to see thought put into various parts of the problem, like reallocation&#x2F;preallocation, stack allocation, etc.

Link lists can move items in O(1) but their O(N) search can be bad because of all of the cache line misses.

Linked lists get a bum rap.<p>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&#x27;re doing lots of O(n) deletions that would be O(1) with a linked list.<p>But that doesn&#x27;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&#x27;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 &quot;natural&quot; 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&#x27;t mean you won&#x27;t ever want to do different iterations.<p>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&#x27;s a waste of time to learn how to manipulate linked lists anymore.<p>I guess a lot of this is probably due to the popularity of high level languages, where you&#x27;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 <i>overhead</i> 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.<p>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&#x27;ll be iterating that list frequently, then the vector may very well be a good idea. If it&#x27;s just for error cases or slow paths, then linked lists really aren&#x27;t bad at all.<p>I&#x27;m not trying to argue <i>for</i> linked lists here so much as arguing against the blanket arguments against them.<p>&lt;&#x2F;rant&gt;

Linked lists are often the wrong choice because they&#x27;re rarely performant or efficient when compared to vecs in the real world.<p>In general, use vecs until you absolutely can&#x27;t.<p>Perhaps there are a few uses for LL&#x27;s in limited circumstances.

Wouldn&#x27;t using push_back prevent the need to reverse the Vec at the end?

This article is disingenuous with its Vec benchmark. Each call to `validate` creates a new Vec, but that means you allocate + free the vec for <i>each</i> 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, &#x27;linked lists faster than vec&#x27;, but you had to engineer the vec example to be worse. Maybe I&#x27;m being cynical.<p>It would be interesting to see the performance of a `Vec&lt;&amp;str&gt;` where you reuse the vector, but also a `Vec&lt;u8&gt;` where you copy the path bytes directly into the vector and don&#x27;t bother doing any pointer traversals. The example path sections are all very small - &#x27;inner&#x27;, &#x27;another&#x27;, 5 bytes, 7 bytes - less than the length of a pointer! storing a whole `&amp;str` is 16 bytes per element and then you have to rebuild it again anyway in the invalid case.<p>---<p>This whole article is kinda bad, it&#x27;s titled &#x27;blazingly fast linked lists&#x27; which gives it some authority but the approach is all wrong. Man, be responsible if you&#x27;re choosing titles like this. Someone&#x27;s going to read this and assume it&#x27;s a reasonable approach, but the entire section with Vec is bonkers.<p>Why are we designing &#x27;blazingly fast&#x27; 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:<p>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 (???)<p>2. this is really slow for obvious reasons, how about we: pull in a whole new dependency (&#x27;imbl&#x27;) that attempts to optimize for the general case using complex trees (???????????????)<p>You also mention:<p>&gt; In some scenarios, where modifications occur way less often than clones, you can consider using Arc as explained in this video<p>I understand you&#x27;re trying to be complete, but &#x27;some scenarios&#x27; is doing a lot of work here. An Arc&lt;[T]&gt; approach is <i>literally</i> just the same as the naive approach <i>but</i> with extra atomic refcounts! Why mention it in this context?<p>You finally get around to mutating the vector + using it like a stack, but then comment:<p>&gt; However, this approach requires more bookkeeping and somewhat more lifetime annotations, which can increase code complexity.<p>I have no idea why you mention &#x27;code complexity&#x27; here (complexity introduced <i>by rust</i> and its lifetimes), but fail to mention how adding a dependency on &#x27;imbl&#x27; is a negative.

this is interesting!