import typing
+# Layouts
+
+class TypeLayout
+ # Unic ids or each Mtype
+ var ids: Map[MType, Int] = new HashMap[MType, Int]
+ # Fixed positions of each MType in all tables
+ var pos: Map[MType, Int] = new HashMap[MType, Int]
+end
+
+class PHTypeLayout
+ super TypeLayout
+ # Masks used by hash function
+ var masks: Map[MType, Int] = new HashMap[MType, Int]
+ # Positions of each MType for each tables
+ var hashes: Map[MType, Map[MType, Int]] = new HashMap[MType, Map[MType, Int]]
+end
+
abstract class TypeLayoutBuilder
+
+ type LAYOUT: TypeLayout
+
private var mmodule: MModule
init(mmodule: MModule) do self.mmodule = mmodule
# Compute mtypes ids and position
- fun build_layout(mtypes: Set[MType]): TypeLayout is abstract
+ fun build_layout(mtypes: Set[MType]): LAYOUT is abstract
# Give each MType a unic id using a descending linearization of the `mtypes` set
private fun compute_ids(mtypes: Set[MType]): Map[MType, Int] do
end
end
-class TypeLayout
- # Unic ids or each Mtype
- var ids: Map[MType, Int] = new HashMap[MType, Int]
- # Fixed positions of each MType in all tables
- var pos: Map[MType, Int] = new HashMap[MType, Int]
-end
-
# Layout builder for MType using Binary Matrix (BM)
class BMTypeLayoutBuilder
super TypeLayoutBuilder
end
# Compute mtypes ids and position using BM
- redef fun build_layout(mtypes: Set[MType]): TypeLayout do
+ redef fun build_layout(mtypes) do
var result = new TypeLayout
result.ids = self.compute_ids(mtypes)
result.pos = self.colorer.colorize(mtypes)
end
end
+# Layout builder for MType using Perfect Hashing (PH)
+class PHTypeLayoutBuilder
+ super TypeLayoutBuilder
+
+ redef type LAYOUT: PHTypeLayout
+
+ private var hasher: MTypeHasher
+
+ init(mmodule: MModule, operator: PHOperator) do
+ super
+ self.hasher = new MTypeHasher(mmodule, operator)
+ end
+
+ # Compute mtypes ids and position using BM
+ redef fun build_layout(mtypes) do
+ var result = new PHTypeLayout
+ result.ids = self.compute_ids(mtypes)
+ result.masks = self.hasher.compute_masks(mtypes, result.ids)
+ result.hashes = self.hasher.compute_hashes(mtypes, result.ids, result.masks)
+ return result
+ end
+
+ # Ids start from 1 instead of 0
+ redef fun compute_ids(mtypes) do
+ var ids = new HashMap[MType, Int]
+ var lin = self.mmodule.reverse_linearize_mtypes(mtypes)
+ for mtype in lin do
+ ids[mtype] = ids.length + 1
+ end
+ return ids
+ end
+end
+
abstract class AbstractColoring[E: Object]
private var core: Set[E] = new HashSet[E]
redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mtypes(elements)
end
-abstract class TypePerfectHashing
- super TypeLayoutBuilder
- super AbstractColoring[MType]
+# MType Perfect Hashing
+private class MTypeHasher
- type T: MType
+ var mmodule: MModule
+ var operator: PHOperator
- init(mmodule: MModule) do self.mmodule = mmodule
+ init(mmodule: MModule, operator: PHOperator) do
+ self.mmodule = mmodule
+ self.operator = operator
+ end
- fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
- for e in elements do
- # Create super type list
- var supers = new HashSet[T]
- supers.add_all(self.super_elements(e, elements))
- supers.add(e)
- # Compute the hashing 'mask'
- self.coloration_result[e] = compute_mask(supers, ids)
+ fun compute_masks(mtypes: Set[MType], ids: Map[MType, Int]): Map[MType, Int] do
+ var masks = new HashMap[MType, Int]
+ for mtype in mtypes do
+ var supers = new HashSet[MType]
+ supers.add_all(self.mmodule.super_mtypes(mtype, mtypes))
+ supers.add(mtype)
+ masks[mtype] = compute_mask(supers, ids)
end
- return self.coloration_result
+ return masks
end
- private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
+ private fun compute_mask(supers: Set[MType], ids: Map[MType, Int]): Int do
var mask = 0
loop
var used = new List[Int]
- for sup in mtypes do
- var res = op(mask, ids[sup])
+ for sup in supers do
+ var res = operator.op(mask, ids[sup])
if used.has(res) then
break
else
used.add(res)
end
end
- if used.length == mtypes.length then break
+ if used.length == supers.length then break
mask += 1
end
return mask
end
- private fun op(mask: Int, id:Int): Int is abstract
- private fun phash(id: Int, mask: Int): Int do return op(mask, id)
+ fun compute_hashes(mtypes: Set[MType], ids: Map[MType, Int], masks: Map[MType, Int]): Map[MType, Map[MType, Int]] do
+ var hashes = new HashMap[MType, Map[MType, Int]]
+ for mtype in mtypes do
+ var supers = new HashSet[MType]
+ supers.add_all(self.mmodule.super_mtypes(mtype, mtypes))
+ supers.add(mtype)
+ var inhashes = new HashMap[MType, Int]
+ var mask = masks[mtype]
+ for sup in supers do
+ inhashes[sup] = operator.op(mask, ids[sup])
+ end
+ hashes[mtype] = inhashes
+ end
+ return hashes
+ end
+end
- redef fun super_elements(element, elements) do return self.mmodule.super_mtypes(element, elements)
- redef fun is_element_mi(element, elements) do return self.super_elements(element, elements).length > 1
- redef fun sub_elements(element, elements) do do return self.mmodule.sub_mtypes(element, elements)
- redef fun linearize(elements) do return self.mmodule.linearize_mtypes(elements)
- redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mtypes(elements)
+# Abstract operator used for perfect hashing
+abstract class PHOperator
+ fun op(mask: Int, id:Int): Int is abstract
end
-class TypeModPerfectHashing
- super TypePerfectHashing
- init(mainmodule: MModule) do super
+# Hashing using modulo (MOD) operator
+# slower but compact
+class PHModOperator
+ super PHOperator
+ init do end
redef fun op(mask, id) do return mask % id
end
-class TypeAndPerfectHashing
- super TypePerfectHashing
- init(mainmodule: MModule) do super
+# Hashing using binary and (AND) operator
+# faster but sparse
+class PHAndOperator
+ super PHOperator
+ init do end
redef fun op(mask, id) do return mask.bin_and(id)
end
init(mainmodule: MModule, mmbuilder: ModelBuilder, runtime_type_analysis: RapidTypeAnalysis) do
super
- self.init_layout_builders
self.header = new_visitor
+ self.init_layout_builders
self.runtime_type_analysis = runtime_type_analysis
self.do_property_coloring
self.compile_box_kinds
if modelbuilder.toolcontext.opt_bm_typing.value then
self.type_layout_builder = new BMTypeLayoutBuilder(self.mainmodule)
else if modelbuilder.toolcontext.opt_phmod_typing.value then
- self.type_layout_builder = new TypeModPerfectHashing(self.mainmodule)
+ self.type_layout_builder = new PHTypeLayoutBuilder(self.mainmodule, new PHModOperator)
+ self.header.add_decl("#define HASH(mask, id) ((mask)%(id))")
else if modelbuilder.toolcontext.opt_phand_typing.value then
- self.type_layout_builder = new TypeAndPerfectHashing(self.mainmodule)
+ self.type_layout_builder = new PHTypeLayoutBuilder(self.mainmodule, new PHAndOperator)
+ self.header.add_decl("#define HASH(mask, id) ((mask)&(id))")
else
self.type_layout_builder = new CLTypeLayoutBuilder(self.mainmodule)
end
end
mtypes.add_all(self.partial_types)
- # set type unique id
- if modelbuilder.toolcontext.opt_phmod_typing.value or modelbuilder.toolcontext.opt_phand_typing.value then
- var sorted_mtypes = new Array[MType].from(mtypes)
- var sorter = new ReverseTypeSorter(self.mainmodule)
- sorter.sort(sorted_mtypes)
- for mtype in sorted_mtypes do
- self.typeids[mtype] = self.typeids.length + 1
- end
- else
- for mtype in mtypes do
- self.typeids[mtype] = self.typeids.length
- end
- end
-
# VT and FT are stored with other unresolved types in the big unanchored_tables
self.compile_unanchored_tables(mtypes)
# colorize types
var type_coloring = self.type_layout_builder
- if type_coloring isa TypeModPerfectHashing then
- self.type_colors = type_coloring.compute_masks(mtypes, typeids)
- self.type_tables = self.hash_type_tables(mtypes, typeids, type_colors, type_coloring)
- self.header.add_decl("#define HASH(mask, id) ((mask)%(id))")
- else if type_coloring isa TypeAndPerfectHashing then
- self.type_colors = type_coloring.compute_masks(mtypes, typeids)
- self.type_tables = self.hash_type_tables(mtypes, typeids, type_colors, type_coloring)
- self.header.add_decl("#define HASH(mask, id) ((mask)&(id))")
+ if type_coloring isa PHTypeLayoutBuilder then
+ var result = type_coloring.build_layout(mtypes)
+ self.typeids = result.ids
+ self.type_colors = result.masks
+ self.type_tables = self.hash_type_tables(mtypes, result.hashes)
else
var result = type_coloring.build_layout(mtypes)
self.typeids = result.ids
self.type_colors = result.pos
self.type_tables = self.build_type_tables(mtypes, type_colors, type_coloring)
end
-
-
return mtypes
end
end
# Build type tables
- fun hash_type_tables(mtypes: Set[MType], ids: Map[MType, Int], masks: Map[MType, Int], colorer: TypePerfectHashing): Map[MType, Array[nullable MType]] do
+ fun hash_type_tables(mtypes: Set[MType], hashes: Map[MType, Map[MType, Int]]): Map[MType, Array[nullable MType]] do
var tables = new HashMap[MType, Array[nullable MType]]
for mtype in mtypes do
var table = new Array[nullable MType]
- var supers = new HashSet[MType]
- supers.add_all(colorer.super_elements(mtype, mtypes))
- supers.add(mtype)
-
- for sup in supers do
- var color = colorer.phash(ids[sup], masks[mtype])
+ var supers = hashes[mtype]
+ for sup, color in supers do
if table.length <= color then
for i in [table.length .. color[ do
table[i] = null
nitlanguage / nit.git / commitdiff