On Thu, Oct 23, 2003 at 02:24:01PM -0700, Michael Wojcik wrote: > > On Wed, Oct 22, 2003 at 07:26:07PM -0700, > > > If you want to update [a reference counter], I don't see how you can > > > guarantee updates will not collide [without locking], but I'm willing > > > to be educated, if you can provide a link to a web resource. > > > "High Performance Dynamic Lock-Free Hash Tables and List-Based Sets" by > > Maged M. Micheal. > > Requires a compare-and-swap (CAS) primitive (or > load-linked/store-conditional, or some equivalent). Is one available on > every architecture Xerces might be ported to? And if it is, who's going to > code to each variant? How many processor families is Xerces running on now? I don't know what archtectures Xerces isbuilt for at the moment, but the CAS instruction is available on Intel x86 as of i486, and on SPARC at least as of v8; the LL/SC instructions are available on PowerPC, MIPS and Alpha. All this is according to the footnote (number 4) of the article - I have only verified for x86 and SPARC because I've actually needed them on those architectures. I wouldn't be surprised if Motorola's 68k series comes with something similar as well, but I haven't checked.
> If CAS were universally available, in itself it'd be sufficient to implement > a thread-safe reference counter. No need to implement Michael's algorithm, > nifty though it is. A thread-safe reference counter would in deed be possible with a CAS instruction, but for implementing hashes, lists, etc. it tends to add a lot of overhead - i.e. it's only really useful for COWs(*) and global initializers such as the XMLPlatformUtils::Initialize function. > (There seems to be some interesting work going on with lockless or > minimally-locking shared data structures lately, though. I just > recently read the piece on IBM's DeveloperWorks site about Doug Lea's > minimal-locking ConcurrentHashMap, which uses Java's garbage collection to > avoid having to lock the list during deletions. Nice.) Yes.. but only possible with Java (or more generally, when you have a garbage collection mechanism in your memory management). I usually write in C or C++ and don't have the luxury of a memory manager, let alone a garbage collector.. rlc *) COW: Copy On Write --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
