andrewt@cs.su.oz (Andrew Taylor) (07/04/90)
In article <3357@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >As an example of slowness, it failed utterly, because we were given >NO DATA WHATSOEVER. He specifically claimed that quicksort is an example >that shows that vanRoy et al's results aren't a defence against claims >that Prolog is slow. But quicksort is precisely the kind of thing that >the new Berkeley compiler ought to be very good at! ... Richard is right, a Prolog compiler using global analysis can produce good code for quicksort. Appended below is the standard quicksort benchmark and the code my compiler yields (in pseudo-C for readability). The best way to compare this to C is not clear. If you literally as possible translate the Prolog to C, including data structures, I'd expect similar code and similar execution times. This seems an artificial comparison. I timed the C library function qsort on an array containg the same numbers. It was over 3 times slower. This is unfair because the C library function is more general, taking an arbitrary comparison function as argument. I modified the source of the C library function to do only integer comparison. This left it 10% slower than the Prolog. All of this was on a MIPS R2030. Prolog isn't slow at quicksort'ing. Andrew main :- list50(L), qsort(L, X, []), write(X), nl. qsort([X|L], R, R0) :- partition(L, X, L1, L2), qsort(L2, R1, R0), qsort(L1, R, [X|R1]). qsort([], R, R). partition([X|Xs], Y, [X|Ls], Bs) :- X < Y, !, partition(Xs, Y, Ls, Bs). partition([X|Xs], Y, Ls, [X|Bs]) :- partition(Xs, Y, Ls, Bs). partition([], _, [], []). list50([27,74,17,33,94,18,46,83,65,2,32,53,28,85,99,47,28,82,6,11, 55,29,29,81,90,37,10,0,66,51,7,21,85,27,31,63,75,4,95,99,11,28,61, 74,18,92,40,53,59,8]). p_main_0: call_1 = stackp + 8 stackp[0] = successp stackp = stackp + 12 p_list50_1() call_1 = stackp[-4] call_2 = stackp + -8 call_3 = CONST([]) p_qsort_3() call_1 = stackp[-8] p_write_1() successp = stackp[-12] stackp = stackp + -12 goto p_nl_0 p_qsort_3: r2 = CONST([]) if (call_1 == r2) goto L9 stackp[4] = call_2 call_2 = call_1[-2] stackp[16] = call_1 call_1 = call_1[2] stackp[24] = call_3 call_3 = stackp + 8 call_4 = stackp + 20 stackp[0] = successp stackp = stackp + 28 p_partition_4() call_3 = stackp[-4] call_1 = stackp[-8] call_2 = stackp + -16 p_qsort_3() r3 = stackp[-12] r12 = r3[-2] r13 = stackp[-16] call_2 = stackp[-24] call_1 = stackp[-20] successp = stackp[-28] stackp = stackp + -28 call_3 = globalp globalp[-2] = r12 globalp[2] = r13 globalp = globalp + 8 goto p_qsort_3 L9: call_2[0] = call_3 goto successp p_partition_4: r2 = CONST([]) L7: if (call_1 == r2) goto L4 r3 = call_1[-2] if (r3 >= call_2) goto L6 call_1 = call_1[2] call_3[0] = globalp call_3 = globalp + 2 globalp[-2] = r3 globalp = globalp + 8 goto L7 L6: r12 = call_1[-2] call_1 = call_1[2] call_4[0] = globalp call_4 = globalp + 2 globalp[-2] = r12 globalp = globalp + 8 goto p_partition_4 L4: r13 = CONST([]) call_4[0] = r13 call_3[0] = r13 goto successp p_list50_1: r2 = c_struct([27,74,17,33,94,18,46,83,65,2,32,53,28,85,99,47,28,82,6,11,55,29,29,81,90,37,10,0,66,51,7,21,85,27,31,63,75,4,95,99,11,28,61,74,18,92,40,53,59,8],98) call_1[0] = r2 goto successp