Merge: Faster lookup

This series improves the lookup strategies:

* special fast track for the virtual type SELF
* choose to iterate on the mclassdefs instead of the mpropdefs if they are less numerous.

This mainly limit the degenerative cases that where discovered while investigating the slowdown of #2223

with nitc/nitc/nitc:
before: 0m7.168s
after: 0m6.232s

with nitpick ../contrib:
before: 0m20.928s
after: 0m19.432s

Pull-Request: #2245
Reviewed-by: Lucas Bajolet <r4pass@hotmail.com>

diff --git a/src/model/model.nit b/src/model/model.nit
index 5349485..0357df2 100644 (file)
--- a/src/model/model.nit
+++ b/src/model/model.nit
@@ -720,8 +720,11 @@ class MClassDef
        # All properties introduced by the classdef
        var intro_mproperties = new Array[MProperty]
 
-       # All property definitions in the class (introductions and redefinitions)
+       # All property introductions and redefinitions in `self` (not inheritance).
        var mpropdefs = new Array[MPropDef]
+
+       # All property introductions and redefinitions (not inheritance) in `self` by its associated property.
+       var mpropdefs_by_property = new HashMap[MProperty, MPropDef]
 end
 
 # A global static type
@@ -1451,6 +1454,9 @@ class MVirtualType
        do
                if not cleanup_virtual then return self
                assert can_resolve_for(mtype, anchor, mmodule)
+
+               if mproperty.is_selftype then return mtype
+
                # self is a virtual type declared (or inherited) in mtype
                # The point of the function it to get the bound of the virtual type that make sense for mtype
                # But because mtype is maybe a virtual/formal type, we need to get a real receiver first
@@ -2053,14 +2059,27 @@ abstract class MProperty
                #print "select prop {mproperty} for {mtype} in {self}"
                # First, select all candidates
                var candidates = new Array[MPROPDEF]
-               for mpropdef in self.mpropdefs do
-                       # If the definition is not imported by the module, then skip
-                       if not mmodule.in_importation <= mpropdef.mclassdef.mmodule then continue
-                       # If the definition is not inherited by the type, then skip
-                       if not mtype.is_subtype(mmodule, null, mpropdef.mclassdef.bound_mtype) then continue
-                       # Else, we keep it
-                       candidates.add(mpropdef)
+
+               # Here we have two strategies: iterate propdefs or iterate classdefs.
+               var mpropdefs = self.mpropdefs
+               if mpropdefs.length <= 1 or mpropdefs.length < mtype.collect_mclassdefs(mmodule).length then
+                       # Iterate on all definitions of `self`, keep only those inherited by `mtype` in `mmodule`
+                       for mpropdef in mpropdefs do
+                               # If the definition is not imported by the module, then skip
+                               if not mmodule.in_importation <= mpropdef.mclassdef.mmodule then continue
+                               # If the definition is not inherited by the type, then skip
+                               if not mtype.is_subtype(mmodule, null, mpropdef.mclassdef.bound_mtype) then continue
+                               # Else, we keep it
+                               candidates.add(mpropdef)
+                       end
+               else
+                       # Iterate on all super-classdefs of `mtype`, keep only the definitions of `self`, if any.
+                       for mclassdef in mtype.collect_mclassdefs(mmodule) do
+                               var p = mclassdef.mpropdefs_by_property.get_or_null(self)
+                               if p != null then candidates.add p
+                       end
                end
+
                # Fast track for only one candidate
                if candidates.length <= 1 then
                        self.lookup_definitions_cache[mmodule, mtype] = candidates
@@ -2247,6 +2266,9 @@ class MVirtualTypeProp
 
        # The formal type associated to the virtual type property
        var mvirtualtype = new MVirtualType(self)
+
+       # Is `self` the special virtual type `SELF`?
+       var is_selftype: Bool is lazy do return name == "SELF"
 end
 
 # A definition of a property (local property)
@@ -2277,6 +2299,7 @@ abstract class MPropDef
        do
                mclassdef.mpropdefs.add(self)
                mproperty.mpropdefs.add(self)
+               mclassdef.mpropdefs_by_property[mproperty] = self
                if mproperty.intro_mclassdef == mclassdef then
                        assert not isset mproperty._intro
                        mproperty.intro = self

diff --git a/src/rapid_type_analysis.nit b/src/rapid_type_analysis.nit
index 88e2b7e..c5ddc4a 100644 (file)
--- a/src/rapid_type_analysis.nit
+++ b/src/rapid_type_analysis.nit
@@ -313,6 +313,7 @@ class RapidTypeAnalysis
                                if not ot.can_resolve_for(t, t, mainmodule) then continue
                                var rt = ot.anchor_to(mainmodule, t)
                                if live_types.has(rt) then continue
+                               if not is_valid_type(rt) then continue
                                if not check_depth(rt) then continue
                                #print "{ot}/{t} -> {rt}"
                                live_types.add(rt)
@@ -329,6 +330,7 @@ class RapidTypeAnalysis
                        for t in live_types do
                                if not ot.can_resolve_for(t, t, mainmodule) then continue
                                var rt = ot.anchor_to(mainmodule, t)
+                               if not is_valid_type(rt) then continue
                                live_cast_types.add(rt)
                                #print "  {ot}/{t} -> {rt}"
                        end
@@ -336,6 +338,16 @@ class RapidTypeAnalysis
                #print "cast MType {live_cast_types.length}: {live_cast_types.join(", ")}"
        end
 
+       # Quick and dirty check that a forced type resolution gives a legal type
+       # TODO: move up in the model and kill `can_resolve_for`
+       private fun is_valid_type(mtype: MType): Bool
+       do
+               if mtype isa MGenericType then
+                       return mtype.is_subtype(mainmodule, null, mtype.mclass.intro.bound_mtype)
+               end
+               return true
+       end
+
        private fun check_depth(mtype: MClassType): Bool
        do
                var d = mtype.length