Skip to content

par: no heap allocation inside per-step parallel sections (full_piv_lu best vector, for_each_child item/slot vectors) #111

Closed

Description

@shinaoka

Problem

Every parallel step of a per-step factorization allocates on the heap. A step of full-pivoting LU allocates three times:

  • the best vector of per-task maxima (lu/full_pivoting/factor.rs);
  • the items vector of utils::team::for_each_child, which collects the producer's items;
  • the Slots vector of utils::team::for_each_child.

The tridiagonal, Bunch-Kaufman and column-pivoting QR steps, and every other for_each region, pay the last two the same way.

Why it matters

#109 (#91) runs these steps at the widest width that pays. At the floor, the estimate is 1.8-2.9 us against 3 x D(w). The dispatch row D(w) is the cost of an empty section and contains none of these allocations.

On evo, full_piv_lu f64 128 at 8T took 19 such steps at widths 2-7 and lost 20-30 us overall, +6.6 to +10.4%. The analysis is in #109, comment 6488188460. The monitor ruled that the allocations are a defect of the mechanism, not a host constant.

Proposal

  • Allocate nothing inside a per-step parallel section.
    • Workspace such as best is allocated once, outside the step loop: in the call's scratch, or once per call.
    • for_each_child deals the producer's items to the children without collecting them into vectors. Either inline the split over the indexed producer (split_at per child), or keep a fixed-capacity buffer on the stack for the common case.
  • Decide on a cost-model term later. Whether the model needs a per-region fixed-cost term is decided after the allocations are gone, by re-measuring the evo cell.

Done when

  • No heap allocation per step in the converted per-step factorizations or in for_each_child, checked with a counting allocator in a test.
  • full_piv_lu f64 128 at 8T on evo is re-measured against origin/main.

Parent: #95. Follows #91 / #109.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions