[Encosia]

Assuming he's searching a trie to build the list of anagrams, he could distribute a single request's work over a thread per letter.

[Evbn]

If he has multi core, which is often missing in a VM.