gc tweaking to gain a few percent of performance

7 files changed, 153 insertions, 104 deletions

diff --git a/lib/core/macros.nim b/lib/core/macros.nim
index e262ec012..e51141025 100755
--- a/lib/core/macros.nim
+++ b/lib/core/macros.nim
@@ -13,60 +13,60 @@
 

 ## .. include:: ../doc/astspec.txt

 

-type
-  TNimrodNodeKind* = enum
-    nnkNone, nnkEmpty, nnkIdent, nnkSym, 
-    nnkType, nnkCharLit, nnkIntLit, nnkInt8Lit, 
-    nnkInt16Lit, nnkInt32Lit, nnkInt64Lit, nnkFloatLit, 
-    nnkFloat32Lit, nnkFloat64Lit, nnkStrLit, nnkRStrLit, 
-    nnkTripleStrLit, nnkMetaNode, nnkNilLit, nnkDotCall, 
-    nnkCommand, nnkCall, nnkCallStrLit, nnkExprEqExpr, 
-    nnkExprColonExpr, nnkIdentDefs, nnkVarTuple, nnkInfix, 
-    nnkPrefix, nnkPostfix, nnkPar, nnkCurly, 
-    nnkBracket, nnkBracketExpr, nnkPragmaExpr, nnkRange, 
-    nnkDotExpr, nnkCheckedFieldExpr, nnkDerefExpr, nnkIfExpr, 
-    nnkElifExpr, nnkElseExpr, nnkLambda, nnkAccQuoted, 
-    nnkTableConstr, nnkBind, nnkSymChoice, nnkHiddenStdConv, 
-    nnkHiddenSubConv, nnkHiddenCallConv, nnkConv, nnkCast, 
-    nnkAddr, nnkHiddenAddr, nnkHiddenDeref, nnkObjDownConv, 
-    nnkObjUpConv, nnkChckRangeF, nnkChckRange64, nnkChckRange, 
-    nnkStringToCString, nnkCStringToString, nnkPassAsOpenArray, nnkAsgn, 
-    nnkFastAsgn, nnkGenericParams, nnkFormalParams, nnkOfInherit, 
-    nnkModule, nnkProcDef, nnkMethodDef, nnkConverterDef, 
-    nnkMacroDef, nnkTemplateDef, nnkIteratorDef, nnkOfBranch, 
-    nnkElifBranch, nnkExceptBranch, nnkElse, nnkMacroStmt, 
-    nnkAsmStmt, nnkPragma, nnkIfStmt, nnkWhenStmt, 
-    nnkForStmt, nnkWhileStmt, nnkCaseStmt, nnkVarSection, 
-    nnkConstSection, nnkConstDef, nnkTypeSection, nnkTypeDef, 
-    nnkYieldStmt, nnkTryStmt, nnkFinally, nnkRaiseStmt, 
-    nnkReturnStmt, nnkBreakStmt, nnkContinueStmt, nnkBlockStmt, 
-    nnkDiscardStmt, nnkStmtList, nnkImportStmt, nnkFromStmt, 
-    nnkIncludeStmt, nnkCommentStmt, nnkStmtListExpr, nnkBlockExpr, 
-    nnkStmtListType, nnkBlockType, nnkTypeOfExpr, nnkObjectTy, 
-    nnkTupleTy, nnkRecList, nnkRecCase, nnkRecWhen, 
-    nnkRefTy, nnkPtrTy, nnkVarTy, nnkDistinctTy, 
-    nnkProcTy, nnkEnumTy, nnkEnumFieldDef, nnkReturnToken
-  TNimNodeKinds* = set[TNimrodNodeKind]
-  TNimrodTypeKind* = enum
-    ntyNone, ntyBool, ntyChar, ntyEmpty, 
-    ntyArrayConstr, ntyNil, ntyExpr, ntyStmt, 
-    ntyTypeDesc, ntyGenericInvokation, ntyGenericBody, ntyGenericInst, 
-    ntyGenericParam, ntyDistinct, ntyEnum, ntyOrdinal, 
-    ntyArray, ntyObject, ntyTuple, ntySet, 
-    ntyRange, ntyPtr, ntyRef, ntyVar, 
-    ntySequence, ntyProc, ntyPointer, ntyOpenArray, 
-    ntyString, ntyCString, ntyForward, ntyInt, 
-    ntyInt8, ntyInt16, ntyInt32, ntyInt64, 
-    ntyFloat, ntyFloat32, ntyFloat64, ntyFloat128
-  TNimTypeKinds* = set[TNimrodTypeKind]
-  TNimrodSymKind* = enum
-    nskUnknown, nskConditional, nskDynLib, nskParam, 
-    nskGenericParam, nskTemp, nskType, nskConst, 
-    nskVar, nskProc, nskMethod, nskIterator, 
-    nskConverter, nskMacro, nskTemplate, nskField, 
-    nskEnumField, nskForVar, nskModule, nskLabel, 
-    nskStub
-  TNimSymKinds* = set[TNimrodSymKind]
+type

