On Tue, Sep 30, 2008 at 9:18 AM, Manlio Perillo <[EMAIL PROTECTED]> wrote: > Graham Fawcett ha scritto: >> >> On Thu, Sep 25, 2008 at 5:09 PM, Manlio Perillo >> <[EMAIL PROTECTED]> wrote: >>> >>> Graham Fawcett ha scritto: >>>> >>>> If you're on Intel/Itanium, I believe there's a CMPXCHG instruction >>>> that will do atomic compare-and-set on a memory address, and I'm not >>>> sure you could get much faster than that. :-) >>> >>> I have an early draft of this type of database (written in D). >>> Operations on integers use CMPXCHG, and for other operations a simple >>> spin >>> lock (implemented following the implementation in Nginx) is used. >> >> And I thought I was being original. :-) >> >>> The problem is that it is a simple shared array! >> >> I'm guessing you've also ruled out sparse arrays? If not, what >> complexity is acceptable on your lookup function? >> > > Never though about sparse array, what is the advantage? > For the complexity, the same of a good hash map.
Almost certainly worse complexity than a hash map; but the overhead could be much smaller. If (for example) you only needed a small number of key/value pairs (say, hundreds of thousands), you could implement your "database" trivially, e.g. a NULL-terminated array of key/value structs in shared memory. (Though having separate arrays for keys and values might help cache locality and boost performance). Lookup might be O(n) but with a small-ish N and with such a low overhead, it could perform very, very well. Of course, you know what your requirements are, and I don't. :-) But I think if one needed a "shared map, size N, of integers to incrementing registers" where N wasn't enormous, then this might be attractive. Cheers, Graham > By the way, for the moment I think I will use Data.Map, serializing it to a > file, since only one process will update it, and the other processes needs > not to read an up-to-date snapshot. > The only thing that needs to be taken care of, is to write the file > atomically, but this is easy. > > > > Thanks Manlio Perillo > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
