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
