AngouriMath

Navigation

Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug Donate Contacts

AngouriMath.Core.Budgets

← Back to list of namespaces

Classes within the AngouriMath.Core.Budgets namespace

• BudgetLedger

  Summary

  The accounting side of a WorkBudget: what has been spent so far, and
  what stopped the computation if anything has.
  

  Remarks

  Mutable, and single-flow, on purpose. The limits are an immutable value so
  that they can be shared; the drawing-down is one object mutated in program order.
  The alternative — threading a remaining count through as an immutable value — has to
  split the count at every branch of a search, and there is no right split: an
  even one starves the branch that needed the work, giving it all to the first starves
  the rest, and a branch that fails then needs a protocol for handing back what it did
  not spend. A single ledger drawn down in program order needs none of that, is exactly
  reproducible as long as the algorithm's own order is defined — which
  #746's third
  design principle requires anyway — and bounds the search as a whole rather than each
  branch of it, which is the difference between a bound and a suggestion.
  A subgoal inherits the ledger rather than getting one. Passing the same object
  down is what makes a call bounded end to end. Giving each stage a budget of its own
  bounds each stage and leaves the whole unbounded, which is how
  #896 arose:
  the same call is bounded or not depending on which internal path accepted it, and
  that is worse to debug than either extreme.
  Honouring is cooperative, so no thread is involved. The algorithm asks —
  Spend(System.Int64) before doing a unit of work, Require(System.Boolean,System.String) before letting
  a structure grow — and declines when told to. Nothing is interrupted, nothing is
  aborted, and there is no second thread to make the answer depend on scheduling. The
  cost is that an algorithm which does not ask cannot be bounded, which is the honest
  trade: a bound that is enforced from outside is a thread abort, and a thread abort in
  the middle of a rewrite leaves no answer worth having.
  The first ceiling to fire is the one reported. Once one has, every subsequent
  question answers "no" without re-testing, so the reason cannot be overwritten by
  whatever the algorithm happened to ask next on its way out.
  

• BudgetOutcome

  Summary

  What a bounded computation spent, and what stopped it if anything did.
  

  Remarks

  The point of it is that Reason survives. A computation that gives up
  on a resource and a computation that concluded there is nothing to find both hand the
  caller nothing, and the library has had no way to tell those apart —
  #896 is that
  gap reported as a defect. An outcome is the "because" that goes with the shrug.
  It does not say what to do next, and deliberately makes no attempt to. Which ceiling
  fired was measured against whether the fall-through then terminates, on
  #896's own
  corpus, and the same ceiling appears on both sides: two systems the fall-through
  solves in seconds and one it cannot finish at all all decline on the quotient
  dimension. So this is a report, not a routing decision.
  

  Parameter "Where"

  Which computation this is about, for a reader — not a stable identifier to switch on.
  

  Parameter "Reason"

  What stopped the computation — a ceiling it reached, or a shape it could not work
  with — or null where it ran to its own end. Named rather than
  enumerated because most of these belong to one algorithm and mean nothing outside it.
  

  Parameter "Steps"

  Units of work charged.

  Parameter "Elapsed"

  How long it took, whether or not a clock bounded it.

  Parameter "IsDeterministic"

  Whether this outcome is a function of the input alone. False exactly when a wall-clock
  ceiling is what stopped it, in which case a faster machine would have got further.
  

• BudgetRecording

  Summary

  Collects what each bounded computation spent while it is open, so that an answer can
  be asked why it stopped rather than only what it is.
  

  Remarks

  A scope rather than a setting, and off unless asked for. With no recording open, a
  bounded computation costs one ambient read more than it did — per computation, not
  per step — and allocates nothing. A caller who never mentions budgets pays for none
  of this, which is the condition
  #746 puts on
  anything added above the tree.
  It exists because the reason has further to travel than the return value does.
  Solve hands back a set; a set has no room in it for "the Gröbner path declined
  on the quotient dimension and the fall-through answered instead", and widening every
  signature between here and there to carry a reason nobody usually wants is a poor
  trade. A scope reaches the caller across those signatures without changing any of
  them.
  Per flow, like Settings and
  RewriteRecording: the recording
  belongs to the call rather than to the thread running it, so it survives an
  await, and a recording opened inside a task is invisible to that
  task's siblings. Order across flows is not guaranteed; within one it is the order
  the computations finished in.
  

  Example

  using AngouriMath;
  using AngouriMath.Core.Budgets;
              
  using var recording = BudgetRecording.Start();
  var solutions = MathS.Equations("x2 + y2 - 4", "x y - 1").Solve("x", "y");
  foreach (var outcome in recording.Outcomes)
      Console.WriteLine(outcome);

• WorkBudget

  Summary

  What a computation is allowed to spend before it declines. A value, not a counter:
  two budgets with the same ceilings are the same budget, and one can be reused,
  shared and cached freely.
  

  Remarks

  Two axes, and they are not the same kind of thing.Steps counts
  work the algorithm does and so gives the same answer on every machine;
  Time reads a clock and so does not. Both are here because they catch
  different runaways — a computation can be spending a colossal number of cheap steps
  or a handful of ruinous ones — but only the first can appear in an answer that is
  supposed to be reproducible, which is why
  IsDeterministic exists and why exhaustion says which
  ceiling fired rather than only that one did
  (#373).
  A step is one unit of whatever the algorithm charges for. It is deliberately
  not defined further: an algorithm charges where it would otherwise be able to loop,
  and comparing step counts between two algorithms means nothing. What a step does
  guarantee is that the count is a function of the input, so the same input exhausts at
  the same point twice.
  What is not counted, and is not pretended to be. Nodes allocated and memory
  held are both named as budget axes by
  #746 and neither
  is counted anywhere in the library, so neither is a property here. A ceiling nothing
  enforces reads as a promise, and the caller finds out it was not one by waiting.
  Algorithm-specific ceilings — how many S-polynomial pairs, how wide a coefficient may
  get — stay with the algorithm that knows what they mean; they are reported through
  the same BudgetOutcome by name.