June 2010 - Tachyon-list - mailman.iro.umontreal.ca

Bug in remItem
by Marc Feeley 02 Jul '10

02 Jul '10

There is a bug in the algorithm for deleting a key from a hash map (method remItem). Imagine the scenario where the keys are added in turn A, B, C where A and C hash to the index 1 and B hashes to the index 2. The array containing the elements will be: 0 1 2 3 4 +---+---+---+---+---+ | | A | B | C | | +---+---+---+---+---+ If the key A is removed, it will be replaced by "freeKey" and B and C will not move. But if C is then looked up in the hash map it will not be found. You really need 2 code: freeKey = this element has never contained a key (since the hash table was created or resized) deletedKey = this element used to contain a key which has since been deleted. It is possible to do away with the "deletedKey" code, but it requires (in general) rehashing the table, which is a very high price to pay. Check the Gambit sources for the algorithms in Scheme and C, or an algorithms textbook. Marc

3 8

Profiler: Following changes from a remote directory with custom modifications
by Erick Lavoie 28 Jun '10

28 Jun '10

See the original GDoc document <http://docs.google.com/Doc?docid=0ARkLUElWcqxDZGdkOWo3c2ZfOTloamhkNm1ocw&hl…> to have access to the nice drawing ;-). <http://docs.google.com/Doc?docid=0ARkLUElWcqxDZGdkOWo3c2ZfOTloamhkNm1ocw&hl…> Erick Git Notes Following changes from a remote directory with custom modifications Git provides tools which can be used to ease maintaining a set of patches in sync with an evolving project. The instrumentation of WebKit is an example of that kind of usage. The most interesting usage is the automatic application of modifications to newer code, when no conflicts arise. This can be done either by merging with newer commits or rebasing commits on top of newer ones. For a comparison between the two approches, see this blog post <http://softwareswirl.blogspot.com/2009/04/truce-in-merge-vs-rebase-war.html>. Rebasing will be preferred here because it allows an easier review of the commits by someone not familiar with the code by only requiring understanding how the changes are made related to a specific version of the master code. However that kind of usage is potentially dangerous in a distributed version control system. It modifies the history of commits which renders merging between independently developed branches a lot harder when someone else has made commits on top of a rebased branch. Without care, it creates duplicates entries in the history. Even with care, it forces everyone with a copy of the branch to manually fix their history. See the official git-rebase documentation <http://www.kernel.org/pub/software/scm/git/docs/git-rebase.html>, especially the section "Recovering from upstream rebase". By leaving the old branches into place, we should avoid having people manually fix their history. They will simply have to track an additional branch each time we rebase the changes. It also has the effect of leaving previous versions available, should we need to reproduce the traces we made in the past (as long as the website's javascript code doesn't change significantly...). In the case of WebKit, I suggest having branches with the following naming convention: "prof_svn<rev nb>" where <rev nb> is the svn revision number mentioned in the commit message of the base git commit. In the following example: The profiler should have a branch name of "prof_svn40". After some time, when we want to profile a more recent version of WebKit we use the following commands: git checkout master git pull upstream master # Add the latest changes in the master branch git log -n 1 # Retrieve the svn revision number from the commit message git checkout prof_svn40 # Switch to the profiler branch git checkout -b prof_svn42 # Create a new branch containing the same commits git rebase master # Rebase all the commits on top of the HEAD of master We should end up with the following repository: Note that further modifications of older branches will need to be ported manually to newer versions so we should restrain from doing this. Google Docs makes it easy to create, store and share online documents, spreadsheets and presentations. Google Docs logo <http://docs.google.com>

3 5

One month old
by Marc Feeley 24 Jun '10

24 Jun '10

The first commit to the repository was exactly one month ago! Let there be many more happy anniversaries (mensuaries?) in the future. The repository now has about 10,000 lines of JavaScript code (if we ignore the test files and parser.js which is in large part generated by a script). Marc

2 1

Variant of inline caching
by Marc Feeley 24 Jun '10

24 Jun '10

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

2 1

Whiteboard snapshots for Object Representation
by Erick Lavoie 23 Jun '10

23 Jun '10

2 1

hash-table vs. linear search
by Marc Feeley 22 Jun '10

22 Jun '10

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

4 5

x86 programmer model
by Marc Feeley 19 Jun '10

19 Jun '10

Here is the x86 programmer model I showed in today's meeting. The 8086 subset is in dark pink. The whole thing is for 80386. The x86-64 extends the general purpose registers to 64 bits (RAX, RBX, ...), and adds 8 general purpose registers (R8 ... R15). Marc

1 0

Code review
by Marc Feeley 18 Jun '10

18 Jun '10

Hello, I've looked at some of the new code (I do regular 'git pull' on the project) and have some comments, which I discuss below. It occurred to me that it might be a good practice to do regular code reviews to catch bugs and understand the code base we are creating. What are your thoughts about this? As for the comments, here they are... File source/ir/instructions.js : /** @class String constant value @augments ConstInstr */ function StrConst(value) { /** Get a string representation of a string constant */ this.toString = function() { return '"' + String(this.value) + '"'; } ... } 1) There's a semicolon missing at the end of the assignment this.toString = ... 2) It would be more space efficient to do, after the function definition, StrConst.prototype.toString = ... (I didn't have that habit when I wrote the parser, but in new code I am now using that style as it can save a lot of space for objects that are frequent). 3) It might be very OOish to have separate classes for each type of constant (null, undefined, boolean, integer, float, string, object) as subclasses to the ConstInstr, but I don't see the point. The code becomes very verbose for no apparent benefit. In the AST there is just one node type for literals with the field "value", and JS introspection can be used on the value when it is important to know the type of value (i.e. typeof x.value == "number"). For example, to test for a constant that is a number equal to 0, it would be possible to do if (x.value === 0) ... instead of if (x instanceof IntConst && x.value == 0) ... Moreover, to test for a number n it would be possible to do if (x.value === n) ... instead of if ((x instanceof IntConst || x instanceof FPConst) && x.value == n) ... If a class hierarchy is used for constants, why stop at those specific types? Why not also have subclasses of "boolean" for "true" and "false", and a subclass of integer for nonnegative integers, and one for 32 bit integers (or fixnums)? Also, to be consistent, the integer and float subclasses should have a "number" superclass. For other types of instructions I agree that a class hierarchy can be beneficial for code clarity and modularity. 4) What is an "Object" constant? I fail to see when it would be useful. In JS the notations [ ... ] and { ... } construct *new* objects when they are evaluated, even when all their fields are constant, including when there are no fields or elements. For example: function f() { return []; } print(f() == f()); // prints false print(f() === f()); // prints false 5) What is a "ConstInstr"? Is it a constant instruction? What does a constant *instruction* do? Perhaps "ConstExpr", for constant expression, or "ConstOperand" would be a better name? 6) The toString function for strings as written above does not generate the proper escapes for embedded special characters. I understand that this was probably coded expediently to hack something together quickly. I'm in the habit of leaving a "TODO" comment for such code so that I remember to come back to it later and actually implement the proper behaviour. 7) The toString function for strings (which generates escapes) is needed in several places, including the AST pretty-printer, so this is definitely a function that should be in a global module (such as a "miscellaneous" module misc.js). I'm happy to see that the code base is growing quickly! Marc

2 1

Whiteboard snapshots from object layout meeting
by Bruno Dufour 17 Jun '10

17 Jun '10

1 0

Whiteboard snapshots from today's meeting
by Bruno Dufour 16 Jun '10

16 Jun '10

2 1