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
Afficher les réponses par date
I added the "mem-fib" target to the makefile to compute an approximation of the total memory allocation made by tachyon to initialize the runtime and compile fib. The result of adding all allocations logged by the gc is over 650 MB.
The result is automatically computed using a python script when calling the "mem-fib" target and the trace produced can be found in "gc_trace.txt".
The compilation for fib uses less than 50 MB on v8 (The total heap size before compiling fib is around 45 MB and no gc is triggered during fib compilation). It means that our object representation uses at least 5X more memory than v8, only on parsing.
Erick
Le 11-02-28 18:43 , Erick Lavoie a écrit :
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
The compilation for fib uses less than 50 MB on v8 (The total heap size before compiling fib is around 45 MB and no gc is triggered during fib compilation). It means that our object representation uses at least 5X more memory than v8, only on parsing.
I don't think the issue is really one of object size. I would guess that our objects are about as big as theirs by default.
The real issue is probably that we create alot of temporary objects during parsing. Our standard library code, for example, converts strings to char code arrays before processing them. If the parser uses the String functions alot, it may be creating temporary arrays and strings every time it does so, which at the time, we have no way of reclaiming since we have no GC.
V8 probably has standard library code that makes less spurious allocations. Our current library code, particularly the string code, does alot of allocations that could probably be avoided. I think just calling String.prototype.charAt will allocate memory for each call, for example.
If we look more carefully at what string functions the parser uses, and optimize those, we may be able to get farther in the compilation. If there are about 650 MB of allocations to initialize the standard library while running in V8, though, that's a little steep to run without a GC, but still possible.
- Maxime
Optimizing the parser is not the solution. Even if we rewrite it to allocate very little memory, the other parts of the compiler will be allocating lots more memory. Recall that the parsing takes a small fraction of the total execution time, and the execution time is a good measure of the allocation rate, so the rest of the compiler probably allocates a lot.
We need a global optimization called "garbage collection".
Marc
P.S. are we sure the problem is not that repeated array operations, such as series of pushes, generate quadratic space usage? That could explain part of the problem...
On 2011-02-28, at 10:35 PM, chevalma@iro.umontreal.ca wrote:
The compilation for fib uses less than 50 MB on v8 (The total heap size before compiling fib is around 45 MB and no gc is triggered during fib compilation). It means that our object representation uses at least 5X more memory than v8, only on parsing.
I don't think the issue is really one of object size. I would guess that our objects are about as big as theirs by default.
The real issue is probably that we create alot of temporary objects during parsing. Our standard library code, for example, converts strings to char code arrays before processing them. If the parser uses the String functions alot, it may be creating temporary arrays and strings every time it does so, which at the time, we have no way of reclaiming since we have no GC.
V8 probably has standard library code that makes less spurious allocations. Our current library code, particularly the string code, does alot of allocations that could probably be avoided. I think just calling String.prototype.charAt will allocate memory for each call, for example.
If we look more carefully at what string functions the parser uses, and optimize those, we may be able to get farther in the compilation. If there are about 650 MB of allocations to initialize the standard library while running in V8, though, that's a little steep to run without a GC, but still possible.
- Maxime
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
Optimizing the parser is not the solution. Even if we rewrite it to allocate very little memory, the other parts of the compiler will be allocating lots more memory.
If just parsing fib takes over 256MB of heap space, there is obviously something we can do to optimize that. Furthermore, it's not necessarily the parser we should tweak here, rather the string functions.
Recall that the parsing takes a small fraction of the total execution time, and the execution time is a good measure of the allocation rate, so the rest of the compiler probably allocates a lot.
Allocations are currently very fast, and as I explained, our string code is very wasteful. I would bet the IR code allocates less than the parser, even though it's several times slower. Obviously, that's still no guarantee we can bootstrap without a GC.
We need a global optimization called "garbage collection".
I agree that we need a GC. Either that or we need to make Tachyon run in 64-bit mode so it can run on that server of yours with 48GBs of RAM ;)
P.S. are we sure the problem is not that repeated array operations, such as series of pushes, generate quadratic space usage?
Array pushes append elements at the end. If the arrays do not have enough capacity to push an element, their capacity is doubled.
- Maxime
On 2011-02-28, at 22:35 , chevalma@iro.umontreal.ca wrote:
The compilation for fib uses less than 50 MB on v8 (The total heap size before compiling fib is around 45 MB and no gc is triggered during fib compilation). It means that our object representation uses at least 5X more memory than v8, only on parsing.
I don't think the issue is really one of object size. I would guess that our objects are about as big as theirs by default.
I agree.
The real issue is probably that we create alot of temporary objects during parsing. Our standard library code, for example, converts strings to char code arrays before processing them. If the parser uses the String functions alot, it may be creating temporary arrays and strings every time it does so, which at the time, we have no way of reclaiming since we have no GC.
If the internal char array used by Strings is recreated each time a String function is called, then yes, this would could lead to a lot of objects staying in the heap. This conversion happens in (almost?) every function. My original thought when writing the code was that the internal String data would simply be exposed through the IIR.
V8 probably has standard library code that makes less spurious allocations. Our current library code, particularly the string code, does alot of allocations that could probably be avoided. I think just calling String.prototype.charAt will allocate memory for each call, for example.
I don't see why that is the case. True, the string functions can be rather wasteful, but the only memory that needs to be allocated (and that *should* be allocated) by charAt in particular is what is needed for the returned String object. If Strings are unique, then there should only be one such string per character at most, so it shouldn't be the cause for the high memory cost of parsing.
If we look more carefully at what string functions the parser uses, and optimize those, we may be able to get farther in the compilation. If there are about 650 MB of allocations to initialize the standard library while running in V8, though, that's a little steep to run without a GC, but still possible.
I tend to avoid speculative optimizations like what you're proposing, just because they often end up wasting more resources than what is gained. How could we easily gather evidence to point us toward the most profitable optimizations? I'm not suggesting that string optimizations are not at fault (although I'd like to verify that as well), but if they are, we need to determine which ones are the most hurtful in terms of allocated memory.
Bruno
the only memory that needs to be allocated (and that *should* be allocated) by charAt in particular is what is needed for the returned String object. If Strings are unique, then there should only be one such string per character at most, so it shouldn't be the cause for the high memory cost of parsing.
I agree that's how it should be. From memory, the way it works now is that charAt uses slice. the slice function converts the string to a charcode array (allocating an array). Then the relevant characters are extracted into a second array. Finally, a string is constructed from this... This allocates a string object, which we then lookup in the string table. If it's found in the string table, the one from the table is returned.
This could probably be optimized in at least two ways:
1. We could change the string code to directly read characters from string objects, eliminating the need for a char code array.
2. Instead of first allocating strings and then looking them up in the string table, it might be useful to have some kind of a system where we can write characters into a mutable buffer. When done, we can lookup the data from that buffer into the string table, and allocate a new string object only if its not found in the table. Ideally, the buffer would be kept alive (we could have a pointer to it in the context) between queries. It could have a fixed size that works well for common small strings (eg: 2KB). For bigger strings, we could allocate a bigger buffer and drop it afterwards.
I tend to avoid speculative optimizations like what you're proposing, just because they often end up wasting more resources than what is gained. How could we easily gather evidence to point us toward the most profitable optimizations? I'm not suggesting that string optimizations are not at fault (although I'd like to verify that as well), but if they are, we need to determine which ones are the most hurtful in terms of allocated memory.
Well, I'm not sure right now is necessarily the best time to do string optimizations. I'm guessing most of our time in the immediate future will go towards writing a GC. However, it probably wouldn't be so difficult to optimize most or all string functions in the way I just described.
- Maxime
-
Bruno Dufour -
chevalma＠iro.umontreal.ca -
Erick Lavoie -
Marc Feeley