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

**Re: Slowdown**

**Simple Fourier help**

**Re: Slowdown**

**Re: Re: Slowdown**