vermaseren / form

The FORM project for symbolic manipulation of very big expressions
GNU General Public License v3.0
1.16k stars 138 forks source link

micro-optimization: input vector for poly::get_variables() #571

Open tueda opened 2 weeks ago

tueda commented 2 weeks ago

poly::get_variables() does not need a temporary copy of the input vector containing pointers to function arguments. Passing it by reference rather than by value avoids a heap allocation and a memory copy.

coveralls commented 2 weeks ago

Coverage Status

coverage: 49.988% (+0.002%) from 49.986% when pulling 506e5d945784ccf886520d37678d2c76b241ce32 on tueda:improve-get_variables into 61ecfdd9655bae0641e6a3a01ae73edfd1a081b9 on vermaseren:master.

tueda commented 2 weeks ago

I've reserved capacity for vectors passed to poly::get_variables() when they are known to have a fixed size. Without reserving capacity, for example,

vector<WORD *> e;
e.push_back(a);
e.push_back(b);
poly::get_variables(BHEAD e, false, false);

calls new and delete twice each, because typically the capacity grows as 0, 1, 2, 4, ..., so a reallocation is needed.

If we can use C++11, then this could be rewritten with std::array and by templatizing:

    template <typename Container>
    static void get_variables (PHEAD const Container &, bool, bool);

(Optionally, with_arghead and bool sort_vars can be converted to template parameters, which allows more compiler optimization.)

jodavies commented 2 weeks ago

Could you measure any improvement from these in poly benches? #297 could go in with this also in principle?

tueda commented 2 weeks ago

The improvement in speed is negligible. So, practically, the difference is only in writing code in a more proper style.

  Revision: v5.0.0-beta.1-71-g61ecfdd (master)
  Command being timed: "/home/tueda/work/form/build/sources/form ratfuntest.frm"
  n = 10                                            Mean (          SD)            Min            Max
  User time (seconds):                            14.139 (       0.028)          14.08          14.17
  System time (seconds):                           0.508 (       0.021)           0.48           0.55

  Revision: v5.0.0-beta.1-71-g61ecfdd (master)
  Command being timed: "/home/tueda/work/form/build/sources/form test-mbox1l.frm"
  n = 10                                            Mean (          SD)            Min            Max
  User time (seconds):                            42.063 (       0.018)          42.04           42.1
  System time (seconds):                           0.030 (       0.011)           0.01           0.05

vs.

  Revision: v5.0.0-beta.1-73-g506e5d9 (improve-get_variables)
  Command being timed: "/home/tueda/work/form/build/sources/form ratfuntest.frm"
  n = 10                                            Mean (          SD)            Min            Max
  User time (seconds):                            14.170 (       0.028)          14.13          14.21
  System time (seconds):                           0.513 (       0.025)           0.47           0.56

  Revision: v5.0.0-beta.1-73-g506e5d9 (improve-get_variables)
  Command being timed: "/home/tueda/work/form/build/sources/form test-mbox1l.frm"
  n = 10                                            Mean (          SD)            Min            Max
  User time (seconds):                            42.142 (       0.021)          42.11          42.17
  System time (seconds):                           0.024 (       0.010)           0.01           0.04