Layout time doubles per nesting level: `computeMinContentMainSize` recurses twice per child

yoga/algorithm/CalculateLayout.cpp の computeMinContentMainSize と、その呼び出し元である computeAutoMinMainSize から始めます。既存のレイアウト動作と提案された結合トラバーサルを比較し、issue で説明されている差分ハーネスを使って、深くネストされたレイアウトが線形にスケールし、ジオメトリが変わらないことを検証します。

Summary

computeMinContentMainSize in yoga/algorithm/CalculateLayout.cpp is a
per-axis function, so the container branch recurses into every child twice
-- once for the node's main axis and once for its cross axis:

float childMain = computeMinContentMainSize(
    child, nodeMainAxis, direction, ownerWidth, ownerHeight);
...
float childCross = computeMinContentMainSize(
    child, nodeCrossAxis, direction, ownerWidth, ownerHeight);

Each call re-walks that child's entire subtree and keeps a single component,
so a chain of flex containers costs T(d) = 2*T(d-1) -- i.e. O(2^depth).
Nothing memoizes it: the recursion does no layout writes and does not go
through the layout cache, so the cost is invisible to the cache counters.

This is reachable from ordinary markup. computeAutoMinMainSize calls it for
every in-flow flex item whenever the config does not set
Errata::MinSizeUndefinedInsteadOfAuto -- i.e. under the modern default --
which is the CSS Flexbox §4.5 automatic minimum size path.

Repro

Plain nested flex rows, no measure functions, no custom config beyond
YGErrataNone, one concrete leaf at the bottom:

#include <yoga/Yoga.h>
#include <chrono>
#include <cstdio>
#include <vector>

static double timeDepth(int depth) {
  YGConfigRef config = YGConfigNew();
  YGConfigSetErrata(config, YGErrataNone);

  std::vector<YGNodeRef> chain;
  YGNodeRef root = YGNodeNewWithConfig(config);
  YGNodeStyleSetFlexDirection(root, YGFlexDirectionRow);
  YGNodeStyleSetWidth(root, 800);
  YGNodeStyleSetHeight(root, 600);
  chain.push_back(root);

  for (int i = 0; i < depth; i++) {
    YGNodeRef n = YGNodeNewWithConfig(config);
    YGNodeStyleSetFlexDirection(n, YGFlexDirectionRow);
    YGNodeInsertChild(chain.back(), n, 0);
    chain.push_back(n);
  }
  YGNodeRef leaf = YGNodeNewWithConfig(config);
  YGNodeStyleSetWidth(leaf, 20);
  YGNodeStyleSetHeight(leaf, 20);
  YGNodeInsertChild(chain.back(), leaf, 0);

  auto t0 = std::chrono::steady_clock::now();
  YGNodeCalculateLayout(root, YGUndefined, YGUndefined, YGDirectionLTR);
  auto t1 = std::chrono::steady_clock::now();
  YGNodeFreeRecursive(root);
  YGConfigFree(config);
  return std::chrono::duration<double>(t1 - t0).count();
}

int main() {
  for (int d : {16, 18, 20, 22, 24, 26}) {
    std::printf("%3d %8.3f s\n", d, timeDepth(d));
    std::fflush(stdout);
  }
}

main@433d463, clang -O2 (Apple M-series), median of 5 runs:

Steady ~4x per two levels, i.e. ~2x per level -- the 2^depth signature.
Extrapolating the same factor, depth 30 lands around a minute, which reads as
a hang rather than as slowness.

Proposed fix

Compute both components in a single walk. Each subtree then costs exactly one
recursion and the per-pass cost goes back to linear.

Semantics are preserved point for point:

