when any why to use improper lists

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

when any why to use improper lists

Karlo Kuna
dealing with digraph module i have noticed use of improper lists as representations of edges: 
['$e' | 123]

is there a good reason to use improper lists instead of tuple for this and in general 
when is a good idea to use improper lists?? (i can't think of example for justified use)

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: when any why to use improper lists

Dmitry Belyaev-3
It's a way to reduce memory footprint.

Tuple of size N is roughly represented in memory as an array [TupleTag, N, TupleElement1, TupleElement2, ..., TupleElementN].
Compare it to Cons cell representation: [ConsTag, HeadElement, TailElement] - it saves 1 word per structure.

Kind regards,
Dmitry Belyaev

On Fri, Jun 29, 2018 at 9:50 AM, Karlo Kuna <[hidden email]> wrote:
dealing with digraph module i have noticed use of improper lists as representations of edges: 
['$e' | 123]

is there a good reason to use improper lists instead of tuple for this and in general 
when is a good idea to use improper lists?? (i can't think of example for justified use)

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: when any why to use improper lists

Dmytro Lytovchenko
A tuple of 2 elements will take 3 words of memory minimum
tuple1 = [ headerWord, element1, element2 ]

A cons cell has no header word, so an improper list of 1 element and 2nd element as a tail, just 2 values stored side to side
(same as normal list below except that only 1 cons cell is used, 2 words)
cons1 = [ element1, element2 ]

A proper list of 2 elements will take 2 cons cells, i.e. 4 words of memory minimum
cons2 = [ element2, [] ]
cons1 = [ element1, cons2 ]


2018-06-29 2:23 GMT+02:00 Dmitry Belyaev <[hidden email]>:
It's a way to reduce memory footprint.

Tuple of size N is roughly represented in memory as an array [TupleTag, N, TupleElement1, TupleElement2, ..., TupleElementN].
Compare it to Cons cell representation: [ConsTag, HeadElement, TailElement] - it saves 1 word per structure.

Kind regards,
Dmitry Belyaev

On Fri, Jun 29, 2018 at 9:50 AM, Karlo Kuna <[hidden email]> wrote:
dealing with digraph module i have noticed use of improper lists as representations of edges: 
['$e' | 123]

is there a good reason to use improper lists instead of tuple for this and in general 
when is a good idea to use improper lists?? (i can't think of example for justified use)

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: when any why to use improper lists

Dmitry Klionsky-2

Some numbers

1> erts_debug:flat_size([a,b]).
4
2> erts_debug:flat_size({a,b}).
3
3> erts_debug:flat_size([a|b]).
2


On 06/29/2018 03:35 AM, Dmytro Lytovchenko wrote:
A tuple of 2 elements will take 3 words of memory minimum
tuple1 = [ headerWord, element1, element2 ]

A cons cell has no header word, so an improper list of 1 element and 2nd element as a tail, just 2 values stored side to side
(same as normal list below except that only 1 cons cell is used, 2 words)
cons1 = [ element1, element2 ]

A proper list of 2 elements will take 2 cons cells, i.e. 4 words of memory minimum
cons2 = [ element2, [] ]
cons1 = [ element1, cons2 ]


2018-06-29 2:23 GMT+02:00 Dmitry Belyaev <[hidden email]>:
It's a way to reduce memory footprint.

Tuple of size N is roughly represented in memory as an array [TupleTag, N, TupleElement1, TupleElement2, ..., TupleElementN].
Compare it to Cons cell representation: [ConsTag, HeadElement, TailElement] - it saves 1 word per structure.

Kind regards,
Dmitry Belyaev

On Fri, Jun 29, 2018 at 9:50 AM, Karlo Kuna <[hidden email]> wrote:
dealing with digraph module i have noticed use of improper lists as representations of edges: 
['$e' | 123]

is there a good reason to use improper lists instead of tuple for this and in general 
when is a good idea to use improper lists?? (i can't think of example for justified use)

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions




_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

-- 
BR,
Dmitry

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: when any why to use improper lists

Pierre Fenoll-2
Has there been some testing / measurements done on the memory saved by introducing a "tuple of 2" tag only for 2-tuples?
{ok, Bla} or {error, R} is such a common pattern and "most" machines being 64bits nowadays this should save many times 8 bytes, shouldn't it?
So we have a tag for lists (cons), a tag for n-sized tuples and tags for other data. How about a tag for a memory structure that's basically [a|b] but which would be understood as {a,b}.

Cheers,
-- 
Pierre Fenoll



On Fri, 29 Jun 2018 at 10:16, Dmitry Klionsky <[hidden email]> wrote:

Some numbers

1> erts_debug:flat_size([a,b]).
4
2> erts_debug:flat_size({a,b}).
3
3> erts_debug:flat_size([a|b]).
2


On 06/29/2018 03:35 AM, Dmytro Lytovchenko wrote:
A tuple of 2 elements will take 3 words of memory minimum
tuple1 = [ headerWord, element1, element2 ]

A cons cell has no header word, so an improper list of 1 element and 2nd element as a tail, just 2 values stored side to side
(same as normal list below except that only 1 cons cell is used, 2 words)
cons1 = [ element1, element2 ]

A proper list of 2 elements will take 2 cons cells, i.e. 4 words of memory minimum
cons2 = [ element2, [] ]
cons1 = [ element1, cons2 ]


2018-06-29 2:23 GMT+02:00 Dmitry Belyaev <[hidden email]>:
It's a way to reduce memory footprint.

Tuple of size N is roughly represented in memory as an array [TupleTag, N, TupleElement1, TupleElement2, ..., TupleElementN].
Compare it to Cons cell representation: [ConsTag, HeadElement, TailElement] - it saves 1 word per structure.

Kind regards,
Dmitry Belyaev

On Fri, Jun 29, 2018 at 9:50 AM, Karlo Kuna <[hidden email]> wrote:
dealing with digraph module i have noticed use of improper lists as representations of edges: 
['$e' | 123]

is there a good reason to use improper lists instead of tuple for this and in general 
when is a good idea to use improper lists?? (i can't think of example for justified use)

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions




_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

-- 
BR,
Dmitry
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: when any why to use improper lists

Dmytro Lytovchenko
A problem, cons is a pointer. Tuple is also a pointer. Currently 2 bits are used for such tags, and adding more special cases will need more bits.

Tagged value must have enough bits to hold a whole pointer, so by using the fact that all memory words are 4 (8) byte-aligned, there are only 2 bits available (for compatibility with 32 bit systems) and on 64-bit it could become 3 bit to fit some extra special cases in there. This 3-bit tagging is not implemented in BEAM VM. With existing C code in BEAM VM i am sure it will create a lot of suffering for a person trying to implement it.

Another trick to tag a pointer is to use high bits above 48 or 56 which depending on platform may be unused and on Intel must always be set to 1. This trick is not portable and is not used.

2018-06-29 14:14 GMT+02:00 Pierre Fenoll <[hidden email]>:
Has there been some testing / measurements done on the memory saved by introducing a "tuple of 2" tag only for 2-tuples?
{ok, Bla} or {error, R} is such a common pattern and "most" machines being 64bits nowadays this should save many times 8 bytes, shouldn't it?
So we have a tag for lists (cons), a tag for n-sized tuples and tags for other data. How about a tag for a memory structure that's basically [a|b] but which would be understood as {a,b}.

Cheers,
-- 
Pierre Fenoll



On Fri, 29 Jun 2018 at 10:16, Dmitry Klionsky <[hidden email]> wrote:

Some numbers

1> erts_debug:flat_size([a,b]).
4
2> erts_debug:flat_size({a,b}).
3
3> erts_debug:flat_size([a|b]).
2


On 06/29/2018 03:35 AM, Dmytro Lytovchenko wrote:
A tuple of 2 elements will take 3 words of memory minimum
tuple1 = [ headerWord, element1, element2 ]

A cons cell has no header word, so an improper list of 1 element and 2nd element as a tail, just 2 values stored side to side
(same as normal list below except that only 1 cons cell is used, 2 words)
cons1 = [ element1, element2 ]

A proper list of 2 elements will take 2 cons cells, i.e. 4 words of memory minimum
cons2 = [ element2, [] ]
cons1 = [ element1, cons2 ]


2018-06-29 2:23 GMT+02:00 Dmitry Belyaev <[hidden email]>:
It's a way to reduce memory footprint.

Tuple of size N is roughly represented in memory as an array [TupleTag, N, TupleElement1, TupleElement2, ..., TupleElementN].
Compare it to Cons cell representation: [ConsTag, HeadElement, TailElement] - it saves 1 word per structure.

Kind regards,
Dmitry Belyaev

On Fri, Jun 29, 2018 at 9:50 AM, Karlo Kuna <[hidden email]> wrote:
dealing with digraph module i have noticed use of improper lists as representations of edges: 
['$e' | 123]

is there a good reason to use improper lists instead of tuple for this and in general 
when is a good idea to use improper lists?? (i can't think of example for justified use)

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions




_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

-- 
BR,
Dmitry
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: when any why to use improper lists

Mikael Pettersson-5
With the current tag scheme, special-casing 2-element tuples would not
be a win space-wise, as we cannot make them header-less without
sacrificing something else, and that's not going to happen.
With 3 primary tag bits we could achieve that, but then general tuple
tests would be more complicated since multiple primary tags would map
to tuples.

However, OTP should definitely go to a 64-bit, 3 primary tag bits, tag
scheme soon.  Who cares about 32-bit machines, right?

Just use CONS cells for 2-tuples of there's no confusion and you're
behind an ADT layer.

On Fri, Jun 29, 2018 at 2:30 PM, Dmytro Lytovchenko
<[hidden email]> wrote:

> A problem, cons is a pointer. Tuple is also a pointer. Currently 2 bits are
> used for such tags, and adding more special cases will need more bits.
>
> Tagged value must have enough bits to hold a whole pointer, so by using the
> fact that all memory words are 4 (8) byte-aligned, there are only 2 bits
> available (for compatibility with 32 bit systems) and on 64-bit it could
> become 3 bit to fit some extra special cases in there. This 3-bit tagging is
> not implemented in BEAM VM. With existing C code in BEAM VM i am sure it
> will create a lot of suffering for a person trying to implement it.
>
> Another trick to tag a pointer is to use high bits above 48 or 56 which
> depending on platform may be unused and on Intel must always be set to 1.
> This trick is not portable and is not used.
>
> 2018-06-29 14:14 GMT+02:00 Pierre Fenoll <[hidden email]>:
>>
>> Has there been some testing / measurements done on the memory saved by
>> introducing a "tuple of 2" tag only for 2-tuples?
>> {ok, Bla} or {error, R} is such a common pattern and "most" machines being
>> 64bits nowadays this should save many times 8 bytes, shouldn't it?
>> So we have a tag for lists (cons), a tag for n-sized tuples and tags for
>> other data. How about a tag for a memory structure that's basically [a|b]
>> but which would be understood as {a,b}.
>>
>> Cheers,
>> --
>> Pierre Fenoll
>>
>>
>>
>> On Fri, 29 Jun 2018 at 10:16, Dmitry Klionsky <[hidden email]>
>> wrote:
>>>
>>> Some numbers
>>>
>>> 1> erts_debug:flat_size([a,b]).
>>> 4
>>> 2> erts_debug:flat_size({a,b}).
>>> 3
>>> 3> erts_debug:flat_size([a|b]).
>>> 2
>>>
>>>
>>> On 06/29/2018 03:35 AM, Dmytro Lytovchenko wrote:
>>>
>>> A tuple of 2 elements will take 3 words of memory minimum
>>>
>>> http://beam-wisdoms.clau.se/en/latest/indepth-memory-layout.html#tuple-arityval-0
>>> tuple1 = [ headerWord, element1, element2 ]
>>>
>>> A cons cell has no header word, so an improper list of 1 element and 2nd
>>> element as a tail, just 2 values stored side to side
>>> (same as normal list below except that only 1 cons cell is used, 2 words)
>>> cons1 = [ element1, element2 ]
>>>
>>> A proper list of 2 elements will take 2 cons cells, i.e. 4 words of
>>> memory minimum
>>> cons2 = [ element2, [] ]
>>> cons1 = [ element1, cons2 ]
>>>
>>> http://beam-wisdoms.clau.se/en/latest/indepth-memory-layout.html#lists-cons
>>>
>>>
>>> 2018-06-29 2:23 GMT+02:00 Dmitry Belyaev <[hidden email]>:
>>>>
>>>> It's a way to reduce memory footprint.
>>>>
>>>> Tuple of size N is roughly represented in memory as an array [TupleTag,
>>>> N, TupleElement1, TupleElement2, ..., TupleElementN].
>>>> Compare it to Cons cell representation: [ConsTag, HeadElement,
>>>> TailElement] - it saves 1 word per structure.
>>>>
>>>> Kind regards,
>>>> Dmitry Belyaev
>>>>
>>>> On Fri, Jun 29, 2018 at 9:50 AM, Karlo Kuna <[hidden email]>
>>>> wrote:
>>>>>
>>>>> dealing with digraph module i have noticed use of improper lists as
>>>>> representations of edges:
>>>>> ['$e' | 123]
>>>>>
>>>>> is there a good reason to use improper lists instead of tuple for this
>>>>> and in general
>>>>> when is a good idea to use improper lists?? (i can't think of example
>>>>> for justified use)
>>>>>
>>>>> _______________________________________________
>>>>> erlang-questions mailing list
>>>>> [hidden email]
>>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> erlang-questions mailing list
>>>> [hidden email]
>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> erlang-questions mailing list
>>> [hidden email]
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>
>>>
>>> --
>>> BR,
>>> Dmitry
>>>
>>> _______________________________________________
>>> erlang-questions mailing list
>>> [hidden email]
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>
>
> _______________________________________________
> erlang-questions mailing list
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions