If you could illustrate your problem with an smallish example benchmark program
that would be good and should lead to better answers.
Without seeing any code, we are forced to guess.
I am guessing your problem is similar to a thread I mentioned earlier,
where some folks suggested using an external database (such as SQLite) instead of a gigantic Perl hash.
From that thread, this quote from the infamous BrowserUk sounds similar to the problem you're facing:
I've run Perl's hashes up to 30 billion keys/2 terabytes (ram) and they are 1 to 2 orders of magnitude faster, and ~1/3rd the size of storing the same data (64-bit integers) in an sqlite memory-based DB. And the performance difference increases as the size grows.
Part of the difference is that however fast the C/C++ DB code is, calling into it from Perl, adds a layer of unavoidable overhead that Perl's built-in hashes do not have.
Have you tried using a database (such as SQLite) instead of a gigantic Perl hash?
If so, what was the performance difference?
Though I can't personally endorse Judy Arrays because I've never used them,
they worked for BrowserUk, albeit with a
warning that the Judy code is horribly complex and hard to understand if something goes wrong.