[erlang-questions] documentation of data structures

[Lev Walkin]

Matej Kosik wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Lev Walkin wrote:
>> Matej Kosik wrote:
>>
>>>> If Erlang is implemented properly, this would be efficient despite the
>>>> fact that there are many
>>>> processes. Real measurements would either support or reject such
>>>> hypothesis.
>>>>
>>>>> This design has the same drawback as ets: lots of copying [between
>>>>> processes]. Consequently, a part of my email still applies:
>>> Are you sure? When (in which kind of operation) would such copying (of
>>> what) be needed.
>>>
>>> Sure, the cost of explicit copying of a queue instance has O(len(N))
>>> complexity. But we were talking
>>> about adding/removing elements at the head/tail of the queue.
>> I suspect implementing a queue as a separate process would have
>> larger constant factor than the current queues implementation for
>> data of pretty much any size.
> 
> In my scheme, queue is not implemented as a process. Particular cells are implemented as processes.
> Many such cells are employed in representation of such queue.
> 
> The described operations (empty, make, get, set, isEmpty have O(1)) complexity. Indeed, good
> question is, whether the `spawn' operation (necessary when creating new cells) is expensive or heap.
> Isn't this true in Erlang? How much more expensive is spawn than the cost of a function call in Erlang?

See below.

>> With larger elements the cost
>> of copying between processes only increases (unless they contain
>> larger binaries, of course).
> 
> Why would I want to copy the queue when I want to insert/remove elements at the head or tail of the
> queue?

Not queue. Element. See below.

>> So I see no point in implementing queues as an external data
>> structure, since there's going to be no performance benefit,
>> or more properly put, they'll have a negative performance impact.
>>
> 
> I do not think we understand each other. Neither of us changed their (mutually inconsistent)
> beliefs. That is a pity of some of us.

I am not talking about copying the queue. I am talking about extracting 
an element out of the queue or adding an element into it.

The cost of function call is more than order of magnitude cheaper than
spawn() in Erlang. Cost of intermodular queue:new() is slightly larger
than cost of sending a single atom message, but not importantly so.

The problem is that we start growing past simple atom messages
or starting to allocate and deallocate cells. spawn() will kill this
idea.

I understand your point, but I am working within a constraint of
a particular language, Erlang, which has such and such timings
of most important constructs. Spawn() is a heavy construct
(compared to a function call).

> Here
> http://altair.sk:60001/mediawiki/upload/2/2b/Backwater.pdf
> is a series of definitions of various data types in Pict.
> 
> Section 2.4 contains implementation of Cells. All operations have O(1) complexity and "spawn" as
> cheap as sending of a message.
> 
> Section 2.15 contains implementation of Queue as I have described it (and more).
> 
> Regards
> - --
> Matej Kosik
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.6 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
> 
> iD8DBQFHXo/HL+CaXfJI/hgRAhVbAJ9PX8an3fbWWP+j9SG7hYpo4kvpKwCeJMg7
> +LPPM/Ryav5dKYN9iGI6f64=
> =taUn
> -----END PGP SIGNATURE-----