I've seen dramatic speedups reducing an array from ~10mb to ~1mb. The problem was that the algorithm did multiple passes over the array, and each pass it would pull in blocks from main memory, only to evict them later on before they could be reused.

It depends a lot on the workload, but you'll see dramatic performance differences well before you fill up main memory.