1. Pypy
  2. Untitled project
  3. pypy

Commits

Alex Gaynor  committed 610189b Merge

merged upstream

  • Participants
  • Parent commits 1646d57, 584c219
  • Branches default

Comments (0)

Files changed (23)

File demo/autopath.py

  • Ignore whitespace
-import sys, os
-sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))

File demo/bpnn.py

  • Ignore whitespace
-#!/usr/bin/env python
-"""
-    Translator Demo
-
-    To analyse and type-annotate the functions and class defined in
-    this module, starting from the entry point function demo(),
-    use the following command line:
-
-        ../pypy/translator/goal/translate.py bpnn.py
-
-    Insert '--help' before 'bpnn.py' for a list of translation options,
-    or see the Overview of Command Line Options for translation at
-    http://codespeak.net/pypy/dist/pypy/doc/config/commandline.html
-"""
-# Back-Propagation Neural Networks
-# 
-# Written in Python.  See http://www.python.org/
-#
-# Neil Schemenauer <nascheme@enme.ucalgary.ca>
-#
-# Modifications to the original (Armin Rigo):
-#   * import random from PyPy's lib, which is Python 2.2's plain
-#     Python implementation
-#   * print a doc about how to start the Translator
-
-import sys
-import math
-import time
-
-import autopath
-from pypy.rlib import rrandom
-
-PRINT_IT = True
-
-random = rrandom.Random(1)
-
-# calculate a random number where:  a <= rand < b
-def rand(a, b):
-    return (b-a)*random.random() + a
-
-# Make a matrix (we could use NumPy to speed this up)
-def makeMatrix(I, J, fill=0.0):
-    m = []
-    for i in range(I):
-        m.append([fill]*J)
-    return m
-
-class NN:
-    
-    def __init__(self, ni, nh, no):
-        # number of input, hidden, and output nodes
-        self.ni = ni + 1 # +1 for bias node
-        self.nh = nh
-        self.no = no
-
-        # activations for nodes
-        self.ai = [1.0]*self.ni
-        self.ah = [1.0]*self.nh
-        self.ao = [1.0]*self.no
-        
-        # create weights
-        self.wi = makeMatrix(self.ni, self.nh)
-        self.wo = makeMatrix(self.nh, self.no)
-        # set them to random vaules
-        for i in range(self.ni):
-            for j in range(self.nh):
-                self.wi[i][j] = rand(-2.0, 2.0)
-        for j in range(self.nh):
-            for k in range(self.no):
-                self.wo[j][k] = rand(-2.0, 2.0)
-
-        # last change in weights for momentum   
-        self.ci = makeMatrix(self.ni, self.nh)
-        self.co = makeMatrix(self.nh, self.no)
-
-    def update(self, inputs):
-        if len(inputs) != self.ni-1:
-            raise ValueError, 'wrong number of inputs'
-
-        # input activations
-        for i in range(self.ni-1):
-            #self.ai[i] = 1.0/(1.0+math.exp(-inputs[i]))
-            self.ai[i] = inputs[i]
-
-        # hidden activations
-        for j in range(self.nh):
-            sum = 0.0
-            for i in range(self.ni):
-                sum = sum + self.ai[i] * self.wi[i][j]
-            self.ah[j] = 1.0/(1.0+math.exp(-sum))
-
-        # output activations
-        for k in range(self.no):
-            sum = 0.0
-            for j in range(self.nh):
-                sum = sum + self.ah[j] * self.wo[j][k]
-            self.ao[k] = 1.0/(1.0+math.exp(-sum))
-
-        return self.ao[:]
-
-
-    def backPropagate(self, targets, N, M):
-        if len(targets) != self.no:
-            raise ValueError, 'wrong number of target values'
-
-        # calculate error terms for output
-        output_deltas = [0.0] * self.no
-        for k in range(self.no):
-            ao = self.ao[k]
-            output_deltas[k] = ao*(1-ao)*(targets[k]-ao)
-
-        # calculate error terms for hidden
-        hidden_deltas = [0.0] * self.nh
-        for j in range(self.nh):
-            sum = 0.0
-            for k in range(self.no):
-                sum = sum + output_deltas[k]*self.wo[j][k]
-            hidden_deltas[j] = self.ah[j]*(1-self.ah[j])*sum
-
-        # update output weights
-        for j in range(self.nh):
-            for k in range(self.no):
-                change = output_deltas[k]*self.ah[j]
-                self.wo[j][k] = self.wo[j][k] + N*change + M*self.co[j][k]
-                self.co[j][k] = change
-                #print N*change, M*self.co[j][k]
-
-        # update input weights
-        for i in range(self.ni):
-            for j in range(self.nh):
-                change = hidden_deltas[j]*self.ai[i]
-                self.wi[i][j] = self.wi[i][j] + N*change + M*self.ci[i][j]
-                self.ci[i][j] = change
-
-        # calculate error
-        error = 0.0
-        for k in range(len(targets)):
-            delta = targets[k]-self.ao[k]
-            error = error + 0.5*delta*delta
-        return error
-
-
-    def test(self, patterns):
-        for p in patterns:
-            if PRINT_IT:
-                print p[0], '->', self.update(p[0])
-
-    def weights(self):
-        if PRINT_IT:
-            print 'Input weights:'
-            for i in range(self.ni):
-                print self.wi[i]
-            print
-            print 'Output weights:'
-            for j in range(self.nh):
-                print self.wo[j]
-
-    def train(self, patterns, iterations=2000, N=0.5, M=0.1):
-        # N: learning rate
-        # M: momentum factor
-        for i in xrange(iterations):
-            error = 0.0
-            for p in patterns:
-                inputs = p[0]
-                targets = p[1]
-                self.update(inputs)
-                error = error + self.backPropagate(targets, N, M)
-            if PRINT_IT and i % 100 == 0:
-                print 'error', error
-
-
-def demo():
-    # Teach network XOR function
-    pat = [
-        [[0,0], [0]],
-        [[0,1], [1]],
-        [[1,0], [1]],
-        [[1,1], [0]]
-    ]
-
-    # create a network with two input, two hidden, and two output nodes
-    n = NN(2, 3, 1)
-    # train it with some patterns
-    n.train(pat, 2000)
-    # test it
-    n.test(pat)
-
-
-# __________  Entry point for stand-alone builds __________
-
-import time
-
-def entry_point(argv):
-    if len(argv) > 1:
-        N = int(argv[1])
-    else:
-        N = 200
-    T = time.time()
-    for i in range(N):
-        demo()
-    t1 = time.time() - T
-    print "%d iterations, %s milliseconds per iteration" % (N, 1000.0*t1/N)
-    return 0
-
-# _____ Define and setup target ___
-
-def target(*args):
-    return entry_point, None
-
-if __name__ == '__main__':
-    if len(sys.argv) == 1:
-        sys.argv.append('1')
-    entry_point(sys.argv)
-    print __doc__

File demo/dis-goal.py

  • Ignore whitespace
-"""
-An old-time classical example, and one of our first goals.
-To run on top of PyPy.
-"""
-
-import dis
-dis.dis(dis.dis)

File demo/distribution/client.py

  • Ignore whitespace
-""" This a sample client, suitable for use with server.py from this
-directory
-
-run by:
-pypy-c client.py
-"""
-
-HOST = '127.0.0.1'
-PORT = 12222
-
-from distributed.socklayer import connect
-remote_handle = connect((HOST, PORT))
-
-import code
-code.interact(local=locals())
-
-""" Things that can be done: 1. remote object access
-
-x = remote_handle.x
-assert type(x) is remote_handle.X # typecheck
-x.meth(lambda x: x + 10, 6) # remote call, with callback localy
-x.meth(remote_handle.f, 3) # remote call, remote callback
-remote_handle.sys._getframe(2).f_locals['x'] # remote frame access
-# XXX should be 'is x' and shouldn't need (2) argument
-
-# XXX next one does not work, while it should. Too much mangling with remote
-# traceback frames probably
-try:
-  x.meth(1, 2) # non-callable argument, AssertionError
-except:
-  import sys
-  e, c, tb = sys.exc_info()
-  import pdb
-  pdb.post_mortem(tb)
-"""

File demo/distribution/fileclient.py

  • Ignore whitespace
-
-""" This is sample client for a server based in fileserver.py, not counting
-initialization, code.interact and __doc__ has just 2 lines! Usage:
-
-pypy-c fileclient.py
-
-The file_opener is a proxy for remote file object. Which means you can
-perform same operations as locally, like file_opener('/etc/passwd').read()
-or file_opener('/tmp/x', 'w').write('x')
-
-pypy-c needs to be compiled with --allworkingmodules in order to have socket
-working.
-"""
-
-HOST = '127.0.0.1'
-PORT = 12221
-
-from distributed.socklayer import connect
-file_opener = connect((HOST, PORT)).open
-
-import code
-code.interact(local=locals())
-# The file_opener is a proxy for remote file object. Which means you can
-# perform same operations as locally, like file_opener('/etc/passwd').read()
-# or file_opener('/tmp/x', 'w').write('x')

File demo/distribution/fileserver.py

  • Ignore whitespace
-""" This is a sample demo showcasing file server, done by the pypy
-distribution library.
-
-Not counting __doc__ and initialization this is 2 line,
-fully operational file server,
-sample client which is in fileclient.py is included as well.
-
-run by:
-pypy-c fileserver.py
-
-pypy-c needs to be compiled with --allworkingmodules in order to have socket
-working.
-"""
-
-HOST = '127.0.0.1' # defaults to localhost, not to export your files
-PORT = 12221
-
-from distributed.socklayer import socket_loop
-socket_loop((HOST, PORT), {'open':open})

File demo/distribution/server.py

  • Ignore whitespace
