Hashed nametables

7 files changed, 673 insertions, 170 deletions

diff --git a/TODO b/TODO
index eb358bb..931264a 100644
--- a/TODO
+++ b/TODO
@@ -1,4 +1,3 @@
-* hashed nametables
 * make '' applicable to arrays, too, i.e. save input type
 * utf8
 * glob
diff --git a/compiler/elymas.ey b/compiler/elymas.ey
index fd0a3db..42cf217 100755
--- a/compiler/elymas.ey
+++ b/compiler/elymas.ey
@@ -1,6 +1,9 @@
 #!/home/drahflow/elymas/interpreter/elymas
 
 "standard.ey" include
+
+1 ==ASSERTIONS
+
 "elymasGlobal.ey" include
 "elymasTokenize.ey" include
 "elymasLexer.ey" include
diff --git a/compiler/elymasAsm.ey b/compiler/elymasAsm.ey
index ff57627..e792b21 100644
--- a/compiler/elymasAsm.ey
+++ b/compiler/elymasAsm.ey
@@ -6,12 +6,15 @@
 
   6148914691236517205 ==STACKBOTTOMMARKER
   4 ==ERRORMARKER
+  3 ==HASHPOSITIONS # number of positions to probe on collisions
 
   # hex decoding
   {
-    "(.)(.)" regex { } { "not a valid hex-string" die } ? *
-    { { eq }_ [ "0" "1" "2" "3" "4" "5" "6" "7" "8" "9" "A" "B" "C" "D" "E" "F" ] -01 index }
-    -20*10* 16 mul add
+    0 -01 { "(.)(.*)" regex } {
+      { 16 mul }
+      { { eq }_ [ "0" "1" "2" "3" "4" "5" "6" "7" "8" "9" "A" "B" "C" "D" "E" "F" ] -01 index add }
+      -41*20*3
+    } loop
   } "%" defq
 
   "elymasAsmOps.ey" include
diff --git a/compiler/elymasAsmLib.ey b/compiler/elymasAsmLib.ey
index 71763c6..b2a2e59 100644
--- a/compiler/elymasAsmLib.ey
+++ b/compiler/elymasAsmLib.ey
@@ -136,6 +136,7 @@
   } /unboxInteger deff
 
   # internal functions, ABI follows SysV standards
+  # except that r8-r15 are also callee-saved
 
   <
     # dump string to stderr for internal error reporting
@@ -149,24 +150,185 @@
       :retn
     ] /internalDumpErrorString defv
 
