Re: Re: Re: Re: Re: Slowdown
- To: mathgroup at smc.vnet.net
- Subject: [mg53329] Re: [mg53309] Re: [mg53278] Re: [mg53254] Re: [mg53241] Re: Slowdown
- From: János <janos.lobb at yale.edu>
- Date: Thu, 6 Jan 2005 02:52:07 -0500 (EST)
- References: <cr33tt$je6$1@smc.vnet.net> <200501020912.EAA27775@smc.vnet.net> <200501030929.EAA10649@smc.vnet.net> <C570DAF1-5D86-11D9-8B6F-000A95B4967A@mimuw.edu.pl> <200501040813.DAA27157@smc.vnet.net> <opsj294nmciz9bcq@monster.ma.dl.cox.net> <200501050621.BAA11685@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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 >> >>
- References:
- Re: Slowdown
- From: Roland Franzius <roland.franzius@uos.de>
- Re: Re: Slowdown
- From: yehuda ben-shimol <benshimo@bgu.ac.il>
- Re: Re: Re: Slowdown
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Re: Re: Re: Re: Slowdown
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Re: Slowdown