Re: [Haskell-cafe] pure Haskell database

On Tue, Sep 30, 2008 at 9:18 AM, Manlio Perillo wrote:

Graham Fawcett ha scritto:

...

On Thu, Sep 25, 2008 at 5:09 PM, Manlio Perillo 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