[erlang-questions] when any why to use improper lists

[Mikael Pettersson]

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
<dmytro.lytovchenko@REDACTED> 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 <pierrefenoll@REDACTED>:
>>
>> 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 <dm.klionsky@REDACTED>
>> 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 <be.dmitry@REDACTED>:
>>>>
>>>> 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 <kuna.prime@REDACTED>
>>>> 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
>>>>> erlang-questions@REDACTED
>>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> erlang-questions mailing list
>>>> erlang-questions@REDACTED
>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>
>>>
>>> --
>>> BR,
>>> Dmitry
>>>
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>