How Much Linear Memory Access Is Enough?