So let’s say you’ve got some particles in 2-dimensional space.
There they are. Now let’s say you want any two particles which are very close to each other to interact. You need to know which pairs are close enough. You could take all possible pairs of particles, calculate their distances, and compare those to the minimum distance
d. That’s fine if you have 10 particles, but if you have 5,000 that’s going to add up to over 12,000,000 pairs. That’s too many pairs.
That complexity can be alleviated if for each particle
P we can efficiently find a subset of all particles which includes all those within
P and which includes as few as possible which aren’t within
d. Then we can calculate the distances from
P to the few particles in this subset and determine which ones are actually within distance
Enter: spatial hashing. I’ll show how
boost::unordered_multimap can be used to do this.
compcache. Use it.
The general idea is to set apart some physical memory as swap space, with compression on the pages going in. Much of what’s in RAM is very compressible, so a fast compression algorithm can do a lot. I ran a large portion of a swap file through LZO and got a ratio above 3:1. And it was fast. I’ve never seen compression that fast. The bottom line is: compressing back to RAM is orders of magnitude faster than copying to disk, in more ways than one.
I enabled this feature on an old Pentium III laptop and it works wonderfully. I found it was already present in CrunchBang 9.04, an extremely light Ubuntu variant; I just had to set
COMPCACHE_SIZEin an init script. That machine has 256M memory and a
So I tried it on my workstation with its 2 gig memory. With
COMPCACHE_SIZE="30 %", if the compression ratio holds out, I’ve got more like 3.2 gig, and I’m pushing the limits of my primitive ape address space. A 64 bit machine could have, say, 8 gig RAM. A 50% compcache would be stellar: 4 gig of real RAM, and quick access to another 8 gig or more. There is definitely no need for the disk, and swapping is definitely a waste of SSD life.
To set it up in Ubuntu:
(specific instructions are there in the file)
- disable swap files in
(optional probably. I think compcache gets priority.)