$10k bounty - make HVML.c 50% faster on Apple M3

HVML_submit.c

// Post: https://x.com/VictorTaelin/status/1854326873590792276
// Note: The atomics must be kept.

// Main changes:
//  - supports linux by using mmap
//  - computed gotos / threaded interpreter
//  - optional support for atomic 128bit load/stores when ENABLE_128B is defined
//
// - some smaller changes to reduce pointer indirections
//
// compile with: clang HVML_submit.c -O3 -DENABLE_128B=1 -march=native -mcpu=apple-m3 -o HVML_submit.c

#include <stdint.h>
#include <stdatomic.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>


#include <sys/mman.h>
#include <unistd.h>
#include <stddef.h>
#include <errno.h>

//#define ENABLE_128B 1

typedef uint8_t  Tag;
typedef uint32_t Lab;
typedef uint32_t Loc;
typedef uint64_t Term;
typedef uint64_t u64;

typedef _Atomic(u64) a64;
typedef _Atomic(Term) ATerm;

typedef _Atomic(__int128) ATerm2;
typedef union Term2 {
  __int128 t2;
  struct {
    Term t1, t2;
  } t;
} Term2;

#define INLINE __attribute__((always_inline)) inline

// Runtime Types
// -------------


typedef struct {
  a64 itr; // interaction count
  a64 end; // memory alloc index
  
  ATerm* restrict mem; // global memory
  Term* restrict  stk; // evaluation stack
  
  a64 ini; // memory first index (not used)
} Heap;

// Constants
// ---------

#define DP0 0x00
#define DP1 0x01
#define VAR 0x02
#define APP 0x03
#define ERA 0x04
#define LAM 0x05
#define SUP 0x06
#define SUB 0x07

#define VOID 0x00000000000000

// Initialization
// --------------

// this makes is also support linux
void* myalloc(size_t s) {
  size_t page_size = sysconf(_SC_PAGESIZE);
  size_t rounded_size = (s + page_size - 1) & ~(page_size - 1);
  void* ptr = mmap(NULL, rounded_size,
                  PROT_READ | PROT_WRITE,
                  MAP_ANONYMOUS | MAP_PRIVATE | MAP_NORESERVE,
                  -1, 0);

  if (ptr == MAP_FAILED) {
    exit(-1); // error handling
  }
  return ptr;
}

Heap* restrict new_heap() {
  Heap* restrict heap = malloc(sizeof(Heap));
  heap->mem = myalloc((1ULL << 32) * sizeof(ATerm));
  heap->stk = myalloc((1ULL << 32) * sizeof(Term));
  atomic_store_explicit(&heap->ini, 0, memory_order_relaxed);
  atomic_store_explicit(&heap->end, 1, memory_order_relaxed);
  atomic_store_explicit(&heap->itr, 0, memory_order_relaxed);
  return heap;
}

INLINE Term new_term(Tag tag, Lab lab, Loc loc) {
  Term tag_enc = tag;
  Term lab_enc = ((Term)lab) << 8;
  Term loc_enc = ((Term)loc) << 32;
  return tag_enc | lab_enc | loc_enc;
}

INLINE  Tag get_tag(Term x) {
  return x & 0xFF;
}

INLINE Lab get_lab(Term x) {
  return (x >> 8) & 0xFFFFFF;
}

INLINE  Loc get_loc(Term x) {
  return (x >> 32) & 0xFFFFFFFF;
}

INLINE Loc get_key(Term term) {
  switch (get_tag(term)) {
    case VAR: return get_loc(term) + 0;
    case DP0: return get_loc(term) + 0;
    case DP1: return get_loc(term) + 1;
    default:  return 0;
  }
}

INLINE Loc get_ini(Heap* restrict heap) {
  return atomic_load_explicit(&heap->ini, memory_order_relaxed);
}

INLINE Loc get_end(Heap* restrict heap) {
  return atomic_load_explicit(&heap->end, memory_order_relaxed);
}

INLINE Loc get_itr(Heap* restrict heap) {
  return atomic_load_explicit(&heap->itr, memory_order_relaxed);
}

INLINE void set_ini(Heap* restrict heap, Loc value) {
  atomic_store_explicit(&heap->ini, value, memory_order_relaxed);
}

INLINE void set_end(Heap* restrict heap, Loc value) {
  atomic_store_explicit(&heap->end, value, memory_order_relaxed);
}