-""" This is a demo exposing all globals from the current process over
-socket, to be accessible remotely.
-
-run by:
-pypy-c server.py
-
-pypy-c needs to be compiled with --allworkingmodules in order to have socket
-working.
-"""
-
-# things to export
-# function
-def f(x):
-    return x + 3
-
-# class
-class X:
-    def __init__(self):
-        self.slot = 3
-    
-    def meth(self, f, arg):
-        """ Method eating callable and calling it with an argument
-        """
-        assert callable(f)
-        return f(arg)
-
-# object
-x = X()
-
-# module
-import sys
-
-# constants
-HOST = '127.0.0.1'
-PORT = 12222
-
-from distributed.socklayer import socket_loop
-socket_loop((HOST, PORT), globals())

File demo/foodbill.py

  • Ignore whitespace
-"""
-Of historical interest: we computed the food bill of our first Gothenburg
-sprint with PyPy :-)
-"""
-
-slips=[(1, 'Kals MatMarkn', 6150, 'Chutney for Curry', 'dinner Saturday'),
-       (2, 'Kals MatMarkn', 32000, 'Spaghetti, Beer', 'dinner Monday'),
-       (2, 'Kals MatMarkn', -810, 'Deposit on Beer Bottles', 'various'),
-       (3, 'Fram', 7700, 'Rice and Curry Spice', 'dinner Saturday'),
-       (4, 'Kals MatMarkn', 25000, 'Alcohol-Free Beer, sundries', 'various'),
-       (4, 'Kals MatMarkn', -1570, "Michael's toothpaste", 'none'),
-       (4, 'Kals MatMarkn', -1690, "Laura's toothpaste", 'none'),
-       (4, 'Kals MatMarkn', -720, 'Deposit on Beer Bottles', 'various'),
-       (4, 'Kals MatMarkn', -60, 'Deposit on another Beer Bottle', 'various'),
-       (5, 'Kals MatMarkn', 26750, 'lunch bread meat cheese', 'lunch Monday'),
-       (6, 'Kals MatMarkn', 15950, 'various', 'dinner Tuesday and Thursday'),
-       (7, 'Kals MatMarkn', 3650, 'Drottningsylt, etc.', 'dinner Thursday'),
-       (8, 'Kals MatMarkn', 26150, 'Chicken and Mushroom Sauce', 'dinner Wed'),
-       (8, 'Kals MatMarkn', -2490, 'Jacob and Laura -- juice', 'dinner Wed'),
-       (8, 'Kals MatMarkn', -2990, "Chicken we didn't cook", 'dinner Wednesday'),
-       (9, 'Kals MatMarkn', 1380, 'fruit for Curry', 'dinner Saturday'),
-       (9, 'Kals MatMarkn', 1380, 'fruit for Curry', 'dinner Saturday'),
-       (10, 'Kals MatMarkn', 26900, 'Jansons Frestelse', 'dinner Sunday'),
-       (10, 'Kals MatMarkn', -540, 'Deposit on Beer Bottles', 'dinner Sunday'),
-       (11, 'Kals MatMarkn', 22650, 'lunch bread meat cheese', 'lunch Thursday'),
-       (11, 'Kals MatMarkn', -2190, 'Jacob and Laura -- juice', 'lunch Thursday'),
-       (11, 'Kals MatMarkn', -2790, 'Jacob and Laura -- cereal', 'lunch Thurs'),
-       (11, 'Kals MatMarkn', -760, 'Jacob and Laura -- milk', 'lunch Thursday'),
-       (12, 'Kals MatMarkn', 18850, 'lunch bread meat cheese', 'lunch Friday'),
-       (13, 'Kals MatMarkn', 18850, 'lunch bread meat cheese', 'guestimate Sun'),
-       (14, 'Kals MatMarkn', 18850, 'lunch bread meat cheese', 'guestimate Tues'),
-       (15, 'Kals MatMarkn', 20000, 'lunch bread meat cheese', 'guestimate Wed'),
-       (16, 'Kals MatMarkn', 42050, 'grillfest', 'dinner Friday'),
-       (16, 'Kals MatMarkn', -1350, 'Deposit on Beer Bottles', 'dinner Friday'),
-       (17, 'System Bolaget', 15500, 'Cederlunds Caloric', 'dinner Thursday'),
-       (17, 'System Bolaget', 22400, '4 x Farnese Sangiovese 56SEK', 'various'),
-       (17, 'System Bolaget', 22400, '4 x Farnese Sangiovese 56SEK', 'various'),
-       (17, 'System Bolaget', 13800, '2 x Jacobs Creek 69SEK', 'various'),
-       (18, 'J and Ls winecabinet', 10800, '2 x Parrotes 54SEK', 'various'),
-       (18, 'J and Ls winecabinet', 14700, '3 x Saint Paulin 49SEK', 'various'),
-       (18, 'J and Ls winecabinet', 10400, '2 x Farnese Sangioves 52SEK',
-        'cheaper when we bought it'),
-       (18, 'J and Ls winecabinet', 17800, '2 x Le Poiane 89SEK', 'various'),
-       (18, 'J and Ls winecabinet', 9800, '2 x Something Else 49SEK', 'various'),
-       (19, 'Konsum', 26000, 'Saturday Bread and Fruit', 'Slip MISSING'),
-       (20, 'Konsum', 15245, 'Mooseburgers', 'found slip'),
-       (21, 'Kals MatMarkn', 20650, 'Grilling', 'Friday dinner'),
-       (22, 'J and Ls freezer', 21000, 'Meat for Curry, grilling', ''),
-       (22, 'J and Ls cupboard', 3000, 'Rice', ''),
-       (22, 'J and Ls cupboard', 4000, 'Charcoal', ''),
-       (23, 'Fram', 2975, 'Potatoes', '3.5 kg @ 8.50SEK'),
-       (23, 'Fram', 1421, 'Peas', 'Thursday dinner'),
-       (24, 'Kals MatMarkn', 20650, 'Grilling', 'Friday dinner'),
-       (24, 'Kals MatMarkn', -2990, 'TP', 'None'),
-       (24, 'Kals MatMarkn', -2320, 'T-Gul', 'None')
-       ]
- 
-print [t[2] for t in slips]
-print (reduce(lambda x, y: x+y, [t[2] for t in slips], 0))/900

File demo/pickle_coroutine.py

  • Ignore whitespace
-"""
-Stackless demo.
-
-This example only works on top of a pypy-c compiled with stackless features
-and the signal module:
-
-    translate.py --stackless targetpypystandalone --withmod-signal
-
-Usage:
-
-    pypy-c pickle_coroutine.py --start demo.pickle
-
-        Start the computation.  You can interrupt it at any time by
-        pressing Ctrl-C; at this point, the state of the computing
-        coroutine is saved in demo.pickle.
-
-    pypy-c pickle_coroutine.py --resume demo.pickle
-
-        Reload the coroutine from demo.pickle and continue running it.
-        (It can be interrupted again with Ctrl-C.)
-
-This demo is documented in detail in pypy/doc/stackless.txt.
-"""
-
-try:
-    import sys, pickle, signal
-    from stackless import coroutine
-except ImportError:
-    print __doc__
-    sys.exit(2)
-
-
-def ackermann(x, y):
-    check()
-    if x == 0:
-        return y + 1
-    if y == 0:
-        return ackermann(x - 1, 1)
-    return ackermann(x - 1, ackermann(x, y - 1))
-
-# ____________________________________________________________
-
-main = coroutine.getcurrent()
-sys.setrecursionlimit(100000)
-
-interrupt_flag = False
-
-def interrupt_handler(*args):
-    global interrupt_flag
-    interrupt_flag = True
-
-def check():
-    if interrupt_flag:
-        main.switch()
-
-
-def execute(coro):
-    signal.signal(signal.SIGINT, interrupt_handler)
-    res = coro.switch()
-    if res is None and coro.is_alive:    # interrupted!
-        print "interrupted! writing %s..." % (filename,)
-        f = open(filename, 'w')
-        pickle.dump(coro, f)
-        f.close()
-        print "done"
-    else:
-        print "result:", res
-
-try:
-    operation, filename = sys.argv[1:]
-except ValueError:
-    print __doc__
-    sys.exit(2)
-
-if operation == '--start':
-    coro = coroutine()
-    coro.bind(ackermann, 3, 7)
-    print "running from the start..."
-    execute(coro)
-elif operation == '--resume':
-    print "reloading %s..." % (filename,)
-    f = open(filename)
-    coro = pickle.load(f)
-    f.close()
-    print "done, running now..."
-    execute(coro)

File demo/tproxy/persistence.py

  • Ignore whitespace
-"""
-
-This small example implements a basic orthogonal persistence 
-mechanism on top of PyPy's transparent proxies. 
-
-"""
-from tputil import make_proxy
-
-list_changeops = set('__iadd__ __imul__ __delitem__ __setitem__ __setattr__'
-                     '__delslice__ __setslice__ '
-                     'append extend insert pop remove reverse sort'.split())
-
-dict_changeops = set('__delitem__ __setitem__  __setattr__'
-                     'clear pop popitem setdefault update'.split())
-
-def ischangeop(operation): 
-    """ return True if this operation is a changing operation 
-        on known builtins (dicts, lists). 
-    """ 
-    if isinstance(operation.obj, list):
-        changeops = list_changeops 
-    elif isinstance(operation.obj, dict):
-        changeops = dict_changeops 
-    else:
-        return False
-    return operation.opname in changeops 
-
-def make_persistent_proxy(instance, storage): 
-    def perform(operation): 
-        res = operation.delegate()
-        if ischangeop(operation):
-            print "persisting after:", operation 
-            storage.dump(instance)
-        if res is not operation.proxyobj and isinstance(res, (dict, list)):
-            res = make_proxy(perform, obj=res)
-        return res
-    return make_proxy(perform, obj=instance) 
-
-def load(storage):
-    obj = storage.load()
-    return make_persistent_proxy(obj, storage) 
-    
-if __name__ == '__main__': 
-    import py 
-    storage = py.path.local("/tmp/dictpickle")
-    pdict = make_persistent_proxy({}, storage) 
-
-    # the code below is not aware of pdict being a proxy 
-    assert type(pdict) is dict
-    pdict['hello'] = 'world'       
-    pdict['somelist'] = []
-    del pdict 
-
-    newdict = load(storage) 
-    assert newdict == {'hello': 'world', 'somelist': []}
-    l = newdict['somelist']  
-    l.append(1)              # this triggers persisting the whole dict 
-    l.extend([2,3])          # this triggers persisting the whole dict 
-    del newdict, l 
-    
-    newdict = load(storage)
-    print newdict['somelist']   # will show [1,2,3]

