Crud, I forgot to attach the quicksort in the last one... Brian
On Sat, 2002-05-25 at 21:17, brian wheeler wrote: > On Fri, 2002-05-24 at 15:10, Sean O'Rourke wrote: > > > I was starting with a very simple test to decide how to determine where the > > > memory overuse was coming from, > > > > I'm actually looking at this now as well, though with zip2.pasm instead of > > quicksort. What I've found is that because zip constructs the result with > > incremental packing, and since the 3-argument pack is implemented through > > string_concat, which allocates a new string every time, it chews through > > vast quantities of memory. At some point, these buffers (which are now > > ~45k each) stop getting freed, and Parrot grows from < 10M to about 200M > > before my laptop dies a horrible death. > > > > Sort does things much differently, but I wouldn't be surprised if it's > > hittng the same things-not-being-reclaimed bug as zip. > > > > > ["interesting" sorting results] > > > Am I missing something somewhere? > > > > You've probably got it in EBCDIC mode or something. That or it's a > > "randomized" quicksort, which is supposed to be faster. > > > > /s > > Actually I was getting the wrong results because I was using ge & le to > test the bounds when I should have used gt & lt. > > The attached quicksort fixes it. Its still _huge_ when the memory runs. > > > Looking at the profile data, it looks like Parrot_pushs is the big time > user... > % cumulative self self total > time seconds seconds calls ns/call ns/call name > 66.67 0.02 0.02 singlebyte_decode > 33.33 0.03 0.01 646 15479.88 15479.88 Parrot_pushs > > > Of course, if I understood the calling convention, I might get away with > less pushs's :) > > Brian > > > >
# # quicksort.pasm # # Author: Brian Wheeler ([EMAIL PROTECTED]) # # Usage: # ./parrot quicksort.pbc < /file/to/quicksort # main: new P0,PerlArray set I1,0 m1: readline S0,0 length I0,S0 eq I0,0,m2 chopn S0,1 set_keyed P0,I1,S0 inc I1 branch m1 m2: set I0,0 set I1,P0 dec I1 bsr quicksort m3: get_keyed S0,P0,I0 print S0 print "\n" inc I0 le I0,I1,m3 end # # quicksort # params: # I0 low # I1 high # P0 array to sort # returns: # nothing quicksort: pushi print "Starting quicksort with " print I0 print " and " print I1 print "\n" set I11,I1 # High=high; set I10,I0 # Low=low; le I1,I0,q1 # if(high>low) { bsr partition # pivot=partition(p,low,high); set I0,I10 # quicksort(p,Low,pivot-1) set I1,I2 dec I1 bsr quicksort set I0,I2 # quicksort(p,pivot+1,High) inc I0 set I1,I11 bsr quicksort q1: popi # } ret # # partition # params: # I0 low # I1 high # P0 array to sort # returns: # I2 pivot partition: pushi pushs get_keyed S2,P0,I0 # S2 is pivot_item set I2,I0 # I2 is pivot index set I10,I0 # I10 is left set I11,I1 # I11 is right p1: ge I10,I11,p1e # while(left < right) { p2: get_keyed S0,P0,I10 # while(p[left] <= pivot_item gt S0,S2,p2e gt I10,I11,p2e # && left <= right) { inc I10 # left++; branch p2 # } p2e: p3: get_keyed S1,P0,I11 # while(p[right] > pivot_item le S1,S2,p3e lt I11,I10,p3e # && right >= left) { dec I11 # right--; branch p3 # } p3e: ge I10,I11,p4 # if(left < right) { get_keyed S3,P0,I10 # swap(p,left,right); get_keyed S4,P0,I11 set_keyed P0,I11,S3 set_keyed P0,I10,S4 p4: # } branch p1 # } p1e: get_keyed S3,P0,I11 # p[low]=p[right]; set_keyed P0,I0,S3 set_keyed P0,I11,S2 # p[right]=pivot_item; save I11 pops popi restore I2 # return right; ret