同じアドレスを指すterm同士の同値チェックは定数時間で行われるか？

表題の件、少し気になったので調べてみた。

$ erl
Erlang/OTP 18 [erts-7.1] [source-2882b0c] [64-bit] [smp:4:4] [async-threads:10][hipe] [kernel-poll:false]

Eshell V7.1  (abort with ^G)
> A_0 = lists:seq(1, 10000). % 一万要素のリスト
> A_1 = A_0.                 % `A_1`に`A_0`を束縛 (両者は同じアドレスを指すはず)
> B   = lists:seq(1, 10000). % 別に作った一万要素のリスト

%% 参考計測: `1 =:= 1`を一万回実行
> timer:tc(fun () -> lists:bforeach(fun (_) -> 1 =:= 1 end, A_0) end).
{7954,ok} % 7.8ミリ秒

%% `A_0`と`A_1`の同値チェックを一万回
> timer:tc(fun () -> lists:foreach(fun (_) -> A_0 =:= A_1 end, A_0) end).
{9840,ok}  % 9.8ミリ秒

%% `A_0`と`B`の同値チェックを一万回
> timer:tc(fun () -> lists:foreach(fun (_) -> A_0 =:= B end, A_0) end).  
{269874,ok} % 269.8ミリ秒

同じアドレスを指すterm同士は、ちゃんと定数時間で比較されている模様。

ソースコード的にはutils.cのeq関数とerl_term.hのis_sameマクロ辺りがおそらく該当箇所。

utils.c

int eq(Eterm a, Eterm b)
{
    DECLARE_WSTACK(stack);
    Sint sz;
    Eterm* aa;
    Eterm* bb;

tailrecur:
    /*** 一番初めにis_sameマクロ(下記)でアドレスの一致チェックを行っている ***/
    if (is_same(a, a_base, b, b_base)) goto pop_next;
tailrecur_ne:

    switch (primary_tag(a)) {
    case TAG_PRIMARY_LIST:
        if (is_list(b)) {
            Eterm* aval = list_val_rel(a, a_base);
            Eterm* bval = list_val_rel(b, b_base);
            while (1) {
                Eterm atmp = CAR(aval);
                Eterm btmp = CAR(bval);
                if (!is_same(atmp,a_base,btmp,b_base)) {
                    WSTACK_PUSH2(stack,(UWord) CDR(bval),(UWord) CDR(aval));
                    a = atmp;
                    b = btmp;
                    goto tailrecur_ne;
                }
                atmp = CDR(aval);
                btmp = CDR(bval);
                if (is_same(atmp,a_base,btmp,b_base)) {
                    /*** リストの場合、cdr部のアドレスが一致したら、以降の比較は省略される ***/
                    goto pop_next;
                }
                if (is_not_list(atmp) || is_not_list(btmp)) {
                    a = atmp;
                    b = btmp;
                    goto tailrecur_ne;
                }
                aval = list_val_rel(atmp, a_base);
                bval = list_val_rel(btmp, b_base);
            }
        }
        break; /* not equal */

    case TAG_PRIMARY_BOXED:
/*** 以下、略 ***/

is_sameマクロは、(HALFWORDエミュレーションがOFFの場合は)単にアドレスの比較のみを行っている。

erl_term.h

#define is_same(A,A_BASE,B,B_BASE) ((A)==(B))