Scala Programming Language
  1. Scala Programming Language
  2. SI-5206

copyTypeRef in internal.Types promises an optimization but doesn't do it

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.10.0
    • Fix Version/s: None
    • Component/s: Misc Compiler
    • Labels:
      None
    • Environment:

      scala trunk.

      Description

      While working on SI-5130 I spotted this method:

        // Optimization to avoid creating unnecessary new typerefs.
        def copyTypeRef(tp: Type, pre: Type, sym: Symbol, args: List[Type]): Type = tp match {
          case TypeRef(pre0, sym0, _) if (pre0 eq sym0) && sym0.name == sym.name =>
            if (sym.isAliasType && sameLength(sym.info.typeParams, args) && !sym.lockOK)
              throw new TypeError("illegal cyclic reference involving " + sym)
      
            TypeRef(pre, sym, args)
          case _ =>
            typeRef(pre, sym, args)
        }
      

      1.- The first case will never be followed: both Type and Symbol are classes and they don't extend each other, so a Type and a Symbol can ever be "eq" to each other... ¿am I right?

      2.- Where is the optimization it promises in the heading comment?

        Activity

        Hide
        Paul Phillips added a comment -

        Gasp, it looks like I just broke this a week ago in r25984. I'm sad that my equality sanity checks don't catch that nonsensical eq test, and I know why too. In any case that's obviously supposed to be comparing pre and pre0. The optimization in question is that it is created a TypeRef directly (capital TypeRef) rather than going through the factory (lower case typeRef) because the former mechanism bypasses the unique type cache.

        Show
        Paul Phillips added a comment - Gasp, it looks like I just broke this a week ago in r25984. I'm sad that my equality sanity checks don't catch that nonsensical eq test, and I know why too. In any case that's obviously supposed to be comparing pre and pre0. The optimization in question is that it is created a TypeRef directly (capital TypeRef) rather than going through the factory (lower case typeRef) because the former mechanism bypasses the unique type cache.
        Hide
        Jordi Salvat i Alabart added a comment -

        I've tried removing the (useless) first case and adding this one instead to deliver on the promised optimization:

            case TypeRef(`pre`, `sym`, `args`) =>
              tp
        

        Observations:

        • The new case is run hundreds of times even on the simplest 'pos' tests, thousands on larger ones.
        • All partests pass.
        • The default case is also run – the optimization applies about 1/3rd of the time.

        I'll now try to measure total run times to decide whether the optimization is worth the cost of the comparison (plan B: make the comparison simpler; plan C: remove the method altogether).

        Show
        Jordi Salvat i Alabart added a comment - I've tried removing the (useless) first case and adding this one instead to deliver on the promised optimization: case TypeRef(`pre`, `sym`, `args`) => tp Observations: The new case is run hundreds of times even on the simplest 'pos' tests, thousands on larger ones. All partests pass. The default case is also run – the optimization applies about 1/3rd of the time. I'll now try to measure total run times to decide whether the optimization is worth the cost of the comparison (plan B: make the comparison simpler; plan C: remove the method altogether).
        Hide
        Commit Message Bot added a comment -

        (extempore in r26031) Fix for unfortunate thinko recently introduced.

        Many thanks to Jordi Salvat i Alabart for catching this.
        Universal equality is a formidable foe when it comes to avoiding
        this kind of mistake. Closes SI-5206, no review.

        Show
        Commit Message Bot added a comment - (extempore in r26031 ) Fix for unfortunate thinko recently introduced. Many thanks to Jordi Salvat i Alabart for catching this. Universal equality is a formidable foe when it comes to avoiding this kind of mistake. Closes SI-5206 , no review.
        Hide
        Jordi Salvat i Alabart added a comment -

        Now that this is fixed it may be unimportant, but since I've made the measurements, I'll drop them here even if just for the record:

        ant clean quick.lib

        With the optimization in my 10:35pm message:
        [stopwatch] [quick.lib.timer: 3:51.938 sec]
        [stopwatch] [quick.lib.timer: 3:49.082 sec]

        With copyTypeRef(pre,sym,args) just an alias for typeRef(pre,sym,args):
        [stopwatch] [quick.lib.timer: 3:54.058 sec]
        [stopwatch] [quick.lib.timer: 3:49.825 sec]

        With the optimization guarded by "eq" on all three parameters:
        [stopwatch] [quick.lib.timer: 3:51.777 sec]
        [stopwatch] [quick.lib.timer: 3:51.518 sec]

        ... not even measurable difference...

        ant clean quick.comp:

        With the optimization guarded by "eq" on all three parameters:
        [stopwatch] [quick.lib.timer: 3:51.412 sec]
        [stopwatch] [quick.comp.timer: 3:14.034 sec]
        Total time: 7 minutes 7 seconds

        With the snippet above:
        [stopwatch] [quick.lib.timer: 3:50.794 sec]
        [stopwatch] [quick.comp.timer: 3:12.194 sec]
        Total time: 7 minutes 5 seconds

        With copyTypeRef just calling typeRef – and making it final:
        [stopwatch] [quick.lib.timer: 3:50.895 sec]
        [stopwatch] [quick.comp.timer: 3:13.251 sec]
        Total time: 7 minutes 6 seconds

        ... again, not really measurable.

        I'll try the fix and see what it brings (right now my build is broken )

        Show
        Jordi Salvat i Alabart added a comment - Now that this is fixed it may be unimportant, but since I've made the measurements, I'll drop them here even if just for the record: ant clean quick.lib With the optimization in my 10:35pm message: [stopwatch] [quick.lib.timer: 3:51.938 sec] [stopwatch] [quick.lib.timer: 3:49.082 sec] With copyTypeRef(pre,sym,args) just an alias for typeRef(pre,sym,args): [stopwatch] [quick.lib.timer: 3:54.058 sec] [stopwatch] [quick.lib.timer: 3:49.825 sec] With the optimization guarded by "eq" on all three parameters: [stopwatch] [quick.lib.timer: 3:51.777 sec] [stopwatch] [quick.lib.timer: 3:51.518 sec] ... not even measurable difference... ant clean quick.comp: With the optimization guarded by "eq" on all three parameters: [stopwatch] [quick.lib.timer: 3:51.412 sec] [stopwatch] [quick.comp.timer: 3:14.034 sec] Total time: 7 minutes 7 seconds With the snippet above: [stopwatch] [quick.lib.timer: 3:50.794 sec] [stopwatch] [quick.comp.timer: 3:12.194 sec] Total time: 7 minutes 5 seconds With copyTypeRef just calling typeRef – and making it final: [stopwatch] [quick.lib.timer: 3:50.895 sec] [stopwatch] [quick.comp.timer: 3:13.251 sec] Total time: 7 minutes 6 seconds ... again, not really measurable. I'll try the fix and see what it brings (right now my build is broken )
        Hide
        Jordi Salvat i Alabart added a comment -

        With the fix:
        [stopwatch] [quick.lib.timer: 3:51.923 sec]
        [stopwatch] [quick.comp.timer: 3:16.011 sec]
        Total time: 7 minutes 9 seconds

        [stopwatch] [quick.lib.timer: 3:52.931 sec]
        [stopwatch] [quick.comp.timer: 3:13.868 sec]
        Total time: 7 minutes 9 seconds

        Again, not measurable.

        Show
        Jordi Salvat i Alabart added a comment - With the fix: [stopwatch] [quick.lib.timer: 3:51.923 sec] [stopwatch] [quick.comp.timer: 3:16.011 sec] Total time: 7 minutes 9 seconds [stopwatch] [quick.lib.timer: 3:52.931 sec] [stopwatch] [quick.comp.timer: 3:13.868 sec] Total time: 7 minutes 9 seconds Again, not measurable.
        Hide
        Paul Phillips added a comment -

        It is likely there is a measurable impact in environments making heavier use of implicit search than the compiler does. I say this because the optimization originated with tiark attacking their compile times, and if he shipped it then the smart money is that it was motivated.

        It would be really good if we were collecting regular timings for compiling not-the-compiler things though, as the assessment above is a little inaccessible to everyone but me.

        Show
        Paul Phillips added a comment - It is likely there is a measurable impact in environments making heavier use of implicit search than the compiler does. I say this because the optimization originated with tiark attacking their compile times, and if he shipped it then the smart money is that it was motivated. It would be really good if we were collecting regular timings for compiling not-the-compiler things though, as the assessment above is a little inaccessible to everyone but me.

          People

          • Assignee:
            Paul Phillips
            Reporter:
            Jordi Salvat i Alabart
          • Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development