digraph edges and improper lists

[Fred Youhanaie]

Hi

The digraph module uses the term ['$e'|N] to represent an edge.

Is there an advantage in using an improper list, as opposed to the more intuitive tuple format {'$e', N}?

I recently came across a situation where the following crashed because logger tried to flatten the list of improper lists!

logger:notice(#{ edges => digraph:edges(G) }).

However, these two were OK:

logger:notice(#{ edges => { digraph:edges(G) } }). %% Note the extra braces
logger:notice("edges = ~w", [digraph:edges(G)] ).

For me this was a temporary annoyance, but I'm just curious about the choice of list structure. Is this explained anywhere, such as docs or a blog?

Cheers,
Fred

[Dmytro Lytovchenko]

A list of 2 elements will consume:

1 list cell (2 words of memory) to store $n and pointer to second cell

1 list cell (2 more words) to store N and [] (that's nil, end of proper list)

total: 4 words of memory, on a 64 bit machine that's 32 bytes

An improper list of 2 elements will consume:

1 list cell (2 words of memory) to store $n and tail is stored as N

total 16 bytes of memory on 64 bit machine

http://beam-wisdoms.clau.se/en/latest/indepth-memory-layout.html#lists-cons

http://beam-wisdoms.clau.se/en/latest/indepth-data-sizes.html#list

[Fred Youhanaie]

Hi Dmytro

Many thanks for the explanation and the links.

So, we save memory when using an improper list instead of proper list of 2 elements.

How about 2-element tuples? It seems to be similar to the improper list, but I haven't read text properly yet!

Cheers,
Fred

On 20/12/2021 16:28, Dmytro Lytovchenko wrote:
> A list of 2 elements will consume:
> 1 list cell (2 words of memory) to store $n and pointer to second cell
> 1 list cell (2 more words) to store N and [] (that's nil, end of proper list)
> total: 4 words of memory, on a 64 bit machine that's 32 bytes
>
> An improper list of 2 elements will consume:
> 1 list cell (2 words of memory) to store $n and tail is stored as N
> total 16 bytes of memory on 64 bit machine
>

> http://beam-wisdoms.clau.se/en/latest/indepth-memory-layout.html#lists-cons <http://beam-wisdoms.clau.se/en/latest/indepth-memory-layout.html#lists-cons>
> http://beam-wisdoms.clau.se/en/latest/indepth-data-sizes.html#list <http://beam-wisdoms.clau.se/en/latest/indepth-data-sizes.html#list>

[Mikael Pettersson]

On Mon, Dec 20, 2021 at 6:12 PM Fred Youhanaie <f...@anydata.co.uk> wrote:
>
> Hi Dmytro
>
> Many thanks for the explanation and the links.
>
> So, we save memory when using an improper list instead of proper list of 2 elements.
>
> How about 2-element tuples? It seems to be similar to the improper list, but I haven't read text properly yet!

A 2-element tuple consumes 2+1 = 3 words, so it's not as compact as a
single list cell. It's also faster to determine the shape of that
single list cell than of the 2-element tuple (for the list cell we
only need to inspect the handle, while for the 2-element tuple we also
have to fetch its header and inspect that).

As long as this is hidden behind appropriate ADTs no-one should care
what the representation is.

[Fred Youhanaie]

Hi Mikael

On 20/12/2021 18:19, Mikael Pettersson wrote:
> On Mon, Dec 20, 2021 at 6:12 PM Fred Youhanaie <f...@anydata.co.uk> wrote:
>>
>> Hi Dmytro
>>
>> Many thanks for the explanation and the links.
>>
>> So, we save memory when using an improper list instead of proper list of 2 elements.
>>
>> How about 2-element tuples? It seems to be similar to the improper list, but I haven't read text properly yet!
>
> A 2-element tuple consumes 2+1 = 3 words, so it's not as compact as a
> single list cell. It's also faster to determine the shape of that
> single list cell than of the 2-element tuple (for the list cell we
> only need to inspect the handle, while for the 2-element tuple we also
> have to fetch its header and inspect that).

Many thanks for the clarification.

> As long as this is hidden behind appropriate ADTs no-one should care
> what the representation is.

For the digraph, I didn't care about the representation until logger crashed in me!

Cheers,
f.