microsoft / microsoft/Power-Fx

Improve recalc engine algorithm

Open
#308 12 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

good first issue
Dominant language
C#
Stars
3.4k
Forks
358
Avg merge
10h 34m
Merged PRs (30d)
3

Description

(this is a bit more advanced for a first issue - requires knowledge of topological sorts. But it's marked as a "first issue" since the code is very accessible with few dependencies)

RecalcEngine's lets you define Formulas (via SetFormula) and then it will automatically recalc the formula if the dependencies change.

But the implementation here is extremely hack:
https://github.com/microsoft/Power-Fx/blob/e2ffacc79cd57a2f5b9a30cc05c41460d3478fb0/src/libraries/Microsoft.PowerFx.Interpreter/RecalcEngineWorker.cs#L18

This is the ability to call UpdateVariable() and cause other Formulas (created from SetFormula) to be recalculated.

It's good enough to pass the tests, but a very poor implementation.
See tests here:
https://github.com/microsoft/Power-Fx/blob/e2ffacc79cd57a2f5b9a30cc05c41460d3478fb0/src/tests/Microsoft.PowerFx.Interpreter.Tests/RecalcEngineTests.cs#L124

A good implementation:

  • would statically understand what each formula depends on
  • efficient recalc - does not unnecessary work.
  • robust handling for circular references
  • include aggressive tests.
  • allow deleting a formula.

The current implementation is also very inefficient. We could construct a perf benchmark to show before and after.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with src/libraries/Microsoft.PowerFx.Interpreter/RecalcEngineWorker.cs and the RecalcEngineTests.cs cases around line 124. Compare the current behavior with the requested dependency analysis, efficient recalculation, circular-reference handling, deletion support, and broader tests; done means these requirements are covered and the existing tests still pass.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
compilers
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.