grovesNL

6 ms·

1. 31.▲
   by grovesNL 2y ago

   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 fast
2. 32.▲
   by grovesNL 2y ago

   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 applicatio
3. 33.▲
   by grovesNL 2y ago

   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 ten
4. 34.▲
   by grovesNL 2y ago

   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.,
5. 35.▲
   by grovesNL 2y ago

   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 o
6. 36.▲
   by grovesNL 2y ago

   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 promis
7. 37.▲
   by grovesNL 2y ago

   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 w
8. 38.▲
   by grovesNL 2y ago

   Thanks, I'll take a look! It sounds like they're similar problems.
9. 39.▲
   by grovesNL 2y ago

   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
10. 40.▲
    by grovesNL 2y ago

    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.
11. 41.▲
    by grovesNL 2y ago

    I'm interested in both, but quickly finding the nearest gaps of at least duration X is most important.
12. 42.▲
    by grovesNL 2y ago

    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.
13. 43.▲
    by grovesNL 2y ago

    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 `B
14. 44.▲
    by grovesNL 2y ago

    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&#x27
15. 45.▲
    by grovesNL 2y ago

    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.
16. 46.▲
    by grovesNL 2y ago

    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 loo
17. 47.▲
    by grovesNL 2y ago

    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
18. 48.▲
    by grovesNL 2y ago

    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
19. 49.▲
    by grovesNL 2y ago

    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 minimu
20. 50.▲
    by grovesNL 2y ago

    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 d
21. 51.▲
    by grovesNL 2y ago

    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?
22. 52.▲
    by grovesNL 2y ago

    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 a
23. 53.▲
    by grovesNL 2y ago

    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 gues
24. 54.▲
    by grovesNL 2y ago

    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
25. 55.▲
    by grovesNL 2y ago

    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
26. 56.▲
    by grovesNL 2y ago

    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.
27. 57.▲
    Ask HN: Fast data structures for disjoint intervals?

    185 points by grovesNL 2y ago|119 comments
28. 58.▲
    by grovesNL 3y ago

    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
29. 59.▲
    by grovesNL 4y ago

    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).
30. 60.▲
    by grovesNL 4y ago

    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/professiona