Tachyon-list Mars 2011

tachyon-list@iro.umontreal.ca

4 participants
45 discussions

Basic GC Implementation
by chevalma＠iro.umontreal.ca 02 Mar '11

02 Mar '11

I added a document to google docs under Tachyon/Tech Notes detailing the changes I can see being necessary to our current implementation in order to facilitate the GC implementation. I think I'll be able to complete my part by next Wednesday. I basically intend to auto-generate C functions that can call a GC visit function on all the pointers in heap objects. This code will be generated in function of our object layouts. It should also include debugging assertions (sanity checks) to make sure we aren't improperly leaking object references in raw pointers, or have object references pointing outside of our heap. I would also advise to perhaps have GC maps with *2 bits per object*. This way we can indicate whether stack slots are boxed references, unboxed references, raw pointers or other. This would allow more sanity checks in the GC, which might save us valuable debugging time (we'll know much faster if we're doing something stupid). Perhaps including some kind of function identifier in the GC map might also be useful (it would also facilitate stack trace generation). - Maxime

1 0

Trip to Californye-A
by chevalma＠iro.umontreal.ca 01 Mar '11

01 Mar '11

Say, if my girlfriend and I want to plan a little extended trip around the time we'll be visiting our friends from the south, can we count on the dates for the meeting being pretty much set at this point? I'm assuming the meeting will take place all day on the 28th of March? - Maxime

1 0

tracing execution
by Marc Feeley 01 Mar '11

01 Mar '11

For debugging Tachyon, I have improved the function call tracing mechanism in the js2js preprocessor. I also added a makefile target, "make tachyon-debug.js", which generates a version of the compiler in one file which traces all the function calls. Here's an example: % make tachyon-debug.js parser/js2js -debug utility/debug.js utility/system.js utility/iterators.js utility/graph.js utility/arrays.js utility/heap.js utility/hashmap.js utility/hashset.js utility/linkedlist.js utility/strings.js utility/modules.js utility/misc.js utility/num.js utility/xml.js utility/html.js compiler/targets.js compiler/params.js compiler/config.js compiler/compiler.js compiler/init.js compiler/bootstrap.js parser/misc.js parser/scanner.js parser/parser.js parser/pp.js parser/ast-passes.js ir/types.js ir/static.js ir/instructions.js ir/constants.js ir/iir.js ir/cfg.js ir/functions.js ir/ast-to-ir.js ir/optpatterns.js ir/constprop.js ir/commelim.js ir/inlining.js ir/lowering.js platform/ffi.js platform/mcb.js runtime/layout.js runtime/context.js runtime/objects.js backend/asm.js backend/regalloc.js backend/linearscan.js backend/backend.js backend/x86/asm.js backend/x86/config.js backend/x86/ir-to-asm.js main.js > tachyon-debug.js % d8 tachyon-debug.js | (( "utility/iterators.js"@13.1-17.2: Iterator | | (( "utility/debug.js"@73.1-77.2: assertNew | | | (( "utility/debug.js"@62.1-68.2: isGlobal | | | | (( "utility/debug.js"@65.19-65.47: isGlobal | | | | )) "utility/debug.js"@65.33-65.45: isGlobal | | | )) "utility/debug.js"@67.5-67.27: isGlobal | | )) "utility/debug.js"@73.1-77.2: assertNew | )) "utility/iterators.js"@16.5-16.17: Iterator | (( "utility/iterators.js"@13.1-17.2: Iterator | | (( "utility/debug.js"@73.1-77.2: assertNew | | | (( "utility/debug.js"@62.1-68.2: isGlobal | | | | (( "utility/debug.js"@65.19-65.47: isGlobal | | | | )) "utility/debug.js"@65.33-65.45: isGlobal | | | )) "utility/debug.js"@67.5-67.27: isGlobal | | )) "utility/debug.js"@73.1-77.2: assertNew | )) "utility/iterators.js"@16.5-16.17: Iterator ... The symbol (( indicates a function entry and )) indicates a function return (this is convenient to navigate in an editor which matches parentheses, between the entry and return). The indentation indicates the call nesting. Finally, when it is known, the function name is printed. The execution is rather slow because all the function are traced. To filter out some functions, you'll have to manually edit the file function filter_debug in parser/ast-passes.js . You can filter out all the functions in a file, or specific functions. Here's the current implementation of that function: ast_pass1_ctx.prototype.filter_debug = function (ast) { // TODO: This filtering should be user configurable from a command line option. if (ast.loc.filename === "parser/parser.js" || ast.loc.filename === "parser/scanner.js" || // ast.loc.filename === "utility/debug.js" || (this.fn_decl !== null && this.fn_decl.id.toString() === "assert")) return false; return true; } I'm thinking that we could extend the tracing facility to get timing information and also space usage information. The relevant functions to change are defined in the function walk_statement in parser/ast-passes.js : ast_pass1_ctx.prototype.walk_statement = function (ast) { if (ast === null) { // no transformation return ast; } else if (ast instanceof Program) { var debug_lib = " \ \ var debug$print = print; \ var debug$nesting = 0; \ \ function debug$nest(loc, fn, enter) \ { var level = enter ? ++debug$nesting : debug$nesting--; \ var prefix = \"\"; \ if (level > 9) { prefix = \"|[\"+level+\"] \"; level = 8; } \ while (level-- > 0) prefix = \"| \" + prefix; \ debug$print(prefix+(enter?\"((\":\"))\")+\" \"+loc+\": \"+fn); \ } \ \ function debug$enter(loc, fn) \ { debug$nest(loc, fn, true); } \ \ function debug$return0(loc, fn) \ { debug$nest(loc, fn, false); } \ \ function debug$return1(loc, fn, result) \ { debug$nest(loc, fn, false); \ return result; \ } \ \ "; Marc

2 1

parse_identifier
by Marc Feeley 01 Mar '11

01 Mar '11

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; }

2 1

Memory usage for parsing
by Erick Lavoie 01 Mar '11

01 Mar '11

On the good side, we have squashed enough bugs to start parsing after the bootstrap. On the less good side, even with a heap of 256MB we are unable to parse the fibonacci program because too much memory is being allocated. Maxime thinks we might be able to do it if we optimize the current implementation of the parser (and the rest of the compiler...). I think that given the current implementation, we might need a GC to be able to bootstrap. To test it on your own machine, simply run "make bt-parser" with the latest revision of the master branch. I'll try to find how much memory tachyon allocates on d8 when compiling fibonacci. Erick

4 6

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

Tachyon-list Mars 2011