Pattern matching of literal small/big/bignum integers and binary search

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

Pattern matching of literal small/big/bignum integers and binary search

Edmond Begumisa
Hello all,

I have some questions about how pattern matches on integer literals are  
evaluated by the emulator.

As an example, say I have the following function which expects an integer  
that's a power of 2 and returns corresponding position of the lone "on"  
bit...

       
         single_cardinalty_to_pos(2#1) -> 1;
         single_cardinalty_to_pos(2#10) -> 2;
         single_cardinalty_to_pos(2#100) -> 3;
         ...
         single_cardinalty_to_pos(2#100...0) -> 128.

I'm trying to gauge whether or not I've correctly understood the resultant  
select_val BEAM assembly instruction w.r.t gen_select_val [1] in  
beam_load.c (without even being at all certain that gen_select_val is even  
relevant).

        {label,133}.
          {test,is_integer,{f,132},[{x,0}]}.
          {select_val,{x,0},
                      {f,132},
                      {list,[{integer,170141183460469231731687303715884105728},
                             {f,134},
                             ....
                             {integer,4},
                             {f,139},
                             {integer,2},
                             {f,140},
                             {integer,1},
                             {f,140}]}}.


I could use some help to determine if the following assumptions are  
correct...

    A) That rather than brute forcing, the emulator will perform a binary  
search [2] for the function argument against all the literals from all the  
clauses which is the purpose of quick-sorting the select_val list, and as  
such,

    B) If I want to increase the upper limit that the function can handle,  
I can simply add more clauses rather than trying to implement a binary  
search for the "on" bit myself using various masks and bit shifts.

    C) That the emulator will be smart about whether on not the function  
argument is an 8 bit, 32/64 bit integer versus a bignum integer and thus  
know what candidates can be excluded from the binary search so there's no  
benefit to splitting the function to handle different ranges.

    D) That it's not unreasonable in this case to have even say, 1024  
clauses in order to handle bignum integers of up to 1024 bits. The only  
downside will be longer compile times and possibly longer loading of the  
module.

If these assumptions are correct, then I could have the emulator do a lot  
of work for me with a number of similar functions and avoid writing a lot  
code.

Thanks in advance.

- Edmond -

[1]  
https://github.com/erlang/otp/blob/48e1cc6a6f7bebacd5fb060bfd65ececbabfa6a1/erts/emulator/beam/beam_load.c#L4097

[2]  
https://github.com/erlang/otp/blob/48e1cc6a6f7bebacd5fb060bfd65ececbabfa6a1/erts/emulator/beam/beam_load.c#L4159

--
Using Opera's mail client: http://www.opera.com/mail/
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Pattern matching of literal small/big/bignum integers and binary search

Edmond Begumisa
On Sun, 16 Jun 2019 18:27:58 +1000, Edmond Begumisa  
<[hidden email]> wrote:

> Hello all,
>
> I have some questions about how pattern matches on integer literals are  
> evaluated by the emulator.
>
> As an example, say I have the following function which expects an  
> integer that's a power of 2 and returns corresponding position of the  
> lone "on" bit...
>
>
>          single_cardinalty_to_pos(2#1) -> 1;
>          single_cardinalty_to_pos(2#10) -> 2;
>          single_cardinalty_to_pos(2#100) -> 3;
>          ...
>          single_cardinalty_to_pos(2#100...0) -> 128.
>
> I'm trying to gauge whether or not I've correctly understood the  
> resultant select_val BEAM assembly instruction w.r.t gen_select_val [1]  
> in beam_load.c (without even being at all certain that gen_select_val is  
> even relevant).
>
>         {label,133}.
>           {test,is_integer,{f,132},[{x,0}]}.
>           {select_val,{x,0},
>                       {f,132},
>                       {list,[{integer,170141183460469231731687303715884105728},
>                              {f,134},
>                              ....
>                              {integer,4},
>                              {f,139},
>                              {integer,2},
>                              {f,140},
>                              {integer,1},
>                              {f,140}]}}.
>
>
> I could use some help to determine if the following assumptions are  
> correct...
>
>     A) That rather than brute forcing, the emulator will perform a  
> binary search [2] for the function argument against all the literals  
> from all the clauses which is the purpose of quick-sorting the  
> select_val list, and as such,
>
>     B) If I want to increase the upper limit that the function can  
> handle, I can simply add more clauses rather than trying to implement a  
> binary search for the "on" bit myself using various masks and bit shifts.
>
>     C) That the emulator will be smart about whether on not the function  
> argument is an 8 bit, 32/64 bit integer versus a bignum integer and thus  
> know what candidates can be excluded from the binary search so there's  
> no benefit to splitting the function to handle different ranges.
>
>     D) That it's not unreasonable in this case to have even say, 1024  
> clauses in order to handle bignum integers of up to 1024 bits. The only  
> downside will be longer compile times and possibly longer loading of the  
> module.

Provided I don't go overboard with the size of the bignums due to the  
potential impact on runtime responsiveness (in addition to pattern  
matches, I believe the bignum arith operations are not broken-up for  
rescheduling?)

> If these assumptions are correct, then I could have the emulator do a  
> lot of work for me with a number of similar functions and avoid writing  
> a lot code.
>
> Thanks in advance.
>
> - Edmond -
>
> [1]  
> https://github.com/erlang/otp/blob/48e1cc6a6f7bebacd5fb060bfd65ececbabfa6a1/erts/emulator/beam/beam_load.c#L4097
>
> [2]  
> https://github.com/erlang/otp/blob/48e1cc6a6f7bebacd5fb060bfd65ececbabfa6a1/erts/emulator/beam/beam_load.c#L4159
>
> --
> Using Opera's mail client: http://www.opera.com/mail/


