HNHacker News
TopNewBestAskShowJobs

grovesNL

267 karma · joined February 8, 2017

Email: josh@joshgroves.com
submissionscomments
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Right, this calculation runs on the client and assumes the clients are fast enough. This helps a lot with interactivity because the network stack isn’t involved at all.

It could be interesting to optionally offload some compute to much faster servers when it would be useful, but that introduces request/response latency overhead too.

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
In this specific case, it’s part of an automatic scheduler that performs hundreds of thousands of range queries in a real-time interactive use case, so small improvements here can make a huge difference to the overall feel of the application. A lot of scheduling applications take seconds or minutes to run queries like that, but that would be way too slow for real-time interactions like I’m doing.

The current approach I’m using takes tens of milliseconds for some large test cases (which is great!), however I’d like to improve on it more so I could eventually run much bigger cases at real-time interactive speeds too.

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
The rough numbers I’ve been using in my test cases are in the scale of thousands of relatively densely distributed intervals and hundreds of thousands of range queries. This is for a real-time interactive use case targeting the range of tens of milliseconds or so (obviously depends on CPU, but ideally supporting the last couple generations or so). “Too slow” is the upper end of that range because it’s part of the critical path for interactions.

Slower writes with a dense representation like that would be great. The problem I’ve been seeing in my prototypes is that querying the slots back tends to be about the same performance as the ordered map. Some people mentioned a variation on this idea that would store some coarser-grained statistics based on minimum duration in certain regions which might help a bit.

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
I have (start time, duration) tuples but would like to find the nearest entries (in either direction) given a specific time and minimum duration.

Thanks for the suggestion! I've tried some other spatial acceleration structures (e.g., R-tree and some others) and applying them in 1-d but they didn't outperform the ordered map unfortunately. It could be interesting to try out KD trees at some point though.

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
I'm storing free slots right now, but either would be ok if a data structure would benefit from the other representation.

