stjepang
Joined 10 years ago
Karma
168
Submissions
24
Member since
Jun 7
Recent submissions
Comment · 6 years ago
https://docs.rs/async-compat
Comment · 6 years ago
Right, there is a way - to escape braces and print "text {value}" rather than the actual value, you'd use "text {{value}}"
Comment · 6 years ago
This is being worked on: https://github.com/rust-lang/rust/issues/67984
Comment · 6 years ago
Hi there, thought I might chime in as someone who used to work on tokio and is now working on async-std and smol. :)
A month ago I wrote a blog post about the evolution of async Rust and its async runtimes. Hopefully this answers your questions!
https://stjepang.github.io/2020/04/03/why-im-building-a-new-...
Comment · 8 years ago
Why does option #3 look non-ideal, what are your concerns with it?
Comment · 8 years ago
I'd like to read more about those soundness issues - do you have a link?
Comment · 8 years ago
Yes, it is. But why 'the worst' aspects of each, though? I see it as the opposite: linked lists built on top of vectors combine good cache efficiency of vectors with algorithmic benefits of linked lists (many operations become O(1), or at least in the amortized sense).
Of course, arenas do have tradeoffs - I'll try to summarize.
Pros:
- Completely safe.
- More ergonomic than dealing with `Rc<RefCell<T>>`.
- Improved cache efficiency of linked data structures.
- Fast node allocation and deallocation.
Cons:
- Any two simultaneous node accesses must be immutable.
- Accessing a node incurs the cost of a bound and liveness check.
- Vector growth can be costly and cause a spike in latency.
- Vector growth moves all nodes in memory.
- Removing a node creates a hole in the vector, possibly wasting memory.
Generally speaking, I think anyone learning Rust and trying to implement a graph data structure should first do it on top of a vector. It's easier than other commonly suggested approaches and it's not a bad one either. In fact, that's how rustc builds some of its data structures, how conrod (a GUI toolkit) represents its widget graph, and how Way Cooler (a window manager) manages window tilings.
Comment · 8 years ago
But... doubly-linked lists and graphs are easy in Rust! :) Here are a few examples.
Doubly-linked list: https://github.com/stjepang/vec-arena/blob/master/examples/l...
Splay tree: https://github.com/stjepang/vec-arena/blob/master/examples/s...
Comment · 9 years ago
It's fairly easy to do this kind of thing using an arena and indices instead of pointers. Here's a simple splay tree with uplinks implemented this way:
https://github.com/stjepang/vec-arena/blob/master/examples/s...
Comment · 9 years ago
No, the time complexity is the same: O(n log n). The author of the top answer links to his book, where you can find a proof of time complexity:
https://sites.google.com/site/algoxy/home/elementary-algorit...
Comment · 9 years ago
Absolutely - there are cases when branch misprediction is not the bottleneck. It depends on a lot of factors.
Another such case is when sorting strings because every comparison causes a potential cache miss and introduces even more branching, and all that would dwarf that one misprediction.
Comment · 9 years ago
Basically all comparison-based sort algorithms we use today stem from two basic algorithms: mergesort (stable sort, from 1945) and quicksort (unstable sort, from 1959).
Mergesort was improved by Tim Peters in 2002 and that became timsort. He invented a way to take advantage of pre-sorted intervals in arrays to speed up sorting. It's basically an additional layer over mergesort with a few other low-level tricks to minimize the amount memcpying.
Quicksort was improved by David Musser in 1997 when he developed introsort. He set a strict worst-case bound of O(n log n) on the algorithm, as well as improved the pivot selection strategy. And people are inventing new ways of pivot selection all the time. E.g. Andrei Alexandrescu has published a new method in 2017[1].
In 2016 Edelkamp and Weiß found a way to eliminate branch mispredictions during the partitioning phase in quicksort/introsort. This is a vast improvement. The same year Orson Peters adopted this technique and developed pattern-defeating quicksort. He also figured out multiple ways to take advantage of partially sorted arrays.
Sorting is a mostly "solved" problem in theory, but as new hardware emerges different aspects of implementations become more or less important (cache, memory, branch prediction) and then we figure out new tricks to take advantage of modern hardware. And finally, multicore became a thing fairly recently so there's a push to explore sorting in yet another direction...