+  TNimrodNodeKind* = enum

+    nnkNone, nnkEmpty, nnkIdent, nnkSym, 

+    nnkType, nnkCharLit, nnkIntLit, nnkInt8Lit, 

+    nnkInt16Lit, nnkInt32Lit, nnkInt64Lit, nnkFloatLit, 

+    nnkFloat32Lit, nnkFloat64Lit, nnkStrLit, nnkRStrLit, 

+    nnkTripleStrLit, nnkMetaNode, nnkNilLit, nnkDotCall, 

+    nnkCommand, nnkCall, nnkCallStrLit, nnkExprEqExpr, 

+    nnkExprColonExpr, nnkIdentDefs, nnkVarTuple, nnkInfix, 

+    nnkPrefix, nnkPostfix, nnkPar, nnkCurly, 

+    nnkBracket, nnkBracketExpr, nnkPragmaExpr, nnkRange, 

+    nnkDotExpr, nnkCheckedFieldExpr, nnkDerefExpr, nnkIfExpr, 

+    nnkElifExpr, nnkElseExpr, nnkLambda, nnkAccQuoted, 

+    nnkTableConstr, nnkBind, nnkSymChoice, nnkHiddenStdConv, 

+    nnkHiddenSubConv, nnkHiddenCallConv, nnkConv, nnkCast, 

+    nnkAddr, nnkHiddenAddr, nnkHiddenDeref, nnkObjDownConv, 

+    nnkObjUpConv, nnkChckRangeF, nnkChckRange64, nnkChckRange, 

+    nnkStringToCString, nnkCStringToString, nnkPassAsOpenArray, nnkAsgn, 

+    nnkFastAsgn, nnkGenericParams, nnkFormalParams, nnkOfInherit, 

+    nnkModule, nnkProcDef, nnkMethodDef, nnkConverterDef, 

+    nnkMacroDef, nnkTemplateDef, nnkIteratorDef, nnkOfBranch, 

+    nnkElifBranch, nnkExceptBranch, nnkElse, nnkMacroStmt, 

+    nnkAsmStmt, nnkPragma, nnkIfStmt, nnkWhenStmt, 

+    nnkForStmt, nnkWhileStmt, nnkCaseStmt, nnkVarSection, 

+    nnkConstSection, nnkConstDef, nnkTypeSection, nnkTypeDef, 

+    nnkYieldStmt, nnkTryStmt, nnkFinally, nnkRaiseStmt, 

+    nnkReturnStmt, nnkBreakStmt, nnkContinueStmt, nnkBlockStmt, 

+    nnkDiscardStmt, nnkStmtList, nnkImportStmt, nnkFromStmt, 

+    nnkIncludeStmt, nnkCommentStmt, nnkStmtListExpr, nnkBlockExpr, 

+    nnkStmtListType, nnkBlockType, nnkTypeOfExpr, nnkObjectTy, 

+    nnkTupleTy, nnkRecList, nnkRecCase, nnkRecWhen, 

+    nnkRefTy, nnkPtrTy, nnkVarTy, nnkDistinctTy, 

+    nnkProcTy, nnkEnumTy, nnkEnumFieldDef, nnkReturnToken

+  TNimNodeKinds* = set[TNimrodNodeKind]

+  TNimrodTypeKind* = enum

+    ntyNone, ntyBool, ntyChar, ntyEmpty, 

+    ntyArrayConstr, ntyNil, ntyExpr, ntyStmt, 

+    ntyTypeDesc, ntyGenericInvokation, ntyGenericBody, ntyGenericInst, 

+    ntyGenericParam, ntyDistinct, ntyEnum, ntyOrdinal, 

+    ntyArray, ntyObject, ntyTuple, ntySet, 

+    ntyRange, ntyPtr, ntyRef, ntyVar, 

+    ntySequence, ntyProc, ntyPointer, ntyOpenArray, 

+    ntyString, ntyCString, ntyForward, ntyInt, 

+    ntyInt8, ntyInt16, ntyInt32, ntyInt64, 

+    ntyFloat, ntyFloat32, ntyFloat64, ntyFloat128

+  TNimTypeKinds* = set[TNimrodTypeKind]

+  TNimrodSymKind* = enum

