[erlang-questions] Pattern matching of literal small/big/bignum integers and binary search

[Edmond Begumisa]

On Sun, 16 Jun 2019 18:27:58 +1000, Edmond Begumisa  
<ebegumisa@REDACTED> 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/