From: Jean Privat <jean@pryen.org>
Date: Tue, 9 Aug 2016 01:18:27 +0000 (-0400)
Subject: Merge: Faster lookup
X-Git-Url: http://nitlanguage.org?hp=487fa951892c0910a542784cc2468cfd099d940f

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
--- 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
--- 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