INLINE void set_itr(Heap* restrict heap, Loc value) {
  atomic_store_explicit(&heap->itr, value, memory_order_relaxed);
}

// Memory
// ------

INLINE Term swap(Heap* restrict heap, Loc loc, Term term) {
  return atomic_exchange_explicit(&heap->mem[loc], term, memory_order_relaxed);
}

INLINE Term got(Heap* restrict heap, Loc loc) {
  return atomic_load_explicit(&heap->mem[loc], memory_order_relaxed);
}

INLINE Term2 got2(Heap* restrict heap, Loc loc) {
  Term2 ret;
#if ENABLE_128B
  ret.t2 = atomic_load_explicit((ATerm2*)&heap->mem[loc], memory_order_relaxed);
#else
  ret.t.t1 = atomic_load_explicit(&heap->mem[loc], memory_order_relaxed);
  ret.t.t2 = atomic_load_explicit(&heap->mem[loc+1], memory_order_relaxed);
#endif
  return ret;
}


INLINE void set(Heap* restrict heap, Loc loc, Term term) {
  atomic_store_explicit(&heap->mem[loc], term, memory_order_relaxed);
}

INLINE void set2(Heap* restrict heap, Loc loc, Term term1, Term term2) {
#if ENABLE_128B
  Term2 tmp;
  tmp.t.t1 = term1;
  tmp.t.t2 = term2;
  atomic_store_explicit((ATerm2*)&heap->mem[loc], tmp.t2, memory_order_relaxed);
#else
  set(heap, loc, term1);
  set(heap, loc+1, term2);
#endif
}

INLINE Term take(Heap* restrict heap, Loc loc) {
  return swap(heap, loc, VOID);
}

// Allocation
// ----------

INLINE Loc alloc_node(Heap* restrict heap, Loc arity) {
  return atomic_fetch_add_explicit(&heap->end, arity, memory_order_relaxed);
}

INLINE Loc inc_itr(Heap* restrict heap) {
  return atomic_fetch_add_explicit(&heap->itr, 1, memory_order_relaxed);
}

// Stringification
// ---------------

void print_tag(Tag tag) {
  switch (tag) {
    case SUB: printf("SUB"); break;
    case VAR: printf("VAR"); break;
    case DP0: printf("DP0"); break;
    case DP1: printf("DP1"); break;
    case APP: printf("APP"); break;
    case ERA: printf("ERA"); break;
    case LAM: printf("LAM"); break;
    case SUP: printf("SUP"); break;
    default : printf("???"); break;
  }
}

void print_term(Term term) {
  printf("new_term(");
  print_tag(get_tag(term));
  printf(",0x%06x,0x%09x)", get_lab(term), get_loc(term));
}

void print_heap(Heap* restrict heap) {
  Loc end = get_end(heap);
  for (Loc i = 0; i < end; i++) {
    Term term = got(heap, i);
    if (term != 0) {
      printf("set(heap, 0x%09x, ", i);
      print_term(term);
      printf(");\n");
    }
  }
}

// Evaluation
// ----------

// (* a)
// ----- APP_ERA
// *
INLINE Term reduce_app_era(Heap* restrict heap, Term app, Term era) {
  inc_itr(heap);
  return era;
}

// (λx(body) a)
// ------------ APP_LAM
// x <- a
// body
INLINE Term reduce_app_lam(Heap* restrict heap, Term app, Term lam) {
  inc_itr(heap);
  Loc app_loc = get_loc(app);
  Loc lam_loc = get_loc(lam);
  Term arg    = got(heap, app_loc + 1);
  Term bod    = got(heap, lam_loc + 1);
  set(heap, lam_loc + 0, arg);
  return bod;
}

