At the last meeting we came up with a representation for objects that was based on a hash-table. It occurred to me that, if there are few properties, a linear search in an array will be faster. My intuition is that objects with few properties are accessed often. Can we verify this with our tracing framework?
With linear search there is also the possibility of moving elements in the array to accelerate the lookup time. For example, when a property is found it could be swapped with the first element of the array, so that if an access to the same property occurs next, then the property is found on the first try. There are other fairly simple LRU algorithms that could be used.
Finally, the linear search algorithm is simple enough to be inlined, which eliminates the call to the hash-table lookup function.
We should try to determine if this is true for some benchmark programs.
Note that we could have both representations. Initially a linear search would be done, and when there are greater than "Pmax" properties, then a hash-table would be used. We just have to arrange for the inlined "linear search" algorithm to immediately fail, and fallback to the hash-table lookup done in the out-of-line handler.
Marc
Afficher les réponses par date
My intuition is that objects with few properties are accessed often.
Can we verify this with our tracing framework?
Sure. I might have time to look at that tomorrow.
Initially a linear search would be done, and when there are greater
than "Pmax" properties, then a hash-table would be used. We just have to arrange for the inlined "linear search" algorithm to immediately fail, and fallback to the hash-table lookup done in the out-of-line handler.
I have my doubts that it's worth it to try very hard to optimize this, as hidden classes would probably be faster... But consider this:
If objects contain an "inline" table with a small, constant number of slots, say K = 7 or K = 11, we could use this for objects with few properties, either for linear search or as a hash table. Furthermore, if we used it as a hash table, the actual index after hashing of the property name could be pre-computed in most cases (startIndex = hash(propName) % K). Meaning the lookup would always hopefully begin at the "right" place.
- Maxime
I've been working on filling the missing pieces of the object representation. I would like to clarify with you the following points: 1. Optimizations supported by the baseline compiler (constant propagation, function inlining, etc.) 2. Performance and Extensibility (especially for an eventual specialization of object representations) 3. Boundary between Javascript and C code for the manipulation of the object representation
Would we have time to meet tomorrow to discuss it? I am available anytime during the day. Meeting at 2166 could be fun!
Erick
Le 10-06-21 17:06 , Maxime Chevalier-Boisvert a écrit :
My intuition is that objects with few properties are accessed often.
Can we verify this with our tracing framework?
Sure. I might have time to look at that tomorrow.
Initially a linear search would be done, and when there are greater
than "Pmax" properties, then a hash-table would be used. We just have to arrange for the inlined "linear search" algorithm to immediately fail, and fallback to the hash-table lookup done in the out-of-line handler.
I have my doubts that it's worth it to try very hard to optimize this, as hidden classes would probably be faster... But consider this:
If objects contain an "inline" table with a small, constant number of slots, say K = 7 or K = 11, we could use this for objects with few properties, either for linear search or as a hash table. Furthermore, if we used it as a hash table, the actual index after hashing of the property name could be pre-computed in most cases (startIndex = hash(propName) % K). Meaning the lookup would always hopefully begin at the "right" place.
- Maxime
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
I've been working on filling the missing pieces of the object
representation. I would like to clarify with you the following points: 1. Optimizations supported by the baseline compiler (constant propagation, function inlining, etc.)
I would suggest not focusing on optimizations for the first version of our compiler. However, eventually, our baseline compiler should support constant propagation as well as peephole optimizations of x86 code. Probably not inlining of user functions though, as that is non-trivial in JavaScript and requires sophisticated analyses. We should, however, be able to inline some of our code, which we can guarantee will be called.
Boundary between Javascript and C code for the manipulation of the
object representation
I would like it if we could do all manipulations of the object representation using the inline IR, eventually. For the moment being, if we have a GC written in C, however, it will need to understand some aspects of the representation.
Performance and Extensibility (especially for an eventual
specialization of object representations)
If we have a good reified API for interacting with object representations, this makes it easier to have multiple representations and switch between them later. If this is done using the inline IR, it could actually improve the performance.
Would we have time to meet tomorrow to discuss it? I am available anytime during the day. Meeting at 2166 could be fun!
I would be available in the afternoon tomorrow, but are we not meeting on Wednesday anyway?
- Maxime
Erick Lavoie wrote:
I've been working on filling the missing pieces of the object representation. I would like to clarify with you the following points:
- Optimizations supported by the baseline compiler (constant
propagation, function inlining, etc.) 2. Performance and Extensibility (especially for an eventual specialization of object representations) 3. Boundary between Javascript and C code for the manipulation of the object representation
Would we have time to meet tomorrow to discuss it? I am available anytime during the day. Meeting at 2166 could be fun!
Erick
Le 10-06-21 17:06 , Maxime Chevalier-Boisvert a écrit :
My intuition is that objects with few properties are accessed often.
Can we verify this with our tracing framework?
Sure. I might have time to look at that tomorrow.
Initially a linear search would be done, and when there are greater
than "Pmax" properties, then a hash-table would be used. We just have to arrange for the inlined "linear search" algorithm to immediately fail, and fallback to the hash-table lookup done in the out-of-line handler.
I have my doubts that it's worth it to try very hard to optimize this, as hidden classes would probably be faster... But consider this:
If objects contain an "inline" table with a small, constant number of slots, say K = 7 or K = 11, we could use this for objects with few properties, either for linear search or as a hash table. Furthermore, if we used it as a hash table, the actual index after hashing of the property name could be pre-computed in most cases (startIndex = hash(propName) % K). Meaning the lookup would always hopefully begin at the "right" place.
- Maxime
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
On 2010-06-21, at 18:57 , Maxime Chevalier-Boisvert wrote:
Would we have time to meet tomorrow to discuss it? I am available anytime during the day. Meeting at 2166 could be fun!
I would be available in the afternoon tomorrow, but are we not meeting on Wednesday anyway?
I am also available, but I'd rather just meet tomorrow morning at the regular time if possible.
Bruno
Sorry I'm not at work today.
Marc
On 2010-06-22, at 9:42 AM, Bruno Dufour wrote:
On 2010-06-21, at 18:57 , Maxime Chevalier-Boisvert wrote:
Would we have time to meet tomorrow to discuss it? I am available anytime during the day. Meeting at 2166 could be fun!
I would be available in the afternoon tomorrow, but are we not meeting on Wednesday anyway?
I am also available, but I'd rather just meet tomorrow morning at the regular time if possible.
Bruno _______________________________________________ Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
-
Bruno Dufour -
Erick Lavoie -
Marc Feeley -
Maxime Chevalier-Boisvert