I've written a quicksort which will sort a file on stdin. It could go
into examples, I suppose.
System: Athlon 700 running Redhat 7.3
Parrot is using defaults
Running "./parrot quicksort.pbc < rx.ops" returns times like:
real 0m34.166s
user 0m5.830s
sys 0m3.840s
Which seems a bit long for sorting a 1352 line file. In any case, the
thing that disturbs me most is the memory usage. It peaks at over
422M...which is a bit overkill :) Since it goes goes down before the
process is finished, it doesn't seem like a memory leak.
So, did I:
* really mess up the sort algoritm
* optimize the wrong way (oh! Its like *golf* scores...)
* create the first parrot denial-of-service attack
* find an interesting benchmark
Well, I suspect the first or last :)
Building parrot with -pg makes it run 5s slower. The gprof -T dump of
the timings looks like this:
% cumulative self self total
time seconds seconds calls ms/call ms/call name
34.3 0.12 0.12 90285 0.00 0.00 string_compare [8]
20.0 0.19 0.07 1 70.00 349.75 cg_core [6]
8.6 0.22 0.03 12 2.50 2.50 compact_string_pool [17]
5.7 0.24 0.02 9986 0.00 0.00 new_string_header [11]
5.7 0.26 0.02 7265 0.00 0.01
Parrot_PerlString_set_string_native [9]
5.7 0.28 0.02 7265 0.00 0.01 string_copy [10]
2.9 0.29 0.01 97549 0.00 0.00
Parrot_PerlArray_get_string_keyed [22]
2.9 0.30 0.01 9986 0.00 0.00 Parrot_allocate_string [12]
2.9 0.31 0.01 9151 0.00 0.00 buffer_lives [23]
2.9 0.32 0.01 7265 0.00 0.02
Parrot_PerlArray_set_string_keyed [7]
2.9 0.33 0.01 2721 0.00 0.01 string_make [13]
2.9 0.34 0.01 38 0.26 0.26 free_unused_buffers [24]
2.9 0.35 0.01 19 0.53 0.53 trace_active_buffers [21]
0.0 0.35 0.00 229658 0.00 0.00 singlebyte_decode [65]
0.0 0.35 0.00 229658 0.00 0.00 singlebyte_skip_forward [66]
0.0 0.35 0.00 104814 0.00 0.00 atom2int [67]
0.0 0.35 0.00 97549 0.00 0.00 Parrot_PerlString_get_string [68]
0.0 0.35 0.00 13512 0.00 0.00 add_to_free_pool [69]
0.0 0.35 0.00 11353 0.00 0.00 mem_allocate [16]
0.0 0.35 0.00 11343 0.00 0.00 get_from_free_pool [14]
0.0 0.35 0.00 11068 0.00 0.00 string_length [70]
0.0 0.35 0.00 9349 0.00 0.00 string_to_cstring [62]
0.0 0.35 0.00 9110 0.00 0.00 mark_used [71]
0.0 0.35 0.00 5777 0.00 0.00 mem_sys_allocate [72]
0.0 0.35 0.00 5683 0.00 0.00 alloc_new_block [73]
0.0 0.35 0.00 5431 0.00 0.00 mem_sys_free [74]
0.0 0.35 0.00 4673 0.00 0.00 stack_pop [75]
0.0 0.35 0.00 4673 0.00 0.00 stack_push [76]
0.0 0.35 0.00 3505 0.00 0.00 Parrot_pop_i [77]
0.0 0.35 0.00 3505 0.00 0.00 Parrot_push_i [78]
0.0 0.35 0.00 3505 0.00 0.00 pop_dest [79]
0.0 0.35 0.00 2718 0.00 0.00 Parrot_encoding_lookup [80]
0.0 0.35 0.00 1359 0.00 0.00 Parrot_reallocate [26]
0.0 0.35 0.00 1357 0.00 0.00 new_pmc_header [27]
0.0 0.35 0.00 1357 0.00 0.01 pmc_new <cycle 1> [19]
0.0 0.35 0.00 1355 0.00 0.00 resize_array [28]
0.0 0.35 0.00 1353 0.00 0.01 Parrot_PerlString_init [20]
0.0 0.35 0.00 1352 0.00 0.00 singlebyte_skip_backward [81]
0.0 0.35 0.00 1352 0.00 0.00 string_chopn [82]
0.0 0.35 0.00 1168 0.00 0.00 Parrot_pop_s [83]
0.0 0.35 0.00 1168 0.00 0.00 Parrot_push_s [84]
0.0 0.35 0.00 24 0.00 0.00 PackFile_fetch_op [85]
0.0 0.35 0.00 22 0.00 1.36 Parrot_do_dod_run [15]
0.0 0.35 0.00 20 0.00 0.00 restore_invariants [86]
0.0 0.35 0.00 19 0.00 0.00 Parrot_PerlHash_mark [32]
0.0 0.35 0.00 19 0.00 0.00 free_unused_PMCs [87]
0.0 0.35 0.00 19 0.00 0.00 mark_hash [33]
0.0 0.35 0.00 19 0.00 0.53 trace_active_PMCs [25]
0.0 0.35 0.00 15 0.00 0.00 singlebyte_characters [88]
0.0 0.35 0.00 15 0.00 0.00 string_compute_strlen [89]
0.0 0.35 0.00 12 0.00 0.00 expand_free_pool [54]
0.0 0.35 0.00 8 0.00 0.00 alloc_more_buffer_headers [56]
0.0 0.35 0.00 8 0.00 0.00 mem_allocate_aligned [90]
0.0 0.35 0.00 8 0.00 0.00 new_buffer_header [42]
0.0 0.35 0.00 5 0.00 0.00 new_resource_pool [39]
0.0 0.35 0.00 4 0.00 0.00 alloc_more_pmc_headers [61]
0.0 0.35 0.00 3 0.00 0.00 PIO_new [91]
0.0 0.35 0.00 3 0.00 0.00 PIO_unix_fdopen [92]
0.0 0.35 0.00 3 0.00 0.00 PIO_unix_isatty [93]
0.0 0.35 0.00 3 0.00 0.00 PackFile_Constant_new [94]
0.0 0.35 0.00 3 0.00 0.00 PackFile_Constant_pack_size [95]
0.0 0.35 0.00 3 0.00 0.01 PackFile_Constant_unpack [34]
0.0 0.35 0.00 3 0.00 0.01 PackFile_Constant_unpack_string
[35]
0.0 0.35 0.00 3 0.00 0.00 PackFile_check_segment_size [96]
0.0 0.35 0.00 3 0.00 0.00 chartype_lookup_index [97]
0.0 0.35 0.00 3 0.00 0.00 encoding_lookup_index [98]
0.0 0.35 0.00 3 0.00 0.00 flags_to_unix [99]
0.0 0.35 0.00 3 0.00 0.00 new_memory_pool [100]
0.0 0.35 0.00 2 0.00 0.00 Parrot_PerlArray_init [57]
0.0 0.35 0.00 2 0.00 0.00 Parrot_allocate [58]
0.0 0.35 0.00 2 0.00 0.00 Parrot_chartype_lookup [101]
0.0 0.35 0.00 2 0.00 0.00 new_stack [102]
0.0 0.35 0.00 1 0.00 0.00 PIO_base_new_layer [103]
0.0 0.35 0.00 1 0.00 0.00 PIO_init [104]
0.0 0.35 0.00 1 0.00 0.00 PIO_init_stacks [105]
0.0 0.35 0.00 1 0.00 0.00 PIO_push_layer [106]
0.0 0.35 0.00 1 0.00 0.00 PIO_unix_init [107]
0.0 0.35 0.00 1 0.00 0.00 PackFile_ConstTable_clear [108]
0.0 0.35 0.00 1 0.00 0.04 PackFile_ConstTable_unpack [36]
0.0 0.35 0.00 1 0.00 0.00 PackFile_FixupTable_unpack [109]
0.0 0.35 0.00 1 0.00 0.00 PackFile_assign_transforms [110]
0.0 0.35 0.00 1 0.00 0.00 PackFile_new [111]
0.0 0.35 0.00 1 0.00 0.04 PackFile_unpack [37]
0.0 0.35 0.00 1 0.00 0.01 Parrot_Array_class_init [45]
0.0 0.35 0.00 1 0.00 0.00 Parrot_DynOp_core_0_0_5 [112]
0.0 0.35 0.00 1 0.00 0.01 Parrot_IntQueue_class_init [46]
0.0 0.35 0.00 1 0.00 0.01 Parrot_ParrotPointer_class_init
[47]
0.0 0.35 0.00 1 0.00 0.01 Parrot_PerlArray_class_init [48]
0.0 0.35 0.00 1 0.00 0.00 Parrot_PerlArray_get_integer
[113]
0.0 0.35 0.00 1 0.00 0.01 Parrot_PerlHash_class_init [49]
0.0 0.35 0.00 1 0.00 0.02 Parrot_PerlHash_init <cycle 1>
[43]
0.0 0.35 0.00 1 0.00 0.01 Parrot_PerlInt_class_init [50]
0.0 0.35 0.00 1 0.00 0.01 Parrot_PerlNum_class_init [51]
0.0 0.35 0.00 1 0.00 0.01 Parrot_PerlString_class_init [52]
0.0 0.35 0.00 1 0.00 0.01 Parrot_PerlUndef_class_init [53]
0.0 0.35 0.00 1 0.00 0.00 Parrot_PerlUndef_init [114]
0.0 0.35 0.00 1 0.00 0.00 Parrot_clear_p [115]
0.0 0.35 0.00 1 0.00 0.00 Parrot_clear_s [116]
0.0 0.35 0.00 1 0.00 0.00 Parrot_destroy [117]
0.0 0.35 0.00 1 0.00 0.00 Parrot_init [118]
0.0 0.35 0.00 1 0.00 0.00 Parrot_initialize_memory_pools
[119]
0.0 0.35 0.00 1 0.00 0.02 Parrot_initialize_resource_pools
[40]
0.0 0.35 0.00 1 0.00 0.00 Parrot_loadbc [120]
0.0 0.35 0.00 1 0.00 0.17 Parrot_new [29]
0.0 0.35 0.00 1 0.00 0.04 Parrot_readbc [38]
0.0 0.35 0.00 1 0.00 0.00 Parrot_reallocate_string [63]
0.0 0.35 0.00 1 0.00 349.80 Parrot_runcode [2]
0.0 0.35 0.00 1 0.00 0.00 Parrot_setflag [121]
0.0 0.35 0.00 1 0.00 0.00 alloc_pio_array [122]
0.0 0.35 0.00 1 0.00 0.00 check_fingerprint [123]
0.0 0.35 0.00 1 0.00 0.01 expand_hash [59]
0.0 0.35 0.00 1 0.00 0.11 init_world [30]
0.0 0.35 0.00 1 0.00 0.00 intstack_new [124]
0.0 0.35 0.00 1 0.00 0.06 make_interpreter [31]
0.0 0.35 0.00 1 0.00 0.02 mem_setup_allocator [41]
0.0 0.35 0.00 1 0.00 0.00 mem_sys_realloc [125]
0.0 0.35 0.00 1 0.00 0.02 new_hash [44]
0.0 0.35 0.00 1 0.00 0.00 new_sized_resource_pool [60]
0.0 0.35 0.00 1 0.00 0.01 new_tracked_header [55]
0.0 0.35 0.00 1 0.00 0.00 parseflags [126]
0.0 0.35 0.00 1 0.00 349.75 runops [3]
0.0 0.35 0.00 1 0.00 349.75 runops_cgoto_core [4]
0.0 0.35 0.00 1 0.00 349.75 runops_generic [5]
0.0 0.35 0.00 1 0.00 0.00 sized_index [127]
0.0 0.35 0.00 1 0.00 0.00 string_grow [64]
0.0 0.35 0.00 1 0.00 0.00 string_init [128]
I don't see anything that really stands out (unlike earlier builds where
string_make was taking the most time)
Any thoughts?
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
ge 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
le 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
