Date: Wed, 16 Sep 1998 21:32:41 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: eivind@yes.no (Eivind Eklund) Cc: tlambert@primenet.com, freebsd-hackers@FreeBSD.ORG Subject: Re: Unused functions Message-ID: <199809162132.OAA27690@usr04.primenet.com> In-Reply-To: <19980916100311.62440@follo.net> from "Eivind Eklund" at Sep 16, 98 10:03:11 am
next in thread | previous in thread | raw e-mail | index | archive | help
> Hmmm. I can't see any reason why you would want to do a > Floyd-Warshall - that calculate the connectivity of the entire graph, > which is really producing a lot of data you don't need. Right. Which is why I wanted to do a Hamiltonian, not a Warshall (or a Floyd-Warshall). > Both algorithm 1 and 2 are o(N) and O(N) in the number of edges > connecting the set of used symbols. The only case you can avoid > examining all of these edges is if all symbols are included in the > final used set; then you could do a cutoff. I don't think it would be > worthwhile, though. Well, I think it would, at least if the theory were that you didn't link against things you planned to use, and you were only eliminating dead code in objects from an archive where you knew you were using at least one or more symbols (which is the case under consideration). > > Consider all top level "known referenced" symbols to be connected > > by an edge. > > Connected to _what_ by an edge? Each other. All used symbols are implicitly connected. This means than any other used symbol implies a cycle. > Why is this easier/faster than the trivial algorithms I present above? Because it's O(2) for the test, and only walks the portion of the tree related to the symbol being tested. 8-). > And where does hamilton cycles (as opposed to just cycles in the > graph) enter into this? Before you test a symbol, you "connect" it to all of the other used symbols. If you make it back to the root, then the symbol is used. > I can sort of get a picture of using cycles to separate used/unused > symbols, but I can't see any direct advantages to it, and I can't see > Hamiltonian cycles in there at all. > > What am I missing here? (I'm interested due to sometimes needing this > type of algorithms, and if something else is more effective than the > techniques outlined above - well, then I want that :-) You should look at the section of the Sedgewick C++ book on Hamiltonian cycles. This is really useful for runtime optimizations for things like a hierarchical SMP lock manager. You attach all nodes into the graph for the objects that are intended to be used, and calculate a Warshalls. Then, as you add leaves, you update using standard Floyd-Steinberg, so the Warshall's is always accurate. This allows you to insert leaf nodes in O(1) along the vector to the root of the graph. For a list of locks you want to test for deadlock, the list itself describes a vector. Using this vector as an arc through the existing Warshall-complete graph, you look for a Hamiltonian cycle. If the cycle exists, then you have a deadlock condition. This allows deadlock detection without having to do stack rewind and/or resource precommit (presuming that the tentative lock vector's elements are inserted using intention modes to prevent another tentative lock from coming back "safe"). This algorithm was actually the basis of the lock manager in the NetWare for UNIX server; it was capable of 20,000 transactions a second -- basically 2 orders of magnitude better than Tuxedo. 8-). You can further optimize this using the Dynix paper's finding on shared memory multiprocessors, to wit, you establish seperate intention zones for resource pools on a per processor basis for things like a free page pool so that you don't have to hold the top lock for page allocation, only for pool drain/refill. The same algorithm applies cleanly to the system process table and the system open file table; if you segment the table by the number of expecte reeentrancies, then you can establish an intention write for one processor that does not interfere with a traversal by another processor (intention read/read). The idea is to ensure maximal concurrancy. Of course the top levels of the per processor hierarchies are connected (via an edge through a system-wide lock), to allow deadlock avoidance. The actual system resources are in a pseudo-per-cpu ownership zone, so you lock a cpu zone and that zone, not a "big giant lock", in order to do the fill/drain. The computation of deadlock (transitive closure) is done, as in the symbol table example, by inferring Hamiltonian cycles along the two edges you know about (the real one and the pretend one made up of the resources you will require for a given idempotent operation). This is terrifically fun stuff to watch when it works. It's much better than Djikstra's soloution (the banker's algorithm), in that you wouldn't have to rebuild FreeBSD from the ground up to make it work... Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199809162132.OAA27690>