diff options
| -rw-r--r-- | compiler/ccgtypes.nim | 3 | ||||
| -rw-r--r-- | compiler/liftdestructors.nim | 6 | ||||
| -rw-r--r-- | lib/system/cellseqs_v2.nim | 55 | ||||
| -rw-r--r-- | lib/system/cyclebreaker.nim | 50 | ||||
| -rw-r--r-- | lib/system/cyclicrefs_v2.nim | 75 | ||||
| -rw-r--r-- | tests/arc/thamming_thinout.nim | 183 |
6 files changed, 262 insertions, 110 deletions
diff --git a/compiler/ccgtypes.nim b/compiler/ccgtypes.nim index b116a9aa6..46949831e 100644 --- a/compiler/ccgtypes.nim +++ b/compiler/ccgtypes.nim @@ -1297,7 +1297,8 @@ proc genHook(m: BModule; t: PType; info: TLineInfo; op: TTypeAttachedOp): Rope = if op == attachedTrace and m.config.selectedGC == gcOrc and containsGarbageCollectedRef(t): when false: - # re-enable this check + # unfortunately this check is wrong for an object type that only contains + # .cursor fields like 'Node' inside 'cycleleak'. internalError(m.config, info, "no attached trace proc found") result = rope("NIM_NIL") diff --git a/compiler/liftdestructors.nim b/compiler/liftdestructors.nim index a64857765..61034ef03 100644 --- a/compiler/liftdestructors.nim +++ b/compiler/liftdestructors.nim @@ -91,7 +91,7 @@ proc genWhileLoop(c: var TLiftCtx; i, dest: PNode): PNode = proc genIf(c: var TLiftCtx; cond, action: PNode): PNode = result = newTree(nkIfStmt, newTree(nkElifBranch, cond, action)) -proc genContainerOf(c: TLiftCtx; objType: PType, field, x: PSym): PNode = +proc genContainerOf(c: TLiftCtx; objType: PType, field, x: PSym): PNode = # generate: cast[ptr ObjType](cast[int](addr(x)) - offsetOf(objType.field)) let intType = getSysType(c.g, unknownLineInfo, tyInt) @@ -104,7 +104,7 @@ proc genContainerOf(c: TLiftCtx; objType: PType, field, x: PSym): PNode = let dotExpr = newNodeIT(nkDotExpr, c.info, x.typ) dotExpr.add newNodeIT(nkType, c.info, objType) dotExpr.add newSymNode(field) - + let offsetOf = genBuiltin(c.g, mOffsetOf, "offsetof", dotExpr) offsetOf.typ = intType @@ -174,7 +174,7 @@ proc fillBodyObj(c: var TLiftCtx; n, body, x, y: PNode; enforceDefaultOp: bool) caseStmt.add(branch) if emptyBranches != n.len-1: body.add(caseStmt) - c.filterDiscriminator = oldfilterDiscriminator + c.filterDiscriminator = oldfilterDiscriminator of nkRecList: for t in items(n): fillBodyObj(c, t, body, x, y, enforceDefaultOp) else: diff --git a/lib/system/cellseqs_v2.nim b/lib/system/cellseqs_v2.nim new file mode 100644 index 000000000..c71ba9726 --- /dev/null +++ b/lib/system/cellseqs_v2.nim @@ -0,0 +1,55 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2019 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +# Cell seqs for cyclebreaker and cyclicrefs_v2. + +type + CellTuple = (ptr pointer, PNimType) + CellArray = ptr UncheckedArray[CellTuple] + CellSeq = object + len, cap: int + d: CellArray + +proc add(s: var CellSeq, c: ptr pointer; t: PNimType) {.inline.} = + if s.len >= s.cap: + s.cap = s.cap * 3 div 2 + when defined(useMalloc): + var d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple)))) + else: + var d = cast[CellArray](alloc(s.cap * sizeof(CellTuple))) + copyMem(d, s.d, s.len * sizeof(CellTuple)) + when defined(useMalloc): + c_free(s.d) + else: + dealloc(s.d) + s.d = d + # XXX: realloc? + s.d[s.len] = (c, t) + inc(s.len) + +proc init(s: var CellSeq, cap: int = 1024) = + s.len = 0 + s.cap = cap + when defined(useMalloc): + s.d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple)))) + else: + s.d = cast[CellArray](alloc(s.cap * sizeof(CellTuple))) + +proc deinit(s: var CellSeq) = + when defined(useMalloc): + c_free(s.d) + else: + dealloc(s.d) + s.d = nil + s.len = 0 + s.cap = 0 + +proc pop(s: var CellSeq): (ptr pointer, PNimType) = + result = s.d[s.len-1] + dec s.len diff --git a/lib/system/cyclebreaker.nim b/lib/system/cyclebreaker.nim index e036acb53..1f320b30e 100644 --- a/lib/system/cyclebreaker.nim +++ b/lib/system/cyclebreaker.nim @@ -52,6 +52,8 @@ That seems acceptable, no leak is produced. This implies that the standard depth-first traversal suffices. ]# +include cellseqs_v2 + const colGreen = 0b000 colYellow = 0b001 @@ -72,57 +74,9 @@ proc nimIncRefCyclic(p: pointer) {.compilerRtl, inl.} = inc h.rc, rcIncrement type - CellTuple = (ptr pointer, PNimType) - CellArray = ptr UncheckedArray[CellTuple] - CellSeq = object - len, cap: int - d: CellArray - GcEnv = object traceStack: CellSeq -# ------------------- cell seq handling -------------------------------------- - -proc add(s: var CellSeq, c: ptr pointer; t: PNimType) {.inline.} = - if s.len >= s.cap: - s.cap = s.cap * 3 div 2 - when defined(useMalloc): - var d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple)))) - else: - var d = cast[CellArray](alloc(s.cap * sizeof(CellTuple))) - copyMem(d, s.d, s.len * sizeof(CellTuple)) - when defined(useMalloc): - c_free(s.d) - else: - dealloc(s.d) - s.d = d - # XXX: realloc? - s.d[s.len] = (c, t) - inc(s.len) - -proc init(s: var CellSeq, cap: int = 1024) = - s.len = 0 - s.cap = cap - when defined(useMalloc): - s.d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple)))) - else: - s.d = cast[CellArray](alloc(s.cap * sizeof(CellTuple))) - -proc deinit(s: var CellSeq) = - when defined(useMalloc): - c_free(s.d) - else: - dealloc(s.d) - s.d = nil - s.len = 0 - s.cap = 0 - -proc pop(s: var CellSeq): (ptr pointer, PNimType) = - result = s.d[s.len-1] - dec s.len - -# ---------------------------------------------------------------------------- - proc trace(p: pointer; desc: PNimType; j: var GcEnv) {.inline.} = when false: cprintf("[Trace] desc: %p %p\n", desc, p) diff --git a/lib/system/cyclicrefs_v2.nim b/lib/system/cyclicrefs_v2.nim index 0dd669925..819cb2bd0 100644 --- a/lib/system/cyclicrefs_v2.nim +++ b/lib/system/cyclicrefs_v2.nim @@ -14,6 +14,8 @@ # "Cyclic reference counting" by Rafael Dueire Lins # R.D. Lins / Information Processing Letters 109 (2008) 71–78 +include cellseqs_v2 + const colGreen = 0b000 colYellow = 0b001 @@ -45,58 +47,10 @@ proc markCyclic*[T](x: ref T) {.inline.} = h.setColor colYellow type - CellTuple = (Cell, PNimType) - CellArray = ptr UncheckedArray[CellTuple] - CellSeq = object - len, cap: int - d: CellArray - GcEnv = object traceStack: CellSeq jumpStack: CellSeq -# ------------------- cell seq handling -------------------------------------- - -proc add(s: var CellSeq, c: Cell; t: PNimType) {.inline.} = - if s.len >= s.cap: - s.cap = s.cap * 3 div 2 - when defined(useMalloc): - var d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple)))) - else: - var d = cast[CellArray](alloc(s.cap * sizeof(CellTuple))) - copyMem(d, s.d, s.len * sizeof(CellTuple)) - when defined(useMalloc): - c_free(s.d) - else: - dealloc(s.d) - s.d = d - # XXX: realloc? - s.d[s.len] = (c, t) - inc(s.len) - -proc init(s: var CellSeq, cap: int = 1024) = - s.len = 0 - s.cap = cap - when defined(useMalloc): - s.d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple)))) - else: - s.d = cast[CellArray](alloc(s.cap * sizeof(CellTuple))) - -proc deinit(s: var CellSeq) = - when defined(useMalloc): - c_free(s.d) - else: - dealloc(s.d) - s.d = nil - s.len = 0 - s.cap = 0 - -proc pop(s: var CellSeq): (Cell, PNimType) = - result = s.d[s.len-1] - dec s.len - -# ---------------------------------------------------------------------------- - proc trace(s: Cell; desc: PNimType; j: var GcEnv) {.inline.} = if desc.traceImpl != nil: var p = s +! sizeof(RefHeader) @@ -116,7 +70,10 @@ proc collect(s: Cell; desc: PNimType; j: var GcEnv) = s.setColor colGreen trace(s, desc, j) while j.traceStack.len > 0: - let (t, desc) = j.traceStack.pop() + let (p, desc) = j.traceStack.pop() + let t = head(p[]) + #Remove(<S, T>): + p[] = nil if t.color == colRed: t.setColor colGreen trace(t, desc, j) @@ -129,7 +86,8 @@ proc markRed(s: Cell; desc: PNimType; j: var GcEnv) = s.setColor colRed trace(s, desc, j) while j.traceStack.len > 0: - let (t, desc) = j.traceStack.pop() + let (p, desc) = j.traceStack.pop() + let t = head(p[]) when traceCollector: cprintf("[Cycle dec] %p %ld color %ld in jumpstack %ld\n", t, t.rc shr rcShift, t.color, t.rc and jumpStackFlag) dec t.rc, rcIncrement @@ -137,7 +95,7 @@ proc markRed(s: Cell; desc: PNimType; j: var GcEnv) = t.rc = t.rc or jumpStackFlag when traceCollector: cprintf("[Now in jumpstack] %p %ld color %ld in jumpstack %ld\n", t, t.rc shr rcShift, t.color, t.rc and jumpStackFlag) - j.jumpStack.add(t, desc) + j.jumpStack.add(p, desc) if t.color != colRed: t.setColor colRed trace(t, desc, j) @@ -146,7 +104,8 @@ proc scanGreen(s: Cell; desc: PNimType; j: var GcEnv) = s.setColor colGreen trace(s, desc, j) while j.traceStack.len > 0: - let (t, desc) = j.traceStack.pop() + let (p, desc) = j.traceStack.pop() + let t = head(p[]) if t.color != colGreen: t.setColor colGreen trace(t, desc, j) @@ -158,15 +117,13 @@ proc nimTraceRef(q: pointer; desc: PNimType; env: pointer) {.compilerRtl.} = let p = cast[ptr pointer](q) if p[] != nil: var j = cast[ptr GcEnv](env) - var t = head(p[]) - j.traceStack.add(t, desc) + j.traceStack.add(p, desc) proc nimTraceRefDyn(q: pointer; env: pointer) {.compilerRtl.} = let p = cast[ptr pointer](q) if p[] != nil: var j = cast[ptr GcEnv](env) - var t = head(p[]) - j.traceStack.add(t, cast[ptr PNimType](p[])[]) + j.traceStack.add(p, cast[ptr PNimType](p[])[]) proc scan(s: Cell; desc: PNimType; j: var GcEnv) = when traceCollector: @@ -181,7 +138,8 @@ proc scan(s: Cell; desc: PNimType; j: var GcEnv) = # that are still alive; we also need to mark what they # refer to as alive: while j.jumpStack.len > 0: - let (t, desc) = j.jumpStack.pop + let (p, desc) = j.jumpStack.pop + let t = head(p[]) # not in jump stack anymore! t.rc = t.rc and not jumpStackFlag if t.color == colRed and (t.rc and not rcMask) >= 0: @@ -202,7 +160,8 @@ proc traceCycle(s: Cell; desc: PNimType) {.noinline.} = markRed(s, desc, j) scan(s, desc, j) while j.jumpStack.len > 0: - let (t, desc) = j.jumpStack.pop + let (p, desc) = j.jumpStack.pop + let t = head(p[]) # not in jump stack anymore! t.rc = t.rc and not jumpStackFlag deinit j.jumpStack diff --git a/tests/arc/thamming_thinout.nim b/tests/arc/thamming_thinout.nim new file mode 100644 index 000000000..65c34ef49 --- /dev/null +++ b/tests/arc/thamming_thinout.nim @@ -0,0 +1,183 @@ +discard """ + cmd: "nim c --gc:orc -d:nimThinout -r $file" + output: '''The first 20 hammings are: 1 2 3 4 5 MEM IS 0''' +""" + +# test Nim Hamming Number Lazy List algo with reference counts and not... +# compile with "-d:release -d:danger" and test with various +# memory managment GC's, allocators, threading, etc. + +from times import epochTime +from math import log2 + +# implement our own basic BigInt so the bigints library isn't necessary... +type + BigInt = object + digits: seq[uint32] +let zeroBigInt = BigInt(digits: @[ 0'u32 ]) +let oneBigInt = BigInt(digits: @[ 1'u32 ]) + +proc shladd(bi: var BigInt; n: int; a: BigInt) = + var cry = 0'u64 + for i in 0 ..< min(bi.digits.len, a.digits.len): + cry += (bi.digits[i].uint64 shl n) + a.digits[i].uint64 + bi.digits[i] = cry.uint32 + cry = cry shr 32 + if cry > 0'u64: + bi.digits.add cry.uint32 + +proc `$`(x: BigInt): string = + if x.digits.len == 0 or (x.digits.len == 1 and x.digits[0] == 0'u32): + return "0" + var n = x + var msd = n.digits.high + result = "" + while msd >= 0: + if n.digits[msd] == 0'u32: msd.dec; continue + var brw = 0.uint64 + for i in countdown(msd, 0): + let dvdnd = n.digits[i].uint64 + (brw shl 32) + let q = dvdnd div 10'u64; brw = dvdnd - q*10'u64; n.digits[i] = q.uint32 + result &= $brw + for i in 0 .. result.high shr 1: + let tmp = result[^(i + 1)] + result[^(i + 1)] = result[i] + result[i] = tmp + +proc convertTrival2BigInt(tpl: (uint32, uint32, uint32)): BigInt = + result = oneBigInt + let (x2, x3, x5) = tpl + for _ in 1 .. x2: result.shladd 1, zeroBigInt + for _ in 1 .. x3: result.shladd 1, result + for _ in 1 .. x5: result.shladd 2, result + +type LogRep = (float64, (uint32, uint32, uint32)) +type LogRepf = proc(x: LogRep): LogRep +const one: LogRep = (0.0f64, (0u32, 0u32, 0u32)) +proc `<`(me: LogRep, othr: LogRep): bool = me[0] < othr[0] + +const lb2 = 1.0'f64 +const lb3 = 3.0'f64.log2 +const lb5 = 5.0'f64.log2 + +proc mul2(me: LogRep): LogRep = + let (lr, tpl) = me; let (x2, x3, x5) = tpl + (lr + lb2, (x2 + 1, x3, x5)) + +proc mul3(me: LogRep): LogRep = + let (lr, tpl) = me; let (x2, x3, x5) = tpl + (lr + lb3, (x2, x3 + 1, x5)) + +proc mul5(me: LogRep): LogRep = + let (lr, tpl) = me; let (x2, x3, x5) = tpl + (lr + lb5, (x2, x3, x5 + 1)) + +type + LazyList = ref object + hd: LogRep + tlf: proc(): LazyList {.closure.} + tl: LazyList + +proc rest(ll: LazyList): LazyList = # not thread-safe; needs lock on thunk + if ll.tlf != nil: + ll.tl = ll.tlf() + ll.tlf = nil + ll.tl + +iterator hamming(until: int): (uint32, uint32, uint32) = + proc merge(x, y: LazyList): LazyList = + let xh = x.hd + let yh = y.hd + if xh < yh: LazyList(hd: xh, tlf: proc(): auto = merge x.rest, y) + else: LazyList(hd: yh, tlf: proc(): auto = merge x, y.rest) + proc smult(mltf: LogRepf; s: LazyList): LazyList = + proc smults(ss: LazyList): LazyList = + LazyList(hd: ss.hd.mltf, tlf: proc(): auto = ss.rest.smults) + s.smults + proc unnsm(s: LazyList, mltf: LogRepf): LazyList = + var r: LazyList = nil + let frst = LazyList(hd: one, tlf: proc(): LazyList = r) + r = if s == nil: smult mltf, frst else: s.merge smult(mltf, frst) + r + var hmpll: LazyList = ((nil.unnsm mul5).unnsm mul3).unnsm mul2 + # var hmpll: LazyList = nil; for m in [mul5, mul3, mul2]: echo one.m # ; hmpll = unnsm(hmpll, m) + yield one[1] + var cnt = 1 + while hmpll != nil: + yield hmpll.hd[1] + hmpll = hmpll.rest # almost forever + cnt.inc + if cnt > until: break + #when declared(thinout): + thinout(hmpll) + +proc main = + stdout.write "The first 20 hammings are: " + for h in hamming(4): + write stdout, h.convertTrival2BigInt, " " + + for h in hamming(200): + discard h.convertTrival2BigInt + +let mem = getOccupiedMem() +main() +echo "MEM IS ", getOccupiedMem() - mem + +#[ +result = (smults, :envP.:up)(rest(:envP.ss2)) + +proc anon = + var + :tmpD_284230 + :tmpD_284233 + :tmpD_284236 + try: + `=sink_283407`(result_283502, + `=sink_283927`(:tmpD_284236, (smults_283495, + wasMoved_284234(:tmpD_284233) + `=_284014`(:tmpD_284233, :envP_283898.:up_283899) + :tmpD_284233)) + :tmpD_284236( + `=sink_283407`(:tmpD_284230, rest_283366(:envP_283898.ss2_-283497)) + :tmpD_284230)) + finally: + `=destroy_283914`(:tmpD_284236) + `=destroy_283388`(:tmpD_284230) + +proc smuls(ss: LazyList_283350; :envP_283891): LazyList_283350 = + var :env_283913 + try: + `=destroy_283951`(:env_283913) + internalNew_43643(:env_283913) + `=_283401`(:env_283913.ss2_-283497, ss_283497) + :env_283913.:up_283899 = :envP_283891 + `=sink_283407`(result_283498, LazyList_283350(hd_283353: :envP_283891.mltf1_-283492( + :env_283913.ss2_-283497.hd_283353), tlf_283356: (:anonymous_283499, + let blitTmp_284227 = :env_283913 + wasMoved_284228(:env_283913) + blitTmp_284227))) + finally: + `=destroy_283951`(:env_283913) + +proc smul = + var + :env_283969 + :tmpD_284220 + try: + `=destroy_284008`(:env_283969) + internalNew_43643(:env_283969) + `=_283976`(:env_283969.mltf1_-283492, mltf_283492) + proc smults(ss: LazyList_283350; :envP_283891): LazyList_283350 = + result_283498 = LazyList_283350(hd_283353: mltf_283492(ss_283497.hd_283353), tlf_283356: proc ( + :envP_283898): auto_43100 = result_283502 = smults_283495(rest_283366(ss_283497))) + + `=sink_283407`(result_283494, + `=sink_283927`(:tmpD_284220, (smults_283495, + let blitTmp_284218 = :env_283969 + wasMoved_284219(:env_283969) + blitTmp_284218)) + :tmpD_284220(s_283493)) + finally: + `=destroy_283914`(:tmpD_284220) + `=destroy_284008`(:env_283969) +]# |