I find that weighted_g_order runs particularly slowly. Is this normal？

[cheenyuee]

I find that weighted_g_order runs particularly slowly. Is this normal？

[brc7]

Apologies for the late response, but yes this is expected. I profiled this a while back and the issue is the priority queue. Regular g-order can use a special priority queue implementation that benefits from the assumption that all of the increments / values are the same.

The weighted queue cannot make this assumption (and the C++ standard queues are deficient in a couple important ways, such as memory efficiency and the ability to iterate over the queue). There's likely some easy headroom, as I did not attempt to optimize the runtime of weighted g-order. Happy to follow up if desired.

[cheenyuee]

Apologies for the late response, but yes this is expected. I profiled this a while back and the issue is the priority queue. Regular g-order can use a special priority queue implementation that benefits from the assumption that all of the increments / values are the same.

The weighted queue cannot make this assumption (and the C++ standard queues are deficient in a couple important ways, such as memory efficiency and the ability to iterate over the queue). There's likely some easy headroom, as I did not attempt to optimize the runtime of weighted g-order. Happy to follow up if desired.

Thanks for your reply. So, if I do weighted_g_order under 10M data scale, how long it will takes perhaps? several hours or several days?

[brc7]

If I do weighted_g_order under 10M data scale, how long it will take?

I'd guess hours, but probably less than a day. Unfortunately, it's been a few years since I ran the experiments on 1M (and I can't find the logs that would tell me how long the weighted ordering took). I remember it being 3-4x as long as regular g-order, though. Did you try benchmarking on a small dataset (e.g. a 1M or 500k subset)? I'm happy to revisit the performance if you'd like to try out the method and the reorder time is a bottleneck.

Also, just an FYI - we have a nicer codebase with improved Python bindings here: https://github.com/BlaiseMuhirwa/flatnav-experimental