Автор опубликовал технический разбор планирования сборок Cargo и исследовал, можно ли улучшить порядок выполнения задач. Анализ основан на наблюдении за поведением системы без изучения исходного кода Cargo.

Для восстановления графа зависимостей и точного времени задач автор трассировал системные вызовы Cargo и дочерних процессов, поскольку данных cargo build –timings было недостаточно. В модели компиляция одного crate разделена на frontend с созданием метаданных .rmeta и rest с завершением компиляции, а зависимые crate ждут только frontend.

При параллелизме n=4 планировщик b-level чаще работал быстрее расписания Cargo. Он обошёл Cargo в 15 из 17 проектов.

Медианная экономия времени составила около 8%, а максимальная — 16%.

Проверка утверждений:

  • Автор опубликовал технический разбор планирования сборок Cargo и на наблюдаемом поведении системы исследует, можно ли улучшить порядок выполнения задач без анализа исходного кода Cargo. (подтверждено первоисточником: доказательство; «The whole analysis here is based on observing its behavior from the outside, not on digging into its source code.»)
  • В экспериментальный набор вошли 15 известных Rust-проектов и два проекта автора — HyperQueue и FairyFlow. (подтверждено первоисточником: доказательство; «I picked 15 well-known Rust projects, plus two projects that I maintain myself: HyperQueue and FairyFlow .»)
  • Исследование ограничено обычной отладочной сборкой cargo build и не рассматривает cargo check или release-сборки. (подтверждено первоисточником: доказательство; «Note that, for the sake of simplicity, we always consider a plain debug build ( cargo build ); cargo check and release builds are not considered here.»)
  • Для восстановления графа зависимостей и точного времени задач автор трассировал системные вызовы Cargo и дочерних процессов, поскольку данных cargo build –timings для этого недостаточно. (подтверждено первоисточником: доказательство; «Cargo has a build-timing feature ( cargo build –timings ), but its output does not give us enough information to reconstruct the dependency graph. Tracing the syscalls that Cargo and its children make gets us there instead; that is enough to see which files each rustc process reads and writes, and in what order, and from that we can derive both the dependencies and precise per-task start/end times.»)
  • В модели компиляция одного crate разделена на узел frontend, создающий метаданные .rmeta, и узел rest для завершения компиляции; зависимые crate ждут только frontend. (подтверждено первоисточником: доказательство; «So in our graph, running rustc on a single crate is actually represented as two nodes: “frontend” , which produces the metadata, and “rest” , which finishes the compilation (codegen and linking). Dependent crates only wait for “frontend” to complete.»)
  • Планировщик b-level при освобождении рабочего потока выбирает готовую задачу с максимальной длиной оставшейся до конца сборки цепочки, отдавая приоритет критическому пути. (подтверждено первоисточником: доказательство; «Whenever a worker becomes free, the scheduler picks the ready task with the highest b-level. The idea is simple: prioritize tasks that are on, or close to, the critical path, since delaying them delays everything that depends on them.»)
  • При параллелизме n=4 b-level обошёл расписание Cargo в 15 из 17 проектов с медианной экономией около 8% времени и максимумом 16%; при n=16 — в 14 из 17 с медианой около 2% и максимумом 15%. (подтверждено первоисточником: доказательство; «Across the 17 projects, at n=4 b-level beats cargo’s own schedule in 15 out of 17 cases, saving a median of about 8% of the wall time (up to 16% on the best case). At n=16, it still wins in 14 out of 17 cases, though the gain shrinks to a median of about 2% (up to 15%); which makes sense, since there is simply less room for a bad decision to matter when almost everything can run at once anyway.»)
  • Относительно найденного псевдооптимума b-level оказался в медиане на 1,3% хуже при n=4 и на 0,4% хуже при n=16, тогда как Cargo — на 9,6% и 2,3% соответственно. (подтверждено первоисточником: доказательство; «At n=4, b-level lands at a median of about 1.3% above the pseudo-optimum (worst case 3.3%), while cargo is at a median of about 9.6% above it (worst case just over 20%). At n=16, b-level is a median of 0.4% above (worst case 1.3%), cargo a median of 2.3% above (worst case as high as 17.5%).»)
  • Даже при шуме оценок длительности до σ=60% медианный результат b-level оставался близок к варианту с точными длительностями и превосходил базовое расписание Cargo, хотя отдельные неудачные запуски ухудшались на 30–50%. (подтверждено первоисточником: доказательство; «B-level with noisy estimates stays very close to the noise-free b-level makespan across all three noise levels; the median stays within a fraction of a percent, even at σ=60%. Some unlucky individual runs do get noticeably worse (occasionally by 30-50%), but that’s the tail, not the typical case; the median of the noisy runs still comfortably beats the “cargo” baseline.»)
  • Однобитная классификация задач на короткие и длинные почти сохранила качество точного b-level: медиана составила 1,5% выше псевдооптимума при n=4 и 0,5% при n=16 против 1,3% и 0,4% у точных длительностей. (подтверждено первоисточником: доказательство; «At n=4, this “1b b-level” ends up a median of 1.5% above the pseudo-optimum, against 1.3% for b-level with exact durations and 9.6% for cargo. At n=16 the three numbers are 0.5%, 0.4% and 2.3%.»)
  • Без какой-либо информации о времени, только по глубине графа, метод всё ещё обошёл Cargo в 16 из 17 проектов при n=4 и в 12 из 17 при n=16, но в худших случаях отклонение от псевдооптимума достигало 19%. (подтверждено первоисточником: доказательство; «Even completely blind, it beats the cargo baseline on 16 of 17 projects at n=4 and on 12 of 17 at n=16. The catch is in the tail; few projects go quite wrong: nushell and zola both at 19% above the pseudo-optimum at n=16, gitui at 12% and nushell at 10% at n=4.»)

Первоисточники:

оценка 62.4 · тип research · ревизия 1 · истории st-oeogq7