MathGroup Archive 2005

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

Search the Archive

Re: Re: Re: Re: Re: Slowdown


On Jan 5, 2005, at 1:21 AM, Andrzej Kozlowski wrote:



> 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.
I think the slowdown is
either
it goes to that portion of the memory which might be already out on  
disk when it is called,
or
the Mod[FromDigits[list, k], m] structure of Hash - I am just guessing  
based upon Wolfram's NKS page 1100  
http://www.wolframscience.com/nksonline/page-1100d-text - where m is  a  
prime in the form of k^s-1 has some issue with the selected prime, and  
it takes longer to compute.

János

> 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: global assumptions?? How far can I go?
  • Next by Date: Re: Re: Re: Re: Re: Slowdown
  • Previous by thread: Re: Re: Re: Re: Slowdown
  • Next by thread: Re: Re: Re: Re: Re: Slowdown