Re: Slowdown
- To: mathgroup at smc.vnet.net
- Subject: [mg53221] Re: Slowdown
- From: David Bailey <dave at Remove_Thisdbailey.co.uk>
- Date: Sat, 1 Jan 2005 02:33:41 -0500 (EST)
- References: <cr33tt$je6$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Maxim wrote:
> Consider:
>
> In[1]:=
> Module[{f, L},
> L = f[];
> Do[L = f[L, i], {i, 10^4}]
> ] // Timing
>
> Module[{weirdness, L},
> L = weirdness[];
> Do[L = weirdness[L, i], {i, 10^4}]
> ] // Timing
>
> Out[1]=
> {0.015*Second, Null}
>
> Out[2]=
> {3.063*Second, Null}
>
> Here the timings differ by a factor of 200. Besides, the timing grows
> linearly in the first case and quadratically in the second (therefore, for
> n=10^5 there will be an approximately 2000 times slowdown). We can only
> guess that something goes wrong with the symbol name hashing.
>
> Maxim Rytin
> m.r at inbox.ru
>
Hi Maxim,
I found those timings very interesting. I remember doing some timing
experiments a long time ago - trying to see if when you constructed a
complicated structure - as you are obviously doing - the time went up
quadratically. I expected it would, because each time a new expression
is created, the system has to check that nothing has changed inside the
existing expression, which is getting ever bigger. Although it is clear
to a human in most cases that this is so, it is obviously not easy to
get a machine to do this efficiently. In fact, all my experiments
indicated that adding a new layer to a large structure was no more
expensive that adding one to a tiny structure!
This led me to speculate that maybe Mathematica holds some sort of an
array of bits generated by hash to test to see if a large expression
could have changed (say because of a variable assignment) since it was
created. If this idea is close to the truth, then you would expect there
to be exceptional situations where the hash values would clash and cause
a quadratic time dependency. This could hardly be called "something
going wrong", however - anything that uses a hash strategy will run
slowly in some situations.
Your phenomenon is quite robust, in that it can be set up as a function
that can be used to test any symbol:
test[x_]:=Timing[Module[{x,L},
L=weirdness[];
Do[L=weirdness[L,i],{i,10^4}]]][[1]]
Sure enough test[weirdness] is very slow. Moreover, it is slow every
time you run it, even though each time the Module is run a DIFFERENT
local variable will be created. Therefore, I set Mathematica going
creating 9-letter random variables and testing each in turn - looking
for another 'weird' variable. So far, I have found no others - so the
phenomenon you have discovered must be quite rare.
After searching random variables for a bit test[weirdness] seems to
become even more expensive, but curiously, after a really long search,
'weirdness' lost its weirdness - I guess something gets restructured
when a very large number of symbols get created.
My tests were done on a Windows XP machine, is the variable 'weirdness'
just as weird on other platforms, I wonder?
It would be interesting if we could tempt someone from WRI to comment!
David Bailey
dbaileyconsultancy.co.uk