I've done plenty of multi-threaded code in C++, but never in Perl, so take this with a grain of salt.

I suspect that RMGir is right: Since $tmp seems to be shared amongst all the threads, perl may be wrapping reads/writes to it with a mutex, and you may just have a lot of mutex lock contentions on it. If I understand perl well enough (and I likely don't), then I suspect that moving the my $tmp into the body of the first for loop may resolve the problem: that way, each thread should(?) have it's own copy of $tmp.