Cut calculation time by half with population

[sandcha]

LexImpact has to run two calculations on bulk data (50 000 households) in less than 15 seconds.

Definition of done:
Explore in 2 days max

• extracting vectors in calculation (shorten vectors)
• neutralising variables
• or by optimising byte code production

[fpagnoux]

Some experimentation on this issue, going more in depth into an idea initially introduced by @Morendil.

TLDR: There seems to be a way to speed up the calculations by 33% to 50% in common usecases

Introduction

OpenFisca (OF) runs calculations vectorially. Concretely, when given a large population, OF never loops on the individuals, but run each operation on the global population.
This approach is much faster that looping over the population when the latter is large enough. It however leads to performing a lot of useless calculations, as there is no conditional branching.
For instance, even if a benefit only applies to a small portion of population, it will still be computed for everyone, then zeroed for the ineligible individuals.

The experiment presented here tries to improve performances by reducing these useless calculations by introducing some kind of conditional branching, while respecting the vectorial paradigm.

The idea is, when facing a condition, to "split and combine" (SC):

• Split the population between the individuals who respect the population, and the one who don't
• Run different calculations on these 2 sub-populations
• Combine the results to get it for the whole population

Experiment 1 (symmetric case disjunction)

The code is available on this gist.

• We introduce a benefit that is calculated differently whether individuals are handicapped or not.
• We calculate it both with OF current's vectorial approach, and with the SC approach, and measure the ratio of execution time between the 2.
• We run this 10 times, and take the average ratio.
  • A ratio of 2 for instance means that the SC approach is on average twice faster than the current approach
• We study the impact of 3 factors:
  • The size N of the population
  • The frequency F of handicap in the population.
  • The complexity C of calculations in each case. This is measured in number of basic vectorial operations in a formula. 3 different versions of the formulas are introduced to that extend.

Result

C=13	N=1	N=1M
F=0.1	2	1.5
F=0.5	2	1.1

C=6	N=1	N=1M
F=0.1	2	1.35
F=0.5	2	0.9

C=2	N=1	N=1M
F=0.1	1.5	0.6
F=0.5	1.5	0.4

[fpagnoux]

Experiment 2 (eligibility)

Similar to the first experiment, expect that this time only handicapped individuals can get a benefit. This creates a dissymmetry: one case is much less complex than the other one.

Result

C=13	N=1	N=1M
F=0.1	6	2
F=0.5	4	0.8

C=6	N=1	N=1M
F=0.1	4.5	1.5
F=0.5	3	0.67

C=2	N=1	N=1M
F=0.1	1.9	0.4
F=0.5	1.6	0.3

[fpagnoux]

Interpretation

• SC is always more efficient for a single-individual population. This was expected, as in this case we can "short-circuit" the calculation and only use the relevant formula.
• For a large population, SC is more efficient:
  • when complexity is high. This makes sense, as there is some fixed overhead of splitting and combining. If the formulas operations are trivial, this overhead is bigger than the small cost of the operations.
  • when frequency is low, especially in the "eligibility" cases where complex calculations only need to be run for a fraction of the population.

Conclusion

I think the approach is really promising: it doesn't take a lot of operations to make SC more efficient than our current implementation, especially when calculations are relevant to only a small fraction of the population.

[fpagnoux]

Implementation challenges

I think the main big challenges would be to adapt the cache to the fact that we would now only "partially" calculate some variables.

There will also be some plumbing to do, but the way formulas are written is actually helping a lot: because they take "persons" array as a first argument, this persons can be an object that represent a subset of the simulation's persons without too much adaptation.

[Morendil]

The "depth" factor would strike me as an important one to study too, understood as how many vector computations are chained that depend on one another.

The benefits of SC will multiply in the common cases but that is a lower bound; given small enough frequencies, or (and that is likely common) mutually exclusive conditions at various depths, SC will eliminate altogether some branches of the computation tree.

[bonjourmauko]

The initial need of <15s for LexImpact has been achieved since.

Closing for now, do not hesitate for reopen in the future.

Thanks for all the work! ✨