Library build time down another 3.2%

2 files changed, 54 insertions, 55 deletions

diff --git a/compiler/elymasAsmLib.ey b/compiler/elymasAsmLib.ey
index b221b3b..1fac364 100644
--- a/compiler/elymasAsmLib.ey
+++ b/compiler/elymasAsmLib.ey
@@ -255,6 +255,7 @@
       /noFreeBlockAvailable :jbeLbl32
       /rbx /r8 :btqRegMem # test block bitmap
       /resumeFreeBlockStartSearch :jcLbl8 # block not free
+      /rbx /r9 :btrqRegMem # reset mark bit to reconnect free blocks
       /freeBlockStartFound :jmpLbl8
 
       @freeBlockFound
@@ -269,65 +270,19 @@
       /rbx /rbp :cmpqRegReg
       /dontSplit :jbeLbl8
 
-      %FE /rsi :movqImmReg
-      /rbx /rcx :movqRegReg
-      7 /cl :andbImmReg
-      /sil :rolbClReg # rsi now contains mask bit for block/mark in byte (reset bit at relevant position)
-
-      /rbx /rax :movqRegReg
-      3 /rax :shrqImm8Reg
-      1 /r8 /rax /sil :orbMemIndexScaleReg # sil now { mask block bor }
-      /rsi :notqReg # sil now { mask block bor bnot }
-      /sil 1 /r9 /rax :orbRegMemIndexScale # set mark bit if block bit was zero
+      /rbx /r8 :btqRegMem # the next block already starts here?
+      /dontSplit :jcLbl8 # yes
+      /rbx /r9 :btsqRegMem # set mark bit if block bit was zero
 
       @dontSplit
       # mark block as used (-> white)
-      /rdi /rsi :movqRegReg
-      /rsi :decqReg
+      1 neg /rdi /rsi :leaqMemDisp8Reg
       4 /rsi :shrqImm8Reg
       /rsi :incqReg
       /rsi /rbx :subqRegReg
 
-      1 /rsi :movqImmReg
-      /rbx /rcx :movqRegReg
-      7 /cl :andbImmReg
-      /rsi :shlqClReg # rsi now contains mask bit for block/mark in byte (set bit at relevant position)
-
-      /rbx /rax :movqRegReg
-      3 /rax :shrqImm8Reg
-      /sil 1 /r8 /rax :orbRegMemIndexScale # set block bit
-      /rsi :notqReg # sil now { mask bnot }
-      /sil 1 /r9 /rax :andbRegMemIndexScale # reset mark bit
-
-      # ensure the new block is marked as block extend throughout in the bitmaps
-      # TODO reconnect free blocks while scanning instead
-      /rbx :pushqReg
-      /rdi :pushqReg
-
-      /rdi :decqReg
-      4 /rdi :shrqImm8Reg
-
-      @markBlockFree
-      /rdi /rdi :andqRegReg
-      /markedBlockFree :jzLbl8
-      /rdi :decqReg
-      /rbx :incqReg
-
-      1 /rsi :movqImmReg
-      /rbx /rcx :movqRegReg
-      7 /cl :andbImmReg
-      /rsi :shlqClReg # rsi now contains mask bit for block/mark in byte (set bit at relevant position)
-      /rsi :notqReg # (reset bit at relevant position)
-
-      /rbx /rax :movqRegReg
-      3 /rax :shrqImm8Reg
-      /sil 1 /r8 /rax :andbRegMemIndexScale # reset block bit
-      /sil 1 /r9 /rax :andbRegMemIndexScale # reset mark bit
-      /markBlockFree :jmpLbl8
-
-      @markedBlockFree
-      /rdi :popqReg
-      /rbx :popqReg
+      /rbx /r8 :btsqRegMem # set block bit
+      /rbx /r9 :btrqRegMem # reset mark bit
 
       # prepare block length and GC header (-> light grey)
       4 /rbx :shlqImm8Reg
@@ -339,10 +294,9 @@
       # zero rest of block # TODO eliminate this one day
       /rax :pushqReg
       /rdi /rcx :movqRegReg
-      /rax /rdi :movqRegReg
+      8 /rax /rdi :leaqMemDisp8Reg
       3 /rcx :shrqImm8Reg
       /rcx :decqReg
-      8 /rdi :addqImm8Reg
       /rax /rax :xorqRegReg
       :reprcx :stosq
       /rax :popqReg
diff --git a/notes b/notes
index 540f60c..c58e185 100644
--- a/notes
+++ b/notes
@@ -114,16 +114,61 @@ a-z: bareword characters
 
 = Memory Management =
 
+== Currently implemented ==
+
 Inspiration: http://wiki.luajit.org/new-garbage-collector
 
 0x6???????????: Heap memory ("16 TB should be enough for everyone.")
 0x5???????????: GC block bitmap
 0x4???????????: GC mark bitmap
 
+== Musings about possibly better schemes ==
+
+0x500?????????: GC block bitmap
+0x501?????????: GC block bitmap
+0x502?????????: GC mark bitmap
+0x503?????????: GC mark bitmap
+0x504?????????: GC free bitmap
+0x505?????????: GC free bitmap
+0x506?????????: GC "all cells used"-tree
+0x507?????????: GC "all cells used"-tree
+0x508?????????: GC "any cells used"-tree
+0x509?????????: GC "any cells used"-tree
+
 Large set of reachable, old objects
 Large set of unreachable, new objects
 Small set in between
 
+=== How to find free space ===
+
+A valid state:
+
+1                16-cell element blocked
+1       1         8-cell element blocked
+1   0   1   1     4-cell element blocked
+1 1 0 0 1 1 1 1   2-cell element blocked
+1011000010101010  usage of cells
+
+Tree-Layout:
+
+E
+6   D
+2 5 9 C
+013478AB
+
+Right child: 1 sub
+Left child: 1 height level sub shl sub 
+
+Algorithm of allocation (of byte-count n):
+
+Find correct level m = height-log_2(n/16) (from top).
+Walk zeros in "all cells used"-tree down to level m-1.
+Find zero in "any cells used"-tree on level m.
+Set "all cells used"-bit on level m (or multiple bits on the lower levels according to object size)
+  Propagate as necessary.
+Set "any cells used"-bits on levels m to 0.
+
+Overhead: 1/32.
 
 == Object Memory Layout ==
 
@@ -232,7 +277,7 @@ Main problem: How do we find out if the names mean what we believe they do?
 * Default scopes are dynamic, but the user can specify otherwise
 - many methods would not get optimized because the user forgot to flag the scope
 
-== Dynamic / Static / Constant Names ==
+== Dynamic / Static / Constant Names (implemented) ==
 * A name can be static (i.e. it is never overwritten after being resolved in a child scope and remains at the same scope index)
 * A name can be constant (i.e. its value never changes after being resolved in a child scope)
 * An optimized version of the code can be generated whenever it is called (using current name values)