[erlang-questions] documentation of data structures

[Matej Kosik]

-----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?

> 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?

> 
> 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.

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-----