MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Slowdown
  • Next by Date: Simple Fourier help
  • Previous by thread: Re: Slowdown
  • Next by thread: Re: Re: Slowdown