Re: Re: Re: Re: Slowdown

*To*: mathgroup at smc.vnet.net*Subject*: [mg53309] Re: [mg53278] Re: [mg53254] Re: [mg53241] Re: Slowdown*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Wed, 5 Jan 2005 01:21:34 -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>*Sender*: owner-wri-mathgroup at wolfram.com

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 >

**Follow-Ups**:**Re: Re: Re: Re: Re: Slowdown***From:*János <janos.lobb@yale.edu>

**Re: Re: Re: Re: Re: Slowdown***From:*János <janos.lobb@yale.edu>

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