-    # compare two strings
-    # rdi -> address of first string
-    # rsi -> address of second string
-    # rax <- 1 if both strings are equal, 0 otherwise
-    [
-      /rax /rax :xorqRegReg
-      :cmpsq # ignore memory length header
-      :cmpsq # ignore hash
-      /rsi /rdx :movqMemReg # load exact length
-      :cmpsq # same exact length
-      /fail :jnzLbl8
-      /rdx /rcx :movqRegReg
-      :repz :cmpsb
-      /fail :jnzLbl8
-      /rax :incqReg
-      @fail
+    # rdi -> string to hash
+    # rax <- hash value
+    # This is (or should be) MurmurHash3_x64_128
+    [[
+      /rbx :pushqReg
+      /r8 :pushqReg
+      /r9 :pushqReg
+      /r10 :pushqReg
+      /r11 :pushqReg
+      /r12 :pushqReg
+      /r13 :pushqReg
+
+      # const uint8_t * data = (const uint8_t*)key;
+      24 /rdi /rsi :leaqMemDisp8Reg
+
+      # uint64_t h1 = seed;
+      /r12 /r12 :xorqRegReg
+      # uint64_t h2 = seed;
+      /r13 /r13 :xorqRegReg
+
+      # const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
+      /r8 :movqImmOOBReg [ %87 %C3 %7B %91 %11 %42 %53 %D5 ] reverse 8 dearray
+      # const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
+      /r9 :movqImmOOBReg [ %4C %F5 %AD %43 %27 %45 %93 %7F ] reverse 8 dearray
+
+      # const int nblocks = len / 16;
+      16 /rdi /rcx :movqMemDisp8Reg
+      16 /rcx :subqImm8Reg
+      /blockLoopFinished :jbLbl8
+
+      # //---------- body
+
+      # const uint64_t * blocks = (const uint64_t *)(data);
+
+      # for(int i = 0; i < nblocks; i++) {
+
+      @blockLoop
+
+      /rsi /rax :movqMemReg # uint64_t k1 = getblock64(blocks,i*2+0);
+      /r8 :mulqReg          # k1 *= c1;
+      31 /rax :rolqImm8Reg  # k1  = ROTL64(k1,31);
+      /r9 :mulqReg          # k1 *= c2;
+
+      /rax /r12 :xorqRegReg # h1 ^= k1;
+      27 /r12 :rolqImm8Reg  # h1 = ROTL64(h1,27);
+      /r13 /r12 :addqRegReg # h1 += h2;
+      %52DCE729 4 /r12 /r12 /r12 :leaqMemIndexScaleDisp32Reg # h1 = h1*5+0x52dce729;
+
+      8 /rsi /rax :movqMemDisp8Reg # uint64_t k2 = getblock64(blocks,i*2+1);
+      /r9 :mulqReg                 # k2 *= c2;
+      33 /rax :rolqImm8Reg         # k2  = ROTL64(k2,33);
+      /r8 :mulqReg                 # k2 *= c1;
+      /rax /r13 :xorqRegReg        # h2 ^= k2;
+
+      31 /r13 :rolqImm8Reg  # h2 = ROTL64(h2,31);
+      /r12 /r13 :addqRegReg # h2 += h1;
+      %38495AB5 4 /r13 /r13 /r13 :leaqMemIndexScaleDisp32Reg #   h2 = h2*5+0x38495ab5;
+
+      16 /rsi :addqImm8Reg
+      16 /rcx :subqImm8Reg
+      /blockLoop :jaeLbl8
+      # }
+
+      @blockLoopFinished
+      16 /rcx :addqImm8Reg
+      /finalize :jzLbl8
+
+      # //---------- tail
+
+      /rcx /rbp :movqRegReg
+
+      # const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
+
+      # switch(len & 15)
+      # {
+      # case  8: k1 ^= ((uint64_t)tail[ 7]) << 56;
+      # case  7: k1 ^= ((uint64_t)tail[ 6]) << 48;
+      # case  6: k1 ^= ((uint64_t)tail[ 5]) << 40;
+      # case  5: k1 ^= ((uint64_t)tail[ 4]) << 32;
+      # case  4: k1 ^= ((uint64_t)tail[ 3]) << 24;
+      # case  3: k1 ^= ((uint64_t)tail[ 2]) << 16;
+      # case  2: k1 ^= ((uint64_t)tail[ 1]) << 8;
+      # case  1: k1 ^= ((uint64_t)tail[ 0]) << 0;
+      1 /rax :movqImmReg
+      2 /rcx :shlqImm8Reg
+      /rax :shlqClReg
+      /rax :shlqClReg # support 64bit shift
+      /rax :decqReg # rax == bitmask for selection
+      /rsi /rax :andqMemReg
+
+      /r8 :mulqReg # k1 *= c1;
+      31 /rax :rolqImm8Reg # k1  = ROTL64(k1,31);
+      /r9 :mulqReg # k1 *= c2;
+      /rax /r12 :xorqRegReg # h1 ^= k1;
+
+      8 /rbp :subqImm8Reg
+      /finalize :jbeLbl8
+      8 /rsi :addqImm8Reg
+
+      # case 15: k2 ^= ((uint64_t)tail[14]) << 48;
+      # case 14: k2 ^= ((uint64_t)tail[13]) << 40;
+      # case 13: k2 ^= ((uint64_t)tail[12]) << 32;
+      # case 12: k2 ^= ((uint64_t)tail[11]) << 24;
+      # case 11: k2 ^= ((uint64_t)tail[10]) << 16;
+      # case 10: k2 ^= ((uint64_t)tail[ 9]) << 8;
+      # case  9: k2 ^= ((uint64_t)tail[ 8]) << 0;
+      /rbp /rcx :movqRegReg
+      1 /rax :movqImmReg
+      3 /rcx :shlqImm8Reg
+      /rax :shlqImm8Reg
+      /rax :decqReg # rax == bitmask for selection
+      /rsi /rax :andqMemReg
+
+      /r9 :mulqReg # k2 *= c2;
+      33 /rax :rolqImm8Reg         # k2  = ROTL64(k2,33);
+      /r8 :mulqReg # k2 *= c1;
+      /rax /r13 :xorqRegReg # h2 ^= k2;
+
+      # };
+
+      # //---------- finalization
+      @finalize
+
+      16 /rdi /r12 :xorqMemDisp8Reg # h1 ^= len;
+      16 /rdi /r13 :xorqMemDisp8Reg # h2 ^= len;
+
+      /r13 /r12 :addqRegReg # h1 += h2;
+      /r12 /r13 :addqRegReg # h2 += h1;
+
+      %85EBCA6B /r8 :movqImmReg
+      %C2B2AE35 /r9 :movqImmReg
+      # h1 = fmix64(h1);
+      /r12 /rax :movqRegReg
+      16 /r12 :shrqImm8Reg
+      /r12 /rax :xorqRegReg
+      #   h ^= h >> 16;
+      /r8 :mulqReg # h *= 0x85ebca6b;
+      /rax /r12 :movqRegReg
+      13 /r12 :shrqImm8Reg
+      /r12 /rax :xorqRegReg
+      # h ^= h >> 13;
+      /r9 :mulqReg # h *= 0xc2b2ae35;
+      /rax /r12 :movqRegReg
+      16 /r12 :shrqImm8Reg
+      /rax /r12 :xorqRegReg
+      # h ^= h >> 16;
+
+      # h2 = fmix64(h2);
+      /r13 /rax :movqRegReg
+      16 /r13 :shrqImm8Reg
+      /r13 /rax :xorqRegReg
+      #   h ^= h >> 16;
+      /r8 :mulqReg # h *= 0x85ebca6b;
+      /rax /r13 :movqRegReg
+      13 /r13 :shrqImm8Reg
+      /r13 /rax :xorqRegReg
+      # h ^= h >> 13;
+      /r9 :mulqReg # h *= 0xc2b2ae35;
+      /rax /r13 :movqRegReg
+      16 /r13 :shrqImm8Reg
+      /rax /r13 :xorqRegReg
+      # h ^= h >> 16;
+
+      /r13 /r12 :addqRegReg # h1 += h2;
+      /r12 /r13 :addqRegReg # h2 += h1;
+
+      # ((uint64_t*)out)[0] = h1;
+      /r12 /rax :movqRegReg
+      # ((uint64_t*)out)[1] = h2;
+
+      /r13 :popqReg
+      /r12 :popqReg
+      /r11 :popqReg
+      /r10 :popqReg
+      /r9 :popqReg
+      /r8 :popqReg
+      /rbx :popqReg
       :retn
-    ] /internalStringEquals defv
+    ]] /internalHashString defv
   > { defv }' allocateOffsetStruct
 
   { ==str
@@ -540,20 +702,24 @@
       "unknown object type during mark phase" outputError
       :ud2
       
+      0 /rax :movqImmReg # dead code for disambiguation in debugging
       @markInteger
       # "integer marked\n" outputError
       :retn
 
+      1 /rax :movqImmReg # dead code for disambiguation in debugging
       @markString
       # internalDumpErrorString /rax :movqImmReg
       # /rax :callqReg
       # " string marked\n" outputError
       :retn
 
+      2 /rax :movqImmReg # dead code for disambiguation in debugging
       @markFloat
       # "float marked\n" outputError
       :retn
 
+      4 /rax :movqImmReg # dead code for disambiguation in debugging
       @markExtensionArea
       # /rdi :pushqReg
       # "extension area marked\n" outputError
@@ -573,6 +739,7 @@
       /rcx :popqReg
       :retn
 
+      5 /rax :movqImmReg # dead code for disambiguation in debugging
       @markFunction
       # /rdi :pushqReg
       # "function marked\n" outputError
@@ -592,6 +759,7 @@
       /rdi /rdi :movqMemReg
       /markObject :jmpLbl32
 
+      6 /rax :movqImmReg # dead code for disambiguation in debugging
       @markFunctionCode
       # /rdi :pushqReg
       # "function code marked\n" outputError
@@ -636,6 +804,7 @@
       16 /rdi :subqImm8Reg
       /markObject :jmpLbl32
 
+      7 /rax :movqImmReg # dead code for disambiguation in debugging
       @markArray
       # /rdi :pushqReg
       # "array marked\n" outputError
@@ -657,6 +826,7 @@
       /rcx :popqReg
       :retn
 
+      8 /rax :movqImmReg # dead code for disambiguation in debugging
       @markFunctionType
       # /rdi :pushqReg
       # "function type marked\n" outputError
@@ -676,6 +846,7 @@
       /rcx :popqReg
       :retn
 
+      9 /rax :movqImmReg # dead code for disambiguation in debugging
       @markScope
       # /rdi :pushqReg
       # "scope marked\n" outputError
@@ -695,6 +866,7 @@
       /rcx :popqReg
       :retn
 
+      10 /rax :movqImmReg # dead code for disambiguation in debugging
       @markNameTable
       # /rdi :pushqReg
       # "name table marked\n" outputError
@@ -702,7 +874,7 @@
 
       /rcx :pushqReg
       /rsi :pushqReg
-      8 /rdi /ecx :movlMemDisp8Reg
+      /rdi /ecx :movlMemReg
       /rdi /rsi :movqRegReg
       16 /rcx :subqImm8Reg
       /markNameTableEmpty :jzLbl8
@@ -716,6 +888,7 @@
       /rcx :popqReg
       :retn
 
+      11 /rax :movqImmReg # dead code for disambiguation in debugging
       @markStack
       # /rdi :pushqReg
       # "stack marked\n" outputError
@@ -742,6 +915,7 @@
       /rsi :popqReg
       :retn
 
+      12 /rax :movqImmReg # dead code for disambiguation in debugging
       @markCoroutine
       # /rdi :pushqReg
       # "coroutine marked\n" outputError
@@ -823,6 +997,62 @@
   > { defv }' allocateOffsetStruct
 
   <
+    # rdi -> first string
+    # rsi -> second string
+    # rax <- 1 if both strings are equal, 0 otherwise
+    [[
+      # compare lengths
+      16 /rdi /rax :movqMemDisp8Reg
+      16 /rsi /rax :cmpqMemDisp8Reg
+      /different :jnzLbl8
+
+      # compute hashes
+      0 8 /rdi :cmpqImm8MemDisp8
+      /firstStringHashed :jnzLbl8
+      /rdi :pushqReg
+      /rsi :pushqReg
+      internalHashString /rax :movqImmReg
+      /rax :callqReg
+      /rsi :popqReg
+      /rdi :popqReg
+
+      @firstStringHashed
+
+      0 8 /rsi :cmpqImm8MemDisp8
+      /secondStringHashed :jnzLbl8
+      /rdi :pushqReg
+      /rsi :pushqReg
+      /rsi /rdi :movqRegReg
+      internalHashString /rax :movqImmReg
+      /rax :callqReg
+      /rsi :popqReg
+      /rdi :popqReg
+
+      @secondStringHashed
+
+      # compare hashes
+      8 /rdi /rax :movqMemDisp8Reg
+      8 /rsi /rax :cmpqMemDisp8Reg
+      /different :jnzLbl8
+
+      # compare contents
+      16 /rdi /rcx :movqMemDisp8Reg
+      24 /rdi /rdi :leaqMemDisp8Reg
+      24 /rsi /rsi :leaqMemDisp8Reg
+
+      :repz :cmpsb
+      /different :jneLbl8
+
+      1 /rax :movqImmReg
+      :retn
+
+      @different
+      /rax /rax :xorqRegReg
+      :retn
+    ]] /internalCompareString defv
+  > { defv }' allocateOffsetStruct
+
+  <
     # allocate a chunk of memory and zero it
     # rdi -> size of chunk in bytes
     # rax <- address of allocated chunk
@@ -883,31 +1113,69 @@
       @isScope
       # ENDCHECK
 
+      8 /rsi /rcx :movqMemDisp8Reg
+      /rcx /rcx :testqRegReg
+      /hashComputed :jnzLbl8
+
+      /rsi /rdi :movqRegReg
+      internalHashString /rax :movqImmReg
+      /rax :callqReg
+      /rax /rcx :movqRegReg
+
+      0 /rsp /rsi :movqMemDisp8Reg
+      /rax 8 /rsi :movqRegMemDisp8 # cache hash value in string
+      8 /rsp /rdi :movqMemDisp8Reg
+
+      @hashComputed
+
       8 /rdi /rbp :movqMemDisp8Reg # load name table
       /rbp /rbp :testqRegReg
-      /end :jzLbl8 # no name table present - empty scope
-      
-      16 /rbp /rdx :leaqMemDisp8Reg # rdx will iterate over entries
-      8 /rbp /rbp :addqMemDisp8Reg # compute name table effective end
-      /rsi /rax :movqRegReg
-
-      /rdx /rbp :cmpqRegReg
-      /end :jbeLbl8
-
-      @loop
-      /rdx /rdi :movqMemReg
-      16 /rax /rcx :movqMemDisp8Reg # load exact length
-      16 /rdi /rdi :leaqMemDisp8Reg
-      16 /rax /rsi :leaqMemDisp8Reg
-      :cmpsq # same exact length
-      /fail :jnzLbl8
-      :repz :cmpsb
-      /found :jzLbl8
-
-      @fail
-      16 /rdx :addqImm8Reg
-      /rdx /rbp :cmpqRegReg
-      /loop :jaLbl8
+      /end :jzLbl32 # no name table present - empty scope
+
+      <
+        {
+          # rcx == hash value of key to resolve
+          # rbp == nametable to resolve in
+          # 0 /rsp == key to find
+
+          /ecx /eax :movlRegReg
+          0 /rbp /esi :movlMemDisp8Reg # load table length
+          16 /rsi :subqImm8Reg # substract header length
+          4 /rsi :shrqImm8Reg # divide by slot length
+          /rdx /rdx :xorqRegReg
+          /rsi :divqReg
+
+          # rdx == remainder, i.e. slot index
+          4 /rdx :shlqImm8Reg # multiply by slot length
+          16 1 /rbp /rdx /rax :leaqMemIndexScaleDisp8Reg # load key from bucket
+          0 /rax :cmpqImm8Mem
+          /end :jzLbl32 # empty slot found, key is not present
+
+          0 /rsp /rdi :movqMemDisp8Reg
+          /rax /rsi :movqMemReg
+          /rax :pushqReg
+          /rcx :pushqReg
+          /rbp :pushqReg
+          internalCompareString /rax :movqImmReg
+          /rax :callqReg
+          /rbp :popqReg
+          /rcx :popqReg
+          /rax /rax :testqRegReg
+          /found :jnzLbl32
+
+          /rax :popqReg
+        } /trySlot deff
+
+        :HASHPOSITIONS 1 sub {
+          trySlot
+
+          /rcx /rax :movqRegReg
+          32 /rax :shrqImm8Reg
+          /rax /rcx :addqRegReg # derive a new hash value
+        } rep
+
+        trySlot
+      > --
 
       @end
       # not found at all, retry with parent
@@ -922,7 +1190,7 @@
       /rax :pushqReg
       /rdi :pushqReg
       /rsi :pushqReg
-      /retryWithParent :jnzLbl8
+      /retryWithParent :jnzLbl32
 
       @failed
       /rsi :popqReg
@@ -933,16 +1201,16 @@
       :retn
 
       @found
+      /rdx :popqReg # rdx == hash bucket where we found the key
       /rsi :popqReg # rsi == name to resolve
       /rdi :popqReg # rdi == scope we are resolving in
-      # top of stack -> number of parent pointers followed
 
-      8 /rdx /rax :movqMemDisp8Reg # load default activation
-      8 /rdi /rdx :subqMemDisp8Reg # substract name table start
-      16 /rdx :subqImm8Reg # substract name table header size
-      /rdx :shrq1Reg # divide by 2 to get offset within scope
+      # 0 /rsp -> number of parent pointers followed
+
+      8 /rdx /eax :movlMemDisp8Reg # load default activation
+      12 /rdx /ecx :movlMemDisp8Reg # load index in scope
+      3 /rcx :shlqImm8Reg
 
-      /rdx /rcx :movqRegReg
       # rcx == entry index * 8 in scope
       # rax == entry default activation
       /rcx /rsi :movqRegReg # save into target register for return value
@@ -1087,6 +1355,110 @@
       :retn
     ] /internalAllocateScope defv
 
