Enormous filtering run oddity

[jasonp]

Msieve also uses disk as backing store, but I made the decision early on to write as few temporary files as possible, and make them as small as possible, so that the majority of the disk usage is bound up in (one copy of) the text of relations. That's nice on smaller systems, but Greg and Bruce have systems with tens of gigs of memory. In addition, forcing the reading of relations from sequential disk-based passes means that more than 80% of the time needed by the filtering goes into removing duplicates and singletons, and the processing for this step is pretty trivial. Removing cliques accounts for the majority of the rest, not because the clique processing touches disk but because the process is broken up into so many identical passes to conserve memory.

Ideally what you want is a system that keeps relations in memory when they fit, and spills to disk when they don't. It should also remember every factor of every relation so that ideals can be adaptively remembered or forgotten during the filtering, and so that singleton removal can be combined with clique removal to reduce the number of passes. Originally I thought it wouldn't be hard to add a memory-map layer to the savefile-reading code, but for big problems that only benefits really big systems.

It's possible that all these measures are huge overkill for the vast majority of users, but this thread has shown the pain that you get when you push right up to the limit of what 'organically grown' code can do. I can do better, but I don't exactly know when :)

[henryzz]

Originally Posted by jasonp

Msieve also uses disk as backing store, but I made the decision early on to write as few temporary files as possible, and make them as small as possible, so that the majority of the disk usage is bound up in (one copy of) the text of relations. That's nice on smaller systems, but Greg and Bruce have systems with tens of gigs of memory. In addition, forcing the reading of relations from sequential disk-based passes means that more than 80% of the time needed by the filtering goes into removing duplicates and singletons, and the processing for this step is pretty trivial. Removing cliques accounts for the majority of the rest, not because the clique processing touches disk but because the process is broken up into so many identical passes to conserve memory.

Ideally what you want is a system that keeps relations in memory when they fit, and spills to disk when they don't. It should also remember every factor of every relation so that ideals can be adaptively remembered or forgotten during the filtering, and so that singleton removal can be combined with clique removal to reduce the number of passes. Originally I thought it wouldn't be hard to add a memory-map layer to the savefile-reading code, but for big problems that only benefits really big systems.

It's possible that all these measures are huge overkill for the vast majority of users, but this thread has shown the pain that you get when you push right up to the limit of what 'organically grown' code can do. I can do better, but I don't exactly know when :)

Just rereading old threads....
In the end you ended up changing filtering to not use the disk so much for everyone after all.