// ({a b} c)
// --------------- APP_SUP
// & {x0 x1} = c
// {(a x0) (b x1)}
INLINE Term reduce_app_sup(Heap* restrict heap, Term app, Term sup) {
  inc_itr(heap);
  Loc app_loc = get_loc(app);
  Loc sup_loc = get_loc(sup);
  Term arg    = got(heap, app_loc + 1);
  //Term tm0    = got(heap, sup_loc + 0);
  //Term tm1    = got(heap, sup_loc + 1);
  Term2 tm = got2(heap, sup_loc);
  Term tm0 = tm.t.t1;
  Term tm1 = tm.t.t2;
  /*
  Loc du0     = alloc_node(heap, 3);
  Loc su0     = alloc_node(heap, 2);
  Loc ap0     = alloc_node(heap, 2);
  Loc ap1     = alloc_node(heap, 2);
  */
  Loc du0     = alloc_node(heap, 3+2+2+2);
  Loc su0     = du0+3;
  Loc ap0     = su0+2;
  Loc ap1     = ap0+2;

  //set(heap, du0 + 0, new_term(SUB, 0, 0));
  //set(heap, du0 + 1, new_term(SUB, 0, 0));
  set2(heap, du0 + 0, new_term(SUB, 0, 0), new_term(SUB, 0, 0));

  set(heap, du0 + 2, arg);

  //set(heap, ap0 + 0, tm0);
  //set(heap, ap0 + 1, new_term(DP0, 0, du0));
  set2(heap, ap0, tm0, new_term(DP0, 0, du0));

  //set(heap, ap1 + 0, tm1);
  //set(heap, ap1 + 1, new_term(DP1, 0, du0));
  set2(heap, ap1 + 0, tm1, new_term(DP1, 0, du0));

  //set(heap, su0 + 0, new_term(APP, 0, ap0));
  //set(heap, su0 + 1, new_term(APP, 0, ap1));
  set2(heap, su0 + 0, new_term(APP, 0, ap0), new_term(APP, 0, ap1));
  return new_term(SUP, 0, su0);
}

// & {x y} = *
// ----------- DUP_ERA
// x <- *
// y <- *
INLINE Term reduce_dup_era(Heap* restrict heap, Term dup, Term era) {
  inc_itr(heap);
  Loc dup_loc = get_loc(dup);
  Tag dup_num = get_tag(dup) == DP0 ? 0 : 1;
  //set(heap, dup_loc + 0, era);
  //set(heap, dup_loc + 1, era);
  set2(heap, dup_loc, era, era);
  //XX return got(heap, dup_loc + dup_num);
  return era;
}

// & {r s} = λx(f)
// --------------- DUP_LAM
// & {f0 f1} = f
// r <- λx0(f0)
// s <- λx1(f1)
// x <- {x0 x1}
INLINE Term reduce_dup_lam(Heap* restrict heap, Term dup, Term lam) {
  inc_itr(heap);
  Loc dup_loc = get_loc(dup);
  Tag dup_num = get_tag(dup) == DP0 ? 0 : 1;
  Loc lam_loc = get_loc(lam);
  Term bod    = got(heap, lam_loc + 1);
  /*
  Loc du0     = alloc_node(heap, 3);
  Loc lm0     = alloc_node(heap, 2);
  Loc lm1     = alloc_node(heap, 2);
  Loc su0     = alloc_node(heap, 2);
  */
  Loc du0     = alloc_node(heap, 3+2+2+2);
  Loc lm0     = du0+3;
  Loc lm1     = lm0+2;
  Loc su0     = lm1+2; 

  //set(heap, du0 + 0, new_term(SUB, 0, 0));
  //set(heap, du0 + 1, new_term(SUB, 0, 0));
  set2(heap, du0, new_term(SUB, 0, 0), new_term(SUB, 0, 0));
  set(heap, du0 + 2, bod);

  //set(heap, lm0 + 0, new_term(SUB, 0, 0));
  //set(heap, lm0 + 1, new_term(DP0, 0, du0));
  set2(heap, lm0, new_term(SUB, 0, 0), new_term(DP0, 0, du0));

  //set(heap, lm1 + 0, new_term(SUB, 0, 0));
  //set(heap, lm1 + 1, new_term(DP1, 0, du0));
  set2(heap, lm1, new_term(SUB, 0, 0), new_term(DP1, 0, du0));

  //set(heap, su0 + 0, new_term(VAR, 0, lm0));
  //set(heap, su0 + 1, new_term(VAR, 0, lm1));
  set2(heap, su0, new_term(VAR, 0, lm0), new_term(VAR, 0, lm1));

  //set(heap, dup_loc + 0, new_term(LAM, 0, lm0));
  //set(heap, dup_loc + 1, new_term(LAM, 0, lm1));
  set2(heap, dup_loc, new_term(LAM, 0, lm0), new_term(LAM, 0, lm1));

  set(heap, lam_loc + 0, new_term(SUP, 0, su0));
  //XX return got(heap, dup_loc + dup_num);
  return get_tag(dup) == DP0 ? new_term(LAM, 0, lm0) : new_term(LAM, 0, lm1);
}

