-
Notifications
You must be signed in to change notification settings - Fork 182
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Why is group
slow? Is it slow?
#33
Comments
Group is slower than it should be. I have some data now though. I fired up the This exercise is meant to remove costs associated with looking up different keys, and ask "if we pile all of the changes into just a few keys, how long does it take for each update?". It takes about 2.5us for each update, on average. Or, 2.5s for a batch of one million updates. These numbers aren't exactly accurate yet though, because each of the million "updates" are two changes, each of these input change usually results in two changes to the degrees (addition and retraction for the new and old source), which each usually result in two changes to the counts for each degree. So we may be working with as many as
or fourteen million updates across the computation. We can see how many updates survive merging and it seems to be about 3.6 million per round for these parameters, so perhaps the 2.5 seconds for everything should be read more as 700ns per update; it is less embarrassing at that point. That being said, it should be even lower. I got a breakdown of how long each
The The The Finally, the |
I think one of the problems here is that the collapsing and merging happens in a pessimal manner. Ideally when coming in to a What we see is somewhat different. Here is the merge accounted for by
We merge together two large piles of input data, and then collapse them down to be roughly the former. This actually makes sense, because it is merging the current updates and the historical updates. However, we would rather have had the historical data collapsed down and the current data untouched, as we know it must be while we work on it. We can collapse down the "current" data once it becomes old, which it will at the end of the The
There are generally more changes in Both of these cases suggest that the discipline for collapsing and merging should perhaps be reviewed. These examples would prefer to have a more "collapse-driven" approach, where we collapse a batch as soon as we can, and we merge batches only when we must. The current implementation takes the opposite approach, which I think is due to "merge first, then collapse" having simple amortized performance bounds: it can be hard to know how often to collapse, or whether collapsing anything other than the oldest batch makes any sense. In any case, perhaps we can work around this with better signaling from the |
Perhaps this should be related to #37 which suggests that descriptions might provide some smart guidance on when we should compact batches. For example, if the lower and upper bounds of a batch are not equal, but would become equal when they themselves are compacted, I suspect we have a good candidate for compaction. Just a gut feel at the moment, though. Edit: since batches can be compacted already, perhaps I mean if |
I made a few quick changes to try out ideas. They conceal information from the trace, so they aren't great things to want to do, but they have a beneficial impact:
The numbers improve a bunch. All of the work is now done at
The overall time drops from 2.5s per million input changes to about 2.0s, as we had two I'll need to check out the numbers on other applications to see if the merge-collapse strategy is flawed for them (merging two collapsed traces does not necessarily result in minimal output, as merges do not do cancellation; collapsing merged traces does result in minimal output). Another possible future issue is that collapsing can happen in-place, if the assets are uniquely owned; they are uniquely owned just after a merge, but might not be just before the merge. This could de-activate the hypothetical "collapse-in-place" future optimization. |
A bit more data. Query 01 from the
The numbers are much improved (yay!), but also the performance degradation isn't as pronounced. This makes some sense, as pre-optimization, we would be sitting on un-collapsed data proportional to the batch size, merging batches of that size, etc. By doing less of that, we frustrate large-batch configurations less. I think. |
Diving a bit deeper on the However, the It is probably a good idea to pivot over to loading strictly historical input data from the trace, and current input data from the received batches. This has the potential to make the historical input reads much smaller, and the batch reads simpler (they needn't be complicated merges like the historical data). This will probably reduce the time spent loading historical data for high-throughput scenarios, which should be a good thing. It also gives more precise information about which updates are new and which are not, which can allow some cute optimizations (or at least open the doors for them, a precursor of me typing them in). |
The proposed change, loading historical data strictly prior to the batch, has been committed as #53. The result was some noticeable improvement for Additionally, we have #54 which supports a totally ordered I think this means we have a pretty good handle on where the time is going in
There doesn't seem to be a great mystery about raw |
The
group
operator seems to get down to about a few microseconds per update, which seems too large especially if there is little to do. With large updates, we are essentially sorting the data, and then zipping two sorted lists. The amount of per-key logic could in principle be very small, but several microseconds per update is surprisingly large.Specifically, the
degrees.rs
example does twocount
operators in sequence, each of which should be very simple logically. The firstcount
has low contention (single updates per key) and the secondcount
has higher contention, but neither of these seem like they should take much compute per update. Clearly that isn't the case at the moment, and it would be good to either learn why it is important, or clean things up so that the painful cases are eased.Simple things to check out: there is no logic in
group
for an early exit for trivial updates. If there is a single time, we still prep a great deal of state to help implement things asymptotically awesomely; perhaps we should bail out in the same way thatjoin
does.The text was updated successfully, but these errors were encountered: