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

Edmond Begumisa ebegumisa@REDACTED
Sun Jun 16 10:39:40 CEST 2019

```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.
>
>
> - Edmond -
>
> [1]
>
> [2]