There are some gains to be had from using threads, but not as much as you might hope for. The following are the results of a single threaded test, and a multi-threaded version operating on the same list using 1, 2, 3 & 4 threads:

C:\test>817827
Took 1.622
Odd numbers in list: 4000
Pairs found: 99135

C:\test>817827-t -T=1
Took 1.790000
Odd numbers in list: 4000
Pairs found: 99135

C:\test>817827-t -T=2
Took 1.365000
Odd numbers in list: 4000
Pairs found: 99135

C:\test>817827-t -T=3
Took 1.047500
Odd numbers in list: 4000
Pairs found: 99135

C:\test>817827-t -T=4
Took 0.832500
Odd numbers in list: 4000
Pairs found: 99135
[download]

As you can see, the overhead of threading costs you relative to the non-threaded version for the 1-thread case. You make a small gain using two. And further small gains using 3 or 4. At the cost of complexity. The tests were run on a 4-core system.

Note: These are only test apps; the results produced--a single level hash with composite keys--may not suit your purposes.

Non-threaded:

#! perl -slw
use strict;
use Time::HiRes qw[ time ];
use Data::Dump qw[ pp ];

our $N ||= 4000;
our $S ||= 1;

srand( $S );
my @list = map 1 | int( rand( 2**32 )), 1 .. $N;

my $start = time;
my %hash;
for my $i ( 0 .. $#list ) {
    use integer;
    my $v = $list[ $i ];
    ( $v & $_ ) == 1 and undef $hash{ "$i:$_" }
        for @list[ $i+1 .. $#list ];
}
printf "Took %.3f\n", time() - $start;

print 'Odd numbers in list: ', scalar @list;
print 'Pairs found: ', scalar keys %hash;

#<>; pp \%hash;
[download]

Threaded

#! perl -slw
use strict;
use threads;
use Time::HiRes qw[ time ];
use Data::Dump qw[ pp ];

$|++;
our $N ||= 4000;
our $T ||= 4;
our $S ||= 1;

srand( $S );
my @list = map 1|int( rand( 2**32 ) ), 1 .. $N;

my $cStart = 0;
my $cSize  = int( @list / $T );

my $start = time;
my @threads = map {
    my( $t ) = threads->create( sub{
        my( $lo, $hi ) = @_;
        use integer;
        my $tid = threads->tid;
        my @keys;
        for my $i ( 0 .. $#list ) {
            my $v = $list[ $i ];
            my $start = $i > $lo ? $i+1 : $lo;
            ( $v & $_ ) == 1 and push @keys, "$i:$_" for @list[ $start
+ .. $hi ];
        }
        return @keys;

    }, $cStart, $_<($T) ? $cStart + $cSize + 1 : $#list );
    $cStart += $cSize;
    $t;
} 1 .. $T;


my %hash;
for( @threads ) {
    my @keys = $_->join;
    undef $hash{ $_ } for @keys;
}
printf "Took %.6f\n", time() - $start;

print 'Odd numbers in list: ', scalar @list;
print 'Pairs found: ', scalar keys %hash;

<>; pp \%hash;
[download]