Feedback for new MPQS utility sought

[R.D. Silverman]

Originally Posted by xilman

A much cleaner way is to have each siever write their own file and to designate one siever as the master (this choice should be made at the outset). Every time the client has something to say, it opens its output file in append mode (creating it first if necessary), writes the data, and closes it (thereby flushing the file buffer).

Every so often, the master renames the clients' files and then processes them under the new name.

There is still a race condition, but the amount of data lost or corrupted will be very small in practice, and data corruption needs to be detected anyway. You can mess around with file locking if you wish, but it really isn't necessary and virtually impossible to implement in a portable manner.

By an amazing coincidence, this is how Arjen Lenstra's qs.c program works. By an even more bizarre coincidence, I was the person who taught Arjen how perform some of the filesystem manipulations required.


Paul

Actually, I have implemented (in the past) a very portable file locking
mechanism.

When a process wants to read/write (say) file A, it simply checks if A
is locked by looking for file 'A.lock'. If A.lock is present, then it sleeps
for a few seconds and tries again (length of time determined by how long
another process takes to write to and then close file A).

If A.lock is NOT present, then the process creates it (preventing other
processes from using file A), processes file A, closes file A, then deletes
A.lock


I used this mechanism to control my NFS code while at RSA. I was running
out of a common, shared directory.

[xilman]

Originally Posted by R.D. Silverman

Actually, I have implemented (in the past) a very portable file locking
mechanism.

When a process wants to read/write (say) file A, it simply checks if A
is locked by looking for file 'A.lock'. If A.lock is present, then it sleeps
for a few seconds and tries again (length of time determined by how long
another process takes to write to and then close file A).

If A.lock is NOT present, then the process creates it (preventing other
processes from using file A), processes file A, closes file A, then deletes
A.lock


I used this mechanism to control my NFS code while at RSA. I was running
out of a common, shared directory.

Unfortunately, it doesn't work properly everywhere, even though it may be very effective in particular installations. I've used the technique myself many times in environments where I know (or, at least, firmly believe) it to be applicable.

The problem is that more than one process can look for the lock file at the same time, see it is not there, create it and then stomp on the shared file.

If the filesystem supports atomic "creation if not present" your mechanism works (though any failure to delete the lock file results in subsequent deadlock of the entire set of clients) but this is special case of mandatory access locking and, unfortunately, is still not portable. It won't necessarily work on some NFS implementations where only advisory locks are possible.

Further difficulties can arise from differing interpretations of file system semantics. An obvious one is that some distinguish between alphabetic case and others do not. Some operating systems (thankfully few now) do not allow you to have a zero-length file, so merely creating a file is not enough --- you must write something to it and close it before it becomes visible in the file system to other processes.


A good bullet-proof and yet portable file locking system is not easy to write. Even writing one in a pure single-system Unix environment is not trivial. There have been many security vulnerabilities exploited over the years based on race conditions within the filesystem.


Paul

[xilman]

Originally Posted by R.D. Silverman

I see no point in implementing such a thing. By the time the composites
become large enough for 3 large primes to be effective, NFS becomes quite
a bit faster.

My advice to the author: DON'T.

Seconded.

My experience is that the 2LP/3LP crossover lies at around 100 digits, where NFS is already competitive. Other implementations may put the crossover in other places, of course.

If I remember jasonp's earlier investigations with 3LP, he found an even higher crossover point, where NFS will almost certainly be markedly faster than QS.

I never use 3LP these days.


Paul

[ColdFury]

If A.lock is NOT present, then the process creates it (preventing other

This has a race unless you can check and create the file atomically.

[Prime95]

Another problem is a system or program crash after creating file A.lock. This will block all future accesses to A until someone notices the problem and manually deletes the lock file.

[xilman]

Originally Posted by ColdFury

This has a race unless you can check and create the file atomically.

I think you will find that I said this, in rather greater detail, about 90 minutes earlier.

Paul

[xilman]

Originally Posted by Prime95

Another problem is a system or program crash after creating file A.lock. This will block all future accesses to A until someone notices the problem and manually deletes the lock file.

I mentioned this about 90 minutes earlier. Unfortunately it was buried in a parenthetical comment within a rather more verbose posting.


Paul

[jasonp]

Originally Posted by jasonp

I want to at least finish my benchmark C105 before considering a full release.

My benchmark C105 finished in just 54 hours. This number used to take over 90 hours on the same machine! Clearly the new parameters are a step in the right direction. Another possibility would involve making the factor base size adaptive, increasing it a little at a time until the ratio between the rate of relation discovery and the rate of increase in the factor base size levels off.

jasonp

[akruppa]

Originally Posted by jasonp

Alex: I have docs on locking files for win32 systems, is there a posix-compatible way to do the same thing?

jasonp

I looked up file locking in Linux now. Apparantly there are cooperative locks BSD style with flock(2), but in Linux kernes prior to 2.6.something they don't work across NFS filesystems.

POSIX specifies file locking with fcntl(2) which works over NFS. There are two modes: cooperative and mandatory. A file is marked for mandatory locking by setting file mode g-x g+s (pretty ugly!). In this case, the kernel will block accesses. Without the weird file mode, locking is cooperative. I guess that will be the best way for msieve...

Alex

[jasonp]

Originally Posted by akruppa

POSIX specifies file locking with fcntl(2) which works over NFS. There are two modes: cooperative and mandatory.

Neat! OTOH, if msieve synchronized file writes perfectly, would anyone here throw CPU power at it that was far in excess of what could be easily managed by hand? Alex, wouldn't your cluster be better used running the CWI suite?

I've been working with someone else who is well on the way to making the msieve demo a client-server application that communicates via sockets, although I don't know when / if such a beast will be ready.

In other news, a few more parameter tweaks have made smaller factorizations noticeably faster too. I think I'll spend a little more time tuning things at the 95-110 digit level.

jasonp

[akruppa]

For larger factorisations, I'll definitely keep using S/GNFS. But Paul Zimmermann and I frequently encounter composites around 100 digits in factoring Aliquot sequences and it would be really convenient to just fire up a few msieve processes on whatever cpus are free at the moment and pick up the factors 30 minutes later...

One thing the file locking idea has going for it is that processes can be added/removed dynamically without specifying a master process or anything. It's simple and convenient for the user if nothing else.

Problems I can see: when starting factorisations on different numbers in the same directory. How would processes know that the msieve.dat file is currently in use and not a leftover from an old factorisation? Also, if processes are designated to only sieving (i.e. post-processing inhibited) it should be more efficient to not let them count cycles, but only dump relations into the msieve.dat file. However, if all processes that can post-process die, the only-sievers will keep sieving until the end of time (or the hard disk fills up, whichever comes first).

Alex