Front page | perl.perl5.porters |
Postings from April 2008
[PATCH] changes to perlsec.pod and call for removal of quicksort
Thread Next
From:
John P. Linderman
Date:
April 9, 2008 05:32
Subject:
[PATCH] changes to perlsec.pod and call for removal of quicksort
Message ID:
200804091232.m39CWVkY33722822@raptor.research.att.com
perlsec.pod has a couple typos, and a couple of statements about
sort that are incorrect. The pre-5.8.0 quicksort does not misbehave on
input that is already sorted. In fact, I suspect that there is no
permutation of input elements on which it will perform any better.
If you want to get the old quicksort to go quadratic, organ-pipe,
sort(@sorted, reverse @sorted)
or saw-tooth
sort(@sorted, @sorted)
inputs will do the job. But we have told the reader how to avoid
the problem (get 5.8.0 or later), so I see no reason to explain
how to cause it.
Perl's mergesort is not insensitive to its input data. It will
knock off organ-pipe or saw-tooth input in two or three, not logN,
passes, pre-sorted input in a single pass. It can behave better
than O(NlogN), but never worse. Again, I see no need to go into
this in a security-related document.
On a related topic, is it perhaps time to think about removing the
quicksort code from the core? It's not a major contributor to bloat,
but I'm unconvinced that it is worth what it costs. The only class
of inputs I can think of where quicksort will consistently outperform
mergesort is on a large number of records with a small number,
k < logN, of distinct sort keys, as might be generated by rolls
of a k-sided die. Quicksort will take at most k passes, mergesort
may take logN. But if you know that's what the input looks like,
you can knock it off in two passes using a hash to do a radix sort.
There may be other cases where quicksort is better, or system
architectures where it has nicer cache behavior, but unless
somebody can demonstrate why it should stay, there are code-bloat
reasons why it should go. Scripts might break if they rely on
sort::current returning "quicksort", but the documentation for
the sort pragma has always made it clear that subpragmas starting
with _ (like _quicksort and _qsort) may not persist beyond 5.8,
so people were warned. Otherwise, simply using mergesort even if
quicksort was requested won't break code, it might (or might not)
just slow it down.
Anyway, patch to perlsec.pod follows. -- jpl
===================
*** perlsec.pod.orig Tue Apr 8 14:19:21 2008
--- perlsec.pod Wed Apr 9 07:41:58 2008
*************** code, but none can definitively conceal
*** 420,430 ****
language, not just Perl).
If you're concerned about people profiting from your code, then the
! bottom line is that nothing but a restrictive licence will give you
legal security. License your software and pepper it with threatening
statements like "This is unpublished proprietary software of XYZ Corp.
Your access to it does not give you permission to use it blah blah
! blah." You should see a lawyer to be sure your licence's wording will
stand up in court.
=head2 Unicode
--- 420,430 ----
language, not just Perl).
If you're concerned about people profiting from your code, then the
! bottom line is that nothing but a restrictive license will give you
legal security. License your software and pepper it with threatening
statements like "This is unpublished proprietary software of XYZ Corp.
Your access to it does not give you permission to use it blah blah
! blah." You should see a lawyer to be sure your license's wording will
stand up in court.
=head2 Unicode
*************** Perl running out of memory.
*** 496,510 ****
Sorting - the quicksort algorithm used in Perls before 5.8.0 to
implement the sort() function is very easy to trick into misbehaving
! so that it consumes a lot of time. Nothing more is required than
! resorting a list already sorted. Starting from Perl 5.8.0 a different
! sorting algorithm, mergesort, is used. Mergesort is insensitive to
! its input data, so it cannot be similarly fooled.
=back
See L<http://www.cs.rice.edu/~scrosby/hash/> for more information,
! and any computer science textbook on the algorithmic complexity.
=head1 SEE ALSO
--- 496,509 ----
Sorting - the quicksort algorithm used in Perls before 5.8.0 to
implement the sort() function is very easy to trick into misbehaving
! so that it consumes a lot of time. Starting from Perl 5.8.0 a different
! sorting algorithm, mergesort, is used by default. Mergesort cannot
! misbehave on any input.
=back
See L<http://www.cs.rice.edu/~scrosby/hash/> for more information,
! and any computer science textbook on algorithmic complexity.
=head1 SEE ALSO
Thread Next
-
[PATCH] changes to perlsec.pod and call for removal of quicksort
by John P. Linderman