MathGroup Archive 2005

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

Search the Archive

Re: Re: Slowdown

  • To: mathgroup at
  • Subject: [mg53234] Re: [mg53221] Re: Slowdown
  • From: Andrzej Kozlowski <akoz at>
  • Date: Sun, 2 Jan 2005 04:12:42 -0500 (EST)
  • Sender: owner-wri-mathgroup at

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
> 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

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:


{0.07 Second,Null}


{17.92 Second,Null}


{13.26 Second,Null}


5.1 for Mac OS X (October 25, 2004)

Andrzej Kozlowski
Chiba, Japan

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