Re: Re: Slowdown
- To: mathgroup at smc.vnet.net
- Subject: [mg53236] Re: [mg53221] Re: Slowdown
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sun, 2 Jan 2005 04:12:45 -0500 (EST)
- References: <cr33tt$je6$1@smc.vnet.net> <200501010733.CAA01134@smc.vnet.net> <E11A8158-5BF2-11D9-8DF3-000A95B4967A@mimuw.edu.pl>
- Sender: owner-wri-mathgroup at wolfram.com
There was some confusion in the names I used in my earlier message so
here are the results again. They look even more "weird":
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$1[L,i],{i,10^4}]//Timing
Out[4]=
{0.06 Second,Null}
In[5]:=
L=weirdness$25[];
Do[L=weirdness$25[L,i],{i,10^4}]//Timing
Out[6]=
{14.76 Second,Null}
In[7]:=
L=weirdness[];
Do[L=weirdness[L,i],{i,10^4}]//Timing
Out[8]=
{0.07 Second,Null}
In[9]:=
$Version
Out[9]=
5.1 for Mac OS X (October 25, 2004)
Andrzej
On 1 Jan 2005, at 21:44, Andrzej Kozlowski wrote:
> 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/
>
- References:
- Re: Slowdown
- From: David Bailey <dave@Remove_Thisdbailey.co.uk>
- Re: Slowdown