MathGroup Archive 2005

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

Search the Archive

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/


  • Prev by Date: Re: mathematica parser
  • Next by Date: Re: Slowdown
  • Previous by thread: Re: Re: Re: Re: Slowdown
  • Next by thread: Re: Slowdown