// & {x y} = {a b}
// --------------- DUP_SUP
// x <- a
// y <- b
INLINE Term reduce_dup_sup(Heap* restrict heap, Term dup, Term sup) {
  inc_itr(heap);
  Loc dup_loc = get_loc(dup);
  Tag dup_num = get_tag(dup) == DP0 ? 0 : 1;
  Loc sup_loc = get_loc(sup);
  //Term tm0    = got(heap, sup_loc + 0);
  //Term tm1    = got(heap, sup_loc + 1);
  Term2 tm = got2(heap, sup_loc);
  Term tm0 = tm.t.t1;
  Term tm1 = tm.t.t2;

  //set(heap, dup_loc + 0, tm0);
  //set(heap, dup_loc + 1, tm1);
  set2(heap, dup_loc, tm0, tm1);
  //XX return got(heap, dup_loc + dup_num);
  return get_tag(dup) == DP0 ? tm0 : tm1;
}



//long stats[10];
//#define DISPATCH_LOAD()  {tag = get_tag(next); lab = get_lab(next); loc = get_loc(next); ++stats[tag]; if (++ccc < 0xFFF) print_tag(tag); printf("\n"); }
#define DISPATCH_LOAD()  { tag = get_tag(next); lab = get_lab(next); loc = get_loc(next); }
#define DISPATCH_JMP() { goto *program[tag]; }
#define DISPATCH() { DISPATCH_LOAD(); DISPATCH_JMP(); }

Term reduce(Heap* restrict heap, Term term) {
  Term* restrict path = heap->stk;
  Loc   spos = 0;
  Term  next = term;

  static const void* program[] = { 
    &&TAG_DP0,
    &&TAG_DP1,
    &&TAG_VAR,
    &&TAG_APP,
    &&TAG_ERA,
    &&TAG_LAM,
    &&TAG_SUP,
    &&TAG_SUB
  };

  Tag tag;
  Lab lab;
  Loc loc;
  
  DISPATCH()

  TAG_APP: {
    do {
      path[spos++] = next;
      next = got(heap, loc + 0);
      DISPATCH_LOAD();
    } while (tag == APP);
    DISPATCH_JMP();
  }
  TAG_DP0:
  TAG_DP1: {
    Loc key = get_key(next);
    Term sub = got(heap, key);
    if (get_tag(sub) == SUB) {
      path[spos++] = next;
      next = got(heap, loc + 2);
      DISPATCH()
    } else {
      next = sub;
      DISPATCH()
    }
  }
  TAG_VAR: {
    Loc key = get_key(next);
    Term sub = got(heap, key);
    if (get_tag(sub) == SUB) {
      goto TAG_break;
    } else {
      next = sub;
      DISPATCH()
    }
  }


  TAG_ERA:
  TAG_LAM:
  TAG_SUP:
  TAG_SUB: {
    if (spos == 0) {
      goto TAG_break;
    } else {
      Term prev = path[--spos];
      Tag ptag = get_tag(prev);
      Lab plab = get_lab(prev);
      Loc ploc = get_loc(prev);
      switch (ptag) {
        case APP: {
          switch (tag) {
            case ERA: next = reduce_app_era(heap, prev, next); DISPATCH();
            case LAM: next = reduce_app_lam(heap, prev, next); DISPATCH();
            case SUP: next = reduce_app_sup(heap, prev, next); DISPATCH();
            default: break;
          }
          break;
        }
        case DP0:
        case DP1: {
          switch (tag) {
            case ERA: next = reduce_dup_era(heap, prev, next); DISPATCH();
            case LAM: next = reduce_dup_lam(heap, prev, next); DISPATCH();
            case SUP: next = reduce_dup_sup(heap, prev, next); DISPATCH();
            default: break;
          }
          break;
        }
        default: break;
      }
      goto TAG_break;
    }
  }

TAG_break:
  if (spos == 0) {
    return next;
  } else {
    Term host = path[--spos];
    Tag htag = get_tag(host);
    Lab hlab = get_lab(host);
    Loc hloc = get_loc(host);
    switch (htag) {
      case APP: {
        set(heap, hloc + 0, next);
        DISPATCH();
      }
      case DP0:
      case DP1: {
        set(heap, hloc + 2, next);
        DISPATCH();
      }
      default: {
        return 0;
      }
    }
  }
  return 0;
}

