The choice of the tagging scheme (including number of bits, and tag assignment) should be made with the target processor in mind. In our case the best combination will take advantage of x86 features (instruction set, addressing modes, ...). I propose that Erick and you look at a number of the most important JavaScript primitives and how they would be translated to efficient x86 instructions. That will be a good exercise for which you will have to learn the x86 architecture in more detail. The tags are mainly used for the dynamic typing required at run time to ensure the types are correct for the operation being executed. For operations like +, they are used to detect the common case (adding two fixnums) and treat it inline.
A few comments. If we liberate a tag, then immediate int might be tagged as X----X00 (to give one more significant bit). Why do we need to reserve a tag for 4 constants? I could see having a single tag for all the false values to make testing for false quick. The "other" category is unclear... how do you intend to implement setter/getters? Why do references to hash-tables need to be tagged? I thought we had said "strings" would be included in "objects". If there is an advantage to split them, what is it?
I suspect that the test "is_a_function" will occur often in unoptimized code (because it is logically part of all function calls), so it would be good to find ways to reduce its cost. In a previous message I explained how this can be done for the global object (i.e. calling f(X) will jump to a trampoline for f in the global object, which will jump to an error handler if f is not bound to a function). To handle dynamic calls efficiently we could start all objects with machine code. For all object types except "function", the machine code would be a short sequence (probably 3 bytes) which calls an error handler. That way a function call would always jump to the object, and it is the object that signals that it is not a function.
It might be a good time to run some benchmarks to see which JavaScript primitives are called the most often, and to make sure the tagging and object representation is biased towards the frequent case.
I guess the message I want to convey is that any proposed tagging scheme should come with a justification of why it is efficient, i.e. machine code templates for the frequent operations.
Marc
On 2010-09-09, at 9:52 PM, Maxime Chevalier-Boisvert wrote:
We're getting to the point where we need to pick tag bits for boxed values in order to implement our system.
I've looked at our previous notes and wrote down the following tentative scheme:
Tags needed:
- immediate int X----X000 0
- object X----X111 7
- function obj X----X110 6
- array obj X----X101 5
- float X----X100 4
- string X----X011 3
- constants X----X010 2
- bool/null/undef
- other X----X001 1
- (getter-setter, hash table, etc.)
All tags are 3 bits wide, which has the advantage of making it easy to extract the tag, always using the same mask operation (val & MASK).
I have picked the tags 7, 6 and 5 for objects, functions and arrays, because those 3 can all have properties stored on them, and so might share a similar memory layout (eg; might have a prototype pointer, a hash table pointer, etc, at the same offset, they are all objects). This makes it possible to test if something is "an object" by doing (val & MASK >= 5).
This scheme has 8 possible tags. The last one, "other", is for all the things that may exist in our heap but won't necessarily have a reserved tag. These include getter-setter objects, hash tables, and other possible runtime objects that may end up in the garbage-collected part of the heap.
Some question worth considering are:
Could we do away with some of these tags?
Are there other things worth tagging that are not included in there?
Do we need more tags?
- Would it be worthwhile to pick a different/more complex encoding
scheme, so as to gain 1 or 2 extra bits for immediate integers, or have a simpler (one-bit?) check for "is an object"?
- Maxime
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list