[erlang-questions] 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/