WOLFRAM

Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2005

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

Search the Archive

Re: Re: Re: Re: Slowdown

OK., I should have written "dive". But I would expect that the people  
who wrote to point out this important difference should also explain  
why it is so important. As for me I only wanted to note that the rather  
dramatic change in hash  values that corresponds with a dramatic  
slowdown. This suggests that indeed the problem is related to the  
hashing of names of the form name$number.
On the other  hand if you look at any sequence of hash values of names  
constructed by starting with some name and appending $number, where  
number changes through successive values, you will find  that you get  
sequences of successive positive integers with periodic "dives" or  
"jumps". However, in no other case I have noticed any slowdown. If the  
slowdown is caused by a "collision" of hash values, as seems likely,  
there should be other cases too, but they would be extremely rare and I  
do not know of any way to find them except by relying on chance (very  
unlikely to produce any result).

Andrzej

On 5 Jan 2005, at 02:42, DrBob wrote:

>>> You can see a big jump in the hash value at weirdness$10.
>
> Actually, the hash value gets much SMALLER at that point.
>
> Bobby

>
> On Tue, 4 Jan 2005 03:13:00 -0500 (EST), Andrzej Kozlowski  
> <akoz at mimuw.edu.pl> wrote:
>
>> I just noticed another thing, which seems to throw more light at what
>> is happenng. Look carefully at the Hash values of the different names
>> of the form weirdness$number:
>>
>>
>> MapIndexed[{First[#2], Hash[#1]} & ,
>>    ToExpression /@ (StringJoin["weirdness", "$",
>>        ToString[#1]] & ) /@ Range[20]]
>>
>>
>> {{1, 1783099877}, {2, 1783099878}, {3, 1783099879},
>>    {4, 1783099880}, {5, 1783099881}, {6, 1783099882},
>>    {7, 1783099883}, {8, 1783099884}, {9, 1783099885},
>>    {10, 667842086}, {11, 667842087}, {12, 667842088},
>>    {13, 667842089}, {14, 667842090}, {15, 667842091},
>>    {16, 667842092}, {17, 667842093}, {18, 667842094},
>>    {19, 667842095}, {20, 667843323}}
>>
>> You can see a big jump in the hash value at weirdness$10. That is
>> exactly the point at which the slowdown occurs.
>>
>> Andrzej Kozlowski
>>
>>
>> On 3 Jan 2005, at 21:55, Andrzej Kozlowski wrote:
>>
>>> I can't see any siginificant slowdowns demonstrated by your code. The
>>> differences in timings between different combinations seem
>>> insignificant. Cna you suggest any other name but "weirdness" that
>>> shows significant slowdown?
>>>
>>> Besides, using Module only obsures what is really happening. Module
>>> simply renames local variables by appending $somenumber to their name
>>> but the "number" that is used is different each time. You can do that
>>> whiteout Module and see exactly which names produce the slowdown
>>> effect. It seems that the names weirdness$1 to weirdness$9 do not.
>>>
>>> In[1]:=
>>> L=weirdness$1[];
>>>           Do[L=weirdness$1[L,i],{i,10^4}]//Timing
>>>
>>> Out[2]=
>>> {0.03 Second,Null}
>>>
>>> In[3]:=
>>> L=weirdness$9[];
>>>           Do[L=weirdness$9[L,i],{i,10^4}]//Timing
>>>
>>> Out[4]=
>>> {0.08 Second,Null}
>>>
>>> The problem seems to begin with weirdness$10
>>>
>>> In[5]:=
>>> L=weirdness$10[];
>>>           Do[L=weirdness$10[L,i],{i,10^4}]//Timing
>>>
>>> Out[6]=
>>> {13.2 Second,Null}
>>>
>>> and continues for higher values, as far as I have checked.
>>>
>>> When you run Module with a fresh Kernel Mathematica seems to always
>>> begin by appending $17:
>>>
>>> In[1]:=
>>> Module[{weirdness, L},
>>>    L = weirdness[];
>>>    Do[L = weirdness[L, i], {i, 1}]
>>> ] // Trace
>>>
>>> Out[1]=
>>> {Module[{weirdness,L},L=weirdness[]; 
>>> Do[L=weirdness[L,i],{i,1}]],{L$17=\
>>> weirdness$17[];Do[L$17=weirdness$17[L$17,
>>>
>>> i],{i,1}],{L$17=weirdness$17[],weirdness$17[]},{Do[L$17=weirdness$17[ 
>>> L$
>>> \
>>> 17,i],{i,1}],{{{L$17,weirdness$17[]},{i,1},weirdness$17[weirdness$17[ 
>>> ],
>>>
>>> 1]},L$17=weirdness$17[weirdness$17[],1],weirdness$17[weirdness$17[],1 
>>> ]\
>>> },Null},Null},Null}
>>>
>>> on subsequent runs this is increased:
>>>
>>> In[2]:=
>>> Module[{weirdness, L},
>>>    L = weirdness[];
>>>    Do[L = weirdness[L, i], {i, 1}]
>>> ] // Trace
>>>
>>> Out[2]=
>>> {Module[{weirdness,L},L=weirdness[]; 
>>> Do[L=weirdness[L,i],{i,1}]],{L$19=\
>>> weirdness$19[];Do[L$19=weirdness$19[L$19,
>>>
>>> i],{i,1}],{L$19=weirdness$19[],weirdness$19[]},{Do[L$19=weirdness$19[ 
>>> L$
>>> \
>>> 19,i],{i,1}],{{{L$19,weirdness$19[]},{i,1},weirdness$19[weirdness$19[ 
>>> ],
>>>
>>> 1]},L$19=weirdness$19[weirdness$19[],1],weirdness$19[weirdness$19[],1 
>>> ]\
>>> },Null},Null},Null}
>>>
>>> in any case all these numbers are larger than 10 and produce  
>>> slowdown,
>>> but the numbers 10-16 which never occur inside Module also suffer  
>>> form
>>> this problem:
>>>
>>> In[3]:=
>>> L=weirdness$11[];
>>>           Do[L=weirdness$11[L,i],{i,10^4}]//Timing
>>>
>>> Out[4]=
>>> {13.1 Second,Null}
>>>
>>> In[5]:=
>>> L=weirdness$16[];
>>>           Do[L=weirdness$16[L,i],{i,10^4}]//Timing
>>>
>>> Out[6]=
>>> {14.62 Second,Null}
>>>
>>> However, I have not been able to find any other name but weirdness
>>> that produces this effect. This seems weird.
>>>
>>> Andrzej Kozlowski
>>>
>>>
>>>
>>> On 3 Jan 2005, at 18:29, yehuda ben-shimol wrote:
>>>
>>>> Hi Roland,
>>>> I'm afraid this is not true. Just try to run the code I sent with my
>>>> post.  "weirdness" was time consuming while weirdness1 was not. In
>>>> addition it happened (not consistently) that function name of a  
>>>> SINGLE
>>>> character suffered from this behavior as well.
>>>> the code is given below for your convenience.
>>>>
>>>> t = CharacterRange["a", "z"];
>>>> Do[fname = StringJoin[t[[Table[Random[Integer, {1,26}], {i}]]]];
>>>> Print[i, "\t", fname, "\t",
>>>> 	Timing[
>>>> 	  Module[{fs = ToExpression[fname], L},
>>>>           L = fs[];
>>>>         Do[L = fs[L, j], {j, 104}]]]], {i, 1, 50}, {5}]
>>>>
>>>>
>>>> yehuda
>>>>
>>>> Roland Franzius 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.
>>>>>>
>>>>>>
>>>>>
>>>>> The timing difference occurs when the symbol "wierdness" exceeds 8
>>>>> characters. Test it for "wierdnes". That seems to be a consequence  
>>>>> of
>>>>> the machine routine for string comparison. Up to 8 characters can  
>>>>> be
>>>>> used without using a memory to memory compare. Of course it should  
>>>>> be
>>>>> possible to write a compare routine that makes not such a bit step.
>>>>>
>>>>
>>>
>>
>>
>>
>>
>
>
>
> -- 
> DrBob at bigfoot.com
> www.eclecticdreams.net
>
  • Prev by Date: Re: Spherical density visualization
  • Next by Date: Re: Re: Re: Re: Slowdown
  • Previous by thread: Re: Re: Re: Slowdown
  • Next by thread: Re: Re: Re: Re: Re: Slowdown