)]}' { "commit": "0c6ee24d3ab519131f557d76c5ea023e8ac7805e", "tree": "ab1de59d49b6af65c43341483f7696f19545848a", "parents": [ "d522178b54087d2c3855484c1899ce99ad278169" ], "author": { "name": "Todd Lipcon", "email": "tlipcon@google.com", "time": "Tue Oct 13 19:06:33 2026 -0700" }, "committer": { "name": "Copybara-Service", "email": "copybara-worker@google.com", "time": "Tue Oct 13 19:08:35 2026 -0700" }, "message": "Space out GraphCycles ranks so that InsertEdge can often move just one node\n\nIn debug builds, absl::Mutex deadlock detection records each lock-order edge\nwith GraphCycles::InsertEdge(held, acquired), under a global lock. GraphCycles\nkeeps node ranks in topological order: rank(x) \u003c rank(y) for each edge x-\u003ey.\nWhen a new edge breaks this order, InsertEdge uses the Pearce-Kelly algorithm\nto detect a cycle or repair the ranks.\n\nBefore this change, ranks were a dense permutation of [0, N), and each new slot\ngot the next rank, above all existing nodes. So when a newly created mutex x is\nheld while an older mutex y is acquired, which is common, the edge x-\u003ey often\nbreaks the order. Pearce-Kelly then visits every descendant of y that ranks\nbelow x (nearly all of them, since x is new), and sorts and renumbers them,\njust to put one node in order. With no unused ranks between nodes, even moving\none node means renumbering everything in between.\n\nThis change leaves unused ranks between nodes, so that InsertEdge can often fix\nthe order by moving just x or just y:\n\n- Ranks are now int64_t, and new slots get ranks 2^32 above the highest rank.\n All slots, including free slots, are kept in a doubly linked list sorted by\n rank. As before, a free slot keeps its rank (and now its place in the list),\n which is reused with the slot.\n- If rank(x) \u003e rank(y), InsertEdge(x, y) first tries to move x below y, which\n requires all in-neighbors of x to rank below y. x moves to the midpoint\n between y and the slot just below y, or 2^32 below the lowest rank if x has\n no in-neighbors. If x cannot move, InsertEdge tries the symmetric move of y\n above x, which requires all out-neighbors of y to rank above x. If neither\n move works, Pearce-Kelly runs as before.\n- Ranks stay unique by construction: each new rank is strictly between the\n ranks of two adjacent slots in the list, or beyond the lowest or highest\n rank, so no other slot can have it. As before, the Pearce-Kelly reorder\n reassigns the ranks of the reordered nodes among them. It now also gives each\n one the list place that goes with its new rank.\n- A move never hides a cycle: the condition for moving x also proves that y\n cannot reach x, since every node reachable from y ranks at or above y, but\n every in-neighbor of x ranks below y. The same holds for moving y, so all\n cycle detection still happens in the Pearce-Kelly path.\n\nWhy not simply give new nodes decreasing initial ranks (below all existing\nnodes)? That makes new -\u003e old edges immediately ordered, but it inverts the\norder for old -\u003e new edges, such as when a long-lived container mutex locks a\nnewly created child mutex, or when a chain of mutexes is acquired in creation\norder. Every old -\u003e new edge then triggers a Pearce-Kelly traversal and dense\nrenumbering, making sequential chain construction (BM_StressTest) quadratic:\nO(N) per edge (114 us/node at N\u003d2048 and 2.9 ms/node at N\u003d32768, vs. under 0.5\nus/node). Spacing ranks out and moving either endpoint handles both directions\nin O(degree) time.\n\nLimits and trade-offs:\n\n- InsertEdge does not try to move x if x has more than 16 in-neighbors to\n check, or y if y has more than 16 out-neighbors. If neither can move, it\n falls back to Pearce-Kelly. This bounds the cost of each attempt.\n- The 2^32 spacing leaves room for about 32 consecutive moves into the gap\n between two adjacent new slots. When the two ranks around a gap are less than\n 2 apart, Respace() first spreads out a run of slots around the gap, keeping\n their order. Starting with the two slots around the gap, the run doubles in\n size until its slots can be evenly spaced at least 2^16 apart between the\n ranks just outside it (-2^62 and 2^62 beyond the ends of the list).\n- Ranks beyond the lowest and highest ones stay within [-2^62, 2^62], which\n leaves room for about 2^30 moves (or new slots) at each end. When that runs\n out, all slots are respaced evenly across [-2^61, 2^61] in O(N) time, which\n leaves room for 2^29 more at each end.\n- Slot indices are still int32_t, and the ranks have room for 2^31 slots, so\n there is no new limit on node count.\n- Node grows by 16 bytes, for the 64-bit rank and two 32-bit list links (with\n alignment). It was already over 400 bytes, since it holds a 40-entry stack\n trace.\n\nNew tests cover each kind of move, the fallbacks to Pearce-Kelly, and both\nkinds of respacing. A new test-only method, TestOnlySetRankStride(), lets a\ntest make the ranks beyond the lowest and highest ones run out after a few\nmoves, to exercise the respacing of all slots.\n\nPiperOrigin-RevId: 999040867\nChange-Id: I3353404e681c094b3cbd4978f384c0415200b2ec\n", "tree_diff": [ { "type": "modify", "old_id": "25b51ffe0b87f03e867a1d906a7b7c7f00fd11f5", "old_mode": 33188, "old_path": "absl/synchronization/internal/graphcycles.cc", "new_id": "707908145f1a6678cea9c5d4c2bdda84a637e0d5", "new_mode": 33188, "new_path": "absl/synchronization/internal/graphcycles.cc" }, { "type": "modify", "old_id": "da0650405308988bf2da8492d8557d384714feff", "old_mode": 33188, "old_path": "absl/synchronization/internal/graphcycles.h", "new_id": "27eaa6c61be032dc4f82486e71394bff4462de39", "new_mode": 33188, "new_path": "absl/synchronization/internal/graphcycles.h" }, { "type": "modify", "old_id": "9012801f7805441e8b75a0f19b415036f01e8cd4", "old_mode": 33188, "old_path": "absl/synchronization/internal/graphcycles_benchmark.cc", "new_id": "9d11c38071f2fd923dac869d633494336d6baea4", "new_mode": 33188, "new_path": "absl/synchronization/internal/graphcycles_benchmark.cc" }, { "type": "modify", "old_id": "d4ba0f6edd8838df3d19daf5925479d16cdcc3f0", "old_mode": 33188, "old_path": "absl/synchronization/internal/graphcycles_test.cc", "new_id": "b1a6daf0825d4b9956bf34538033d98139419ea3", "new_mode": 33188, "new_path": "absl/synchronization/internal/graphcycles_test.cc" } ] }