+    # allocate nametable
+    # rdi -> expected number of entries
+    # rax <- address of nametable on the heap
+    [
+      4 /rdi :shlqImm8Reg
+      32 /rdi :addqImm8Reg
+      internalAllocateAndZero /rax :movqImmReg
+      /rax :callqReg
+
+      # set type
+      %A0 7 /rax :orbImmMemDisp8
+      :retn
+    ] /internalAllocateNametable defv
+
+    # insert string into nametable
+    # rdi -> string to insert
+    # rsi -> nametable to insert within
+    # rax <- address of 16 byte hash slot, or zero if no free bucket was found
+    # rdx <- zero if new entry, one if same key was already present
+    [[
+      /rdi :pushqReg
+      /rsi :pushqReg
+
+      8 /rdi /rcx :movqMemDisp8Reg # load cached hash value
+      /rcx /rcx :testqRegReg
+      /hashComputed :jnzLbl8
+
+      internalHashString /rax :movqImmReg
+      /rax :callqReg
+      /rax /rcx :movqRegReg
+
+      8 /rsp /rdi :movqMemDisp8Reg
+      /rax 8 /rdi :movqRegMemDisp8 # cache hash value in string
+      0 /rsp /rsi :movqMemDisp8Reg
+
+      @hashComputed
+
+      <
+        {
+          # rcx == hash value
+          # rsi == nametable to insert into
+          # rdi == string to insert
+
+          /ecx /eax :movlRegReg
+          /rsi /esi :movlMemReg # load table length
+          16 /rsi :subqImm8Reg # substract header length
+          4 /rsi :shrqImm8Reg # divide by slot length
+          /rdx /rdx :xorqRegReg
+          /rsi :divqReg
+
+          # rdx == remainder of division
+
+          0 /rsp /rsi :movqMemDisp8Reg
+          4 /rdx :shlqImm8Reg # multiply by slot length
+          16 1 /rdx /rsi /rax :leaqMemIndexScaleDisp8Reg # rax == slot address
+          0 /rax :cmpqImm8Mem
+          /emptySlotFound :jzLbl32
+
+          /rax /rsi :movqMemReg
+          /rax :pushqReg
+          /rcx :pushqReg
+          internalCompareString /rax :movqImmReg
+          /rax :callqReg
+          /rcx :popqReg
+          /rax /rax :testqRegReg
+          /equalSlotFound :jnzLbl32
+
+          /rax :popqReg
+          8 /rsp /rdi :movqMemDisp8Reg
+          0 /rsp /rsi :movqMemDisp8Reg
+        } /trySlot deff
+
+        :HASHPOSITIONS 1 sub {
+          trySlot
+
+          /rcx /rax :movqRegReg
+          32 /rax :shrqImm8Reg
+          /rax /rcx :addqRegReg # derive a new hash value
+        } rep
+
+        trySlot
+      > --
+
+      /rax /rax :xorqRegReg # no slot found
+      /rdx /rdx :xorqRegReg
+      16 /rsp :addqImm8Reg
+      :retn
+
+      @emptySlotFound
+      # rax == slot address
+      /rsi :popqReg
+
+      /rax :popqMem # save string into slot
+      /rdx /rdx :xorqRegReg
+      :retn
+
+      @equalSlotFound
+      /rax :popqReg
+      16 /rsp :addqImm8Reg
+
+      1 /rdx :movqImmReg
+      :retn
+    ]] /internalInsertToNametable defv
+
     # allocate function
     # rdi -> code pointer
     # rsi -> scope pointer