File demo/tproxy/print_operations.py

  • Ignore whitespace
-"""
-
-This example transparently intercepts and shows operations on 
-builtin objects.  Requires the "--objspace-std-withtproxy" option. 
-
-"""
-
-from tputil import make_proxy 
-
-def make_show_proxy(instance):
-    def controller(operation):
-        print "proxy sees:", operation
-        res = operation.delegate()
-        return res
-    tproxy = make_proxy(controller, obj=instance)
-    return tproxy
-
-if __name__ == '__main__':
-    mydict = make_show_proxy({}) 
-    assert type(mydict) is dict            # this looks exactly like a dict 
-    mydict['hello'] = 'world'              # will print __setitem__
-    mydict[42] = 23                        # will print __setitem__
-    assert mydict.pop('hello') == 'world'  # will print pop
-    assert mydict.popitem() == (42,23)     # will print popitem
-
-

File pypy/config/test/test_pypyoption.py

View file
  • Ignore whitespace
 
 
 def test_frameworkgc():
-    for name in ["marksweep", "semispace"]:
+    for name in ["minimark", "semispace"]:
         conf = get_pypy_config()
         assert conf.translation.gctransformer != "framework"
         conf.translation.gc = name

File pypy/config/translationoption.py

View file
  • Ignore whitespace
 
     # gc
     ChoiceOption("gc", "Garbage Collection Strategy",
-                 ["boehm", "ref", "marksweep", "semispace", "statistics",
-                  "generation", "hybrid", "markcompact", "minimark", "none"],
+                 ["boehm", "ref", "semispace", "statistics",
+                  "generation", "hybrid", "minimark", "none"],
                   "ref", requires={
                      "ref": [("translation.rweakref", False), # XXX
                              ("translation.gctransformer", "ref")],
                      "none": [("translation.rweakref", False), # XXX
                              ("translation.gctransformer", "none")],
                      "semispace": [("translation.gctransformer", "framework")],
-                     "marksweep": [("translation.gctransformer", "framework")],
                      "statistics": [("translation.gctransformer", "framework")],
                      "generation": [("translation.gctransformer", "framework")],
                      "hybrid": [("translation.gctransformer", "framework")],
                      "boehm": [("translation.continuation", False),  # breaks
                                ("translation.gctransformer", "boehm")],
-                     "markcompact": [("translation.gctransformer", "framework")],
                      "minimark": [("translation.gctransformer", "framework")],
                      },
                   cmdline="--gc"),

File pypy/doc/garbage_collection.rst

View file
  • Ignore whitespace
 Mark and Sweep
 --------------
 
-Classical Mark and Sweep collector.  Also contains a lot of experimental
-and half-unmaintained features.  See `pypy/rpython/memory/gc/marksweep.py`_.
+Classical Mark and Sweep collector.  Also contained a lot of experimental
+and half-unmaintained features.  Was removed.
 
 Semispace copying collector
 ---------------------------
 Mark & Compact GC
 -----------------
 
