| Re: [mat-dev] Concurrent Dominator Tree Creation |
> From: "Nathan Reynolds" > Date: 09/11/2021 22:19 > The Dominator Tree is generated using depth-first search. This > means there is some data structure tracking which objects were > visited. This data structure might be able to be replaced with a > concurrent one. When a thread visits an object, all the children > can be pushed into the front of a ConcurrentLinkedDequeue. The > thread always pushes and pops from the front of the dequeue. This > effectively makes the ConcurrentLinkedDequeue like a stack for that > thread. If the thread finds its dequeue empty, then it tries to pop from the > end of the other thread's dequeues. Using dequeues instead of > stacks allows for using ConcurrentLinkedDequeue and avoids lock > contention. Please enlighten me why this is not done. The dominator tree code dates from first release of MAT in 2007 and is here: https://git.eclipse.org/c/mat/org.eclipse.mat.git/tree/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/internal/DominatorTree.java The algorithm may be based on: Lengauer, T., & Tarjan, R. E. (1979). A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems (TOPLAS), 1(1), 121-141. There are 7 int arrays of size the number of objects, so that is big memory requirement for MAT. The tricky part is ensuring correctness while efficiently parallelizing this code without excessive locking. Reducing the memory requirements would be good, as currently this requires 56GB of RAM for the MAT limit of 2^31 objects. As building a dominator tree is a standard computer science problem someone should first review the literature for any improved algorithms. -- Andrew Johnson Unless stated otherwise above: IBM United Kingdom Limited - Registered in England and Wales with number 741598. Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU
Attachment:
smime.p7s
Description: S/MIME Cryptographic Signature