Tachyon-list

tachyon-list@iro.umontreal.ca

258 discussions

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

Low funds, reduce, reuse, recycle
by Marc Feeley 28 Fév '11

28 Fév '11

Well, my funds have run dry a bit sooner than expected. So there will be no new equipment purchases before the next instalment from NSERC in April. I recently purchased two powerful computers for the lab. Benoit is using a workstation (tawa) with a fast Intel quad core CPU with 16 GB of RAM and a 128 GB SSD. We also have a new server (12 cores, 48 GB RAM) that will be installed soon. Maxime, you say you would benefit from a fast Linux machine for which you have administrator privileges. How about installing "virtual box" (http://www.virtualbox.org/) on tawa and the server and installing Linux in it? With virtual box we could easily test Tachyon on different operating systems without switching machines. Marc

2 1

What's Missing
by chevalma＠iro.umontreal.ca 25 Fév '11

25 Fév '11

At this point we can compile all of the Tachyon code and initialize all of the code units. Our bootstrap is still not *quite* there yet, however. I've been spending most of the day finishing up code intended to make all of our C extensions accessible under the bootstrapped Tachyon (eg: readFile, writeFile, shellCommand, allocMachineCodeBlock, etc.). At this point, all the code is written and compiles, although some of it is hard to test outside of the Tachyon bootstrap. We still need two things to be done before Tachyon can truly execute once compiled: 1. Yesterday I discovered what appears to be a backend bug when compiling ptrToByteArray (runtime/ffi.js). This should hopefully be a minor fix. 2. Because we don't support byte arrays mapped to memory like V8 does, I made a wrapper to write bytes into a machine code block. We will need to change the backend code to write bytes using writeToMachineCodeBlock (see runtime/mcb.js). This should be a fairly trivial refactoring. Once this is done, Tachyon should have everything it needs to run (and compile code) in bootstrapped mode. We will probably make Tachyon drop into its shell once the bootstrap is successfully completed. What remains then is to eliminate the remaining bugs in our system. I suspect we will easily run out of memory (since our heap is currently fixed at 64MB), so I've added a heap limit pointer to the context (we will get an error if this limit is exceeded). The best we can do for now, in terms of debugging, is probably to add more assertions to our code, and use Marc's debugging traces. On this topic, Marc, did you have time to write code to log function returns? If we can know more precisely where Tachyon crashes, it will probably be a huge time saver. I will be in the lab this Monday, doing my best to squash the remaining bugs. - Maxime

1 0

Tachyon initialization complete
by Marc Feeley 25 Fév '11

25 Fév '11

I have managed to work around the d8 GC bug by adding the --nocollect_maps when invoking d8. That means that after 10 minutes of execution on my MacBook Pro, the "make bootstrap" ends with: ... Linking machine code for: "backend/x86/config.js" Linking machine code for: "backend/x86/ir-to-asm.js" Linking machine code for: "backend/x86/asm.js" Linking machine code for: "main.js" Tachyon initialization complete Yay! Now... how do we actually execute the bootstrapped Tachyon? I guess the champagne bottle won't be spending much more time in the fridge... ;-) Marc

3 2

V8 bug
by Marc Feeley 24 Fév '11

24 Fév '11

It seems that the GC bug in V8 is something the V8 developers have been aware of for some time, but have not been able to track down and debug because they don't have a deterministic test setup where they can reproduce the bug. I sent them a message on this wiki: http://code.google.com/p/chromium/issues/detail?id=59688 and they responded with: Comment 15 by project member vegorov(a)chromium.org, Today (3 hours ago) These are amazing news, Marc! Yes we would very appreciate a reproduction! CreateBackPointers traverses map's transition tree and creates back pointers (from transition target to it's source). This is a preparation step for a full garbage collection. GC will use these pointers to properly handle maps which are no longer used by any live object but still should be retained because they are part of the path between two used maps. So I suggest that we create a tar ball we can send them with the relevant sources, and instructions on how to recompile d8, and how to reproduce the bug. Who can take charge of this? Marc

2 2

Bus Error...
by Erick Lavoie 23 Fév '11

23 Fév '11

Following Marc suggestion to execute d8 in gdb to be able to inspect the stack frame after the error, we found that the error originates from d8 in the garbage collector: Generating machine code for: "ir/ast-to-ir.js" Program received signal EXC_BAD_ACCESS, Could not access memory. Reason: KERN_PROTECTION_FAILURE at address: 0x00000023 0x001ee138 in v8::internal::Map::CreateBackPointers () (gdb) bt #0 0x001ee138 in v8::internal::Map::CreateBackPointers () #1 0x001de423 in v8::internal::MarkCompactCollector::CreateBackPointers () Previous frame inner to this frame (gdb could not unwind past this frame) I tried compiling d8 in debug mode but I still get the same error (the address was 0x0000000d for that run). For the record, Map::CreateBackPointers can be found in v8/src/objects.cc. I am wondering if some of our extensions might not interact well with the gc. Erick

2 1

Review utility/num.js
by Erick Lavoie 22 Fév '11

22 Fév '11

Overall the code is really well done and clear. However here is some issues I ran into: bignum_from_js: Using ">>" and "&" breaks when n is not representable on 32 bits, see 11.7.2 and 11.10 in ECMAScript 5. Ex: d8> Math.pow(2,30) >> 29 2 d8> Math.pow(2,32) >> 31 0 Bitwise arithmetic in javascript is done on 32 bits integer. That means we cannot create a bignum from a js number which takes more than 32 bits to represent. bignum_mod: In javascript, the sign of the result is the sign of the dividend, see 11.5.3 (ES 5). For uniformity, I think we might want to stick to the same convention. Erick

2 2

Parser Debugging Tools
by chevalma＠iro.umontreal.ca 22 Fév '11

22 Fév '11

I'm in the process of trying some of the more basic Tachyon code in Tachyon and I think we're at the point where we will be needing more powerful debugging tools. Marc, I remember you mentioning you had code for an ast pass that added print statements at the entry and exit of functions. Could you implement a parser flag to enable this in Tachyon? This will help me solve those annoying segfaults. - Maxime

2 1

JavaScript Performance Data
by chevalma＠iro.umontreal.ca 20 Fév '11

20 Fév '11

I found out that the Computer Language Benchmark Game has some performance data for JavaScript on both V8 and TraceMonkey: http://shootout.alioth.debian.org/ You can compare the performance against other language implementations for the same benchmarks, such as G++: http://shootout.alioth.debian.org/u64/benchmark.php?test=all&lang=v8&lang2=… http://shootout.alioth.debian.org/u64/benchmark.php?test=all&lang=tracemonk… Apparently this was run under a recent version of V8. It's nice to see that there's still a significant performance gap, and hence room for improvement. The pidigits benchmark is one on which both implementations do extremely poorly. - Maxime

2 1

Aller à la page :

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

Tachyon-list