• static per-axis values still win, and when both are defined the function
  still returns without recursing (matching today's early return);
• leaves still measure once per axis and still add their own padding/border;
• each child's contribution is projected onto the parent's main/cross axes,
  which is exactly what the two separate calls produced.

The shape of the change, condensed (full patch in a PR if you want it):

-static float computeMinContentMainSize(
-    yoga::Node* const node,
-    const FlexDirection requestedAxis,
-    const Direction ownerDirection,
-    const float ownerWidth,
-    const float ownerHeight) {
-  const bool wantRow = isRow(requestedAxis);
-  const FloatOptional staticMin =
-      wantRow ? node->getMinContentWidth() : node->getMinContentHeight();
-  if (staticMin.isDefined()) {
-    return staticMin.unwrap();
-  }
+struct MinContentSize {
+  float width;
+  float height;
+};
+
+static MinContentSize computeMinContentSize(
+    yoga::Node* const node,
+    const Direction ownerDirection,
+    const float ownerWidth,
+    const float ownerHeight) {
+  const FloatOptional staticW = node->getMinContentWidth();
+  const FloatOptional staticH = node->getMinContentHeight();
+  // Both pinned -> still no recursion at all, as before.
+  if (staticW.isDefined() && staticH.isDefined()) {
+    return {staticW.unwrap(), staticH.unwrap()};
+  }

   // ... measure-func branch: measure once per axis, add own padding/border
   //     (unchanged, just returning both components)

   for (size_t i = 0; i < node->getChildCount(); i++) {
     ...
-    float childMain = computeMinContentMainSize(
-        child, nodeMainAxis, direction, ownerWidth, ownerHeight);
+    // One recursion per child, then project onto this node's axes.
+    const MinContentSize childSize =
+        computeMinContentSize(child, direction, ownerWidth, ownerHeight);
+
+    float childMain = nodeMainIsRow ? childSize.width : childSize.height;
     childMain += child->style().computeMarginForAxis(nodeMainAxis, ownerWidth);
-
-    float childCross = computeMinContentMainSize(
-        child, nodeCrossAxis, direction, ownerWidth, ownerHeight);
+    float childCross = nodeMainIsRow ? childSize.height : childSize.width;
     childCross +=
         child->style().computeMarginForAxis(nodeCrossAxis, ownerWidth);

     mainTotal += childMain;
     crossMax = std::max(crossMax, childCross);
   }

   // ... padding/border added per axis (unchanged)
-  return wantRow ? widthMin : heightMin;
+  return {
+      staticW.isDefined() ? staticW.unwrap() : widthMin,
+      staticH.isDefined() ? staticH.unwrap() : heightMin};
 }

The single caller in computeAutoMinMainSize then projects instead of
picking an axis up front:

-  const FloatOptional contentMain = FloatOptional{computeMinContentMainSize(
-      child, mainAxis, direction, ownerWidth, ownerHeight)};
+  const MinContentSize contentSize =
+      computeMinContentSize(child, direction, ownerWidth, ownerHeight);
+  const FloatOptional contentMain =
+      FloatOptional{isRow(mainAxis) ? contentSize.width : contentSize.height};

One subtlety worth calling out: when only one axis has a static
min-content value the function must still recurse for the other, so the
static value is applied per-axis at the return sites rather than as a
single early exit. That matches what the two per-axis calls did (one
short-circuited, the other recursed).

With the patch, same machine and harness:

Depth 26 goes from 4.2 s to under a tenth of a millisecond, and depth 200 --
far past where stock yoga stops finishing at all -- costs under a millisecond.

Results are unchanged. I ran a differential harness over 300
pseudo-randomly generated trees (mixed row/column, percent and fixed sizes,
flex grow/shrink, min/max constraints, padding/margin/border, aspect-ratio,
wrap, overflow:scroll, absolute children, both LTR and RTL), dumping
left/top/width/height for every node -- 17,094 lines of geometry, byte
identical between stock and patched builds.

Happy to open a PR with the change plus the differential harness as a test if
that shape is useful; let me know if you would rather have it as a benchmark
under benchmark/ or a gtest case.