[lmi] IRRs really are costly [Was: _M_range_check fails when running "new" PDF]

[Greg Chicares]

On 2018-02-13 23:07, Vadim Zeitlin wrote:
[...]
>  The problem is due to "IrrCsv_GuaranteedZero" vector being empty
My first thought was to calculate all IRRs all the time. At one time
we thought it worthwhile to calculate IRRs only if necessary, but I
wondered whether that was still the case now, several hardware
generations later. It is.

I used the experimental patch below[0] to measure the cost (using
Ctrl-F to choose at least one IRR column for the calculation summary);
it takes about twelve milliseconds. A default illustration for an
mce_nasd product takes about twenty-five milliseconds to calculate
according to the statusbar, so selecting any IRR costs about fifty
percent extra run time.

With IRRs selected, the statusbar looks like:
  Calculate: 25 milliseconds; format: 30 milliseconds
Deselecting IRRs reduces the "format" timing instead of the "Calculate"
timing, because this calculation isn't done in the "Calculate" step:
it's conditional on the chosen format, so it's deferred to the "format"
step, weird though that certainly is.

I don't suppose we'll make IRR calculations any faster. There's no
better general algorithm for root-finding than the one we already
use (Brent's). Some researchers have suggested special algorithms
for IRR, e.g.:
  
http://www.jofamericanscience.org/journals/am-sci/am1011/029_27371am101114_216_221.pdf
but a cursory examination of that paper doesn't leave me with the
impression that their method would perform noticeably better, and
coding and debugging it would take more time that I want to spend.

Typically, we find IRRs to five decimals (e.g., .12345 = 12.345%),
which seems wasteful because we only print four--and doesn't give
better results, because instead of a point estimate that's rounded,
we calculate a range and pick the lower bound. However, it is less
accurate:
                    choose_lower  format
  [12.345, 12.346] --> 12.345  --> 12.35
  [12.34,  12.35 ] --> 12.34   --> 12.34
so we should change all '.rounding' files--not for speed, but
because reducing precision improves accuracy, or, more exactly,
better prevents loss of accuracy.

It may also be observed that the cost doesn't vary remarkably by
the demanded precision--with a trivially obvious change to the
unit test that's too verbose to present as a patch here, I see:

  Speed test: vector of irrs, length 100, 0 decimals
    3.839e-003 s mean;       3366 us least of 100 runs
  Speed test: vector of irrs, length 100, 1 decimals
    3.599e-003 s mean;       3576 us least of 100 runs
  Speed test: vector of irrs, length 100, 2 decimals
    3.800e-003 s mean;       3636 us least of 100 runs
  Speed test: vector of irrs, length 100, 3 decimals
    3.679e-003 s mean;       3650 us least of 100 runs
  Speed test: vector of irrs, length 100, 4 decimals
    3.702e-003 s mean;       3668 us least of 100 runs
  Speed test: vector of irrs, length 100, 5 decimals
    3.708e-003 s mean;       3678 us least of 100 runs
  Speed test: vector of irrs, length 100, 6 decimals
    3.726e-003 s mean;       3682 us least of 100 runs

IOW, Brent's method converges so quickly that, if we stop it when
four decimals of accuracy have been obtained, we already have six
or more (in this unit test, which is designed to resemble real-world
problems). That's not surprising: the secant method's order of
convergence is ϕ = 1.618, and the inverse quadratic interpolation
that Brent uses is about halfway between that and quadratic
convergence.

---------

"the experimental patch below":

---------8<--------8<--------8<--------8<--------8<--------8<--------8<-------
diff --git a/ledger_text_formats.cpp b/ledger_text_formats.cpp
index f82045bb4..a28d81590 100644
--- a/ledger_text_formats.cpp
+++ b/ledger_text_formats.cpp
@@ -37,6 +37,7 @@
 #include "map_lookup.hpp"
 #include "mc_enum_types_aux.hpp"        // is_subject_to_ill_reg()
 #include "miscellany.hpp"
+#include "timer.hpp"
 #include "value_cast.hpp"
 
 #include <algorithm>                    // find()
@@ -194,7 +195,10 @@ 
calculation_summary_formatter::calculation_summary_formatter
             ;
         if(want_any_irr && !invar_.IsInforce)
             {
+    Timer timer;
             unclean.CalculateIrrs(ledger_);
+    timer.stop();
+warning() <<    timer.elapsed_msec_str() << LMI_FLUSH;
             }
         else
             {
--------->8-------->8-------->8-------->8-------->8-------->8-------->8-------