--
Using Opera's mail client: http://www.opera.com/mail/
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Pattern matching of literal small/big/bignum integers and binary search

Björn Gustavsson-4
In reply to this post by Edmond Begumisa
On Sun, Jun 16, 2019 at 10:28 AM Edmond Begumisa
<[hidden email]> wrote:

>
> Hello all,
>
> I have some questions about how pattern matches on integer literals are
> evaluated by the emulator.
>
> As an example, say I have the following function which expects an integer
> that's a power of 2 and returns corresponding position of the lone "on"
> bit...
>
>
>          single_cardinalty_to_pos(2#1) -> 1;
>          single_cardinalty_to_pos(2#10) -> 2;
>          single_cardinalty_to_pos(2#100) -> 3;
>          ...
>          single_cardinalty_to_pos(2#100...0) -> 128.

The easiest way to determine what the loader will do with the code is
to disassemble the loaded code by calling erts_debug:df/1. If your
module is called 'foo', erts_debug:df('foo') will disassemble the
loaded coded for the module into the file foo.dis.

In the case of your example, the loader will split up the select_val
instruction into multiple instructions. There will be a
select_val_bins instruction that will do a binary search of all
integers that fit into one word. If that instruction fails, there will
be one i_is_ne_exact_literal instruction for comparing each of the
bignum values. Here are the three last instructions from your example
(matching 2^126, 2^127, 2^128):

0000000018E150B8: i_is_ne_exact_literal_fxc f(0000000018E15160) x(0)
85070591730234615865843651857942052864
0000000018E150D0: i_is_ne_exact_literal_fxc f(0000000018E15150) x(0)
42535295865117307932921825928971026432
0000000018E150E8: i_is_ne_exact_literal_fxc f(0000000018E15140) x(0)
21267647932558653966460912964485513216
.
.
.
0000000018E15160: move_return_c 126
0000000018E15170: move_return_c 127
0000000018E15180: move_return_c 128

/Björn

P.S. In OTP 22 documentation, there is internal documentation for the
beam_makeops script and the loader:

http://erlang.org/doc/apps/erts/beam_makeops.html

--
Björn Gustavsson, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Pattern matching of literal small/big/bignum integers and binary search

Björn Gustavsson-4
In reply to this post by Edmond Begumisa
On Sun, Jun 16, 2019 at 10:39 AM Edmond Begumisa
<[hidden email]> wrote:

> Provided I don't go overboard with the size of the bignums due to the
> potential impact on runtime responsiveness (in addition to pattern
> matches, I believe the bignum arith operations are not broken-up for
> rescheduling?)
>

Correct.

--
Björn Gustavsson, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Pattern matching of literal small/big/bignum integers and binary search

Edmond Begumisa
In reply to this post by Björn Gustavsson-4
Thank you Björn,

This answers all my questions precisely, especially revealing how bignum  
literals are treated differently w.r.t binary search.

And erts_debug:df/1 is pure gold. Far more useful than erlc -S. Even made  
it easy to locate the relevant instruction implementation in beam_emu.c

Much appreciated.

- Edmond -


On Mon, 17 Jun 2019 15:45:24 +1000, Björn Gustavsson <[hidden email]>  
wrote:

> On Sun, Jun 16, 2019 at 10:28 AM Edmond Begumisa
> <[hidden email]> wrote:
>>
>> Hello all,
>>
>> I have some questions about how pattern matches on integer literals are
>> evaluated by the emulator.
>>
>> As an example, say I have the following function which expects an  
>> integer
>> that's a power of 2 and returns corresponding position of the lone "on"
>> bit...
>>
>>
>>          single_cardinalty_to_pos(2#1) -> 1;
>>          single_cardinalty_to_pos(2#10) -> 2;
>>          single_cardinalty_to_pos(2#100) -> 3;
>>          ...
>>          single_cardinalty_to_pos(2#100...0) -> 128.
>
> The easiest way to determine what the loader will do with the code is
> to disassemble the loaded code by calling erts_debug:df/1. If your
> module is called 'foo', erts_debug:df('foo') will disassemble the
> loaded coded for the module into the file foo.dis.
>
> In the case of your example, the loader will split up the select_val
> instruction into multiple instructions. There will be a
> select_val_bins instruction that will do a binary search of all
> integers that fit into one word. If that instruction fails, there will
> be one i_is_ne_exact_literal instruction for comparing each of the
> bignum values. Here are the three last instructions from your example
> (matching 2^126, 2^127, 2^128):
>
> 0000000018E150B8: i_is_ne_exact_literal_fxc f(0000000018E15160) x(0)
> 85070591730234615865843651857942052864
> 0000000018E150D0: i_is_ne_exact_literal_fxc f(0000000018E15150) x(0)
> 42535295865117307932921825928971026432
> 0000000018E150E8: i_is_ne_exact_literal_fxc f(0000000018E15140) x(0)
> 21267647932558653966460912964485513216
> .
> .
> .
> 0000000018E15160: move_return_c 126
> 0000000018E15170: move_return_c 127
> 0000000018E15180: move_return_c 128
>
> /Björn
>
> P.S. In OTP 22 documentation, there is internal documentation for the
> beam_makeops script and the loader:
>
> http://erlang.org/doc/apps/erts/beam_makeops.html
>


--
Using Opera's mail client: http://www.opera.com/mail/
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions