The STS (string-to-string) code now allows dumping of a string-to-string map and then quick searches of the dump using a key. This means that a huge data-structure needs to be built in the internal memory first, which sometimes leads to thrashing. An INSERT operation must be implemented. Try to see if you can make it such that the common case is not affected. This could be done by using an in-memory cache whose size depends on the available memory. Also, there might be some cache-oblivious algorithms to take advantage of as much cache as is available.