[Haskell-cafe] pure Haskell database

[Graham Fawcett]

On Tue, Sep 30, 2008 at 9:18 AM, Manlio Perillo
<manlio_perillo at libero.it> wrote:
> Graham Fawcett ha scritto:
>>
>> On Thu, Sep 25, 2008 at 5:09 PM, Manlio Perillo
>> <manlio_perillo at libero.it> 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
>