+    nskUnknown, nskConditional, nskDynLib, nskParam, 

+    nskGenericParam, nskTemp, nskType, nskConst, 

+    nskVar, nskProc, nskMethod, nskIterator, 

+    nskConverter, nskMacro, nskTemplate, nskField, 

+    nskEnumField, nskForVar, nskModule, nskLabel, 

+    nskStub

+  TNimSymKinds* = set[TNimrodSymKind]

 

 type

   TNimrodIdent* = object of TObject

@@ -88,7 +88,7 @@ type
     

 # Nodes should be reference counted to make the `copy` operation very fast!

 # However, this is difficult to achieve: modify(n[0][1]) should propagate to

-# its father. How to do this without back references? Hm, BS, it works without 
+# its father. How to do this without back references? Hm, BS, it works without 

 # them.

 

 proc `[]`* (n: PNimrodNode, i: int): PNimrodNode {.magic: "NChild".}

@@ -105,7 +105,7 @@ proc `$`*(i: TNimrodIdent): string {.magic: "IdentToStr".}
 

 proc `==`* (a, b: TNimrodIdent): bool {.magic: "EqIdent", noSideEffect.}

   ## compares two Nimrod identifiers

-
+

 proc `==`* (a, b: PNimrodNode): bool {.magic: "EqNimrodNode", noSideEffect.}

   ## compares two Nimrod nodes

 

diff --git a/lib/core/threads.nim b/lib/core/threads.nim
index fc120f1a3..a1c16fc85 100755
--- a/lib/core/threads.nim
+++ b/lib/core/threads.nim
@@ -100,7 +100,7 @@ when defined(Windows):
       stdcall, dynlib: "kernel32", importc: "WaitForMultipleObjects".}
 
   proc WaitForSingleObject(hHandle: THANDLE, dwMilliseconds: int32): int32 {.
-      stdcall, dynlib: "kernel32", importc: "WaitForSingleObject".}
+    stdcall, dynlib: "kernel32", importc: "WaitForSingleObject".}
 
   proc TerminateThread(hThread: THandle, dwExitCode: int32): int32 {.
     stdcall, dynlib: "kernel32", importc: "TerminateThread".}
diff --git a/lib/pure/collections/hashtables.nim b/lib/pure/collections/hashtables.nim
index 29ba6bf6f..4f4c4f5a0 100644
--- a/lib/pure/collections/hashtables.nim
+++ b/lib/pure/collections/hashtables.nim
@@ -216,9 +216,16 @@ proc `[]=`*[A, B](t: TOrderedHashTable[A, B], key: A, val: B) =
     inc(t.counter)
 
 proc del*[A, B](t: TOrderedHashTable[A, B], key: A) =
-  ## deletes `key` from hash table `t`.
+  ## deletes `key` from hash table `t`. Warning: It's inefficient for ordered
+  ## tables: O(n).
   var index = RawGet(t, key)
   if index >= 0:
+    var i = t.first
+    while i >= 0:
+      var nxt = t.data[i].next
+      if nxt == index: XXX
+      i = nxt
+    
     t.data[index].slot = seDeleted
     dec(t.counter)
 
diff --git a/lib/system/cgprocs.nim b/lib/system/cgprocs.nim
index 945ce4692..f77768a7a 100755
--- a/lib/system/cgprocs.nim
+++ b/lib/system/cgprocs.nim
@@ -23,28 +23,39 @@ proc nimLoadLibraryError(path: string) {.compilerproc, noinline.}
 
 proc setStackBottom(theStackBottom: pointer) {.compilerRtl, noinline.}
 
-
 # Support for thread local storage:
