RVM
  1. RVM
  2. RVM-515

Make boot image writer traversal of object graph configurable

    Details

    • Type: New Feature New Feature
    • Status: Closed Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.0.1
    • Component/s: Infrastructure: Build
    • Labels:
      None
    • Number of attachments :
      1

      Description

      In the paper, "Boot Image Layout for Jikes RVM" to be presented at ICOOOLPS 2008, we present different ways of traversing the object graph that's written into the boot image. From the current depth first traversal the number of pages containing references can be reduced from 2666 to 1368 by a breadth first prioritized traversal. With such a scheme, modest speedups (<1%) were recorded.

        Activity

        Hide
        Ian Rogers added a comment -

        Patch that implements breadth, depth and prioritized object traversal during boot image writing. It pushes up boot image write time by about 50%. This can possibly be reduced by making the traversal parallel. Not applying patch until there's a clear story on what to do about the build time. The patch will apply against r14328 to 14342.

        Show
        Ian Rogers added a comment - Patch that implements breadth, depth and prioritized object traversal during boot image writing. It pushes up boot image write time by about 50%. This can possibly be reduced by making the traversal parallel. Not applying patch until there's a clear story on what to do about the build time. The patch will apply against r14328 to 14342.
        Ian Rogers made changes -
        Field Original Value New Value
        Attachment RVM-515.patch [ 34831 ]
        Hide
        Steve Blackburn added a comment -

        I would prefer not to see our default boot image writing time increase. The speed with which we can build the system is a key determinant of our "agility" as a platform. A more agile platform is always desirable because it is easier to work with; debugging and development are faster, which is good for the overall health of the project.

        As a side note, I notice that our build times now appear to be much slower than they were some time back. I'd like to quantify this and if I'm correct, we should make it a priority to get the build times back down.

        Since the speedups were so modest, I don't think we should be adding this to the head; better to place it in a research tracker, I think.

        Just my 2c.

        Show
        Steve Blackburn added a comment - I would prefer not to see our default boot image writing time increase. The speed with which we can build the system is a key determinant of our "agility" as a platform. A more agile platform is always desirable because it is easier to work with; debugging and development are faster, which is good for the overall health of the project. As a side note, I notice that our build times now appear to be much slower than they were some time back. I'd like to quantify this and if I'm correct, we should make it a priority to get the build times back down. Since the speedups were so modest, I don't think we should be adding this to the head; better to place it in a research tracker, I think. Just my 2c.
        Hide
        Ian Rogers added a comment -

        As a research virtual machine I think its important that as few design decisions as possible are baked in, hence working to put flexibility back into how we configure the object model. The patch separates out the writing of reference fields in the boot image to a method of its own, this extra stack frame puts pressure on the stack and slows a purely depth first approach. However, one benefit of this approach could be to allow the traversal of the object graph to be parallelized. As well as memory overhead the patch inserted extra assertions, to check for example, a JTOC entry being read as an int was actually numeric. These assertions make sense and usefully capture invariants about the code, they do come at a build time and runtime cost in all but production builds. I think 3 things stem from this:

        1) apply the patch, we shouldn't have an inflexible design and the research tracker will cause the patch to bit rot
        2) parallelize the traversal of the object graph to speed boot image writing (you can't do this without 1)
        3) look to improve our assertion mechanism, having a single global boolean probably isn't sensible - we should probably make assertions particular to the module they are within and then have some kind of defense condition (defcon) status for which assertions should be checked

        Show
        Ian Rogers added a comment - As a research virtual machine I think its important that as few design decisions as possible are baked in, hence working to put flexibility back into how we configure the object model. The patch separates out the writing of reference fields in the boot image to a method of its own, this extra stack frame puts pressure on the stack and slows a purely depth first approach. However, one benefit of this approach could be to allow the traversal of the object graph to be parallelized. As well as memory overhead the patch inserted extra assertions, to check for example, a JTOC entry being read as an int was actually numeric. These assertions make sense and usefully capture invariants about the code, they do come at a build time and runtime cost in all but production builds. I think 3 things stem from this: 1) apply the patch, we shouldn't have an inflexible design and the research tracker will cause the patch to bit rot 2) parallelize the traversal of the object graph to speed boot image writing (you can't do this without 1) 3) look to improve our assertion mechanism, having a single global boolean probably isn't sensible - we should probably make assertions particular to the module they are within and then have some kind of defense condition (defcon) status for which assertions should be checked
        Hide
        David Grove added a comment -

        I don't see a rush to apply this patch. The bootimage writer historically has changed very slowly, so the risk of patch rot in the next month or two seems very low.

        One should at least have empirical data for bootimage writing time with and without the patch applied for writing a prototype, development, and production image so that we can make an empirically guided decision.

        I'm honestly less worried about slowing bootimage writing by a few percent than by the increase in stack depth causing problems for the host JVM and limiting our ability to build some configurations on some platforms. Can you quantify how much bigger the stacks need to be (run with different thread stack sizes for the host JVM with and without the patch and see where you start to get stack overflows).

        3) is completely true, but also completely orthogonal to the question of whether or not this patch should be applied to the head or put in the research archive.

        It's also not clear to me why this patch is worth prioritizing above the many other items sitting against 2.9.4 and 3.0.

        Show
        David Grove added a comment - I don't see a rush to apply this patch. The bootimage writer historically has changed very slowly, so the risk of patch rot in the next month or two seems very low. One should at least have empirical data for bootimage writing time with and without the patch applied for writing a prototype, development, and production image so that we can make an empirically guided decision. I'm honestly less worried about slowing bootimage writing by a few percent than by the increase in stack depth causing problems for the host JVM and limiting our ability to build some configurations on some platforms. Can you quantify how much bigger the stacks need to be (run with different thread stack sizes for the host JVM with and without the patch and see where you start to get stack overflows). 3) is completely true, but also completely orthogonal to the question of whether or not this patch should be applied to the head or put in the research archive. It's also not clear to me why this patch is worth prioritizing above the many other items sitting against 2.9.4 and 3.0.
        Hide
        David Grove added a comment -

        re-read all the comments...missed the earlier data., Slowing down bootimage writing by 50% now to gain flexibility/.parallalization later is not an acceptable trade off in my opinion. -1 on this patch from me until performance issues addressed.

        Show
        David Grove added a comment - re-read all the comments...missed the earlier data., Slowing down bootimage writing by 50% now to gain flexibility/.parallalization later is not an acceptable trade off in my opinion. -1 on this patch from me until performance issues addressed.
        David Grove made changes -
        Fix Version/s 1000 [ 14184 ]
        Fix Version/s 2.9.4 [ 14162 ]
        Hide
        Ian Rogers added a comment -

        The performance degradation was down to seeing if an entry was contained in the pending entries. Adding a flag to the entry avoids this slow down and performance is identical to without the patch. Variant of patch committed in r14876 due to the many changes that happen to BootImageWriter in the build up to 3.0.

        Show
        Ian Rogers added a comment - The performance degradation was down to seeing if an entry was contained in the pending entries. Adding a flag to the entry avoids this slow down and performance is identical to without the patch. Variant of patch committed in r14876 due to the many changes that happen to BootImageWriter in the build up to 3.0.
        Ian Rogers made changes -
        Fix Version/s 3.0.1 [ 14378 ]
        Resolution Fixed [ 1 ]
        Fix Version/s 1000 [ 14184 ]
        Status Open [ 1 ] Resolved [ 5 ]
        Ian Rogers made changes -
        Status Resolved [ 5 ] Closed [ 6 ]

          People

          • Assignee:
            Ian Rogers
            Reporter:
            Ian Rogers
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: