Described is predicting cache locality in a multicore/multithreaded processing environment including when threads share cache data in a non-uniform interleaving manner. Thread execution traces are analyzed to compute a set of per-thread parameters that can then be used to predict cache miss rates for other cache sizes. In one aspect, a model is based upon a probability that the cache reuse distance will increase because of accesses by other threads, and another probability that the reuse distance will decrease because of intercept accesses by other threads to shared data blocks. Estimates of the number of shared data blocks, possibly shared data blocks and private data blocks are used in the computations.