Its got the benefit of being simpler than hidden classes in terms of implementation. However, it might not be as fast, as here, you need to go read into the hash table before you can figure out if you're accessing the right slot. I suppose we could still try it in a couple of months. We will have to take code patching into account in the design of the IR/backend.

I had another idea myself with regards to representations (which is probably not usable until some time later...).

I was thinking that eventually, we may perhaps want to look into "typed" hidden classes. As with V8, we could have classes transitioning between different representations are added, with the difference that property types could be associated with the representations, meaning that primitive values could sometimes be unboxed.

Another way to make this fast would be to directly store property slots into objects on allocation (no indirection, no external table), based on the properties we know could be added to a given object "class", possibly based on the site of creation. We could possibly try to allocate the objects big enough to be able to rewrite different representations the object could switch to into the same contiguous piece of allocated memory.

If at some point, a field we couldn't predict was added to an object, and the representation could no longer fit into the pre-allocated space, we could revert the object's representation to a "naive", hash table based one (which we make sure can always fit in the pre-allocated space), or we could keep a hash table pointer in every object, just for properties that don't fit.

So when we allocate an object, we get something like:

| header | hash tbl ptr | proto ptr | .... reserved space ..... |

Where the reserved space is sized according to a prediction we make about how big an object of this "class" is likely to get. The header would need to contain some kind of representation id to tell us how the reserved space is mapped, and probably a variable to tell us how big the reserved space is.

- Maxime

I had an idea tonight which is a variant on inline cachine. V8 (and Self, and others) uses inline caching to accelerate the implementation of x.y . Basically the code generated for a specific x.y in the code is something like:

c = get_hiddden_class(x); if c == cached_class then result = read_slot(x + cached_offset); else offset = lookup_offset(c, "y"); cached_class = c; cached_offset = offset; result = read_slot(x + offset);

Note that the variables cached_class and cached_offset are actually locations in the code (that are patched for the next execution of the code).

The variant of inline caching I came up with has the advantage of not needing to maintain the concept of hidden class. It works directly on hash tables. The idea is to cache the index in the hash table where the last lookup found the property. The next time, the index can be tried first with a test to make sure that the correct property is found:

ht = get_hash_table(x); if cached_index < length(ht) && read_slot(ht + cached_index) == "y" then result = read_slot(ht + cached_index + 1]; else i = hash_table_lookup(ht, "y"); cached_index = i; result = read_slot(ht + i + 1];

The length test could be made faster by combining it with the "modulo" of the table length (which would be a mask if the hash tables always have a length equal to a power of 2).

I would like to try this out to see how well it does.

Marc

---

Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list