parse_identifier - Tachyon-list

1 Mar 2011


      I modified the parser to try to save some space when reading identifiers.  The parse_identifier method used an algorithms which started with an empty array of characters, and used "push" to add the characters that were read, and finally a String.fromCharCode.apply(null,chars) to convert the array into a string.  The extensions of the array when growing it cause garbage to be created.
The new algorithm (copied below) is recursive and does not generate garbage for the construction of the array.  An array of exactly the correct length is allocated.  Note that the characters that are part of the identifier are temporarily saved on the stack, but the stack will be reclaimed when the recursion unwinds.
In V8 it saved 4% of the space allocated while parsing 200,000 lines of code.  So not a big saving.  Perhaps in Tachyon it would be different, but probably still not significantly when compared to the rest of the compilation pipeline.
Similar algorithms could be used for parsing numbers and strings.  The same idea could be used elsewhere too instead of using "push" on an initially empty array.
Something which would have more impact on space is to use a real Array to store the characters of a string.  That way the String.fromCharCode.apply operation would not have to copy the array.  Alternatively, we could implement an abstraction to allocate the internal array of characters, and mutate these arrays.  There would be an implementation in pure JavaScript (using Arrays), and one for Tachyon.
Marc
// method parse_identifier()
Scanner.prototype.parse_identifier_old = function ()
{
    // This iterative algorithm extends the Array of characters using the
    // "push" method.  The growth of the array generates garbage.
var start_pos = this.lookahead_pos(0);
    var chars = [];
    var h = 0;
    for (;;)
    {
        var c = this.lookahead_char(0);
        if (!(this.identifier_class(c) || this.decimal_class(c)))
            break;
        this.advance(1);
        chars.push(c);
        h = (h * HASH_MULT + c) % HASH_MOD;
    }
    var id = String.fromCharCode.apply(null,chars);
    var x = keyword_hashtable[h];
    if (x !== null && x.id === id)
        return this.valued_token(x.cat, id, start_pos);
    else
        return this.valued_token(IDENT_CAT, id, start_pos);
};
Scanner.prototype.parse_identifier = function ()
{
    var start_pos = this.lookahead_pos(0);
    var id = this.parse_identifier_string();
    var h = 0;
    for (var i=0; i<id.length; i++)
        h = (h * HASH_MULT + id.charCodeAt(i)) % HASH_MOD;
    var x = keyword_hashtable[h];
    if (x !== null && x.id === id)
        return this.valued_token(x.cat, id, start_pos);
    else
        return this.valued_token(IDENT_CAT, id, start_pos);
};
Scanner.prototype.parse_identifier_string = function ()
{
    return String.fromCharCode.apply(null,
                                     this.parse_identifier_string_loop(0));
}
Scanner.prototype.parse_identifier_string_loop = function (n)
{
    // This recursive algorithm saves the characters on the stack
    // and allocates an array of the correct size to hold them.
    // It does not generate garbage.
var chars;
    var c = this.lookahead_char(0);
if (this.identifier_class(c) || this.decimal_class(c))
    {
        this.advance(1);
        chars = this.parse_identifier_string_loop(n+1);
        chars[n] = c;
    }
    else
    {
        chars = new Array(n);
    }
return chars;
}