Term normal(Heap* restrict heap, Term term, long n) {
  Term wnf = reduce(heap, term);
  Tag tag = get_tag(wnf);
  Lab lab = get_lab(wnf);
  Loc loc = get_loc(wnf);
  //print_tag(tag);
  //printf(" normal %x %x %ld\n", loc, tag, n);
  
  switch (tag) {
    case APP: {
      Term fun;
      Term arg;
      fun = got(heap, loc + 0);
      fun = normal(heap, fun, n+1);
      arg = got(heap, loc + 1);
      arg = normal(heap, arg,  n+1);

      //set(heap, loc + 0, fun);
      //set(heap, loc + 1, arg);
      set2(heap, loc + 0, fun, arg);
      return wnf;
    }
    case LAM: {
      Term bod;
      bod = got(heap, loc + 1);
      bod = normal(heap, bod, n+1);
      set(heap, loc + 1, bod);
      return wnf;
    }
    case SUP: {
      Term tm0;
      Term tm1;
      tm0 = got(heap, loc + 0);
      tm0 = normal(heap, tm0,  n+1);
      tm1 = got(heap, loc + 1);
      tm1 = normal(heap, tm1,  n+1);
      //set(heap, loc + 0, tm0);
      //set(heap, loc + 1, tm1);
      set2(heap, loc, tm0, tm1);
      return wnf;
    }
    case DP0: {
      Term val;
      val = got(heap, loc + 2);
      val = normal(heap, val,  n+1);
      set(heap, loc + 2, val);
      return wnf;
    }
    case DP1: {
      Term val;
      val = got(heap, loc + 2);
      val = normal(heap, val,  n+1);
      set(heap, loc + 2, val);
      return wnf;
    }
    default:
      return wnf;
  }
}

// Main
// ----