The slow cases usually tend to be trying to find wider slots and skipping through many smaller slots. There are often a lot of bookings up to the first wide enough slot too though, so it's a little bit of both.

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Thanks for the ideas! I did try lzcnt/tzcnt with bitshifts to find contiguous intervals across elements, but I found that it tended to be more expensive than searching the map depending on the density. I think it's a really promising approach though, and I've like to figure out a way to make it work better for my test case.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Thanks! This sounds very similar to the experiment I tried with sieve-tree (https://github.com/Ralith/sieve-tree/) which can store children directly on a node until it reaches some threshold. I had some problems with the nearest query as you mentioned, because children are in arbitrary order and you might have to search multiple tree levels to find the nearest.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Thanks, I'll take a look! It sounds like they're similar problems.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
I did some simple benchmarks of a `Vec<(u32, u32)>` to a `BTreeMap<u32, u32>` for the test case and found them to be roughly comparable. The intervals are relatively dense so I was hoping for the vector to perform better than it did.

The binary search was useful to find the start position if there are more than a few hundred elements or so (whatever the breakeven point for linear search vs. binary search is on your CPU).

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
That's definitely possible and could be a reasonable tradeoff. I'd be slightly worried about the extent that it sacrifices write performance, but it might not be too bad if if the number of levels are kept small.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
I'm interested in both, but quickly finding the nearest gaps of at least duration X is most important.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Definitely possible! I tried doing something similar which stored the ranges in a single `Vec<(u32, u32)>` but found the performance a bit worse than just using the ordered map.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Thanks, I had a similar idea and tried this with Meta's `sorted_vector_map` (https://github.com/facebookexperimental/rust-shed/tree/main/...) but found the performance to be slightly worse than a `BTreeMap<u32, u32>` for my test case. I did try to change it a bit to do fewer binary searches (`range` tried to find the end immediately) but the binary searches seemed to be slightly worse than finding starting intervals in the map.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Thanks! I did try a 1-dimension R-tree but the performance tended to be much worse than an ordered map.

Priority trees could be really interesting. I did consider them early on but wasn't sure how well they'd apply here, so I'll take another look.

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Thanks, I came across some of Erik's videos in my research but I didn't realize they were part of a bigger series focused on ranges. Cascading methods are exactly the kind of ideas I'm thinking about.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
I did look at QBVH and flattening it to a single dimension, but my understanding is that most specialized BVHs like this prefer mostly static geometry because updates are so expensive. I'd be happy to be wrong on this though - QBVH looked complicated enough that I didn't want to experiment with it without some strong signals that it would be the right direction.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Interesting, thanks! It makes sense that OR-Tools would have something similar. I wonder if they have an explanation behind using `std::vector` vs. some other data structures. I could imagine `std::vector` doing pretty well but in practice I found vectors (Rust's `Vec` in my case) to be roughly on par with the ordered map I'm using. Obviously it can vary depending on how widely it has to binary search.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Exactly, intervals are disjoint and adjacent (automatically coalesced). The ordered map I'm using will coalesce them together which works pretty well. The problem is that I'd like to accelerate range queries even further, probably by excluding certain intervals with some acceleration structure on the side (e.g., skip any intervals with a duration less than X) at the cost of slightly more expensive updates.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
There are definitely a lot of similarities. I spent some time reviewing allocator designs to see if some ideas might carry over.

One problem I found is that a lot of allocators benefit from being able to track freelists based on some minimum sizes needed for allocations (e.g., https://github.com/sebbbi/OffsetAllocator). This problem is a bit different in that I want to know the first available block even though it might be much bigger than I need. Having multiple lists might still be useful though, but it's not as effective as how they're used in allocators - you'd usually need to search multiple freelists to know the first available instead of one.

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
I haven't tried roaring bitmaps on this problem yet. I think it's generally fairly dense so that's why I tried dense bitsets first, but it's a fair point. It might still be beneficial to go with a sparse representation depending on the interval lengths for example.

I also didn't have a good way to measure runs from roaring bitmap's Rust API (https://github.com/RoaringBitmap/roaring-rs/issues/274) which makes it hard to track interval duration, but would be interested to compare this approach.

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
I think this is an interesting idea. It might have some of the same problems as the dense bitset designs I've tried so far though but I'd like to try it out. Is there a detailed description of this anywhere?
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Thanks for the suggestion! I tried dense bitsets in an earlier iteration but the performance wasn't great, so I thought something like RoaringBitmap probably wouldn't work out very well. The ranges are relatively dense but there also aren't that many of them (only a few thousand or so), so the bitset seemed to spend a huge amount of time searching within elements.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
I tried a bitmask/bitset/bitvec but found the performance of searches to be a worse than the ordered map I'm using. Intuitively I expected it to perform slightly better for searches because of the cache efficiency, but I guess the way my ranges were distributed made it spend a lot of time searching within each element of the set. I'd like to revisit it eventually though because I think this direction is promising.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Definitely! It's a great idea and something I've been trying out. So far I've tested typical bounding volume hierarchies and spatial acceleration structures in 1-d (e.g, some of the cache friendly quadtree designs applied to 1d, r-trees, k-d trees) but they weren't able to outperform my simple ordered map yet unfortunately.
grovesNL··on Ask HN: Fast data structures for disjoint intervals?
Thank you! Absolutely, the problem I'm solving is closer to the resource-constrained project scheduling problem (RCPSP) but it's also closely related to job shop scheduling.

I've mostly focused on reducing the search space so far, but I've always wondered if there's a way to significantly accelerate range queries. My B-tree map implementation is already very fast in practice, but intuitively it seems like a data structure should be able to advantage of the fact that intervals are disjoint to greatly improve performance. For example, inversion lists take advantage of disjointedness to reduce storage cost - I'd like to do the same but for performance. Many range queries also have a minimum duration requirement, so it could be useful if a data structure could take advantage of this to quickly exclude intervals during the search.

grovesNL··on Ask HN: Fast data structures for disjoint intervals?
It seems like a good way to describe a common language around interval operations. I'd be interested in data structures that were specialized for some of these operations.
grovesNL··on Translating OpenStreetMap data to HTML5 Canvas with Rust and WebAssembly
It depends on the use case (e.g., how much you're interacting with web APIs) but I'd generally expect this to be the case for data processing at least.

During compilation from Rust to WebAssembly you have the opportunity to apply ahead-of-time optimizations that would be too expensive or impossible to apply to JavaScript during execution, so this can improve performance pretty significantly over JavaScript.

grovesNL··on Show HN: StratusGFX, my open-source real-time 3D rendering engine
Unfortunately WebGL2 doesn't support multi-draw indirect, shader storage buffers, or compute shaders (there was temporary experimental support for compute shaders but it's considered obsolete now).
grovesNL··on Don't call yourself a programmer, and other career advice (2011)
It depends on where they practice. In some countries, they should absolutely be worried about misrepresenting themselves as licensed engineers.

For example, in Canada, the title "engineer" is reserved for licensed/professional engineers, so it would be misleading to use the title "electrical engineer" if they're not actually licensed.

grovesNL··on Don't call yourself a programmer, and other career advice (2011)
That could be the case wherever you live, but this isn't true in general. The word "engineer" is protected title in some countries (without requiring additional qualification such as the word "professional" or "licensed").
← PreviousPage 2 of 4Next →