eprbell / rp2

Privacy-focused, free, open-source cryptocurrency tax calculator for multiple countries: it handles multiple coins/exchanges and computes long/short-term capital gains, cost bases, in/out lot relationships/fractioning, and account balances. It supports FIFO, LIFO, HIFO and it outputs in form 8949 format. It has a programmable plugin architecture
https://pypi.org/project/rp2/
Apache License 2.0
256 stars 42 forks source link

Make FIFO accounting_method linear time #115

Closed qwhelan closed 1 month ago

qwhelan commented 1 month ago

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 commented 1 month ago

@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.

qwhelan commented 1 month ago

@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.

qwhelan commented 1 month ago

@eprbell Should be ready for final review/merge now