in reply to Re^4: Howto Avoid Memory Problem in List::MoreUtils
in thread Howto Avoid Memory Problem in List::MoreUtils

I guess we have different understandings of the term In-place sort.

Yes, inside perl internals, "inplace" just means that instead of passing the elements on the stack, a reference to the target array is passed and the sorting is done directly over it.

... but if the quicksort algorithm is selected, @a = sort @a is also an in-place sort as described on the article pointed by you (if we ignore degenerated cases).

If you need 1.4GB to sort 400MB, it means that you are probably converting numbers to strings inside the sort. For instance: 

use Memchmark 'cmpthese';

use sort '_quicksort';

cmpthese( none => sub {
             my @a = map { int rand 100 } 1..1000000;
          },
          sort_num => sub {
             my @a = map { int rand 100 } 1..1000000;
             @a = sort { $a<=> $b } @a
          },
          sort_str => sub {
             my @a = map { int rand 100 } 1..1000000;
             @a = sort { $a cmp $b } @a
          },
          sort_str_workaround => sub {
             my @a = map { int rand 100 } 1..1000000;
             my ($c, $d);
             @a = sort { ($c, $d) = ($a,$b); $c cmp $d } @a
          }
        );

__END__

test: none,                memory used:  3997696 bytes
test: sort_num,            memory used:  3997696 bytes
test: sort_str,            memory used: 68202496 bytes
test: sort_str_workaround, memory used:  3997696 bytes

[download]
... and as you can see, there is a simple workaround (though it would make the sorting much slower).

Replies are listed 'Best First'.
Re^6: Howto Avoid Memory Problem in List::MoreUtils
by BrowserUk (Patriarch) on May 04, 2006 at 12:30 UTC
    If you need 1.4GB to sort 400MB that means that you are probably converting numbers to strings inside the sort.

    Yep! That's the problem.

    { ($c, $d) = ($a,$b); $c cmp $d

    I wonder if that optimisation could be worked into the internal sort?

    I started to suggest that if both had the (same) IOK or NOK flags set, then use a numeric comparison, but I guess it would only take one string embeded at the wrong place for the entire sort to have to be done over.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
      I started to suggest that if both had the (same) IOK or NOK flags set, then use a numeric comparison

      but if you are sorting lexicograficaly, you can not compare numbers as numbers because they are not equivalent operations (i.e.: 2 < 10 but 2 gt 10).

      It shouldn't be too difficult to write a sorting sub in XS that uses a comparison callback equivalent to the Perl {($c, $d) = ($a, $b); $c cmp $d }. But converting the numbers to strings is an expensive operation, even in C.

      Also, you can apply a transformation to the numbers to make them sort lexicograficaly when compared as numbers. For instance, for positive integers with 8 or less digits (untested): 

      use Sort::Key 'ukeysort_inplace';
my $digits = 8;
ukeysort_inplace {
  my $a = int $_;
  length $a > $digits and die 'integer $a is too big';
  $a .= ' ' x ($digits - length $a);
  $a =~ tr/ 0123456789/0123456789a/;
  hex $a
} @array;

      [download]

      (usortkey_inplace should not use more than 8 additional bytes per value on a 32bits machine, update: + 4 bytes for the merge phase of the mergesort)

[reply]
[d/l]
[select]
        but if you are sorting lexicograficaly,

        True. One further question though.

        Why does using sort{ $a <=> $b } @numbers also cause the memory growth. The same appears to be true for Sort::Key::nsort(_inplace)?

        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]

In Section Seekers of Perl Wisdom