-when false:
-  when defined(windows):
-    proc TlsAlloc(): int32 {.importc: "TlsAlloc", stdcall, dynlib: "kernel32".}
-    proc TlsSetValue(dwTlsIndex: int32, lpTlsValue: pointer) {.
-      importc: "TlsSetValue", stdcall, dynlib: "kernel32".}
-    proc TlsGetValue(dwTlsIndex: int32): pointer {.
-      importc: "TlsGetValue", stdcall, dynlib: "kernel32".}
-    
-  else:
-    type
-      Tpthread_key {.importc: "pthread_key_t", header: "<sys/types.h>".} = int
-
-    proc pthread_getspecific(a1: Tpthread_key): pointer {.
-      importc: "pthread_getspecific", header: "<pthread.h>".}
-    proc pthread_key_create(a1: ptr Tpthread_key, 
-                            a2: proc (x: pointer) {.noconv.}): int32 {.
-      importc: "pthread_key_create", header: "<pthread.h>".}
-    proc pthread_key_delete(a1: Tpthread_key): int32 {.
-      importc: "pthread_key_delete", header: "<pthread.h>".}
-
-    proc pthread_setspecific(a1: Tpthread_key, a2: pointer): int32 {.
-      importc: "pthread_setspecific", header: "<pthread.h>".}
+when defined(windows):
+  type
+    TThreadVarSlot {.compilerproc.} = distinct int32
+
+  proc TlsAlloc(): TThreadVarSlot {.
+    importc: "TlsAlloc", stdcall, dynlib: "kernel32".}
+  proc TlsSetValue(dwTlsIndex: TThreadVarSlot, lpTlsValue: pointer) {.
+    importc: "TlsSetValue", stdcall, dynlib: "kernel32".}
+  proc TlsGetValue(dwTlsIndex: TThreadVarSlot): pointer {.
+    importc: "TlsGetValue", stdcall, dynlib: "kernel32".}
+  
+  proc ThreadVarAlloc(): TThreadVarSlot {.compilerproc, inline.} =
+    result = TlsAlloc()
+  proc ThreadVarSetValue(s: TThreadVarSlot, value: pointer) {.compilerproc.} =
+    TlsSetValue(s, value)
+  proc ThreadVarGetValue(s: TThreadVarSlot): pointer {.compilerproc.} =
+    result = TlsGetValue(s)
+  
+else:
+  type
+    Tpthread_key {.importc: "pthread_key_t", 
+                   header: "<sys/types.h>".} = distinct int
+    TThreadVarSlot {.compilerproc.} = Tpthread_key
+
+  proc pthread_getspecific(a1: Tpthread_key): pointer {.
+    importc: "pthread_getspecific", header: "<pthread.h>".}
+  proc pthread_key_create(a1: ptr Tpthread_key, 
+                          destruct: proc (x: pointer) {.noconv.}): int32 {.
+    importc: "pthread_key_create", header: "<pthread.h>".}
+  proc pthread_key_delete(a1: Tpthread_key): int32 {.
+    importc: "pthread_key_delete", header: "<pthread.h>".}
+
+  proc pthread_setspecific(a1: Tpthread_key, a2: pointer): int32 {.
+    importc: "pthread_setspecific", header: "<pthread.h>".}
 
diff --git a/lib/system/dyncalls.nim b/lib/system/dyncalls.nim
index 88870a209..fb1130938 100755
--- a/lib/system/dyncalls.nim
+++ b/lib/system/dyncalls.nim
@@ -1,7 +1,7 @@
 #
 #
 #            Nimrod's Runtime Library
-#        (c) Copyright 2010 Andreas Rumpf
+#        (c) Copyright 2011 Andreas Rumpf
 #
 #    See the file "copying.txt", included in this
 #    distribution, for details about the copyright.
@@ -21,8 +21,6 @@ proc rawWrite(f: TFile, s: string) =
 
 proc nimLoadLibraryError(path: string) =
   # carefully written to avoid memory allocation:
-  #stdout.write("could not load: ")
-  #quit(path)
   stdout.rawWrite("could not load: ")
   stdout.rawWrite(path)
   stdout.rawWrite("\n")
diff --git a/lib/system/gc.nim b/lib/system/gc.nim
index 950b60c27..1edc33375 100755
--- a/lib/system/gc.nim
+++ b/lib/system/gc.nim
@@ -23,7 +23,7 @@
 const
   CycleIncrease = 2 # is a multiplicative increase
   InitialCycleThreshold = 4*1024*1024 # X MB because cycle checking is slow
-  ZctThreshold = 256  # we collect garbage if the ZCT's size
+  ZctThreshold = 500  # we collect garbage if the ZCT's size
                       # reaches this threshold
                       # this seems to be a good value
 
@@ -294,31 +294,32 @@ proc initGC() =
 proc forAllSlotsAux(dest: pointer, n: ptr TNimNode, op: TWalkOp) =
   var d = cast[TAddress](dest)
   case n.kind
-  of nkNone: assert(false)
   of nkSlot: forAllChildrenAux(cast[pointer](d +% n.offset), n.typ, op)
   of nkList:
     for i in 0..n.len-1: forAllSlotsAux(dest, n.sons[i], op)
   of nkCase:
     var m = selectBranch(dest, n)
     if m != nil: forAllSlotsAux(dest, m, op)
+  of nkNone: assert(false)
 
 proc forAllChildrenAux(dest: Pointer, mt: PNimType, op: TWalkOp) =
   var d = cast[TAddress](dest)
   if dest == nil: return # nothing to do
   if ntfNoRefs notin mt.flags:
     case mt.Kind
