tag:blogger.com,1999:blog-2744072865491516720.post5616344071297453153..comments2023-05-03T06:35:33.259-04:00Comments on Higher Logics: The Most General Concurrent APISandro Magihttp://www.blogger.com/profile/05446177882449578817noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-2744072865491516720.post-64541334545806399342012-02-06T12:44:24.434-05:002012-02-06T12:44:24.434-05:00FYI, .NET objects have a two-word header, one for ...FYI, .NET objects have a two-word header, one for the hashcode/lock/sync block, one for the vtable. See also http://stackoverflow.com/questions/1589669/overhead-of-a-net-arrayQwertiehttps://www.blogger.com/profile/04595705428290721343noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-77698071804638867062012-02-06T12:41:22.381-05:002012-02-06T12:41:22.381-05:00I doubt the suggested solution -- C++/CLI with gcr...I doubt the suggested solution -- C++/CLI with gcroot in an unmanaged block -- is viable for a high-performance data structure. I don't know how it's implemented, but if the garbage collector sees it as a "root" then it probably requires a word or two of bookkeeping per gcroot, plus gcroot would probably need to do some processing in its constructor and destructor. I'm just guessing tho.<br /><br />Yes, I'm my B+ tree isn't designed for maximum performance but rather maximum flexibility. For instance, it supports an indexer and RemoveAt, O(1) freezing and cloning, and there is an unsorted version called A-List which supports appending and splitting.Qwertiehttps://www.blogger.com/profile/04595705428290721343noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-76031377048778941182012-02-05T14:31:30.497-05:002012-02-05T14:31:30.497-05:00@Qwertie,
Re: the more compact struct version, I ...@Qwertie,<br /><br />Re: the more compact struct version, I haven't implemented it because I haven't had a need. Only limited time and other projects are more compelling than micro-optimizing this case.<br /><br />Re: B+ tree, that's cool. I've been meaning to implement a cache-conscious B+ tree, but <a href="http://stackoverflow.com/questions/7692820/c-sharp-fixed-inline-arrays" rel="nofollow">C# again has some limitations in this regard</a>. I'll get to it one day!<br /><br />You'll find that most of the purely functional collections in my Sasa library are only available as structs. The internals use classes, but I keep the public interface as a struct so I can properly handle empty collections without the clients triggering NullReferenceExceptions.Sandro Magihttps://www.blogger.com/profile/05446177882449578817noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-31628023054224946572012-02-05T14:24:24.990-05:002012-02-05T14:24:24.990-05:00Oops, I meant Int16 obviously.Oops, I meant Int16 obviously.Sandro Magihttps://www.blogger.com/profile/05446177882449578817noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-46474229059748280642012-02-05T14:23:45.282-05:002012-02-05T14:23:45.282-05:00@Qwertie, the CLR reserves at least a 32-bit heade...@Qwertie, the CLR reserves at least a 32-bit header in every object for storing lock information (might actually be a 64-bit header, I don't recall exactly). It tries to acquire this lock word in a loop using a CAS. After X number of failures, it allocates a WaitHandle and blocks on that in a queue rooted at that object. <br /><br />It's clear that the WaitHandle should just be part of any thread abstraction, so we only need to create one for the entire thread lifetime.<br /><br />The Locked<T> class represents the headers needed in an object if I were to do this on a low-level. Right now it uses two words, one for each MetaThread pointer, to keep it simple. You can replace these with two Int15, and use those to indirect to a global thread table. This latter technique is used in the paper above to make lock space overhead very small.Sandro Magihttps://www.blogger.com/profile/05446177882449578817noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-61222474847936987862012-02-05T14:18:24.453-05:002012-02-05T14:18:24.453-05:00Oh, does your library offer a 2-word 'struct&#...Oh, does your library offer a 2-word 'struct' version of the lock? That's the only way to let people have two-word overhead.<br /><br />I realize that using a struct can be dangerous since you can't prevent accidental copying of the lock; that's why you should offer both a low-level struct version (nongeneric, no 'value' field) and a high-level generic class version. Then people can use the struct version as an optimization if they need very fine-grained locking (e.g. their program will have over 100,000 locks in it).<br /><br />In the library I've been developing, there are two collection classes that I offer in 'struct' form, InternalList and InternalDList (a deque). They are intended as primitives to be used inside other collection classes, e.g. I also wrote a B+ tree which uses InternalDList inside each leaf node, and a V-List that uses InternalList. High-level code should of course use classes instead (List and DList, the latter being a wrapper for DListInternal).Qwertiehttps://www.blogger.com/profile/04595705428290721343noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-86805499716184222642012-02-05T14:07:11.667-05:002012-02-05T14:07:11.667-05:00(of course, by "word" I mean it in the C...(of course, by "word" I mean it in the CS literature sense of "IntPtr-sized field", not the x86 sense of "two bytes".)Qwertiehttps://www.blogger.com/profile/04595705428290721343noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-36594958107228640052012-02-05T14:05:30.825-05:002012-02-05T14:05:30.825-05:00So if I understand correctly, you only need two po...So if I understand correctly, you only need two pointers (plus a bit of thread-local data) to implement a lock that supports any fair scheduling policy? Nice. I wonder if it uses more or less memory than a standard .NET lock (if you use lock(x) in C#, does it cause a permanent memory allocation associated with x, or does it use some lock technique that only needs one word of storage, in which case the first word of the two-word object header could be used?)<br /><br />In any case, I'm guessing this tends to be faster than lock().Qwertiehttps://www.blogger.com/profile/04595705428290721343noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-59074922377789073202011-10-25T11:30:45.301-04:002011-10-25T11:30:45.301-04:00These are shared memory concurrency abstractions. ...These are shared memory concurrency abstractions. If you're interested in scaling shared memory abstractions across a network, you have to resort to <a href="http://en.wikipedia.org/wiki/Distributed_shared_memory" rel="nofollow">distributed shared memory</a>. Again, that's distributed programming which often require a whole different set of abstractions.Sandro Magihttps://www.blogger.com/profile/05446177882449578817noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-78316215669442133582011-10-25T03:49:33.959-04:002011-10-25T03:49:33.959-04:00Concurrent programs can be executed sequentially o...Concurrent programs can be executed sequentially on a single processor by interleaving the execution steps of each computational process, or executed in parallel by assigning each computational process to one of a set of processors that may be close or distributed across a network. [Wikipedia]egonhttps://www.blogger.com/profile/16474992560782430655noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-46836554054849132002011-10-24T18:07:39.125-04:002011-10-24T18:07:39.125-04:00Concurrent programming is scaling across multiple ...Concurrent programming is scaling across multiple cores on a single computer. Scaling across computers is distributed programming. That's a completely separate problem.Sandro Magihttps://www.blogger.com/profile/05446177882449578817noreply@blogger.comtag:blogger.com,1999:blog-2744072865491516720.post-69531837173753312272011-10-24T17:45:38.295-04:002011-10-24T17:45:38.295-04:00How can it scale over multiple computers with reli...How can it scale over multiple computers with reliability? For example 3 computers and any two can go down and the resource management still works?egonhttps://www.blogger.com/profile/16474992560782430655noreply@blogger.com