rp2 icon indicating copy to clipboard operation
rp2 copied to clipboard

Make FIFO accounting_method linear time

Open qwhelan opened this issue 9 months ago • 3 comments

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

qwhelan avatar May 14 '24 05:05 qwhelan