rp2
rp2 copied to clipboard
Make FIFO accounting_method linear time
The FIFO accounting method is unfortunately quadratic time, even in trivial cases:
One In, One Out
FIFO LIFO HIFO
1 0.000234 0.000234 0.000231
10 0.001319 0.001319 0.001431
100 0.020807 0.013064 0.022888
1000 1.073289 0.129614 1.145311
Buys, then Sells
FIFO LIFO HIFO
1 0.000225 0.000236 0.000239
10 0.001399 0.001412 0.001534
100 0.022002 0.023371 0.031054
1000 1.119583 1.103518 1.977542
The "One In, One Out" alternates n pairs of BUY, SELL such that there is only ever k=1 active lots. This represents the most trivial case for any accounting method. A potential worst case is represented by "Buys, then Sells" which creates n BUYS followed by n SELLS. This creates a worst case scenario of k=n.
In the first case, the LIFO method is roughly linear; in the second case, it is clearly quadratic. The quadratic behavior of LIFO and HIFO will be addressed in a separate PR by using heapq.
It is relatively straightforward to make FIFO linear time in both of these cases by simply advancing an index of the next, un-exhausted lot on AcquiredLotCandidates and persisting this object between invocations of get_acquired_lot_for_taxable_event(). In the event of different accounting methods being used for different tax years, a one-time scan is performed for each switch of accounting method to find the appropriate index.
With this PR, FIFO performance improves to linear time in both cases:
One In, One Out
FIFO LIFO HIFO
1 0.000245 0.000248 0.000242
10 0.001359 0.001396 0.001423
100 0.012248 0.012903 0.022407
1000 0.127431 0.133112 1.161365
Buys, then Sells
FIFO LIFO HIFO
1 0.000233 0.000258 0.000243
10 0.001345 0.001436 0.001533
100 0.012368 0.023112 0.031476
1000 0.129783 1.185451 2.029749
@eprbell Of course, no rush. In the event it's useful, I've uploaded https://github.com/eprbell/rp2/pull/116 so you can check out the LIFO/HIFO changes as well. The latter can wait until this is merged if it over-complicates things.
@eprbell Sure, didn't realize GitHub made it hard to review. The force-pushing was mostly cleaning up early commits with issues I realized later, so I'll try to avoid going forward.
@eprbell Should be ready for final review/merge now