this is interesting!
Fast linked lists
11–20 of 131 posts
Re: Fast linked lists
#12Another 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.
Re: Fast linked lists
#13The "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.
Re: Fast linked lists
#14It 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.
Re: Fast linked lists
#15[flagged]
Re: Fast linked lists
#16Linked 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.
Most 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.
How 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).
Re: Fast linked lists
#17Earlier quoted context omitted.
Most 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.
How 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).
SBCL tries its hardest to allocate sequentially, then moves lists to be sequential in GC.
Re: Fast linked lists
#18Wouldn't using push_back prevent the need to reverse the Vec at the end?
Re: Fast linked lists
#19[flagged]
I 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. :)
Re: Fast linked lists
#20[dead]