+Killed in trunk.  The following documentation is for historical purposes
+only.
+
 Inspired, at least partially, by Squeak's garbage collector, this is a
 single-arena GC in which collection compacts the objects in-place.  The
 main point of this GC is to save as much memory as possible (to be not
 objects' header, in order to let the collector store temporary relation
 information in the regular headers.
 
-More details are available as comments at the start of the source
-in `pypy/rpython/memory/gc/markcompact.py`_.
-
 Minimark GC
 -----------
 

File pypy/rpython/memory/gc/base.py

View file
  • Ignore whitespace
     def write_barrier(self, newvalue, addr_struct):
         pass
 
-    def statistics(self, index):
-        return -1
-
     def size_gc_header(self, typeid=0):
         return self.gcheaderbuilder.size_gc_header
 
     def set_max_heap_size(self, size):
         raise NotImplementedError
 
-    def x_swap_pool(self, newpool):
-        return newpool
-
-    def x_clone(self, clonedata):
-        raise RuntimeError("no support for x_clone in the GC")
-
     def trace(self, obj, callback, arg):
         """Enumerate the locations inside the given obj that can contain
         GC pointers.  For each such location, callback(pointer, arg) is
 def choose_gc_from_config(config):
     """Return a (GCClass, GC_PARAMS) from the given config object.
     """
-    if config.translation.gctransformer != "framework":   # for tests
-        config.translation.gc = "marksweep"     # crash if inconsistent
+    if config.translation.gctransformer != "framework":
+        raise AssertionError("fix this test")
 
-    classes = {"marksweep": "marksweep.MarkSweepGC",
-               "statistics": "marksweep.PrintingMarkSweepGC",
-               "semispace": "semispace.SemiSpaceGC",
+    classes = {"semispace": "semispace.SemiSpaceGC",
                "generation": "generation.GenerationGC",
                "hybrid": "hybrid.HybridGC",
-               "markcompact" : "markcompact.MarkCompactGC",
                "minimark" : "minimark.MiniMarkGC",
                }
     try:

File pypy/rpython/memory/gc/markcompact.py

  • Ignore whitespace
-from pypy.rpython.lltypesystem import lltype, llmemory, llarena, llgroup
-from pypy.rpython.memory.gc.base import MovingGCBase
-from pypy.rpython.memory.gc import env
-from pypy.rlib.debug import ll_assert, have_debug_prints
-from pypy.rlib.debug import debug_print, debug_start, debug_stop
-from pypy.rpython.memory.support import get_address_stack, get_address_deque
-from pypy.rpython.memory.support import AddressDict
-from pypy.rpython.lltypesystem.llmemory import NULL, raw_malloc_usage
-from pypy.rlib.rarithmetic import ovfcheck, LONG_BIT, intmask
-from pypy.rpython.lltypesystem.lloperation import llop
-from pypy.rlib.objectmodel import we_are_translated, running_on_llinterp
-from pypy.rpython.lltypesystem import rffi
-from pypy.rpython.memory.gcheader import GCHeaderBuilder
-from pypy.rlib.rarithmetic import is_valid_int
-
-
-# Mark'n'compact garbage collector
-#
-# main point of this GC is to save as much memory as possible
-# (not to be worse than semispace), but avoid having peaks of
-# memory during collection. Inspired, at least partly by squeak's
-# garbage collector
-
-# so, the idea as now is:
-
-# this gc works more or less like semispace, but has some essential
-# differencies. The main difference is that we have separate phases of
-# marking and assigning pointers, hence order of objects is preserved.
-# This means we can reuse the same space, overwriting it as we collect.
-
-# so the algorithm itself is performed in 3 stages (modulo weakrefs and
-# finalizers):
-
-# 1. We mark alive objects
-# 2. We walk all objects and assign forward pointers in the same order,
-#    also updating all references
-# 3. We compact the space by moving.  We use 'arena_new_view' trick, which
-#    looks like new space to tests, but compiles to the same pointer.
-#    Also we use raw_memmove in case the object overlaps with its destination.
-
-# After each collection, we bump 'next_collect_after' which is a marker
-# where to start each collection.  It should be exponential (but less
-# than 2) from the size occupied by objects so far.
-
-# field optimization - we don't need forward pointer and flags at the same
-# time. Instead we copy the TIDs in a list when we know how many objects are
-# alive, and store the forward pointer in the old object header.
-
-first_gcflag_bit = LONG_BIT//2
-first_gcflag = 1 << first_gcflag_bit
-GCFLAG_HASHTAKEN = first_gcflag << 0      # someone already asked for the hash
-GCFLAG_HASHFIELD = first_gcflag << 1      # we have an extra hash field
-# note that only the first 2 bits are preserved during a collection!
-GCFLAG_MARKBIT   = intmask(first_gcflag << (LONG_BIT//2-1))
-assert GCFLAG_MARKBIT < 0     # should be 0x80000000
-
-GCFLAG_SAVED_HASHTAKEN = GCFLAG_HASHTAKEN >> first_gcflag_bit
-GCFLAG_SAVED_HASHFIELD = GCFLAG_HASHFIELD >> first_gcflag_bit
-
-
-TID_TYPE = llgroup.HALFWORD
-BYTES_PER_TID = rffi.sizeof(TID_TYPE)
-TID_BACKUP = rffi.CArray(TID_TYPE)
-
-def translated_to_c():
-    return we_are_translated() and not running_on_llinterp
-
-
-class MarkCompactGC(MovingGCBase):
-    HDR = lltype.Struct('header', ('tid', lltype.Signed))
-    typeid_is_in_field = 'tid'
-    withhash_flag_is_in_field = 'tid', GCFLAG_HASHFIELD
-    # ^^^ all prebuilt objects have GCFLAG_HASHTAKEN, but only some have
-    #     GCFLAG_HASHFIELD (and then they are one word longer).
-
-    # The default space size is 1.9375 GB, i.e. almost 2 GB, allocated as
-    # a big mmap.  The process does not actually consume that space until
-    # needed, of course.
-    TRANSLATION_PARAMS = {'space_size': int((1 + 15.0/16)*1024*1024*1024),
-                          'min_next_collect_after': 16*1024*1024}   # 16MB
-
-    malloc_zero_filled = False
-    inline_simple_malloc = True
-    inline_simple_malloc_varsize = True
-    #total_collection_time = 0.0
-    #total_collection_count = 0
-
-    free = NULL
-    next_collect_after = -1
-
-    def __init__(self, config, space_size=4096,
-                 min_next_collect_after=128, **kwds):
-        import py
-        py.test.skip("the 'markcompact' gc needs fixing for custom tracers")
-        #
-        MovingGCBase.__init__(self, config, **kwds)
-        self.space_size = space_size
-        self.min_next_collect_after = min_next_collect_after
-
-    def next_collection(self, used_space, num_objects_so_far, requested_size):
-        used_space += BYTES_PER_TID * num_objects_so_far
-        ll_assert(used_space <= self.space_size,
-                  "used_space + num_objects_so_far overflow")
-        try:
-            next = (used_space // 3) * 2 + requested_size
-        except OverflowError:
-            next = self.space_size
-        if next < self.min_next_collect_after:
-            next = self.min_next_collect_after
-        if next > self.space_size - used_space:
-            next = self.space_size - used_space
-        # The value we return guarantees that used_space + next <= space_size,
-        # with 'BYTES_PER_TID*num_objects_so_far' included in used_space.
-        # Normally, the value we return should also be at least requested_size
-        # unless we are out of memory.
-        return next
-
-    def setup(self):
-        envsize = env.read_from_env('PYPY_MARKCOMPACTGC_MAX')
-        if envsize >= 4096:
-            self.space_size = envsize & ~4095
-        mincollect = env.read_from_env('PYPY_MARKCOMPACTGC_MIN')
-        if mincollect >= 4096:
-            self.min_next_collect_after = mincollect
-
-        #self.program_start_time = time.time()
-        self.space = llarena.arena_malloc(self.space_size, False)
-        if not self.space:
-            raise CannotAllocateGCArena
-        self.free = self.space
-        MovingGCBase.setup(self)
-        self.objects_with_finalizers = self.AddressDeque()
-        self.tid_backup = lltype.nullptr(TID_BACKUP)
-        self.next_collect_after = self.next_collection(0, 0, 0)
-
-    def init_gc_object(self, addr, typeid16, flags=0):
-        hdr = llmemory.cast_adr_to_ptr(addr, lltype.Ptr(self.HDR))
-        hdr.tid = self.combine(typeid16, flags)
-
-    def init_gc_object_immortal(self, addr, typeid16, flags=0):
-        hdr = llmemory.cast_adr_to_ptr(addr, lltype.Ptr(self.HDR))
-        flags |= GCFLAG_HASHTAKEN | GCFLAG_MARKBIT
-        # All prebuilt GC objects have the GCFLAG_MARKBIT always set.
-        # That's convenient to make the GC always think that they
-        # survive the current collection.
-        hdr.tid = self.combine(typeid16, flags)
-
-    def _get_memory(self, totalsize):
-        # also counts the space that will be needed during the following
-        # collection to store the TID
-        requested_size = raw_malloc_usage(totalsize) + BYTES_PER_TID
-        self.next_collect_after -= requested_size
-        if self.next_collect_after < 0:
-            result = self.obtain_free_space(requested_size)
-        else:
-            result = self.free
-        self.free += totalsize
-        llarena.arena_reserve(result, totalsize)
-        return result
-    _get_memory._always_inline_ = True
-
-    def _get_totalsize_var(self, nonvarsize, itemsize, length):
-        try:
-            varsize = ovfcheck(itemsize * length)
-        except OverflowError:
-            raise MemoryError
-        # Careful to detect overflows.  The following works even if varsize
-        # is almost equal to sys.maxint; morever, self.space_size is known
-        # to be at least 4095 bytes smaller than sys.maxint, so this function
-        # always raises instead of returning an integer >= sys.maxint-4095.
-        if (raw_malloc_usage(varsize) > self.space_size -
-                                        raw_malloc_usage(nonvarsize)):
-            raise MemoryError
-        return llarena.round_up_for_allocation(nonvarsize + varsize)
-    _get_totalsize_var._always_inline_ = True
-
-    def _setup_object(self, result, typeid16, has_finalizer):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        self.init_gc_object(result, typeid16)
-        if has_finalizer:
-            self.objects_with_finalizers.append(result + size_gc_header)
-        return llmemory.cast_adr_to_ptr(result+size_gc_header, llmemory.GCREF)
-    _setup_object._always_inline_ = True
-
-    def malloc_fixedsize(self, typeid16, size,
-                         has_finalizer=False, contains_weakptr=False):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        totalsize = size_gc_header + size
-        result = self._get_memory(totalsize)
-        return self._setup_object(result, typeid16, has_finalizer)
-
-    def malloc_fixedsize_clear(self, typeid16, size,
-                               has_finalizer=False, contains_weakptr=False):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        totalsize = size_gc_header + size
-        result = self._get_memory(totalsize)
-        llmemory.raw_memclear(result, totalsize)
-        return self._setup_object(result, typeid16, has_finalizer)
-
-    def malloc_varsize_clear(self, typeid16, length, size, itemsize,
-                             offset_to_length):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        nonvarsize = size_gc_header + size
-        totalsize = self._get_totalsize_var(nonvarsize, itemsize, length)
-        result = self._get_memory(totalsize)
-        llmemory.raw_memclear(result, totalsize)
-        (result + size_gc_header + offset_to_length).signed[0] = length
-        return self._setup_object(result, typeid16, False)
-
-    def obtain_free_space(self, requested_size):
-        if self.free == NULL:
-            return self._emergency_initial_block(requested_size)
-        while True:
-            executed_some_finalizers = self.markcompactcollect(requested_size)
-            self.next_collect_after -= requested_size
-            if self.next_collect_after >= 0:
-                break    # ok
-            else:
-                if executed_some_finalizers:
-                    pass   # try again to do a collection
-                else:
-                    raise MemoryError
-        return self.free
-    obtain_free_space._dont_inline_ = True
-
-    def _emergency_initial_block(self, requested_size):
-        # xxx before the GC is fully setup, we might get there.  Hopefully
-        # we will only allocate a couple of strings, e.g. in read_from_env().
-        # Just allocate them raw and leak them.
-        debug_start("gc-initial-block")
-        debug_print("leaking", requested_size, "bytes")
-        debug_stop("gc-initial-block")
-        return llmemory.raw_malloc(requested_size)
-
-    def collect(self, gen=0):
-        self.markcompactcollect()
-
-    def markcompactcollect(self, requested_size=0):
-        self.debug_collect_start(requested_size)
-        self.debug_check_consistency()
-        #
-        # Mark alive objects
-        #
-        self.to_see = self.AddressDeque()
-        self.trace_from_roots()
-        self.to_see.delete()
-        #
-        # Prepare new views on the same memory
-        #
-        toaddr = llarena.arena_new_view(self.space)
-        maxnum = self.space_size - (self.free - self.space)
-        maxnum /= BYTES_PER_TID
-        llarena.arena_reserve(self.free, llmemory.sizeof(TID_BACKUP, maxnum))
-        self.tid_backup = llmemory.cast_adr_to_ptr(self.free,
-                                                   lltype.Ptr(TID_BACKUP))
-        #
-        # Walk all objects and assign forward pointers in the same order,
-        # also updating all references
-        #
-        self.update_forward_pointers(toaddr, maxnum)
-        if (self.run_finalizers.non_empty() or
-            self.objects_with_finalizers.non_empty()):
-            self.update_run_finalizers()
-
-        self.update_objects_with_id()
-        self.compact()
-        #
-        self.tid_backup = lltype.nullptr(TID_BACKUP)
-        self.free = self.finaladdr
-        self.next_collect_after = self.next_collection(self.finaladdr - toaddr,
-                                                       self.num_alive_objs,
-                                                       requested_size)
-        #
-        if not translated_to_c():
-            remaining_size = (toaddr + self.space_size) - self.finaladdr
-            llarena.arena_reset(self.finaladdr, remaining_size, False)
-            llarena.arena_free(self.space)
-            self.space = toaddr
-        #
-        self.debug_check_consistency()
-        self.debug_collect_finish()
-        if self.next_collect_after < 0:
-            raise MemoryError
-        #
-        if self.run_finalizers.non_empty():
-            self.execute_finalizers()
-            return True      # executed some finalizers
-        else:
-            return False     # no finalizer executed
-
-    def debug_collect_start(self, requested_size):
-        if 1:# have_debug_prints():
-            debug_start("gc-collect")
-            debug_print()
-            debug_print(".----------- Full collection -------------------")
-            debug_print("| requested size:",
-                        requested_size)
-            #start_time = time.time()
-            #return start_time
-        #return -1
-
-    def debug_collect_finish(self):
-        if 1:# start_time != -1:
-            #end_time = time.time()
-            #elapsed_time = end_time - start_time
-            #self.total_collection_time += elapsed_time
-            #self.total_collection_count += 1
-            #total_program_time = end_time - self.program_start_time
-            #ct = self.total_collection_time
-            #cc = self.total_collection_count
-            #debug_print("| number of collections so far       ", 
-            #            cc)
-            debug_print("| total space size                   ", 
-                        self.space_size)
-            debug_print("| number of objects alive            ", 
-                        self.num_alive_objs)
-            debug_print("| used space size                    ", 
-                        self.free - self.space)
-            debug_print("| next collection after              ", 
-                        self.next_collect_after)
-            #debug_print("| total collections per second:      ",
-            #            cc / total_program_time)
-            #debug_print("| total time in markcompact-collect: ",
-            #            ct, "seconds")
-            #debug_print("| percentage collection<->total time:",
-            #            ct * 100.0 / total_program_time, "%")
-            debug_print("`----------------------------------------------")
-            debug_stop("gc-collect")
-
-
-    def update_run_finalizers(self):
-        if self.run_finalizers.non_empty():     # uncommon case
-            run_finalizers = self.AddressDeque()
-            while self.run_finalizers.non_empty():
-                obj = self.run_finalizers.popleft()
-                run_finalizers.append(self.get_forwarding_address(obj))
-            self.run_finalizers.delete()
-            self.run_finalizers = run_finalizers
-        #
-        objects_with_finalizers = self.AddressDeque()
-        while self.objects_with_finalizers.non_empty():
-            obj = self.objects_with_finalizers.popleft()
-            objects_with_finalizers.append(self.get_forwarding_address(obj))
-        self.objects_with_finalizers.delete()
-        self.objects_with_finalizers = objects_with_finalizers
-
-    def header(self, addr):
-        # like header(), but asserts that we have a normal header
-        hdr = MovingGCBase.header(self, addr)
-        if not we_are_translated():
-            assert isinstance(hdr.tid, llgroup.CombinedSymbolic)
-        return hdr
-
-    def header_forwarded(self, addr):
-        # like header(), but asserts that we have a forwarding header
-        hdr = MovingGCBase.header(self, addr)
-        if not we_are_translated():
-            assert is_valid_int(hdr.tid)
-        return hdr
-
-    def combine(self, typeid16, flags):
-        return llop.combine_ushort(lltype.Signed, typeid16, flags)
-
-    def get_type_id(self, addr):
-        tid = self.header(addr).tid
-        return llop.extract_ushort(llgroup.HALFWORD, tid)
-
-    def trace_from_roots(self):
-        self.root_walker.walk_roots(
-            MarkCompactGC._mark_root,  # stack roots
-            MarkCompactGC._mark_root,  # static in prebuilt non-gc structures
-            MarkCompactGC._mark_root)  # static in prebuilt gc objects
-        if (self.objects_with_finalizers.non_empty() or
-            self.run_finalizers.non_empty()):
-            self.trace_from_objects_with_finalizers()
-        self._trace_and_mark()
-
-    def _trace_and_mark(self):
-        while self.to_see.non_empty():
-            obj = self.to_see.popleft()
-            self.trace(obj, self._mark_obj, None)
-
-    def _mark_obj(self, pointer, ignored):
-        self.mark(pointer.address[0])
-
-    def _mark_root(self, root):
-        self.mark(root.address[0])
-
-    def mark(self, obj):
-        if not self.marked(obj):
-            self.header(obj).tid |= GCFLAG_MARKBIT
-            self.to_see.append(obj)
-
-    def marked(self, obj):
-        # should work both if tid contains a CombinedSymbolic (for dying
-        # objects, at this point), or a plain integer.
-        return MovingGCBase.header(self, obj).tid & GCFLAG_MARKBIT
-
-    def toaddr_smaller_than_fromaddr(self, toaddr, fromaddr):
-        if translated_to_c():
-            return toaddr < fromaddr
-        else:
-            # convert the addresses to integers, because they are
-            # theoretically not from the same arena
-            return toaddr - self.base_forwarding_addr < fromaddr - self.space
-
-    def update_forward_pointers(self, toaddr, maxnum):
-        self.base_forwarding_addr = base_forwarding_addr = toaddr
-        fromaddr = self.space
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        num = 0
-        while fromaddr < self.free:
-            hdr = llmemory.cast_adr_to_ptr(fromaddr, lltype.Ptr(self.HDR))
-            obj = fromaddr + size_gc_header
-            # compute the original object size, including the
-            # optional hash field
-            basesize = size_gc_header + self.get_size(obj)
-            totalsrcsize = basesize
-            if hdr.tid & GCFLAG_HASHFIELD:  # already a hash field, copy it too
-                totalsrcsize += llmemory.sizeof(lltype.Signed)
-            #
-            if self.marked(obj):
-                # the object is marked as suriving.  Compute the new object
-                # size
-                totaldstsize = totalsrcsize
-                if (hdr.tid & (GCFLAG_HASHTAKEN|GCFLAG_HASHFIELD) ==
-                               GCFLAG_HASHTAKEN):
-                    # grow a new hash field -- with the exception: if
-                    # the object actually doesn't move, don't
-                    # (otherwise, we get a bogus toaddr > fromaddr)
-                    if self.toaddr_smaller_than_fromaddr(toaddr, fromaddr):
-                        totaldstsize += llmemory.sizeof(lltype.Signed)
-                #
-                if not translated_to_c():
-                    llarena.arena_reserve(toaddr, basesize)
-                    if (raw_malloc_usage(totaldstsize) >
-                        raw_malloc_usage(basesize)):
-                        llarena.arena_reserve(toaddr + basesize,
-                                              llmemory.sizeof(lltype.Signed))
-                #
-                # save the field hdr.tid in the array tid_backup
-                ll_assert(num < maxnum, "overflow of the tid_backup table")
-                self.tid_backup[num] = self.get_type_id(obj)
-                num += 1
-                # compute forward_offset, the offset to the future copy
-                # of this object
-                forward_offset = toaddr - base_forwarding_addr
-                # copy the first two gc flags in forward_offset
-                ll_assert(forward_offset & 3 == 0, "misalignment!")
-                forward_offset |= (hdr.tid >> first_gcflag_bit) & 3
-                hdr.tid = forward_offset | GCFLAG_MARKBIT
-                ll_assert(self.marked(obj), "re-marking object failed!")
-                # done
-                toaddr += totaldstsize
-            #
-            fromaddr += totalsrcsize
-            if not translated_to_c():
-                assert toaddr - base_forwarding_addr <= fromaddr - self.space
-        self.num_alive_objs = num
-        self.finaladdr = toaddr
-
-        # now update references
-        self.root_walker.walk_roots(
-            MarkCompactGC._update_ref,  # stack roots
-            MarkCompactGC._update_ref,  # static in prebuilt non-gc structures
-            MarkCompactGC._update_ref)  # static in prebuilt gc objects
-        self.walk_marked_objects(MarkCompactGC.trace_and_update_ref)
-
-    def walk_marked_objects(self, callback):
-        num = 0
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        fromaddr = self.space
-        toaddr = self.base_forwarding_addr
-        while fromaddr < self.free:
-            hdr = llmemory.cast_adr_to_ptr(fromaddr, lltype.Ptr(self.HDR))
-            obj = fromaddr + size_gc_header
-            survives = self.marked(obj)
-            if survives:
-                typeid = self.get_typeid_from_backup(num)
-                num += 1
-            else:
-                typeid = self.get_type_id(obj)
-            baseobjsize = self._get_size_for_typeid(obj, typeid)
-            basesize = size_gc_header + baseobjsize
-            totalsrcsize = basesize
-            #
-            if survives:
-                grow_hash_field = False
-                if hdr.tid & GCFLAG_SAVED_HASHFIELD:
-                    totalsrcsize += llmemory.sizeof(lltype.Signed)
-                totaldstsize = totalsrcsize
-                if (hdr.tid & (GCFLAG_SAVED_HASHTAKEN|GCFLAG_SAVED_HASHFIELD)
-                            == GCFLAG_SAVED_HASHTAKEN):
-                    if self.toaddr_smaller_than_fromaddr(toaddr, fromaddr):
-                        grow_hash_field = True
-                        totaldstsize += llmemory.sizeof(lltype.Signed)
-                callback(self, obj, typeid, basesize, toaddr, grow_hash_field)
-                toaddr += totaldstsize
-            else:
-                if hdr.tid & GCFLAG_HASHFIELD:
-                    totalsrcsize += llmemory.sizeof(lltype.Signed)
-            #
-            fromaddr += totalsrcsize
-    walk_marked_objects._annspecialcase_ = 'specialize:arg(1)'
-
-    def trace_and_update_ref(self, obj, typeid, _1, _2, _3):
-        """Enumerate the locations inside the given obj that can contain
-        GC pointers.  For each such location, callback(pointer, arg) is
-        called, where 'pointer' is an address inside the object.
-        Typically, 'callback' is a bound method and 'arg' can be None.
-        """
-        if self.is_gcarrayofgcptr(typeid):
-            # a performance shortcut for GcArray(gcptr)
-            length = (obj + llmemory.gcarrayofptr_lengthoffset).signed[0]
-            item = obj + llmemory.gcarrayofptr_itemsoffset
-            while length > 0:
-                self._update_ref(item)
-                item += llmemory.gcarrayofptr_singleitemoffset
-                length -= 1
-            return
-        offsets = self.offsets_to_gc_pointers(typeid)
-        i = 0
-        while i < len(offsets):
-            item = obj + offsets[i]
-            self._update_ref(item)
-            i += 1
-        if self.has_gcptr_in_varsize(typeid):
-            item = obj + self.varsize_offset_to_variable_part(typeid)
-            length = (obj + self.varsize_offset_to_length(typeid)).signed[0]
-            offsets = self.varsize_offsets_to_gcpointers_in_var_part(typeid)
-            itemlength = self.varsize_item_sizes(typeid)
-            while length > 0:
-                j = 0
-                while j < len(offsets):
-                    itemobj = item + offsets[j]
-                    self._update_ref(itemobj)
-                    j += 1
-                item += itemlength
-                length -= 1
-        else:
-            weakofs = self.weakpointer_offset(typeid)
-            if weakofs >= 0:
-                self._update_weakref(obj + weakofs)
-
-    def _update_ref(self, pointer):
-        if self.points_to_valid_gc_object(pointer):
-            pointer.address[0] = self.get_forwarding_address(
-                pointer.address[0])
-
-    def _update_weakref(self, pointer):
-        # either update the weak pointer's destination, or
-        # if it dies, write a NULL
-        if self.points_to_valid_gc_object(pointer):
-            if self.marked(pointer.address[0]):
-                pointer.address[0] = self.get_forwarding_address(
-                    pointer.address[0])
-            else:
-                pointer.address[0] = NULL
-
-    def _is_external(self, obj):
-        return not (self.space <= obj < self.free)
-
-    def get_forwarding_address(self, obj):
-        if self._is_external(obj):
-            return obj
-        return self.get_header_forwarded_addr(obj)
-
-    def get_header_forwarded_addr(self, obj):
-        tid = self.header_forwarded(obj).tid
-        ll_assert(tid & GCFLAG_MARKBIT != 0, "dying object is not forwarded")
-        GCFLAG_MASK = ~(GCFLAG_MARKBIT | 3)
-        res = (self.base_forwarding_addr + (tid & GCFLAG_MASK) +
-               self.gcheaderbuilder.size_gc_header)
-        ll_assert(res < self.finaladdr, "forwarded address >= self.finaladdr")
-        return res
-
-    def surviving(self, obj):
-        return self.marked(obj)
-
-    def get_typeid_from_backup(self, num):
-        return self.tid_backup[num]
-
-    def compact(self):
-        self.walk_marked_objects(MarkCompactGC.copy_and_compact)
-
-    def copy_and_compact(self, obj, typeid, basesize, toaddr, grow_hash_field):
-        # 'basesize' is the size without any hash field
-        # restore the normal header
-        hdr = self.header_forwarded(obj)
-        gcflags = hdr.tid & 3
-        if grow_hash_field:
-            gcflags |= GCFLAG_SAVED_HASHFIELD
-            hashvalue = self.get_identityhash_from_addr(obj)
-        elif gcflags & GCFLAG_SAVED_HASHFIELD:
-            fromaddr = llarena.getfakearenaaddress(obj)
-            fromaddr -= self.gcheaderbuilder.size_gc_header
-            hashvalue = (fromaddr + basesize).signed[0]
-        else:
-            hashvalue = 0     # not used
-        #
-        hdr.tid = self.combine(typeid, gcflags << first_gcflag_bit)
-        #
-        fromaddr = obj - self.gcheaderbuilder.size_gc_header
-        if translated_to_c():
-            llmemory.raw_memmove(fromaddr, toaddr, basesize)
-        else:
-            llmemory.raw_memcopy(fromaddr, toaddr, basesize)
-        #
-        if gcflags & GCFLAG_SAVED_HASHFIELD:
-            (toaddr + basesize).signed[0] = hashvalue
-
-    def debug_check_object(self, obj):
-        type_id = self.get_type_id(obj)
-        self.has_gcptr_in_varsize(type_id)   # checks that the type_id is valid
-        #
-        tid = self.header(obj).tid
-        if self._is_external(obj):
-            # All external objects have GCFLAG_MARKBIT and GCFLAG_HASHTAKEN
-            # set.
-            assert tid & GCFLAG_MARKBIT
-            assert tid & GCFLAG_HASHTAKEN
-        else:
-            # Non-external objects have GCFLAG_MARKBIT that should not be set
-            # at the very start or at the very end of a collection -- only
-            # temporarily during the collection.
-            assert tid & GCFLAG_MARKBIT == 0
-
-    def trace_from_objects_with_finalizers(self):
-        if self.run_finalizers.non_empty():   # uncommon case
-            new_run_finalizers = self.AddressDeque()
-            while self.run_finalizers.non_empty():
-                x = self.run_finalizers.popleft()
-                self.mark(x)
-                new_run_finalizers.append(x)
-            self.run_finalizers.delete()
-            self.run_finalizers = new_run_finalizers
-        #
-        # xxx we get to run the finalizers in a random order
-        self._trace_and_mark()
-        new_with_finalizers = self.AddressDeque()
-        while self.objects_with_finalizers.non_empty():
-            x = self.objects_with_finalizers.popleft()
-            if self.marked(x):
-                new_with_finalizers.append(x)
-            else:
-                self.run_finalizers.append(x)
-                self.mark(x)
-                self._trace_and_mark()
-        self.objects_with_finalizers.delete()
-        self.objects_with_finalizers = new_with_finalizers
-
-    def identityhash(self, gcobj):
-        # Unlike SemiSpaceGC.identityhash(), this function does not have
-        # to care about reducing top_of_space.  The reason is as
-        # follows.  When we collect, each object either moves to the
-        # left or stays where it is.  If it moves to the left (and if it
-        # has GCFLAG_HASHTAKEN), we can give it a hash field, and the
-        # end of the new object cannot move to the right of the end of
-        # the old object.  If it stays where it is, then we don't need
-        # to add the hash field.  So collecting can never actually grow
-        # the consumed size.
-        obj = llmemory.cast_ptr_to_adr(gcobj)
-        hdr = self.header(obj)
-        #
-        if hdr.tid & GCFLAG_HASHFIELD:  # the hash is in a field at the end
-            obj = llarena.getfakearenaaddress(obj) + self.get_size(obj)
-            return obj.signed[0]
-        #
-        hdr.tid |= GCFLAG_HASHTAKEN
-        return self.get_identityhash_from_addr(obj)
-
-    def get_identityhash_from_addr(self, obj):
-        if translated_to_c():
-            return llmemory.cast_adr_to_int(obj)  # direct case
-        else:
-            try:
-                adr = llarena.getfakearenaaddress(obj)   # -> arena address
-            except RuntimeError:
-                return llmemory.cast_adr_to_int(obj)  # not in an arena...
-            return adr - self.space
-
-    def get_size_incl_hash(self, obj):
-        size = self.get_size(obj)
-        hdr = self.header(obj)
-        if hdr.tid & GCFLAG_HASHFIELD:
-            size += llmemory.sizeof(lltype.Signed)
-        return size
-
-# ____________________________________________________________
-
-class CannotAllocateGCArena(Exception):
-    pass

File pypy/rpython/memory/gc/marksweep.py

  • Ignore whitespace
-from pypy.rpython.lltypesystem.llmemory import raw_malloc, raw_free
-from pypy.rpython.lltypesystem.llmemory import raw_memcopy, raw_memclear
-from pypy.rpython.lltypesystem.llmemory import NULL, raw_malloc_usage
-from pypy.rpython.memory.support import get_address_stack
-from pypy.rpython.memory.gcheader import GCHeaderBuilder
-from pypy.rpython.lltypesystem import lltype, llmemory, rffi, llgroup
-from pypy.rlib.objectmodel import free_non_gc_object
-from pypy.rpython.lltypesystem.lloperation import llop
-from pypy.rlib.rarithmetic import ovfcheck
-from pypy.rlib.debug import debug_print, debug_start, debug_stop
-from pypy.rpython.memory.gc.base import GCBase
-
-
-import sys, os
-
-##X_POOL = lltype.GcOpaqueType('gc.pool')
-##X_POOL_PTR = lltype.Ptr(X_POOL)
-##X_CLONE = lltype.GcStruct('CloneData', ('gcobjectptr', llmemory.GCREF),
-##                                       ('pool',        X_POOL_PTR))
-##X_CLONE_PTR = lltype.Ptr(X_CLONE)
-
-FL_WITHHASH = 0x01
-##FL_CURPOOL  = 0x02
-
-memoryError = MemoryError()
-class MarkSweepGC(GCBase):
-    HDR = lltype.ForwardReference()
-    HDRPTR = lltype.Ptr(HDR)
-    # need to maintain a linked list of malloced objects, since we used the
-    # systems allocator and can't walk the heap
-    HDR.become(lltype.Struct('header', ('typeid16', llgroup.HALFWORD),
-                                       ('mark', lltype.Bool),
-                                       ('flags', lltype.Char),
-                                       ('next', HDRPTR)))
-    typeid_is_in_field = 'typeid16'
-    withhash_flag_is_in_field = 'flags', FL_WITHHASH
-
-    POOL = lltype.GcStruct('gc_pool')
-    POOLPTR = lltype.Ptr(POOL)
-
-    POOLNODE = lltype.ForwardReference()
-    POOLNODEPTR = lltype.Ptr(POOLNODE)
-    POOLNODE.become(lltype.Struct('gc_pool_node', ('linkedlist', HDRPTR),
-                                                  ('nextnode', POOLNODEPTR)))
-
-    # the following values override the default arguments of __init__ when
-    # translating to a real backend.
-    TRANSLATION_PARAMS = {'start_heap_size': 8*1024*1024} # XXX adjust
-
-    def __init__(self, config, start_heap_size=4096, **kwds):
-        self.param_start_heap_size = start_heap_size
-        GCBase.__init__(self, config, **kwds)
-
-    def setup(self):
-        GCBase.setup(self)
-        self.heap_usage = 0          # at the end of the latest collection
-        self.bytes_malloced = 0      # since the latest collection
-        self.bytes_malloced_threshold = self.param_start_heap_size
-        self.total_collection_time = 0.0
-        self.malloced_objects = lltype.nullptr(self.HDR)
-        self.malloced_objects_with_finalizer = lltype.nullptr(self.HDR)
-        # these are usually only the small bits of memory that make a
-        # weakref object
-        self.objects_with_weak_pointers = lltype.nullptr(self.HDR)
-        # pools, for x_swap_pool():
-        #   'curpool' is the current pool, lazily allocated (i.e. NULL means
-        #   the current POOL object is not yet malloc'ed).  POOL objects are
-        #   usually at the start of a linked list of objects, via the HDRs.
-        #   The exception is 'curpool' whose linked list of objects is in
-        #   'self.malloced_objects' instead of in the header of 'curpool'.
-        #   POOL objects are never in the middle of a linked list themselves.
-        # XXX a likely cause for the current problems with pools is:
-        # not all objects live in malloced_objects, some also live in
-        # malloced_objects_with_finalizer and objects_with_weak_pointers
-        self.curpool = lltype.nullptr(self.POOL)
-        #   'poolnodes' is a linked list of all such linked lists.  Each
-        #   linked list will usually start with a POOL object, but it can
-        #   also contain only normal objects if the POOL object at the head
-        #   was already freed.  The objects in 'malloced_objects' are not
-        #   found via 'poolnodes'.
-        self.poolnodes = lltype.nullptr(self.POOLNODE)
-        self.collect_in_progress = False
-        self.prev_collect_end_time = 0.0
-
-    def maybe_collect(self):
-        if self.bytes_malloced > self.bytes_malloced_threshold:
-            self.collect()
-
-    def write_malloc_statistics(self, typeid16, size, result, varsize):
-        pass
-
-    def write_free_statistics(self, typeid16, result):
-        pass
-
-    def malloc_fixedsize(self, typeid16, size,
-                         has_finalizer=False, is_finalizer_light=False,
-                         contains_weakptr=False):
-        self.maybe_collect()
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        try:
-            tot_size = size_gc_header + size
-            usage = raw_malloc_usage(tot_size)
-            bytes_malloced = ovfcheck(self.bytes_malloced+usage)
-            ovfcheck(self.heap_usage + bytes_malloced)
-        except OverflowError:
-            raise memoryError
-        result = raw_malloc(tot_size)
-        if not result:
-            raise memoryError
-        hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
-        hdr.typeid16 = typeid16
-        hdr.mark = False
-        hdr.flags = '\x00'
-        if has_finalizer:
-            hdr.next = self.malloced_objects_with_finalizer
-            self.malloced_objects_with_finalizer = hdr
-        elif contains_weakptr:
-            hdr.next = self.objects_with_weak_pointers
-            self.objects_with_weak_pointers = hdr
-        else:
-            hdr.next = self.malloced_objects
-            self.malloced_objects = hdr
-        self.bytes_malloced = bytes_malloced
-        result += size_gc_header
-        #llop.debug_print(lltype.Void, 'malloc typeid', typeid16,
-        #                 '->', llmemory.cast_adr_to_int(result))
-        self.write_malloc_statistics(typeid16, tot_size, result, False)
-        return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)
-    malloc_fixedsize._dont_inline_ = True
-
-    def malloc_fixedsize_clear(self, typeid16, size,
-                               has_finalizer=False,
-                               is_finalizer_light=False,
-                               contains_weakptr=False):
-        self.maybe_collect()
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        try:
-            tot_size = size_gc_header + size
-            usage = raw_malloc_usage(tot_size)
-            bytes_malloced = ovfcheck(self.bytes_malloced+usage)
-            ovfcheck(self.heap_usage + bytes_malloced)
-        except OverflowError:
-            raise memoryError
-        result = raw_malloc(tot_size)
-        if not result:
-            raise memoryError
-        raw_memclear(result, tot_size)
-        hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
-        hdr.typeid16 = typeid16
-        hdr.mark = False
-        hdr.flags = '\x00'
-        if has_finalizer:
-            hdr.next = self.malloced_objects_with_finalizer
-            self.malloced_objects_with_finalizer = hdr
-        elif contains_weakptr:
-            hdr.next = self.objects_with_weak_pointers
-            self.objects_with_weak_pointers = hdr
-        else:
-            hdr.next = self.malloced_objects
-            self.malloced_objects = hdr
-        self.bytes_malloced = bytes_malloced
-        result += size_gc_header
-        #llop.debug_print(lltype.Void, 'malloc typeid', typeid16,
-        #                 '->', llmemory.cast_adr_to_int(result))
-        self.write_malloc_statistics(typeid16, tot_size, result, False)
-        return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)
-    malloc_fixedsize_clear._dont_inline_ = True
-
-    def malloc_varsize(self, typeid16, length, size, itemsize,
-                       offset_to_length):
-        self.maybe_collect()
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        try:
-            fixsize = size_gc_header + size
-            varsize = ovfcheck(itemsize * length)
-            tot_size = ovfcheck(fixsize + varsize)
-            usage = raw_malloc_usage(tot_size)
-            bytes_malloced = ovfcheck(self.bytes_malloced+usage)
-            ovfcheck(self.heap_usage + bytes_malloced)
-        except OverflowError:
-            raise memoryError
-        result = raw_malloc(tot_size)
-        if not result:
-            raise memoryError
-        (result + size_gc_header + offset_to_length).signed[0] = length
-        hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
-        hdr.typeid16 = typeid16
-        hdr.mark = False
-        hdr.flags = '\x00'
-        hdr.next = self.malloced_objects
-        self.malloced_objects = hdr
-        self.bytes_malloced = bytes_malloced
-            
-        result += size_gc_header
-        #llop.debug_print(lltype.Void, 'malloc_varsize length', length,
-        #                 'typeid', typeid16,
-        #                 '->', llmemory.cast_adr_to_int(result))
-        self.write_malloc_statistics(typeid16, tot_size, result, True)
-        return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)
-    malloc_varsize._dont_inline_ = True
-
-    def malloc_varsize_clear(self, typeid16, length, size, itemsize,
-                             offset_to_length):
-        self.maybe_collect()
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        try:
-            fixsize = size_gc_header + size
-            varsize = ovfcheck(itemsize * length)
-            tot_size = ovfcheck(fixsize + varsize)
-            usage = raw_malloc_usage(tot_size)
-            bytes_malloced = ovfcheck(self.bytes_malloced+usage)
-            ovfcheck(self.heap_usage + bytes_malloced)
-        except OverflowError:
-            raise memoryError
-        result = raw_malloc(tot_size)
-        if not result:
-            raise memoryError
-        raw_memclear(result, tot_size)        
-        (result + size_gc_header + offset_to_length).signed[0] = length
-        hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
-        hdr.typeid16 = typeid16
-        hdr.mark = False
-        hdr.flags = '\x00'
-        hdr.next = self.malloced_objects
-        self.malloced_objects = hdr
-        self.bytes_malloced = bytes_malloced
-            
-        result += size_gc_header
-        #llop.debug_print(lltype.Void, 'malloc_varsize length', length,
-        #                 'typeid', typeid16,
-        #                 '->', llmemory.cast_adr_to_int(result))
-        self.write_malloc_statistics(typeid16, tot_size, result, True)
-        return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)
-    malloc_varsize_clear._dont_inline_ = True
-
-    def collect(self, gen=0):
-        # 1. mark from the roots, and also the objects that objects-with-del
-        #    point to (using the list of malloced_objects_with_finalizer)
-        # 2. walk the list of objects-without-del and free the ones not marked
-        # 3. walk the list of objects-with-del and for the ones not marked:
-        #    call __del__, move the object to the list of object-without-del
-        import time
-        debug_start("gc-collect")
-        start_time = time.time()
-        self.collect_in_progress = True
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-##        llop.debug_view(lltype.Void, self.malloced_objects, self.poolnodes,
-##                        size_gc_header)
-
-        # push the roots on the mark stack
-        objects = self.AddressStack() # mark stack
-        self._mark_stack = objects
-        self.root_walker.walk_roots(
-            MarkSweepGC._mark_root,  # stack roots
-            MarkSweepGC._mark_root,  # static in prebuilt non-gc structures
-            MarkSweepGC._mark_root)  # static in prebuilt gc objects
-
-        # from this point onwards, no more mallocs should be possible
-        old_malloced = self.bytes_malloced
-        self.bytes_malloced = 0
-        curr_heap_size = 0
-        freed_size = 0
-
-        # mark objects reachable by objects with a finalizer, but not those
-        # themselves. add their size to curr_heap_size, since they always
-        # survive the collection
-        hdr = self.malloced_objects_with_finalizer
-        while hdr:
-            next = hdr.next
-            typeid = hdr.typeid16
-            gc_info = llmemory.cast_ptr_to_adr(hdr)
-            obj = gc_info + size_gc_header
-            if not hdr.mark:
-                self.add_reachable_to_stack(obj, objects)
-            addr = llmemory.cast_ptr_to_adr(hdr)
-            size = self.fixed_size(typeid)
-            if self.is_varsize(typeid):
-                length = (obj + self.varsize_offset_to_length(typeid)).signed[0]
-                size += self.varsize_item_sizes(typeid) * length
-            estimate = raw_malloc_usage(size_gc_header + size)
-            curr_heap_size += estimate
-            hdr = next
-
-        # mark thinks on the mark stack and put their descendants onto the
-        # stack until the stack is empty
-        while objects.non_empty():  #mark
-            curr = objects.pop()
-            gc_info = curr - size_gc_header
-            hdr = llmemory.cast_adr_to_ptr(gc_info, self.HDRPTR)
-            if hdr.mark:
-                continue
-            self.add_reachable_to_stack(curr, objects)
-            hdr.mark = True
-        objects.delete()
-        # also mark self.curpool
-        if self.curpool:
-            gc_info = llmemory.cast_ptr_to_adr(self.curpool) - size_gc_header
-            hdr = llmemory.cast_adr_to_ptr(gc_info, self.HDRPTR)
-            hdr.mark = True
-        # go through the list of objects containing weak pointers
-        # and kill the links if they go to dead objects
-        # if the object itself is not marked, free it
-        hdr = self.objects_with_weak_pointers
-        surviving = lltype.nullptr(self.HDR)
-        while hdr:
-            typeid = hdr.typeid16
-            next = hdr.next
-            addr = llmemory.cast_ptr_to_adr(hdr)
-            size = self.fixed_size(typeid)
-            estimate = raw_malloc_usage(size_gc_header + size)
-            if hdr.mark:
-                offset = self.weakpointer_offset(typeid)
-                hdr.mark = False
-                gc_info = llmemory.cast_ptr_to_adr(hdr)
-                weakref_obj = gc_info + size_gc_header
-                pointing_to = (weakref_obj + offset).address[0]
-                if pointing_to:
-                    gc_info_pointing_to = pointing_to - size_gc_header
-                    hdr_pointing_to = llmemory.cast_adr_to_ptr(
-                        gc_info_pointing_to, self.HDRPTR)
-                    # pointed to object will die
-                    # XXX what to do if the object has a finalizer which resurrects
-                    # the object?
-                    if not hdr_pointing_to.mark:
-                        (weakref_obj + offset).address[0] = NULL
-                hdr.next = surviving
-                surviving = hdr
-                curr_heap_size += estimate
-            else:
-                gc_info = llmemory.cast_ptr_to_adr(hdr)
-                weakref_obj = gc_info + size_gc_header
-                self.write_free_statistics(typeid, weakref_obj)
-                freed_size += estimate
-                raw_free(addr)
-            hdr = next
-        self.objects_with_weak_pointers = surviving
-        # sweep: delete objects without del if they are not marked
-        # unmark objects without del that are marked
-        firstpoolnode = lltype.malloc(self.POOLNODE, flavor='raw')
-        firstpoolnode.linkedlist = self.malloced_objects
-        firstpoolnode.nextnode = self.poolnodes
-        prevpoolnode = lltype.nullptr(self.POOLNODE)
-        poolnode = firstpoolnode
-        while poolnode:   #sweep
-            ppnext = llmemory.cast_ptr_to_adr(poolnode)
-            ppnext += llmemory.offsetof(self.POOLNODE, 'linkedlist')
-            hdr = poolnode.linkedlist
-            while hdr:  #sweep
-                typeid = hdr.typeid16
-                next = hdr.next
-                addr = llmemory.cast_ptr_to_adr(hdr)
-                size = self.fixed_size(typeid)
-                if self.is_varsize(typeid):
-                    length = (addr + size_gc_header + self.varsize_offset_to_length(typeid)).signed[0]
-                    size += self.varsize_item_sizes(typeid) * length
-                estimate = raw_malloc_usage(size_gc_header + size)
-                if hdr.mark:
-                    hdr.mark = False
-                    ppnext.address[0] = addr
-                    ppnext = llmemory.cast_ptr_to_adr(hdr)
-                    ppnext += llmemory.offsetof(self.HDR, 'next')
-                    curr_heap_size += estimate
-                else:
-                    gc_info = llmemory.cast_ptr_to_adr(hdr)
-                    obj = gc_info + size_gc_header
-                    self.write_free_statistics(typeid, obj)
-                    freed_size += estimate
-                    raw_free(addr)
-                hdr = next
-            ppnext.address[0] = llmemory.NULL
-            next = poolnode.nextnode
-            if not poolnode.linkedlist and prevpoolnode:
-                # completely empty node
-                prevpoolnode.nextnode = next
-                lltype.free(poolnode, flavor='raw')
-            else:
-                prevpoolnode = poolnode
-            poolnode = next
-        self.malloced_objects = firstpoolnode.linkedlist
-        self.poolnodes = firstpoolnode.nextnode
-        lltype.free(firstpoolnode, flavor='raw')
-        #llop.debug_view(lltype.Void, self.malloced_objects, self.malloced_objects_with_finalizer, size_gc_header)
-
-        end_time = time.time()
-        compute_time = start_time - self.prev_collect_end_time
-        collect_time = end_time - start_time
-
-        garbage_collected = old_malloced - (curr_heap_size - self.heap_usage)
-
-        if (collect_time * curr_heap_size >
-            0.02 * garbage_collected * compute_time): 
-            self.bytes_malloced_threshold += self.bytes_malloced_threshold / 2
-        if (collect_time * curr_heap_size <
-            0.005 * garbage_collected * compute_time):
-            self.bytes_malloced_threshold /= 2
-
-        # Use atleast as much memory as current live objects.
-        if curr_heap_size > self.bytes_malloced_threshold:
-            self.bytes_malloced_threshold = curr_heap_size
-
-        # Cap at 1/4 GB
-        self.bytes_malloced_threshold = min(self.bytes_malloced_threshold,
-                                            256 * 1024 * 1024)
-        self.total_collection_time += collect_time
-        self.prev_collect_end_time = end_time
-        debug_print("  malloced since previous collection:",
-                    old_malloced, "bytes")
-        debug_print("  heap usage at start of collection: ",
-                    self.heap_usage + old_malloced, "bytes")
-        debug_print("  freed:                             ",
-                    freed_size, "bytes")
-        debug_print("  new heap usage:                    ",
-                    curr_heap_size, "bytes")
-        debug_print("  total time spent collecting:       ",
-                    self.total_collection_time, "seconds")
-        debug_print("  collecting time:                   ",
-                    collect_time)
-        debug_print("  computing time:                    ",
-                    collect_time)
-        debug_print("  new threshold:                     ",
-                    self.bytes_malloced_threshold)
-##        llop.debug_view(lltype.Void, self.malloced_objects, self.poolnodes,
-##                        size_gc_header)
-        assert self.heap_usage + old_malloced == curr_heap_size + freed_size
-
-        self.heap_usage = curr_heap_size
-        hdr = self.malloced_objects_with_finalizer
-        self.malloced_objects_with_finalizer = lltype.nullptr(self.HDR)
-        last = lltype.nullptr(self.HDR)
-        while hdr:
-            next = hdr.next
-            if hdr.mark:
-                hdr.next = lltype.nullptr(self.HDR)
-                if not self.malloced_objects_with_finalizer:
-                    self.malloced_objects_with_finalizer = hdr
-                else:
-                    last.next = hdr
-                hdr.mark = False
-                last = hdr
-            else:
-                obj = llmemory.cast_ptr_to_adr(hdr) + size_gc_header
-                finalizer = self.getfinalizer(hdr.typeid16)
-                # make malloced_objects_with_finalizer consistent
-                # for the sake of a possible collection caused by finalizer
-                if not self.malloced_objects_with_finalizer:
-                    self.malloced_objects_with_finalizer = next
-                else:
-                    last.next = next
-                hdr.next = self.malloced_objects
-                self.malloced_objects = hdr
-                #llop.debug_view(lltype.Void, self.malloced_objects, self.malloced_objects_with_finalizer, size_gc_header)
-                finalizer(obj, llmemory.NULL)
-                if not self.collect_in_progress: # another collection was caused?
-                    debug_print("outer collect interrupted "
-                                "by recursive collect")
-                    debug_stop("gc-collect")
-                    return
-                if not last:
-                    if self.malloced_objects_with_finalizer == next:
-                        self.malloced_objects_with_finalizer = lltype.nullptr(self.HDR)
-                    else:
-                        # now it gets annoying: finalizer caused a malloc of something
-                        # with a finalizer
-                        last = self.malloced_objects_with_finalizer
-                        while last.next != next:
-                            last = last.next
-                            last.next = lltype.nullptr(self.HDR)
-                else:
-                    last.next = lltype.nullptr(self.HDR)
-            hdr = next
-        self.collect_in_progress = False
-        debug_stop("gc-collect")
-
-    def _mark_root(self, root):   # 'root' is the address of the GCPTR
-        gcobjectaddr = root.address[0]
-        self._mark_stack.append(gcobjectaddr)
-
-    def _mark_root_and_clear_bit(self, root):
-        gcobjectaddr = root.address[0]
-        self._mark_stack.append(gcobjectaddr)
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        gc_info = gcobjectaddr - size_gc_header
-        hdr = llmemory.cast_adr_to_ptr(gc_info, self.HDRPTR)
-        hdr.mark = False
-
-    STAT_HEAP_USAGE     = 0
-    STAT_BYTES_MALLOCED = 1
-    STATISTICS_NUMBERS  = 2
-
-    def get_type_id(self, obj):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        gc_info = obj - size_gc_header
-        hdr = llmemory.cast_adr_to_ptr(gc_info, self.HDRPTR)
-        return hdr.typeid16
-
-    def add_reachable_to_stack(self, obj, objects):
-        self.trace(obj, self._add_reachable, objects)
-
-    def _add_reachable(pointer, objects):
-        obj = pointer.address[0]
-        objects.append(obj)
-    _add_reachable = staticmethod(_add_reachable)
-
-    def statistics(self, index):
-        # no memory allocation here!
-        if index == self.STAT_HEAP_USAGE:
-            return self.heap_usage
-        if index == self.STAT_BYTES_MALLOCED:
-            return self.bytes_malloced
-        return -1
-
-    def init_gc_object(self, addr, typeid):
-        hdr = llmemory.cast_adr_to_ptr(addr, self.HDRPTR)
-        hdr.typeid16 = typeid
-        hdr.mark = False
-        hdr.flags = '\x00'
-
-    def init_gc_object_immortal(self, addr, typeid, flags=0):
-        # prebuilt gc structures always have the mark bit set
-        # ignore flags
-        hdr = llmemory.cast_adr_to_ptr(addr, self.HDRPTR)
-        hdr.typeid16 = typeid
-        hdr.mark = True
-        hdr.flags = '\x00'
-
-    # experimental support for thread cloning
-    def x_swap_pool(self, newpool):
-        raise NotImplementedError("old operation deprecated")
-
-    def x_clone(self, clonedata):
-        raise NotImplementedError("old operation deprecated")
-
-    def identityhash(self, obj):
-        obj = llmemory.cast_ptr_to_adr(obj)
-        hdr = self.header(obj)
-        if ord(hdr.flags) & FL_WITHHASH:
-            obj += self.get_size(obj)
-            return obj.signed[0]
-        else:
-            return llmemory.cast_adr_to_int(obj)
-
-
-class PrintingMarkSweepGC(MarkSweepGC):
-    _alloc_flavor_ = "raw"
-    COLLECT_EVERY = 2000
-
-    def __init__(self, config, **kwds):
-        MarkSweepGC.__init__(self, config, **kwds)
-        self.count_mallocs = 0
-
-    def maybe_collect(self):
-        self.count_mallocs += 1
-        if self.count_mallocs > self.COLLECT_EVERY:
-            self.collect()
-
-    def write_malloc_statistics(self, typeid, size, result, varsize):
-        if varsize:
-            what = "malloc_varsize"
-        else:
-            what = "malloc"
-        llop.debug_print(lltype.Void, what, typeid, " ", size, " ", result)
-