To access data (e.g., a tree node) in request t1 which may incur a cache miss, the thread issues a prefetch and switches to another request t2, and repeats this process. While the data needed by t1 is being fetched from memory to CPU cache, the worker thread handles t2, which may further cause the thread to issue prefetch and switch to another request. By the time the worker thread switches back to t1, the hope is that the needed data is (already and still) cache-resident. The thread then picks up at where it left for t1, dereferences the pointer to the prefetched data and continues executing t1 until the next possible cache miss upon which a prefetch will be issued. It is important that the switching mechanism and representation of requests are cheap and lightweight enough to achieve a net gain.