# Perfect hashing and perfect numbering
var ph: Perfecthashing = new Perfecthashing
- # Handles memory and garbage collection
+ # Handles memory allocated in C
var memory_manager: MemoryManager = new MemoryManager
# The unique instance of the `MInit` value
do
assert recv isa MutableInstance
- # Read the attribute value with perfect hashing
- var id = mproperty.intro_mclassdef.mclass.vtable.id
+ var i: Instance
- var i = read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
+ if mproperty.intro_mclassdef.mclass.positions_attributes[recv.mtype.as(MClassType).mclass] != -1 then
+ # if this attribute class has an unique position for this receiver, then use direct access
+ i = read_attribute_sst(recv.internal_attributes, mproperty.absolute_offset)
+ else
+ # Otherwise, read the attribute value with perfect hashing
+ var id = mproperty.intro_mclassdef.mclass.vtable.id
+
+ i = read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
recv.vtable.mask, id, mproperty.offset)
+ end
# If we get a `MInit` value, throw an error
if i == initialization_value then
end
# Return the attribute value in `instance` with a sequence of perfect_hashing
- # `instance` is the attributes array of the receiver
- # `vtable` is the pointer to the virtual table of the class (of the receiver)
- # `mask` is the perfect hashing mask of the class
- # `id` is the identifier of the class
- # `offset` is the relative offset of this attribute
+ # * `instance` is the attributes array of the receiver
+ # * `vtable` is the pointer to the virtual table of the class (of the receiver)
+ # * `mask` is the perfect hashing mask of the class
+ # * `id` is the identifier of the class
+ # * `offset` is the relative offset of this attribute
private fun read_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int): Instance `{
// Perfect hashing position
int hv = mask & id;
return res;
`}
+ # Return the attribute value in `instance` with a direct access (SST)
- # `instance` is the attributes array of the receiver
- # `offset` is the absolute offset of this attribute
++ # * `instance` is the attributes array of the receiver
++ # * `offset` is the absolute offset of this attribute
+ private fun read_attribute_sst(instance: Pointer, offset: Int): Instance `{
+ /* We can make a direct access to the attribute value
+ because this attribute is always at the same position
+ for the class of this receiver */
+ Instance res = ((Instance *)instance)[offset];
+
+ return res;
+ `}
+
# Replace in `recv` the value of the attribute `mproperty` by `value`
redef fun write_attribute(mproperty: MAttribute, recv: Instance, value: Instance)
do
assert recv isa MutableInstance
- var id = mproperty.intro_mclassdef.mclass.vtable.id
-
# Replace the old value of mproperty in recv
- write_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
+ if mproperty.intro_mclassdef.mclass.positions_attributes[recv.mtype.as(MClassType).mclass] != -1 then
+ # if this attribute class has an unique position for this receiver, then use direct access
+ write_attribute_sst(recv.internal_attributes, mproperty.absolute_offset, value)
+ else
+ # Otherwise, use perfect hashing to replace the old value
+ var id = mproperty.intro_mclassdef.mclass.vtable.id
+
+ write_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
recv.vtable.mask, id, mproperty.offset, value)
+ end
end
# Replace the value of an attribute in an instance
- # `instance` is the attributes array of the receiver
- # `vtable` is the pointer to the virtual table of the class (of the receiver)
- # `mask` is the perfect hashing mask of the class
- # `id` is the identifier of the class
- # `offset` is the relative offset of this attribute
- # `value` is the new value for this attribute
+ # * `instance` is the attributes array of the receiver
+ # * `vtable` is the pointer to the virtual table of the class (of the receiver)
+ # * `mask` is the perfect hashing mask of the class
+ # * `id` is the identifier of the class
+ # * `offset` is the relative offset of this attribute
+ # * `value` is the new value for this attribute
private fun write_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int, value: Instance) `{
// Perfect hashing position
int hv = mask & id;
Instance_incr_ref(value);
`}
+ # Replace the value of an attribute in an instance with direct access
- # `instance` is the attributes array of the receiver
- # `offset` is the absolute offset of this attribute
- # `value` is the new value for this attribute
++ # * `instance` is the attributes array of the receiver
++ # * `offset` is the absolute offset of this attribute
++ # * `value` is the new value for this attribute
+ private fun write_attribute_sst(instance: Pointer, offset: Int, value: Instance) `{
+ // Direct access to the position with the absolute offset
+ ((Instance *)instance)[offset] = value;
+ Instance_incr_ref(value);
+ `}
+
# Is the attribute `mproperty` initialized in the instance `recv`?
redef fun isset_attribute(mproperty: MAttribute, recv: Instance): Bool
do
var nb_methods = new Array[Int]
var nb_attributes = new Array[Int]
- # Absolute offset of the beginning of the attributes table
+ # Absolute offset of attribute from the beginning of the attributes table
var offset_attributes = 0
- # Absolute offset of the beginning of the methods table
+ # Absolute offset of method from the beginning of the methods table
var offset_methods = 0
+ # The previous element in `superclasses`
+ var previous_parent: nullable MClass = null
+ if superclasses.length > 0 then previous_parent = superclasses[0]
for parent in superclasses do
if not parent.loaded then parent.make_vt(v)
for p in parent.intro_mproperties(none_visibility) do
if p isa MMethod then methods += 1
- if p isa MAttribute then
- attributes += 1
- end
+ if p isa MAttribute then attributes += 1
end
ids.push(parent.vtable.id)
nb_methods.push(methods)
nb_attributes.push(attributes)
- # Update `positions_attributes` and `positions_methods` in `parent`
- update_positions(offset_attributes, offset_methods, parent)
+ # Update `positions_attributes` and `positions_methods` in `parent`.
+ # If the position is invariant for this parent, store this position
+ # else store a special value (-1)
+ var pos_attr = -1
+ var pos_meth = -1
+
+ if previous_parent.as(not null).positions_attributes[parent] == offset_attributes then pos_attr = offset_attributes
+ if previous_parent.as(not null).positions_methods[parent] == offset_methods then pos_meth = offset_methods
+
+ parent.update_positions(pos_attr, pos_meth, self)
offset_attributes += attributes
offset_methods += methods
end
# Allocate a single vtable
- # `ids : Array of superclasses identifiers
- # `nb_methods : Array which contain the number of introduced methods for each class in ids
- # `nb_attributes : Array which contain the number of introduced attributes for each class in ids
- # `offset_attributes : Offset from the beginning of the table of the group of attributes
- # `offset_methods : Offset from the beginning of the table of the group of methods
+ # * `ids : Array of superclasses identifiers
+ # * `nb_methods : Array which contain the number of introduced methods for each class in ids
+ # * `nb_attributes : Array which contain the number of introduced attributes for each class in ids
+ # * `offset_attributes : Offset from the beginning of the table of the group of attributes
+ # * `offset_methods : Offset from the beginning of the table of the group of methods
private fun allocate_vtable(v: VirtualMachine, ids: Array[Int], nb_methods: Array[Int], nb_attributes: Array[Int],
offset_attributes: Int, offset_methods: Int)
do
if p isa MMethod then
self_methods += 1
p.offset = relative_offset_meth
+ p.absolute_offset = offset_methods + relative_offset_meth
relative_offset_meth += 1
end
if p isa MAttribute then
nb_introduced_attributes += 1
p.offset = relative_offset_attr
+ p.absolute_offset = offset_attributes + relative_offset_attr
relative_offset_attr += 1
end
end
nb_attributes_total.push(nb_introduced_attributes)
# Save the offsets of self class
update_positions(offset_attributes, offset_methods, self)
# Since we have the number of attributes for each class, calculate the delta
- var d = calculate_delta(nb_attributes_total)
- vtable.internal_vtable = v.memory_manager.init_vtable(ids_total, nb_methods_total, d, vtable.mask)
+ var deltas = calculate_delta(nb_attributes_total)
+ vtable.internal_vtable = v.memory_manager.init_vtable(ids_total, nb_methods_total, deltas, vtable.mask)
end
# Fill the vtable with methods of `self` class
- # `v` : Current instance of the VirtualMachine
- # `table` : the table of self class, will be filled with its methods
+ # * `v` : Current instance of the VirtualMachine
+ # * `table` : the table of self class, will be filled with its methods
private fun fill_vtable(v:VirtualMachine, table: VTable, cl: MClass)
do
var methods = new Array[MMethodDef]
# Computes delta for each class
# A delta represents the offset for this group of attributes in the object
- # `nb_attributes` : number of attributes for each class (classes are linearized from Object to current)
- # return deltas for each class
+ # *`nb_attributes` : number of attributes for each class (classes are linearized from Object to current)
+ # * return deltas for each class
private fun calculate_delta(nb_attributes: Array[Int]): Array[Int]
do
var deltas = new Array[Int]
end
# A kind of Depth-First-Search for superclasses ordering
- # `v` : the current executed instance of VirtualMachine
- # `res` : Result Array, ie current superclasses ordering
+ # *`v` : the current executed instance of VirtualMachine
+ # * `res` : Result Array, ie current superclasses ordering
private fun dfs(v: VirtualMachine, res: Array[MClass]): Array[MClass]
do
# Add this class at the beginning
return res
end
- # Update positions of self class in `parent`
+ # Update positions of the class `cl`
- # `attributes_offset`: absolute offset of introduced attributes
- # `methods_offset`: absolute offset of introduced methods
+ # * `attributes_offset`: absolute offset of introduced attributes
+ # * `methods_offset`: absolute offset of introduced methods
- private fun update_positions(attributes_offsets: Int, methods_offset:Int, parent: MClass)
+ private fun update_positions(attributes_offsets: Int, methods_offset:Int, cl: MClass)
do
- parent.positions_attributes[self] = attributes_offsets
- parent.positions_methods[self] = methods_offset
+ positions_attributes[cl] = attributes_offsets
+ positions_methods[cl] = methods_offset
end
end
redef class MAttribute
- # Represents the relative offset of this attribute in the runtime instance
+ # Relative offset of this attribute in the runtime instance
+ # (beginning of the block of its introducing class)
var offset: Int
+
+ # Absolute offset of this attribute in the runtime instance (beginning of the attribute table)
+ var absolute_offset: Int
end
redef class MMethod
- # Represents the relative offset of this attribute in the runtime instance
+ # Relative offset of this method in the virtual table (from the beginning of the block)
var offset: Int
+
+ # Absolute offset of this method in the virtual table (from the beginning of the vtable)
+ var absolute_offset: Int
end
# Redef MutableInstance to improve implementation of attributes in objects
`}
# Put implementation of methods of a class in `vtable`
- # `vtable` : Pointer to the C-virtual table
- # `mask` : perfect-hashing mask of the class corresponding to the vtable
- # `id` : id of the target class
- # `methods` : array of MMethodDef of the target class
+ # * `vtable` : Pointer to the C-virtual table
+ # * `mask` : perfect-hashing mask of the class corresponding to the vtable
+ # * `id` : id of the target class
+ # * `methods` : array of MMethodDef of the target class
fun put_methods(vtable: Pointer, mask: Int, id: Int, methods: Array[MMethodDef])
import Array[MMethodDef].length, Array[MMethodDef].[] `{
nitlanguage / nit.git / commitdiff