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/