Re: Re: Slowdown

*To*: mathgroup at smc.vnet.net*Subject*: [mg53234] Re: [mg53221] Re: Slowdown*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Sun, 2 Jan 2005 04:12:42 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

On 1 Jan 2005, at 16:33, David Bailey wrote: > 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 > > The problem does not actually seem to involve Module itself, rather it appears connected with variable names of the form weirdness$somenumber. Here is what I see: In[1]:= L=weirdness[]; Do[L=weirdness[L,i],{i,10^4}]//Timing Out[2]= {0.07 Second,Null} In[3]:= L=weirdness$1[]; Do[L=weirdness$25[L,i],{i,10^4}]//Timing Out[4]= {17.92 Second,Null} In[5]:= L=weirdness$25[]; Do[L=weirdness$25[L,i],{i,10^4}]//Timing Out[6]= {13.26 Second,Null} In[7]:= $Version Out[7]= 5.1 for Mac OS X (October 25, 2004) Andrzej Kozlowski Chiba, Japan http://www.akikoz.net/~andrzej/ http://www.mimuw.edu.pl/~akoz/

**Re: mathematica parser**

**Re: Slowdown**

**Re: Re: Re: Re: Slowdown**

**Re: Slowdown**