41–50 of 131 posts
The "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.
It 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 fo…
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).
> 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.
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.
> 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.
> 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.
Out of all the programmers in the world, what percentage of them do you think work in the kernel/driver/embedded spaces?
Earlier quoted context omitted.
Why cant we 'simply' get processor extension to mark data as pointer so that the prefetcher would actually know what to fetch. From my understanding this is what led to the recent 'unpatchable' exploit in Apple's M1, but rather then trying to guess it by some heuristic, why not just give compilers option to make that optimization?
This was the idea of Itanium. It failed mostly because of economics. It turns out programmers, or rather their employers, don't really care about using hardware efficiency. They care about shipping things yesterday, because that's how business deals get closed, and making software efficient is secondary to money changing hands. Performance never really matters to business people after the checks are cashed. Multicore…
Earlier quoted context omitted.
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).
Instead of thinking of a linked list structurally, think of it functionally. You can have a token that represents a location in the linked list. From that token you have a Fetch() operation that will fetch what is at that location, a Next() operation that will fetch the next token or some indication that you are done, and depending on your language, some sort of insert or append operation (mutability factors in here)…
> 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.
> In kernels, drivers, and embedded systems they are very common. Out of all the programmers in the world, what percentage of them do you think work in the kernel/driver/embedded spaces?
The "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.
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` 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.