Extending Plus very slow

• To: mathgroup at smc.vnet.net
• Subject: [mg66761] Extending Plus very slow
• From: Giuseppe Bilotta <bilotta78 at hotpop.com>
• Date: Mon, 29 May 2006 06:06:03 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```Still working with extending the internals of Mathematica to deal with
AffineExpression objects, I found an interesting bottleneck in the way
Plus is handled. If I have:

Unprotect[Plus];
PlusNS[a__AffineExpression /; Length[{a}] > 1] :=
Sanitize@AffineExpression[Plus @@ Center /@ {a},
Join @@ Deviations /@ {a}];
Plus[a__AffineExpression /; Length[{a}] > 1] :=
Sanitize@AffineExpression[Plus @@ Center /@ {a},
Join @@ Deviations /@ {a}];
a_AffineExpression + b_Interval := a + AffineExpression[b]
a_Interval + b_AffineExpression := AffineExpression[a] + b
AffineExpression[c_, dev_] + other_?NumberQ :=
AffineExpression[c + other, dev]
Protect[Plus];

and then run an intensive test

LastNoiseSymbol = 0;
rndaff :=
AffineExpression[Random[Real, {-1, 1}], Table[{Random[Integer, {2,
20}], Random[Real, {-1, 1}]}, {Random[Integer, {2, 8}]}]];
Timing@(pretest = Table[rndaff, {10000}];)
Timing@(test = Sanitize /@ pretest;)
Timing@(sns = PlusNS @@ test;)
Timing@(sp = Plus @@ test;)

I get that sp calculates in about 10 times as much time as sns (about
5 seconds vs about .5 seconds).

This is quite bothersome, since the algorithms I need this for has dot
products at its core. Is there a way to speed this up?

A related remark, although not strictly part of my quesiton, is the
following: the idea at the core of Sanitize is the same as the
pairPlus function defined as an example in the Mathematica help (MH)
for Plus (Sanitize additionally Select[]s the pairs where the second
element is not null). MH defines pairPlus as

{#[[1, 1]], Plus @@ Last /@ #} & /@ Split[Sort@alist,
First[#1] === First[#2] &]

whereas on my own I had defined it as

Reap[Sow[#2, #1] & @@ # & /@ alist, _, {#1, Plus @@ #2} &][[2]]

By running the tests above it turns out that

1. sanitizing many short lists (e.g. calculating test from pretest) is
faster with MH code (1.8 seconds vs 2.2)
2. sanitizing a single long list (e.g. calculating sns) is faster with
my code (0.6 vs 0.8)

so it seems that MH code is faster for many runs with short lists,
whereas my code is faster for few runs with long lists (this probably
depends on the fact that MH needs to Sort[] the list)

Interestingly, sp takes about the same time regardless of the pairPlus
code used, so it somehow hits the sweet spot between length of lists
and number of runs.

--
Giuseppe "Oblomov" Bilotta

"E la storia dell'umanità, babbo?"
"Ma niente: prima si fanno delle cazzate,
poi si studia che cazzate si sono fatte"
(Altan)