Your description of how you use it sounds to me like order doesn't matter. Perhaps your arrays are always sorted so this aspect doesn't impact the end result (just impacts the efficiency of getting to the result)?

Finding the set difference more efficiently is pretty easy:

my @old = ...;
my @new = ...;

my %added;
@added{@new} = ();
delete @added{@old};
my @added = keys %added;

# or

my %is_old = map { $_ => 1 } @old;
my @added = grep ! $is_old{$_}, @new;
[download]