Depends on what your bottleneck is. For me, it's usually been memory rather than CPU. I was using 64bit, then switched to 32bit and saw a gigantic improvement in mem usage. (See slicehost vs linode comparisons etc)
Look at the big picture, whether it be pointers or integers into an array: the size of the index grows with the log of the number of things being indexed. You can't avoid this growth, but it matters less and less as you grow.