I'm building an algebraic search algorithm, consider it as a prioritized
depth-first search with pruning. I use a PriorityBlockingQueue to hold the partial solutions, ordered by the partial evaluator, and when I find a complete solution, I call queue.removeIf((t) -> t.cost >= knownCost); The trouble is that PriorityBlockingQueue.removeIf() uses PBQ$Itr, within which remove() calls PriorityBlockingQueue.removeEQ(), which itself has linear cost, making PBQ.removeIf() have quadratic overall complexity. What solutions are available to me? I'm aiming for >10K ops/sec on 4 cores, so it's not at the point where synchronization is murder but it matters. I do need to prune the queues, as they aren't remotely FIFO and old elements will get left around for a long time. Queue sizes are in the order of some millions. * I could execute the removeIf() on a background thread. * I could use a non-Blocking queue and use coarse grained locking - but then I lose poll(long, TimeUnit), which I could reimplement * I could use another queue implementation - which one do you suggest? Thank you. S. _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
Late in jdk9 development we tried to optimize various bulk operations in j.u.c. including PBQ.removeif, but the PBQ changes didn't make the jdk9 train. At least removeIf is not O(n**2) like some other collections ! On Wed, Mar 1, 2017 at 1:59 PM, Shevek <[hidden email]> wrote: I'm building an algebraic search algorithm, consider it as a prioritized depth-first search with pruning. I use a PriorityBlockingQueue to hold the partial solutions, ordered by the partial evaluator, and when I find a complete solution, I call queue.removeIf((t) -> t.cost >= knownCost); _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
In reply to this post by Shevek
I've experimented with alternate ordered blocking queue implementations. One I've written that is reasonably well-tested (though not used in any production system that I know of) is backed by a ConcurrentSkipListSet: here's source. (It's lock-free, so I was hoping it could perform better than PriorityBlockingQueue under contention. Preliminary performance tests suggest any performance benefit is slim to none, though I've not done anything in the way of profiling).
Unfortunately, it looks like iterator#remove() for ConcurrentSkipListSet is also not constant time. So this implementation is better at O(n * log n) instead of O(n ^ 2). But a skip-list is not a cache-friendly data structure with lots and lots of pointer chasing (so higher constant factors). So this still isn't that great. It may be just as good to roll your own your own O(n) removeIf by copying the queue, pruning it, and then re-initializing it. Speaking of rolling your own, one approach is to wrap a PriorityBlockingQueue and use a ReadWriteLock to protect it: "read" lock just means shared, which is for every normal queue operation (since the wrapped queue is thread-safe); "write" lock is exclusive, which you'd hold while re-building/pruning its contents. If you know you're using a particular JRE and are willing to tie yourself to its implementation, you could just sub-class PriorityBlockingQueue and use reflection in the ctor to get a ref to the queue's private lock and internal object array. Then you can provide your own optimized removeIf() by grabbing the lock, pruning the array directly (could be done efficiently with a single O(n) pass over its contents), re-heapify what's left in the array (also O(n)), and then release the lock. On Wed, Mar 1, 2017 at 4:59 PM, Shevek <[hidden email]> wrote: I'm building an algebraic search algorithm, consider it as a prioritized depth-first search with pruning. I use a PriorityBlockingQueue to hold the partial solutions, ordered by the partial evaluator, and when I find a complete solution, I call queue.removeIf((t) -> t.cost >= knownCost); _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
In reply to this post by Martin Buchholz-3
Looking again, I noticed the subject of this thread, and I believe it's not true. I believe PBQ and PQ removeIf methods are O(n log n) not O(n ^2), but we can get to O(n) because heapify is known to be O(n). _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
It's not about the heapify.
If I have a queue of 1M objects, and I want to remove K = N/2 of them: I walk the queue using the iterator. That's N. For each item I remove, removeEQ() walks the array from 0 to i in order to call removeAt(). That's asymptotically the second factor of N. It's this behaviour within removeEQ() which I think people on this thread may not have realized. Therefore PBQ's removeIf() is quadratic, assuming it removes some number of elements which is a linear function of N. S. On 03/01/2017 03:23 PM, Martin Buchholz wrote: > Looking again, I noticed the subject of this thread, and I believe it's > not true. I believe PBQ and PQ removeIf methods are O(n log n) not O(n > ^2), but we can get to O(n) because heapify is known to be O(n). _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
In reply to this post by Martin Buchholz-3
Martin,
That looks to be true for PQ, but not for PBQ. PBQ makes a copy of the underlying array so iteration is strongly consistent (and safe with regards to concurrent modifications). So when iterator#remove() is called, it must perform a linear scan of the live min-heap to first find the element, and then it can do the the O(log n) sifting. So that would make removeIf(...) O(n^2) On Wed, Mar 1, 2017 at 6:23 PM, Martin Buchholz <[hidden email]> wrote:
_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
In reply to this post by Shevek
Hmmm ... I stand corrected. PBQ.removeIf is quadratic, but probably only noticeably so for large element sizes (10,000 ?) , since removeEQ is a very fast linear memory scan when e.g. the array fits into cache. My point about heapify is that removeIf can lock the entire collection, ignore the heap invariant as it traverses the array, then restores the invariant using heapfiy at the end before unlocking. Historically, we have tried hard to make blocking queue interior removal operations correct, but not necessarily fast. Implementers' lives would have been easier if interior removal was never supported (especially for ArrayBlockingQueue). On Wed, Mar 1, 2017 at 3:46 PM, Shevek <[hidden email]> wrote: It's not about the heapify. _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
On Wed, Mar 1, 2017 at 7:10 PM Martin Buchholz <[hidden email]> wrote:
linear scan of ... references requiring a deref (and assume cache miss on each)? There won't be anything fast about that :)
-- Sent from my phone
_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
On Wed, Mar 1, 2017 at 7:15 PM, Vitaly Davidovich <[hidden email]> wrote:
It's actually doing identity equality checks, so nothing needs to be de-referenced in this case.
Yep. That's what I was suggesting as a hack (interim?) solution: do that via a sub-class that uses reflection to access the superclass's private lock and object array.
_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
On Wed, Mar 1, 2017 at 8:10 PM Josh Humphries <[hidden email]> wrote:
Indeed, you're right - I didn't notice that until now after you mentioned it.
-- Sent from my phone
_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
Shevek,
FWIW, here's a hack solution where removeIf() is orders of magnitude faster for huge queue w/ non-trivial number of deletions during removeIf: https://gist.github.com/jhump/ Since it uses reflection to poke at the JRE class's internals, it obviously isn't expected to work except on recent Oracle JDK 1.8 release. A possibly safer option is to simply fork all of the source code from OpenJDK's PriorityBlockingQueue.java and add the new method. Then you have no need for reflection and it wouldn't be brittle when running on different JREs or versions of Oracle JRE. On Wed, Mar 1, 2017 at 8:25 PM, Vitaly Davidovich <[hidden email]> wrote:
_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
You're wonderful, thank you. Yes, I totally believe the performance
improvements - it all started when I was trying to work out why my performance wasn't scaling and all threads were blocked, and as you can see, it was slow enough that even stack sampling worked. Hopefully we get a built-in performance improvement in a future version. I was using removeIf() on the assumption that builtins know things about structure and allocation which make them faster than iterators, but the answer may be "not quite yet". Aside: visualvm CPU sampler isn't working on the latest JDK8s. :-( I haven't looked at why not, yet. S. On 03/01/2017 05:55 PM, Josh Humphries wrote: > Shevek, > FWIW, here's a hack solution where removeIf() is orders of magnitude > faster for huge queue w/ non-trivial number of deletions during removeIf: > https://gist.github.com/jhump/2dc67844dc57ba510d305c56aa640440 > <https://gist.github.com/jhump/2dc67844dc57ba510d305c56aa640440> > Since it uses reflection to poke at the JRE class's internals, it > obviously isn't expected to work except on recent Oracle JDK 1.8 release. > > A possibly safer option is to simply fork all of the source code from > OpenJDK's PriorityBlockingQueue.java and add the new method. Then you > have no need for reflection and it wouldn't be brittle when running on > different JREs or versions of Oracle JRE. > > ---- > *Josh Humphries* > [hidden email] <mailto:[hidden email]> > > On Wed, Mar 1, 2017 at 8:25 PM, Vitaly Davidovich <[hidden email] > <mailto:[hidden email]>> wrote: > > > > On Wed, Mar 1, 2017 at 8:10 PM Josh Humphries <[hidden email] > <mailto:[hidden email]>> wrote: > > On Wed, Mar 1, 2017 at 7:15 PM, Vitaly Davidovich > <[hidden email] <mailto:[hidden email]>> wrote: > > > On Wed, Mar 1, 2017 at 7:10 PM Martin Buchholz > <[hidden email] <mailto:[hidden email]>> wrote: > > Hmmm ... I stand corrected. PBQ.removeIf is quadratic, > but probably only noticeably so for large element sizes > (10,000 ?) , since removeEQ is a very fast linear memory > scan when e.g. the array fits into cache. > > linear scan of ... references requiring a deref (and assume > cache miss on each)? There won't be anything fast about that :) > > > It's actually doing identity equality checks, so nothing needs > to be de-referenced in this case. > > Indeed, you're right - I didn't notice that until now after you > mentioned it. > > > > > My point about heapify is that removeIf can lock the > entire collection, ignore the heap invariant as it > traverses the array, then restores the invariant using > heapfiy at the end before unlocking. > > > Yep. That's what I was suggesting as a hack (interim?) solution: > do that via a sub-class that uses reflection to access the > superclass's private lock and object array. > > > > Historically, we have tried hard to make blocking queue > interior removal operations correct, but not necessarily > fast. Implementers' lives would have been easier if > interior removal was never supported (especially for > ArrayBlockingQueue). > > On Wed, Mar 1, 2017 at 3:46 PM, Shevek > <[hidden email] <mailto:[hidden email]>> wrote: > > It's not about the heapify. > > If I have a queue of 1M objects, and I want to > remove K = N/2 of them: > > I walk the queue using the iterator. That's N. > > For each item I remove, removeEQ() walks the array > from 0 to i in order to call removeAt(). That's > asymptotically the second factor of N. It's this > behaviour within removeEQ() which I think people on > this thread may not have realized. > > Therefore PBQ's removeIf() is quadratic, assuming it > removes some number of elements which is a linear > function of N. > > S. > > > On 03/01/2017 03:23 PM, Martin Buchholz wrote: > > Looking again, I noticed the subject of this > thread, and I believe it's > not true. I believe PBQ and PQ removeIf methods > are O(n log n) not O(n > ^2), but we can get to O(n) because heapify is > known to be O(n). > > > _______________________________________________ > Concurrency-interest mailing list > [hidden email] > <mailto:[hidden email]> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest > <http://cs.oswego.edu/mailman/listinfo/concurrency-interest> > > -- > Sent from my phone > > _______________________________________________ > Concurrency-interest mailing list > [hidden email] > <mailto:[hidden email]> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest > <http://cs.oswego.edu/mailman/listinfo/concurrency-interest> > > -- > Sent from my phone > > Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
Free forum by Nabble | Edit this page |