Commits

Antonio Cuni committed ef4527d

implement a "raw virtual buffer": the idea is that we can write values to the
buffer at arbitrary positions in the buffer: as long as we write and read to
non-overlapping pices of memory, it's all fine, but we need to detect the case
in which a write might partially overwrite the memory already stored earlier:
in that case, we raise an exception and abort the optimization

Comments (0)

Files changed (2)

pypy/jit/metainterp/optimizeopt/rawbuffer.py

+class InvalidRawOperation(Exception):
+    pass
+
+class InvalidRawWrite(InvalidRawOperation):
+    pass
+
+class InvalidRawRead(InvalidRawOperation):
+    pass
+
+class RawBuffer(object):
+    def __init__(self):
+        # the following lists represents the writes in the buffer: values[i]
+        # is the value of length lengths[i] stored at offset[i].
+        #
+        # the invariant is that they are ordered by offset, and that
+        # offset[i]+length[i] <= offset[i+1], i.e. that the writes never
+        # overlaps
+        self.offsets = []
+        self.lengths = []
+        self.values = []
+
+    def _get_memory(self):
+        """
+        NOT_RPYTHON
+        for testing only
+        """
+        return zip(self.offsets, self.lengths, self.values)
+
+    def write_value(self, offset, length, value):
+        i = 0
+        N = len(self.offsets)
+        while i < N:
+            if self.offsets[i] == offset:
+                if length != self.lengths[i]:
+                    raise InvalidRawWrite
+                # update the value at this offset
+                self.offsets[i] = offset
+                self.lengths[i] = length
+                self.values[i] = value
+                return
+            elif self.offsets[i] > offset:
+                break
+            i += 1
+        #
+        if i < len(self.offsets) and offset+length > self.offsets[i]:
+            raise InvalidRawWrite
+        # insert a new value at offset
+        self.offsets.insert(i, offset)
+        self.lengths.insert(i, length)
+        self.values.insert(i, value)
+
+    def read_value(self, offset, length):
+        i = 0
+        N = len(self.offsets)
+        while i < N:
+            if self.offsets[i] == offset:
+                if length != self.lengths[i]:
+                    raise InvalidRawRead
+                return self.values[i]
+            i += 1
+        # memory location not found: this means we are reading from
+        # uninitialized memory, give up the optimization
+        raise InvalidRawRead

pypy/jit/metainterp/optimizeopt/test/test_rawbuffer.py

+import py
+from pypy.jit.metainterp.optimizeopt.rawbuffer import (InvalidRawWrite,
+                                                       InvalidRawRead, RawBuffer)
+
+def test_write_value():
+    buf = RawBuffer()
+    buf.write_value(8, 4, 'three')
+    buf.write_value(0, 4, 'one')
+    buf.write_value(4, 2, 'two')
+    buf.write_value(12, 2, 'four')
+    assert buf._get_memory() == [
+        ( 0, 4, 'one'),
+        ( 4, 2, 'two'),
+        ( 8, 4, 'three'),
+        (12, 2, 'four'),
+        ]
+    #
+
+def test_write_value_update():
+    buf = RawBuffer()
+    buf.write_value(0, 4, 'one')
+    buf.write_value(4, 2, 'two')
+    buf.write_value(0, 4, 'ONE')
+    assert buf._get_memory() == [
+        ( 0, 4, 'ONE'),
+        ( 4, 2, 'two'),
+        ]
+
+def test_write_value_invalid_length():
+    buf = RawBuffer()
+    buf.write_value(0, 4, 'one')
+    with py.test.raises(InvalidRawWrite):
+        buf.write_value(0, 5, 'two')
+    
+def test_write_value_overlapping():
+    buf = RawBuffer()
+    buf.write_value(0, 4, 'one')
+    buf.write_value(6, 4, 'two')
+    with py.test.raises(InvalidRawWrite):
+        buf.write_value(4, 4, 'three')
+
+def test_read_value():
+    buf = RawBuffer()
+    buf.write_value(0, 4, 'one')
+    buf.write_value(4, 4, 'two')
+    assert buf.read_value(0, 4) == 'one'
+    assert buf.read_value(4, 4) == 'two'
+    with py.test.raises(InvalidRawRead):
+        buf.read_value(0, 2)
+    with py.test.raises(InvalidRawRead):
+        buf.read_value(8, 2)
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.