static void inject_P24(Heap* restrict heap) {
  set_ini(heap, 0x000000000);
  set_end(heap, 0x0000000f1);
  set_itr(heap, 0x000000000);
  set(heap, 0x000000000, new_term(APP,0x000000,0x000000001));
  set(heap, 0x000000001, new_term(APP,0x000000,0x000000003));
  set(heap, 0x000000002, new_term(LAM,0x000000,0x0000000ed));
  set(heap, 0x000000003, new_term(LAM,0x000000,0x000000005));
  set(heap, 0x000000004, new_term(LAM,0x000000,0x0000000df));
  set(heap, 0x000000005, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000006, new_term(LAM,0x000000,0x0000000d9));
  set(heap, 0x000000007, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000008, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000009, new_term(VAR,0x000000,0x000000005));
  set(heap, 0x00000000a, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000000b, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000000c, new_term(LAM,0x000000,0x00000000d));
  set(heap, 0x00000000d, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000000e, new_term(APP,0x000000,0x00000000f));
  set(heap, 0x00000000f, new_term(DP0,0x000000,0x000000007));
  set(heap, 0x000000010, new_term(APP,0x000000,0x000000011));
  set(heap, 0x000000011, new_term(DP1,0x000000,0x000000007));
  set(heap, 0x000000012, new_term(VAR,0x000000,0x00000000d));
  set(heap, 0x000000013, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000014, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000015, new_term(LAM,0x000000,0x000000016));
  set(heap, 0x000000016, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000017, new_term(APP,0x000000,0x000000018));
  set(heap, 0x000000018, new_term(DP0,0x000000,0x00000000a));
  set(heap, 0x000000019, new_term(APP,0x000000,0x00000001a));
  set(heap, 0x00000001a, new_term(DP1,0x000000,0x00000000a));
  set(heap, 0x00000001b, new_term(VAR,0x000000,0x000000016));
  set(heap, 0x00000001c, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000001d, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000001e, new_term(LAM,0x000000,0x00000001f));
  set(heap, 0x00000001f, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000020, new_term(APP,0x000000,0x000000021));
  set(heap, 0x000000021, new_term(DP0,0x000000,0x000000013));
  set(heap, 0x000000022, new_term(APP,0x000000,0x000000023));
  set(heap, 0x000000023, new_term(DP1,0x000000,0x000000013));
  set(heap, 0x000000024, new_term(VAR,0x000000,0x00000001f));
  set(heap, 0x000000025, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000026, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000027, new_term(LAM,0x000000,0x000000028));
  set(heap, 0x000000028, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000029, new_term(APP,0x000000,0x00000002a));
  set(heap, 0x00000002a, new_term(DP0,0x000000,0x00000001c));
  set(heap, 0x00000002b, new_term(APP,0x000000,0x00000002c));
  set(heap, 0x00000002c, new_term(DP1,0x000000,0x00000001c));
  set(heap, 0x00000002d, new_term(VAR,0x000000,0x000000028));
  set(heap, 0x00000002e, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000002f, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000030, new_term(LAM,0x000000,0x000000031));
  set(heap, 0x000000031, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000032, new_term(APP,0x000000,0x000000033));
  set(heap, 0x000000033, new_term(DP0,0x000000,0x000000025));
  set(heap, 0x000000034, new_term(APP,0x000000,0x000000035));
  set(heap, 0x000000035, new_term(DP1,0x000000,0x000000025));
  set(heap, 0x000000036, new_term(VAR,0x000000,0x000000031));
  set(heap, 0x000000037, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000038, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000039, new_term(LAM,0x000000,0x00000003a));
  set(heap, 0x00000003a, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000003b, new_term(APP,0x000000,0x00000003c));
  set(heap, 0x00000003c, new_term(DP0,0x000000,0x00000002e));
  set(heap, 0x00000003d, new_term(APP,0x000000,0x00000003e));
  set(heap, 0x00000003e, new_term(DP1,0x000000,0x00000002e));
  set(heap, 0x00000003f, new_term(VAR,0x000000,0x00000003a));
  set(heap, 0x000000040, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000041, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000042, new_term(LAM,0x000000,0x000000043));
  set(heap, 0x000000043, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000044, new_term(APP,0x000000,0x000000045));
  set(heap, 0x000000045, new_term(DP0,0x000000,0x000000037));
  set(heap, 0x000000046, new_term(APP,0x000000,0x000000047));
  set(heap, 0x000000047, new_term(DP1,0x000000,0x000000037));
  set(heap, 0x000000048, new_term(VAR,0x000000,0x000000043));
  set(heap, 0x000000049, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000004a, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000004b, new_term(LAM,0x000000,0x00000004c));
  set(heap, 0x00000004c, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000004d, new_term(APP,0x000000,0x00000004e));
  set(heap, 0x00000004e, new_term(DP0,0x000000,0x000000040));
  set(heap, 0x00000004f, new_term(APP,0x000000,0x000000050));
  set(heap, 0x000000050, new_term(DP1,0x000000,0x000000040));
  set(heap, 0x000000051, new_term(VAR,0x000000,0x00000004c));
  set(heap, 0x000000052, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000053, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000054, new_term(LAM,0x000000,0x000000055));
  set(heap, 0x000000055, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000056, new_term(APP,0x000000,0x000000057));
  set(heap, 0x000000057, new_term(DP0,0x000000,0x000000049));
  set(heap, 0x000000058, new_term(APP,0x000000,0x000000059));
  set(heap, 0x000000059, new_term(DP1,0x000000,0x000000049));
  set(heap, 0x00000005a, new_term(VAR,0x000000,0x000000055));
  set(heap, 0x00000005b, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000005c, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000005d, new_term(LAM,0x000000,0x00000005e));
  set(heap, 0x00000005e, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000005f, new_term(APP,0x000000,0x000000060));
  set(heap, 0x000000060, new_term(DP0,0x000000,0x000000052));
  set(heap, 0x000000061, new_term(APP,0x000000,0x000000062));
  set(heap, 0x000000062, new_term(DP1,0x000000,0x000000052));
  set(heap, 0x000000063, new_term(VAR,0x000000,0x00000005e));
  set(heap, 0x000000064, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000065, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000066, new_term(LAM,0x000000,0x000000067));
  set(heap, 0x000000067, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000068, new_term(APP,0x000000,0x000000069));
  set(heap, 0x000000069, new_term(DP0,0x000000,0x00000005b));
  set(heap, 0x00000006a, new_term(APP,0x000000,0x00000006b));
  set(heap, 0x00000006b, new_term(DP1,0x000000,0x00000005b));
  set(heap, 0x00000006c, new_term(VAR,0x000000,0x000000067));
  set(heap, 0x00000006d, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000006e, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000006f, new_term(LAM,0x000000,0x000000070));
  set(heap, 0x000000070, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000071, new_term(APP,0x000000,0x000000072));
  set(heap, 0x000000072, new_term(DP0,0x000000,0x000000064));
  set(heap, 0x000000073, new_term(APP,0x000000,0x000000074));
  set(heap, 0x000000074, new_term(DP1,0x000000,0x000000064));
  set(heap, 0x000000075, new_term(VAR,0x000000,0x000000070));
  set(heap, 0x000000076, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000077, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000078, new_term(LAM,0x000000,0x000000079));
  set(heap, 0x000000079, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000007a, new_term(APP,0x000000,0x00000007b));
  set(heap, 0x00000007b, new_term(DP0,0x000000,0x00000006d));
  set(heap, 0x00000007c, new_term(APP,0x000000,0x00000007d));
  set(heap, 0x00000007d, new_term(DP1,0x000000,0x00000006d));
  set(heap, 0x00000007e, new_term(VAR,0x000000,0x000000079));
  set(heap, 0x00000007f, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000080, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000081, new_term(LAM,0x000000,0x000000082));
  set(heap, 0x000000082, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000083, new_term(APP,0x000000,0x000000084));
  set(heap, 0x000000084, new_term(DP0,0x000000,0x000000076));
  set(heap, 0x000000085, new_term(APP,0x000000,0x000000086));
  set(heap, 0x000000086, new_term(DP1,0x000000,0x000000076));
  set(heap, 0x000000087, new_term(VAR,0x000000,0x000000082));
  set(heap, 0x000000088, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000089, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000008a, new_term(LAM,0x000000,0x00000008b));
  set(heap, 0x00000008b, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000008c, new_term(APP,0x000000,0x00000008d));
  set(heap, 0x00000008d, new_term(DP0,0x000000,0x00000007f));
  set(heap, 0x00000008e, new_term(APP,0x000000,0x00000008f));
  set(heap, 0x00000008f, new_term(DP1,0x000000,0x00000007f));
  set(heap, 0x000000090, new_term(VAR,0x000000,0x00000008b));
  set(heap, 0x000000091, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000092, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000093, new_term(LAM,0x000000,0x000000094));
  set(heap, 0x000000094, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x000000095, new_term(APP,0x000000,0x000000096));
  set(heap, 0x000000096, new_term(DP0,0x000000,0x000000088));
  set(heap, 0x000000097, new_term(APP,0x000000,0x000000098));
  set(heap, 0x000000098, new_term(DP1,0x000000,0x000000088));
  set(heap, 0x000000099, new_term(VAR,0x000000,0x000000094));
  set(heap, 0x00000009a, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000009b, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000009c, new_term(LAM,0x000000,0x00000009d));
  set(heap, 0x00000009d, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x00000009e, new_term(APP,0x000000,0x00000009f));
  set(heap, 0x00000009f, new_term(DP0,0x000000,0x000000091));
  set(heap, 0x0000000a0, new_term(APP,0x000000,0x0000000a1));
  set(heap, 0x0000000a1, new_term(DP1,0x000000,0x000000091));
  set(heap, 0x0000000a2, new_term(VAR,0x000000,0x00000009d));
  set(heap, 0x0000000a3, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000a4, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000a5, new_term(LAM,0x000000,0x0000000a6));
  set(heap, 0x0000000a6, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000a7, new_term(APP,0x000000,0x0000000a8));
  set(heap, 0x0000000a8, new_term(DP0,0x000000,0x00000009a));
  set(heap, 0x0000000a9, new_term(APP,0x000000,0x0000000aa));
  set(heap, 0x0000000aa, new_term(DP1,0x000000,0x00000009a));
  set(heap, 0x0000000ab, new_term(VAR,0x000000,0x0000000a6));
  set(heap, 0x0000000ac, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000ad, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000ae, new_term(LAM,0x000000,0x0000000af));
  set(heap, 0x0000000af, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000b0, new_term(APP,0x000000,0x0000000b1));
  set(heap, 0x0000000b1, new_term(DP0,0x000000,0x0000000a3));
  set(heap, 0x0000000b2, new_term(APP,0x000000,0x0000000b3));
  set(heap, 0x0000000b3, new_term(DP1,0x000000,0x0000000a3));
  set(heap, 0x0000000b4, new_term(VAR,0x000000,0x0000000af));
  set(heap, 0x0000000b5, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000b6, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000b7, new_term(LAM,0x000000,0x0000000b8));
  set(heap, 0x0000000b8, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000b9, new_term(APP,0x000000,0x0000000ba));
  set(heap, 0x0000000ba, new_term(DP0,0x000000,0x0000000ac));
  set(heap, 0x0000000bb, new_term(APP,0x000000,0x0000000bc));
  set(heap, 0x0000000bc, new_term(DP1,0x000000,0x0000000ac));
  set(heap, 0x0000000bd, new_term(VAR,0x000000,0x0000000b8));
  set(heap, 0x0000000be, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000bf, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000c0, new_term(LAM,0x000000,0x0000000c1));
  set(heap, 0x0000000c1, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000c2, new_term(APP,0x000000,0x0000000c3));
  set(heap, 0x0000000c3, new_term(DP0,0x000000,0x0000000b5));
  set(heap, 0x0000000c4, new_term(APP,0x000000,0x0000000c5));
  set(heap, 0x0000000c5, new_term(DP1,0x000000,0x0000000b5));
  set(heap, 0x0000000c6, new_term(VAR,0x000000,0x0000000c1));
  set(heap, 0x0000000c7, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000c8, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000c9, new_term(LAM,0x000000,0x0000000ca));
  set(heap, 0x0000000ca, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000cb, new_term(APP,0x000000,0x0000000cc));
  set(heap, 0x0000000cc, new_term(DP0,0x000000,0x0000000be));
  set(heap, 0x0000000cd, new_term(APP,0x000000,0x0000000ce));
  set(heap, 0x0000000ce, new_term(DP1,0x000000,0x0000000be));
  set(heap, 0x0000000cf, new_term(VAR,0x000000,0x0000000ca));
  set(heap, 0x0000000d0, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000d1, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000d2, new_term(LAM,0x000000,0x0000000d3));
  set(heap, 0x0000000d3, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000d4, new_term(APP,0x000000,0x0000000d5));
  set(heap, 0x0000000d5, new_term(DP0,0x000000,0x0000000c7));
  set(heap, 0x0000000d6, new_term(APP,0x000000,0x0000000d7));
  set(heap, 0x0000000d7, new_term(DP1,0x000000,0x0000000c7));
  set(heap, 0x0000000d8, new_term(VAR,0x000000,0x0000000d3));
  set(heap, 0x0000000d9, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000da, new_term(APP,0x000000,0x0000000db));
  set(heap, 0x0000000db, new_term(DP0,0x000000,0x0000000d0));
  set(heap, 0x0000000dc, new_term(APP,0x000000,0x0000000dd));
  set(heap, 0x0000000dd, new_term(DP1,0x000000,0x0000000d0));
  set(heap, 0x0000000de, new_term(VAR,0x000000,0x0000000d9));
  set(heap, 0x0000000df, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000e0, new_term(APP,0x000000,0x0000000e1));
  set(heap, 0x0000000e1, new_term(APP,0x000000,0x0000000e3));
  set(heap, 0x0000000e2, new_term(LAM,0x000000,0x0000000e9));
  set(heap, 0x0000000e3, new_term(VAR,0x000000,0x0000000df));
  set(heap, 0x0000000e4, new_term(LAM,0x000000,0x0000000e5));
  set(heap, 0x0000000e5, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000e6, new_term(LAM,0x000000,0x0000000e7));
  set(heap, 0x0000000e7, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000e8, new_term(VAR,0x000000,0x0000000e7));
  set(heap, 0x0000000e9, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000ea, new_term(LAM,0x000000,0x0000000eb));
  set(heap, 0x0000000eb, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000ec, new_term(VAR,0x000000,0x0000000e9));
  set(heap, 0x0000000ed, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000ee, new_term(LAM,0x000000,0x0000000ef));
  set(heap, 0x0000000ef, new_term(SUB,0x000000,0x000000000));
  set(heap, 0x0000000f0, new_term(VAR,0x000000,0x0000000ed));
}

int main() {
  Heap* restrict heap = new_heap();
  inject_P24(heap);

  clock_t start = clock();

  // Normalize and get interaction count
  Term root = got(heap, 0);
  normal(heap, root, 0);
  clock_t end = clock();

  printf("Itrs: %u\n", get_itr(heap));
  double time_spent = (double)(end - start) / CLOCKS_PER_SEC * 1000;
  printf("Size: %u nodes\n", get_end(heap));
  printf("Time: %.2f seconds\n", time_spent / 1000.0);
  printf("MIPS: %.2f\n", (get_itr(heap) / 1000000.0) / (time_spent / 1000.0));

  // TODO call munmap
  //munmap(heap->stk);
  //munmap(heap->mem);

  //free(heap->ini);
  //free(&heap->end);
  //free(heap->itr);
  free(heap);
  return 0;
}