-    of tyArray, tyArrayConstr, tyOpenArray:
-      for i in 0..(mt.size div mt.base.size)-1:
-        forAllChildrenAux(cast[pointer](d +% i *% mt.base.size), mt.base, op)
     of tyRef, tyString, tySequence: # leaf:
       doOperation(cast[ppointer](d)[], op)
     of tyObject, tyTuple, tyPureObject:
       forAllSlotsAux(dest, mt.node, op)
+    of tyArray, tyArrayConstr, tyOpenArray:
+      for i in 0..(mt.size div mt.base.size)-1:
+        forAllChildrenAux(cast[pointer](d +% i *% mt.base.size), mt.base, op)
     else: nil
 
 proc forAllChildren(cell: PCell, op: TWalkOp) =
   assert(cell != nil)
   assert(cell.typ != nil)
+  assert cell.typ.kind in {tyRef, tySequence, tyString}
   case cell.typ.Kind
   of tyRef: # common case
     forAllChildrenAux(cellToUsr(cell), cell.typ.base, op)
@@ -329,14 +330,57 @@ proc forAllChildren(cell: PCell, op: TWalkOp) =
       for i in 0..s.len-1:
         forAllChildrenAux(cast[pointer](d +% i *% cell.typ.base.size +%
           GenericSeqSize), cell.typ.base, op)
-  of tyString: nil
-  else: assert(false)
+  else: nil
 
 proc checkCollection {.inline.} =
   # checks if a collection should be done
   if recGcLock == 0:
     collectCT(gch)
 
+proc addNewObjToZCT(res: PCell) {.inline.} =
+  # we check the last 8 entries (cache line) for a slot that could be reused.
+  # In 63% of all cases we succeed here! But we have to optimize the heck
+  # out of this small linear search so that ``newObj`` is not slowed down.
+  # 
+  # Slots to try          cache hit
+  # 1                     32%
+  # 4                     59%
+  # 8                     63%
+  # 16                    66%
+  # all slots             68%
+  var L = gch.zct.len
+  var d = gch.zct.d
+  when true:
+    # loop unrolled for performance:
+    template replaceZctEntry(i: expr) =
+      c = d[i]
+      if c.refcount >=% rcIncrement:
+        c.refcount = c.refcount and not colorMask
+        d[i] = res
+        return
+    if L > 8:
+      var c: PCell
+      replaceZctEntry(L-1)
+      replaceZctEntry(L-2)
+      replaceZctEntry(L-3)
+      replaceZctEntry(L-4)
+      replaceZctEntry(L-5)
+      replaceZctEntry(L-6)
+      replaceZctEntry(L-7)
+      replaceZctEntry(L-8)
+      add(gch.zct, res)
+    else:
+      d[L] = res
+      inc(gch.zct.len)
+  else:
+    for i in countdown(L-1, max(0, L-8)):
+      var c = d[i]
+      if c.refcount >=% rcIncrement:
+        c.refcount = c.refcount and not colorMask
+        d[i] = res
+        return
+    add(gch.zct, res)
+
 proc newObj(typ: PNimType, size: int): pointer {.compilerRtl.} =
   # generates a new object and sets its reference counter to 0
   aquire(gch)
@@ -354,18 +398,7 @@ proc newObj(typ: PNimType, size: int): pointer {.compilerRtl.} =
   res.refcount = rcZct # refcount is zero, but mark it to be in the ZCT  
   assert(isAllocatedPtr(allocator, res))
   # its refcount is zero, so add it to the ZCT:
-  block addToZCT: 
-    # we check the last 8 entries (cache line) for a slot
-    # that could be reused
-    var L = gch.zct.len
-    var d = gch.zct.d
-    for i in countdown(L-1, max(0, L-8)):
-      var c = d[i]
-      if c.refcount >=% rcIncrement:
-        c.refcount = c.refcount and not colorMask
-        d[i] = res
-        break addToZCT
-    add(gch.zct, res)
+  addNewObjToZCT(res)
   when logGC: writeCell("new cell", res)
   gcTrace(res, csAllocated)  
   release(gch)
diff --git a/lib/system/mmdisp.nim b/lib/system/mmdisp.nim
index de604869b..bd377c5df 100755
--- a/lib/system/mmdisp.nim
+++ b/lib/system/mmdisp.nim
@@ -1,7 +1,7 @@
 #
 #
 #            Nimrod's Runtime Library
-#        (c) Copyright 2010 Andreas Rumpf
+#        (c) Copyright 2011 Andreas Rumpf
 #
 #    See the file "copying.txt", included in this
 #    distribution, for details about the copyright.