@@ -1270,6 +1642,71 @@
 
       :retn
     ]] /internalAllocateCodeFromEncodingBuffer defv
+
+    # rdi -> nametable to enlarge
+    # rsi -> number of entries to have in the new hashtable
+    # rax <- new, larger nametable
+    [[
+      /rdi :pushqReg
+
+      @retry
+
+      /rsi /rdi :movqRegReg
+      internalAllocateNametable /rax :movqImmReg
+      /rax :callqReg
+      /rax :pushqReg
+
+      8 /rsp /rsi :movqMemDisp8Reg
+
+      8 /rsi /rdx :movqMemDisp8Reg
+      /rdx 8 /rax :movqRegMemDisp8 # transfer entry count
+
+      /rsi /ecx :movlMemReg
+      16 /rcx :subqImm8Reg # substract header size
+      4 /rcx :shrqImm8Reg # divide by 16 to get number of buckets
+
+      # rcx == number of entries to rehash
+
+      @rehashEntry
+      16 /rsi :addqImm8Reg
+
+      # rsi == hash bucket to rehash
+
+      0 /rsi :cmpqImm8Mem
+      /entryIsEmpty :jzLbl8
+
+      /rcx :pushqReg
+      /rsi :pushqReg
+
+      /rsi /rdi :movqMemReg
+      16 /rsp /rsi :movqMemDisp8Reg
+      internalInsertToNametable /rax :movqImmReg
+      /rax :callqReg
+      /rax /rax :testqRegReg
+      /rehashFailed :jzLbl8
+
+      /rsi :popqReg
+      /rcx :popqReg
+
+      8 /rsi /rdx :movqMemDisp8Reg
+      /rdx 8 /rax :movqRegMemDisp8 # transfer entry data
+
+      @entryIsEmpty
+      
+      /rehashEntry :loopLbl8
+
+      /rax :popqReg
+      8 /rsp :addqImm8Reg
+      :retn
+
+      @rehashFailed
+      16 /rsp :addqImm8Reg
+      /rax :popqReg
+      /rax /esi :movlMemReg
+      3 /rsi :shrqImm8Reg
+
+      /retry :jmpLbl8
+    ]] /internalGrowNametable defv
   > { defv }' allocateOffsetStruct
 
   [
diff --git a/compiler/elymasAsmOps.ey b/compiler/elymasAsmOps.ey
index 3adba21..3d30518 100644
--- a/compiler/elymasAsmOps.ey
+++ b/compiler/elymasAsmOps.ey
@@ -1294,6 +1294,16 @@ memoryAddressingVariants keys { ==variant memoryAddressingVariants variant . =*p
   /zero reg modrm11
 } /rolqClReg deff
 
+{ ==reg ==i
+  reg bit64assert
+  i 64 lt not { "Shift immediate too large" die } rep
+
+  1 /none /none reg rex
+  %C1
+  /zero reg modrm11
+  i imm8
+} /rolqImm8Reg deff
+
 {
   %AE
 } /scasb deff
diff --git a/compiler/elymasGlobal.ey b/compiler/elymasGlobal.ey
index 805a3db..90fbfda 100644
--- a/compiler/elymasGlobal.ey
+++ b/compiler/elymasGlobal.ey
@@ -116,127 +116,93 @@
       /r15 :popqMem
 
       8 /r15 :subqImm8Reg
-      /r15 :popqMem # /r15 now points to activation
+      /r15 :popqMem
 
-      /rdi :popqReg
+      8 /r15 :subqImm8Reg
+      /r15 :popqMem
+      # 8 /r15 now points to activation
+      # /r15 now points to key to define
       
-      /rax :popqReg # CHECK this is just sanity checking
-      /rax :pushqReg
-      /rax /rax :testqRegReg
-      /realObject :jnzLbl8
-      "trying to store zero object address" ::outputError
-      :ud2
-      @realObject # CHECK end of checking
+      ASSERTIONS {
+        /rax :popqReg
+        /rax :pushqReg
+        /rax /rax :testqRegReg
+        /realObject :jnzLbl8
+        "trying to store zero object address" ::outputError
+        :ud2
+        @realObject
+
+        /r15 /rax :movqMemReg
+        7 /rax /al :movbMemDisp8Reg
+        %f0 /al :andbImmReg
+        %10 /al :cmpbImmReg
+        /keyIsString :jzLbl8
+        "tried to def to non-string key" ::outputError
+        :ud2
+        @keyIsString
+      } rep
 
       # search for name in nametable
       /r14 /rbx :movqRegReg # rbx == start of scope in heap
-      8 /rbx /rdx :movqMemDisp8Reg # rdx == start of nametable in heap
-      /rdx /rdx :testqRegReg
-      /createNameTable :jzLbl32
       8 /rbx /rsi :movqMemDisp8Reg # rsi == start of nametable in heap
-      8 /rsi /rsi :addqMemDisp8Reg # rsi == end of nametable in heap (according to fill)
+      /rsi /rsi :testqRegReg
+      /nameTableExists :jnzLbl32
 
-      @nameSearch
-      16 /rdx :addqImm8Reg
-
-      # rsi: end of nametable
-      # rdx: current element of nametable
+      INITIALNAMETABLESIZE /rdi :movqImmReg
+      ::internalAllocateNametable /rax :movqImmReg
+      /rax :callqReg
 
-      /rdx /rsi :cmpqRegReg
-      /nameUndefined :jbeLbl8
+      # rax == nametable
+      /rax 8 /rbx :movqRegMemDisp8 # save new nametable
+      /rax /rsi :movqRegReg
 
-      /rdx :pushqReg # TODO code does not seem optimal here
-      /rsi :pushqReg
-      /rdi :pushqReg
-      /rcx :pushqReg
-      /rdx /rsi :movqMemReg
-      /rax /rax :xorqRegReg
-      :cmpsq # ignore memory length header
-      :cmpsq # ignore hash
-      /rsi /rdx :movqMemReg # load exact length
-      :cmpsq # same exact length
-      /fail :jnzLbl8
-      /rdx /rcx :movqRegReg
-      :repz :cmpsb
-      /fail :jnzLbl8
-      /rax :incqReg
-      @fail
-      /rcx :popqReg
-      /rdi :popqReg
-      /rsi :popqReg
-      /rdx :popqReg
-      /rax /rax :testqRegReg
-      /nameOffsetKnown :jnzLbl32
-      /nameSearch :jmpLbl8
+      @nameTableExists
+      /r15 /rdi :movqMemReg
 
-      # if not exists, insert
-      @nameUndefined
-      8 /rbx /rdx :movqMemDisp8Reg # rdx == start of nametable in heap
-      /rdx /eax :movlMemReg # add memory length to obtain memory end
-      /rax /rdx :addqRegReg
+      # rdi == string to insert
+      # rsi == nametable on heap
 
-      /rsi /rdx :cmpqRegReg
-      /enlargeNameTable :jbeLbl8
+      ::internalInsertToNametable /rax :movqImmReg
+      /rax :callqReg
 
-      # insert into name table
-      @insertIntoNameTable
-      /rdi /rsi :movqRegMem
-      /r15 /rax :movqMemReg
-      /rax ::unboxInteger
-      /rax 8 /rsi :movqRegMemDisp8 # set default activation mode
-      8 /rbx /rdx :movqMemDisp8Reg # rdx == start of nametable in heap
-      16 8 /rdx :addqImm8MemDisp8 # increment fill
-      /rsi /rdx :movqRegReg
-      /nameOffsetKnown :jmpLbl32
+      # rax == start of 16 byte slot (or zero if no slot was found)
+      /rax /rax :testqRegReg
+      /slotFound :jnzLbl8
 
-      @enlargeNameTable
-      # if name table is already full, double size
-      8 /rbx /rdx :movqMemDisp8Reg # rdx == start of nametable in heap
-      /rdi :pushqReg
-      /rdx :pushqReg
-      /rdx /edi :movlMemReg # load current length
-      /rdi /rdi :addqRegReg
+      8 /rbx /rdi :movqMemDisp8Reg # rdi == start of nametable in heap
+      /rdi /esi :movlMemReg
+      3 /rsi :shrqImm8Reg
 
-      ::internalAllocateAndZero /rax :movqImmReg
+      ::internalGrowNametable /rax :movqImmReg
       /rax :callqReg
-      %A0 7 /rax :orbImmMemDisp8 # set type
-      /rdx :popqReg
-      8 /rdx /rcx :movqMemDisp8Reg
-      /rcx 8 /rax :movqRegMemDisp8 # copy fill
+      # rax == new, larger nametable
+      /rax 8 /rbx :movqRegMemDisp8 # store new nametable in scope
+      /rax /rsi :movqRegReg
+      /nameTableExists :jmpLbl8
 
-      16 /rdx /rsi :leaqMemDisp8Reg
-      16 /rax /rdi :leaqMemDisp8Reg
-      16 /rcx :subqImm8Reg
-      3 /rcx :shrqImm8Reg
-      :reprcx :movsq # copy content
-      /insertIntoNewNameTable :jmpLbl8
+      @slotFound
+      # rax == address of 16 byte slot in nametable
+      /rdx /rdx :testqRegReg
+      /nameExists :jnzLbl8
 
-      @createNameTable
-      /rdi :pushqReg
+      8 /r15 /esi :movlMemDisp8Reg
+      /esi 8 /rax :movlRegMemDisp8 # store execution mode
 
-      INITIALNAMETABLESIZE 16 mul 16 add /rdi :movqImmReg
-      ::internalAllocateAndZero /rax :movqImmReg
-      /rax :callqReg
-      %A0 7 /rax :orbImmMemDisp8 # set type
-      16 8 /rax :orbImmMemDisp8 # set initial fill
-      16 /rax /rdi :leaqMemDisp8Reg # load first entry address
+      8 /rbx /rdi :movqMemDisp8Reg # rdi == start of nametable in heap
+      8 /rdi /esi :movlMemDisp8Reg
+      /esi 12 /rax :movlRegMemDisp8 # store scope index # FIXME measure performance and consider orq-ing the two fields by hand
+      1 8 /rdi :addqImm8MemDisp8 # increment number of assigned slots
+
+      /rsi /rdx :movqRegReg
+      /nameInserted :jmpLbl8
 
-      @insertIntoNewNameTable
+      @nameExists
+      12 /rax /edx :movlMemDisp8Reg # load slot index from hash
 
-      # rax == enlarged or new name table on heap
-      # rdi == target address for name table entry
-      
-      /rax 8 /rbx :movqRegMemDisp8 # switch scope to new name table
+      @nameInserted
+      # rdx == slot index
 
-      # insert into name table
-      /rsi :popqReg
-      /rsi /rdi :xchgqRegReg
-      /insertIntoNameTable :jmpLbl32
-      
-      @nameOffsetKnown
-      8 /rbx /rdx :subqMemDisp8Reg # substract name table address
-      16 /rdx :subqImm8Reg # substract name table header size
-      /rdx :shrq1Reg # divide by 2 to get offset within scope
+      3 /rdx :shlqImm8Reg # multiply by 8 to get offset within scope
 
       # rdx == offset in scope
       # top of stack: the object to store
@@ -308,7 +274,7 @@
       /rax :popqReg
       /rax /rbx /rdx :movqRegMemIndex # save entry pointer
 
-      8 /r15 :addqImm8Reg
+      16 /r15 :addqImm8Reg
       /r15 :pushqMem
       8 /r15 :addqImm8Reg
       :retn
@@ -435,13 +401,18 @@
       # rdx == array on heap
       /rbx :popqReg
       63 /rbx :btrqImm8Reg
-      /arrayIntArgumentUnboxed :jcLbl8
+      /arrayIntArgumentUnboxed :jcLbl32
 
       7 /rbx /cl :movbMemDisp8Reg
       %F0 /cl :andbImmReg
       %00 /cl :cmpbImmReg
       /arrayIntArgumentBoxed :jeLbl8
 
+      %01 /cl :cmpbImmReg
+      /arrayWrongScalarArgumentBoxed :jeLbl8
+      %02 /cl :cmpbImmReg
+      /arrayWrongScalarArgumentBoxed :jeLbl8
+
       # escape this to compiled high-level code
       /rbx :pushqReg
       /rdx :pushqReg
@@ -465,6 +436,10 @@
       8 /r15 :addqImm8Reg
       :retn
 
+      @arrayWrongScalarArgumentBoxed
+      "trying to execute array on string or float" ::outputError
+      :ud2
+
       @arrayIntArgumentBoxed
       8 /rbx /rax :movqMemDisp8Reg # rax == requested index
       /arrayIntArgumentLoaded :jmpLbl8
@@ -1853,6 +1828,26 @@
       8 /r15 :popqMemDisp8 # output arguments
       /r15 :popqMem # input arguments
 
+      ASSERTIONS {
+        /r15 /rax :movqMemReg
+        7 /rax /al :movbMemDisp8Reg
+        %f0 /al :andbImmReg
+        %70 /al :cmpbImmReg
+        /inputIsArray :jzLbl8
+        "tried to '' for non-array input arguments" ::outputError
+        :ud2
+        @inputIsArray
+
+        8 /r15 /rax :movqMemDisp8Reg
+        7 /rax /al :movbMemDisp8Reg
+        %f0 /al :andbImmReg
+        %70 /al :cmpbImmReg
+        /outputIsArray :jzLbl8
+        "tried to '' for non-array output arguments" ::outputError
+        :ud2
+        @outputIsArray
+      } rep
+
       /r15 /rdx :movqMemReg
       /rdx /edi :movlMemReg
       8 /r15 /rdx :movqMemDisp8Reg
@@ -2458,27 +2453,35 @@
       /emptyScope :jzLbl8
 
       16 /rax /rsi :leaqMemDisp8Reg
-      /rsi :pushqReg
+      /rsi :pushqReg # save start of bucket array
+      /rax /ecx :movlMemReg
+      16 /rcx :subqImm8Reg # substract header size
+      4 /rcx :shrqImm8Reg
+      /rcx :pushqReg # save bucket count
       8 /rax /rdi :movqMemDisp8Reg
-      16 /rdi :subqImm8Reg
-      /rdi :pushqReg
-      /rdi :shrq1Reg
+      3 /rdi :shlqImm8Reg
       ::internalAllocateArray /rax :movqImmReg
       /rax :callqReg
 
       8 /rax /rdi :leaqMemDisp8Reg
       /rcx :popqReg
       /rsi :popqReg
-      4 /rcx :shrqImm8Reg
+
+      /rax :pushqReg # save array on stack as result
+
+      /rcx /rcx :testqRegReg
       /empty :jzLbl8
       @loop
-      :movsq
-      8 /rsi :addqImm8Reg
+      /rsi /rax :movqMemReg
+      /rax /rax :testqRegReg
+      /emptyBucket :jzLbl8
+      12 /rsi /edx :movlMemDisp8Reg # load entry index
+      /rax 8 /rdx /rdi :movqRegMemIndexScale # put into array
+      @emptyBucket
+      16 /rsi :addqImm8Reg
       /loop :loopLbl8
       @empty
 
-      /rax :pushqReg
-
       /r15 :pushqMem
       8 /r15 :addqImm8Reg
       :retn
diff --git a/doc/notes b/doc/notes
index 4a3ea3d..e768ddd 100644
--- a/doc/notes
+++ b/doc/notes
@@ -271,16 +271,17 @@ Overhead: 1/32.
 * data
   [ <reference> ]*
 
-=== Name Table ===
-( TODO: create a hash-table based implementation here )
+=== Name Table (hashed implementation) ===
 * Length in bytes (including header)
   bit 63-60: 1 0 1 0
   bit 59: reserved for GC
-* End of fill in bytes (i.e. if this field == length, table is full)
-* data
-  [ <string reference>, <execution mode> ]*
-  ( TODO: Oh, the performance... )
-  The 0th string maps to 0 and so on.
+* Number of keys (also next scope entry index to assign)
+* Hash buckets (16 bytes each)
+  [
+    <string reference>  (8 bytes)
+    <execution mode>    (4 bytes)
+    <scope entry index> (4 bytes)
+  ]*
 
 === Stack ===
 * Length in bytes (including header)
@@ -397,6 +398,53 @@ eq [ sys .typed .SCALAR _ ] [ Int ] ''
 eq [ sys .typed .var _ ] [ Int ] ''
 { 1 eq } { "foo" eq } and # [ $X $Y ] [ Int ] # 1 eq -01 "foo" eq and
 
+== Variant: Scalar Argument-Selector ==
+
+=== Obvious Case 1 ===
+1 [ 1 2 3 ] add => [ 2 3 4 ]
+[ 1 2 3 ] 1 add => [ 2 3 4 ]
+Because:
+[ 1 1 1 ] [ 1 2 3 ] add => [ 2 3 4 ]
+
+=== Obvious Case 2 ===
+If f, g unrelated:
+|f |g h => { f ==x g ==y y x h } *
+
+|add |sub mul => { ==x ==y x y add x y sub mul } *
+
+WTF??? Hence:
+Say f, g have a type which specifies which stack position they'd like to consume, like so:
+|f type => [ 2 0 ] . [ 0 ]
+|g type => [ 1 0 ] . [ 0 ]
+then
+|f |g h => { ==z ==y ==x y x g ==G z x f ==F F G h } *
+
+=== Obvious Case 3 ===
+{ -- { -- { 1 } } } =*f (i.e. the constant function from two arguments to 1)
+|f |f add => { -- { -- { 2 } } } (i.e. the constant function from two arguments to 2)
+
+With the above:
+|f type => [ 0 ] . [ [ 0 ] . 0 ]
+
+=== Case 4 ===
+{ _ } =*dup (clearly with type [ 0 ] . [ 0 0 ])
+
+|dup |add ; => { _ add }
+X |dup add => { ==y y dup ==D1 ==D2 X D2 add D1 }
+|dup X add => { ==y y dup ==D1 ==D2 D2 X add D1 }
+
+=== Case 5 ===
+
+
+
+f: A->B->X
+   |  |
+   v  v
+   a0 b0
+   |
+   v
+   a1
+
 = Musings about function composition operator =
 
 Maybe ; should act differently when getting a string, or use another single char for category operations