Another implementation for you. This one seems pretty speedy (update: optimized and benchmarks updated with everyone else's updates):

sub fastolfe {
        my $source = shift;
        my $chop   = shift;
        local($_);

        my %found;
        $found{$_}++ while ($_ = chop($source)) ne '';
        while (($_ = chop($chop)) ne '') {
                return if --$found{$_} < 0;
        }

        my $result;
        foreach (sort keys %found) {
                $result .= $_ while $found{$_}--;
        }
        $result;
}
[download]

Hybridizing the above with merlyn's version, we can squeeze out a bit more speed:

sub fast_merl {
        my ($source, $chop) = @_;
        local($_);

        my %found;
        $found{$_}++ while ($_ = chop($source)) ne '';
        while (($_ = chop($chop)) ne '') {
                return if --$found{$_} < 0;
        }

        return join "", map { $_ x $found{$_} } keys %found;
}
[download]

Benchmarking most of the versions I see thus far (minus a couple of the less interesting ones, because these benchmarks are getting big), using test input from above (2 success, 2 fail) as well as demerphq's tests below:

# demerphq's test set
             Rate blakem merlyn demq_scan demerphq fastolfe fast_merl 
+fast_c scan_c
blakem      479/s     --   -24%      -39%     -44%     -46%      -47% 
+  -97%   -98%
merlyn      629/s    31%     --      -20%     -27%     -29%      -30% 
+  -96%   -97%
demq_scan   790/s    65%    26%        --      -8%     -11%      -12% 
+  -95%   -97%
demerphq    861/s    80%    37%        9%       --      -3%       -4% 
+  -95%   -96%
fastolfe    887/s    85%    41%       12%       3%       --       -1% 
+  -94%   -96%
fast_merl   901/s    88%    43%       14%       5%       2%        -- 
+  -94%   -96%
fast_c    15708/s  3179%  2396%     1889%    1723%    1671%     1644% 
+    --   -31%
scan_c    22648/s  4627%  3499%     2767%    2529%    2453%     2415% 
+   44%     --

# simple success case
             Rate blakem merlyn demerphq fastolfe fast_merl demq_scan 
+fast_c scan_c
blakem     6244/s     --   -14%     -26%     -32%      -35%      -43% 
+  -90%   -93%
merlyn     7221/s    16%     --     -14%     -21%      -24%      -34% 
+  -89%   -92%
demerphq   8429/s    35%    17%       --      -8%      -12%      -23% 
+  -87%   -91%
fastolfe   9181/s    47%    27%       9%       --       -4%      -16% 
+  -86%   -90%
fast_merl  9563/s    53%    32%      13%       4%        --      -12% 
+  -85%   -90%
demq_scan 10908/s    75%    51%      29%      19%       14%        -- 
+  -83%   -88%
fast_c    65634/s   951%   809%     679%     615%      586%      502% 
+    --   -28%
scan_c    91428/s  1364%  1166%     985%     896%      856%      738% 
+   39%     --

# simple failure case
              Rate blakem merlyn demerphq demq_scan fastolfe fast_merl
+ scan_c fast_c
blakem      7759/s     --   -39%     -51%      -60%     -63%      -63%
+   -94%   -94%
merlyn     12666/s    63%     --     -20%      -35%     -39%      -40%
+   -89%   -91%
demerphq   15783/s   103%    25%       --      -19%     -24%      -26%
+   -87%   -89%
demq_scan  19581/s   152%    55%      24%        --      -5%       -8%
+   -84%   -86%
fastolfe   20720/s   167%    64%      31%        6%       --       -2%
+   -83%   -85%
fast_merl  21209/s   173%    67%      34%        8%       2%        --
+   -82%   -85%
scan_c    119642/s  1442%   845%     658%      511%     477%      464%
+     --   -14%
fast_c    139171/s  1694%   999%     782%      611%     572%      556%
+    16%     --
[download]

Source: http://fastolfe.net/transient/2001/11/02/pm.string.difference.bench

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.