[Pharo-project] Counting Messages as a Proxy for Average Execution Time in Pharo
Hi! There has been many discussion on profiling and execution. I believe the paper titled "Counting Messages as a Proxy for Average Execution Time in Pharo" draws some bases for a new generation of code profilers that are not tied to execution sampling. Advantages are numerous without not that many drawbacks. http://bergel.eu/download/papers/Berg11c-compteur.pdf I will put some effort on having "Compteur" in the main Pharo vm. This has to be carefully done and monitored to make sure there is no unwanted overhead. In the experience I have done, there is no overhead. I have started to get in touch with people close to the VM. I will keep you informed, especially when reviews and testing will be needed. One very cool think that everybody can benefit from, is to be able to write assertion in unit tests like: self assertIs: [ "expression1" ] fasterThan: [ "expression2" ] It compares the amount of messages sent by expression1 with the amount of messages sent by expression2, no matter how many messages are sent. Counting messages is, in the average, closely link to the average execution time. This cannot be done with [ ... ] timeToRun or MessageTally. I will keep you informed. Cheers, Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Alex, On 28 April 2011 15:37, Alexandre Bergel <alexandre.bergel@me.com> wrote:
Counting messages is, in the average, closely link to the average execution time.
I believe this is correct only as long as a purely interpreting VM is used, even though quick messages add a tiny bit of uncertainty. But add a JIT compiler and some inlining, and timeToRun and MessageTally are suddenly interesting again. Not having read your text, I surely cannot say anything remotely conclusive, but the assumption that execution time roughly equals the amount of messages sent seems rather naïve once you leave the cosy well-predictable niche inhabited by pure interpreters. Best, Michael
Hi: On 28 Apr 2011, at 14:57, Michael Haupt wrote:
On 28 April 2011 15:37, Alexandre Bergel <alexandre.bergel@me.com> wrote:
Counting messages is, in the average, closely link to the average execution time. In the setting of the paper, that might be correct. Even for the stated goal of optimizing for performance, it might still be interesting. However, the optimizations done based on this criteria are bound to one specific VM implementation.
I believe this is correct only as long as a purely interpreting VM is used, even though quick messages add a tiny bit of uncertainty. But add a JIT compiler and some inlining, and timeToRun and MessageTally are suddenly interesting again. Or have a VM that is not Squeak, and perhaps use a language that is not used in the style Smalltalk is (7 lines of code per method, right?).
Have only skimmed the paper, Alexandre, so excuse the perhaps stupid question: Why don't you just count the number of executed bytecodes? The correlation between bytecodes and execution time should be even more close than messages to exec time. Bye the way, the remark on the mismatch between OO programming and profiling: profiling is about the execution model, and the execution model of Smalltalk is based on a stack machine. To me the execution model seems to be orthogonal to the structuring of the code. I don't see how you can really abstract from that, without coming up with a 'object-oriented' execution model (what ever that would be). Perhaps, the closest to that would be an actor-based execution model, like Erlang's language semantics. No stacks just message buffers. Best regards Stefan -- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525
Counting messages is, in the average, closely link to the average execution time. In the setting of the paper, that might be correct. Even for the stated goal of optimizing for performance, it might still be interesting. However, the optimizations done based on this criteria are bound to one specific VM implementation.
Not only to the VM, but also to the compiler.
I believe this is correct only as long as a purely interpreting VM is used, even though quick messages add a tiny bit of uncertainty. But add a JIT compiler and some inlining, and timeToRun and MessageTally are suddenly interesting again. Or have a VM that is not Squeak, and perhaps use a language that is not used in the style Smalltalk is (7 lines of code per method, right?).
Yes, but there hasn't been a major change on the VM front since I started Smalltalk. Cog is the notable exception, but the assumption I made without Cog remains valid with Cog.
Have only skimmed the paper, Alexandre, so excuse the perhaps stupid question: Why don't you just count the number of executed bytecodes? The correlation between bytecodes and execution time should be even more close than messages to exec time.
Indeed, it does. Counting bytecode instructions is also a valid way to estimate average execution time. There is some work on this (cf the related work section). Counting bytecode is more expensive than counting messages. In general, my opinion is that OO programming is about sending messages, not executing bytecode. Message counting has also the advantage to be friendlier with a JIT.
Bye the way, the remark on the mismatch between OO programming and profiling: profiling is about the execution model, and the execution model of Smalltalk is based on a stack machine. To me the execution model seems to be orthogonal to the structuring of the code. I don't see how you can really abstract from that, without coming up with a 'object-oriented' execution model (what ever that would be). Perhaps, the closest to that would be an actor-based execution model, like Erlang's language semantics. No stacks just message buffers.
Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable, and so, whatever the effort you will put in the thread scheduling, memory management or whatsoever. I am simply focusing on sending messages, which is in my opinion, the essence of the OO executing model. Using a stack machine is an implementation matter. It is not essential to OO. Alexandre
Best regards Stefan
-- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Hi Alex, On 28 April 2011 18:14, Alexandre Bergel <alexandre.bergel@me.com> wrote:
Or have a VM that is not Squeak, and perhaps use a language that is not used in the style Smalltalk is (7 lines of code per method, right?).
Yes, but there hasn't been a major change on the VM front since I started Smalltalk. Cog is the notable exception, but the assumption I made without Cog remains valid with Cog.
do you mean "on the *Smalltalk* VM front"? I'm pretty sure you do. :-)
Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable, and so, whatever the effort you will put in the thread scheduling, memory management or whatsoever.
I think you're being a bit harsh on stack sampling there. It is exact enough to drive optimisation in some really high-performance VMs. It is also deterministic enough to yield data leading to very good performance results in those VMs. Whether focusing on counting messages instead of taking samples is more beneficial would have to be determined by experiment ... What you mean with "non-portable" I do not understand.
I am simply focusing on sending messages, which is in my opinion, the essence of the OO executing model.
Yup, good point. Best, Michael
Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable, and so, whatever the effort you will put in the thread scheduling, memory management or whatsoever.
I think you're being a bit harsh on stack sampling there. It is exact enough to drive optimisation in some really high-performance VMs. It is also deterministic enough to yield data leading to very good performance results in those VMs. Whether focusing on counting messages instead of taking samples is more beneficial would have to be determined by experiment ...
Yes, 25 pages of experiment :-)
What you mean with "non-portable" I do not understand.
The information about the execution time contained in your profile cannot be compared with a new profile realized on a different machine, with a different CPU. Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Hi Alex, On 29 April 2011 00:08, Alexandre Bergel <alexandre.bergel@me.com> wrote:
I think you're being a bit harsh on stack sampling there. It is exact enough to drive optimisation in some really high-performance VMs. It is also deterministic enough to yield data leading to very good performance results in those VMs. Whether focusing on counting messages instead of taking samples is more beneficial would have to be determined by experiment ...
Yes, 25 pages of experiment :-)
oh, I was not referring to your paper. I was referring to the general applicability of message counting as opposed to sampling. The latter is true-and-tried in many high performance VMs. For the former, an experiment has yielded good results (from what I take from this thread - I still haven't read your paper, sorry, it's on top of the pile) in a constrained setting. All I was saying is that it is not possible to conclude anything for the broader area from the experiments you conducted. But we're probably of the same opinion here.
What you mean with "non-portable" I do not understand.
The information about the execution time contained in your profile cannot be compared with a new profile realized on a different machine, with a different CPU.
That is correct, but the approach itself is portable - may I quote you: "Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable". You weren't talking about the results. Those are obviously specific to the platform, clock frequency, L1/L2/L3 cache and memory sizes, application input (!) and other factors. Best, Michael
+1 Alexandre On 28 Apr 2011, at 17:35, Michael Haupt wrote:
Hi Alex,
On 29 April 2011 00:08, Alexandre Bergel <alexandre.bergel@me.com> wrote:
I think you're being a bit harsh on stack sampling there. It is exact enough to drive optimisation in some really high-performance VMs. It is also deterministic enough to yield data leading to very good performance results in those VMs. Whether focusing on counting messages instead of taking samples is more beneficial would have to be determined by experiment ...
Yes, 25 pages of experiment :-)
oh, I was not referring to your paper. I was referring to the general applicability of message counting as opposed to sampling. The latter is true-and-tried in many high performance VMs. For the former, an experiment has yielded good results (from what I take from this thread - I still haven't read your paper, sorry, it's on top of the pile) in a constrained setting. All I was saying is that it is not possible to conclude anything for the broader area from the experiments you conducted. But we're probably of the same opinion here.
What you mean with "non-portable" I do not understand.
The information about the execution time contained in your profile cannot be compared with a new profile realized on a different machine, with a different CPU.
That is correct, but the approach itself is portable - may I quote you: "Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable". You weren't talking about the results. Those are obviously specific to the platform, clock frequency, L1/L2/L3 cache and memory sizes, application input (!) and other factors.
Best,
Michael
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
One silly idea while reading this thread (not the paper): For single core, the idea makes sense. It may even extend easily to multicore VM (just forget about Smalltalk for a while) by counting message sent per core and taking the max. Nicolas 2011/4/29 Alexandre Bergel <alexandre.bergel@me.com>:
+1
Alexandre
On 28 Apr 2011, at 17:35, Michael Haupt wrote:
Hi Alex,
On 29 April 2011 00:08, Alexandre Bergel <alexandre.bergel@me.com> wrote:
I think you're being a bit harsh on stack sampling there. It is exact enough to drive optimisation in some really high-performance VMs. It is also deterministic enough to yield data leading to very good performance results in those VMs. Whether focusing on counting messages instead of taking samples is more beneficial would have to be determined by experiment ...
Yes, 25 pages of experiment :-)
oh, I was not referring to your paper. I was referring to the general applicability of message counting as opposed to sampling. The latter is true-and-tried in many high performance VMs. For the former, an experiment has yielded good results (from what I take from this thread - I still haven't read your paper, sorry, it's on top of the pile) in a constrained setting. All I was saying is that it is not possible to conclude anything for the broader area from the experiments you conducted. But we're probably of the same opinion here.
What you mean with "non-portable" I do not understand.
The information about the execution time contained in your profile cannot be compared with a new profile realized on a different machine, with a different CPU.
That is correct, but the approach itself is portable - may I quote you: "Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable". You weren't talking about the results. Those are obviously specific to the platform, clock frequency, L1/L2/L3 cache and memory sizes, application input (!) and other factors.
Best,
Michael
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel  http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
On 28 Apr 2011, at 23:56, Nicolas Cellier wrote:
One silly idea while reading this thread (not the paper): For single core, the idea makes sense. It may even extend easily to multicore VM (just forget about Smalltalk for a while) by counting message sent per core and taking the max. So, why forget about Smalltalk in this context? If you don't like the performance of the RoarVM, just integrate the ideas into Cog :-P
*scnr* Bye the way, I just remember two interesting talks at OOPSLA'09, that are related: http://www.oopsla.org/oopsla2009/program/research-program/110-reliability-an...
How Java VM Can Get More from a Hardware Performance Monitor Inferred Call Path Profiling
Stefan -- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525
2011/4/29 Stefan Marr <pharo@stefan-marr.de>:
On 28 Apr 2011, at 23:56, Nicolas Cellier wrote:
One silly idea while reading this thread (not the paper): For single core, the idea makes sense. It may even extend easily to multicore VM (just forget about Smalltalk for a while) by counting message sent per core and taking the max. So, why forget about Smalltalk in this context? If you don't like the performance of the RoarVM, just integrate the ideas into Cog :-P
Sure, maybe the ;) were de rigueur. However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ? Nicolas
*scnr*
Bye the way, I just remember two interesting talks at OOPSLA'09, that are related: http://www.oopsla.org/oopsla2009/program/research-program/110-reliability-an...
How Java VM Can Get More from a Hardware Performance Monitor Inferred Call Path Profiling
Stefan
-- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: Â +32 2 629 3525
On 29 Apr 2011, at 00:32, Nicolas Cellier wrote:
However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ?
Sure, you have to do: n times: [ [ 1 expensiveComputation. ] fork ]. I don't belief in holy grails or silver bullets. Automatic parallelization is something nice for the kids, like Santa Clause or the Easter Bunny... Best regards Stefan -- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525
2011/4/29 Stefan Marr <pharo@stefan-marr.de>:
On 29 Apr 2011, at 00:32, Nicolas Cellier wrote:
However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ?
Sure, you have to do: n times: [ [ 1 expensiveComputation. ] fork ].
I don't belief in holy grails or silver bullets. Automatic parallelization is something nice for the kids, like Santa Clause or the Easter Bunny...
Best regards Stefan
Unless your hobby is oriented toward functional languages maybe... But I just know enough of it to now shut up ;) Nicolas
-- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: Â +32 2 629 3525
On 29 Apr 2011, at 01:07, Nicolas Cellier wrote:
However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ? Sure, you have to do: n times: [ [ 1 expensiveComputation. ] fork ].
I don't belief in holy grails or silver bullets. Automatic parallelization is something nice for the kids, like Santa Clause or the Easter Bunny...
Unless your hobby is oriented toward functional languages maybe... But I just know enough of it to now shut up ;) Would be nice, but that is also a fairy tale.
The best we have today, in terms of being 'easily' automatically scheduleable are data-flow/stream languages. Things like StreamIT or Lucid have interesting properties, but well, its still a search for the holly grail. Best regards Stefan -- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525
Hi Stefan, I though about your email. I do not understand why automatic parallelization is not the way to go. In my opinion, the computer has much more knowledge about the programmer about where side effects appear and where to cut or split a computation. Actually, if I want to be provocative, I would say that parallelization cannot be effective without being automatic. For a similar reason that the compiler will always know better than me how to properly allocate registers. I feel it would be cheaper for me to buy a faster computer than to learn how to program in a multi-core fashion. Cheers, Alexandre
However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ? Sure, you have to do: n times: [ [ 1 expensiveComputation. ] fork ].
I don't belief in holy grails or silver bullets. Automatic parallelization is something nice for the kids, like Santa Clause or the Easter Bunny...
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
I have a hunch that Stefan is referring to the PhD thesis of Charlotte Herzeel without giving names. As far as I understood from my discussions with her (and her talks), it generally doesn't really pay off to automatically parallelize on branches. You get minimal speedups (1% at best). I tend to agree with Stefan / Michael / Guy Steele... Maybe you don't need much, but the mapreduce style is the minimum requirement to give the language enough "wiggle room" to automatically parallelize stuff. But it DOES require you to restructure your application in a slightly more declarative fashion. cheers, Toon On 04/29/2011 04:55 PM, Alexandre Bergel wrote:
Hi Stefan,
I though about your email. I do not understand why automatic parallelization is not the way to go. In my opinion, the computer has much more knowledge about the programmer about where side effects appear and where to cut or split a computation.
Actually, if I want to be provocative, I would say that parallelization cannot be effective without being automatic. For a similar reason that the compiler will always know better than me how to properly allocate registers.
I feel it would be cheaper for me to buy a faster computer than to learn how to program in a multi-core fashion.
Cheers, Alexandre
However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ? Sure, you have to do: n times: [ [ 1 expensiveComputation. ] fork ].
I don't belief in holy grails or silver bullets. Automatic parallelization is something nice for the kids, like Santa Clause or the Easter Bunny...
Interesting result. But still, I feel that the computer should be able to do some inference. This could be at runtime, at compile time or during the development. I think than expecting the user to have the knowledge about how to parallelize an application is too much asking. I will read Charlotte's work. Alexandre On 29 Apr 2011, at 09:58, Toon Verwaest wrote:
I have a hunch that Stefan is referring to the PhD thesis of Charlotte Herzeel without giving names. As far as I understood from my discussions with her (and her talks), it generally doesn't really pay off to automatically parallelize on branches. You get minimal speedups (1% at best).
I tend to agree with Stefan / Michael / Guy Steele... Maybe you don't need much, but the mapreduce style is the minimum requirement to give the language enough "wiggle room" to automatically parallelize stuff. But it DOES require you to restructure your application in a slightly more declarative fashion.
cheers, Toon
On 04/29/2011 04:55 PM, Alexandre Bergel wrote:
Hi Stefan,
I though about your email. I do not understand why automatic parallelization is not the way to go. In my opinion, the computer has much more knowledge about the programmer about where side effects appear and where to cut or split a computation.
Actually, if I want to be provocative, I would say that parallelization cannot be effective without being automatic. For a similar reason that the compiler will always know better than me how to properly allocate registers.
I feel it would be cheaper for me to buy a faster computer than to learn how to program in a multi-core fashion.
Cheers, Alexandre
However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ? Sure, you have to do: n times: [ [ 1 expensiveComputation. ] fork ].
I don't belief in holy grails or silver bullets. Automatic parallelization is something nice for the kids, like Santa Clause or the Easter Bunny...
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Actually if you listen to Guy Steele's talk the whole point is to let the developer be even more ignorant than you are now. You shouldn't write "do" loops that start at the beginning and go until the end. You should just say that you want the calculation done and that your intent is that you have visited everything. And then of course you might have dependencies etc... but the idea is generally, don't say how to do it, just declare what you want as a result. Of course, it doesn't immediately match what we are used to doing: telling the computer how we want things done; but you can't really say that you have to tell the computer more about parallelization. It's exactly the opposite. On 04/29/2011 05:05 PM, Alexandre Bergel wrote:
Interesting result. But still, I feel that the computer should be able to do some inference. This could be at runtime, at compile time or during the development. I think than expecting the user to have the knowledge about how to parallelize an application is too much asking.
I will read Charlotte's work.
Alexandre
On 29 Apr 2011, at 09:58, Toon Verwaest wrote:
I have a hunch that Stefan is referring to the PhD thesis of Charlotte Herzeel without giving names. As far as I understood from my discussions with her (and her talks), it generally doesn't really pay off to automatically parallelize on branches. You get minimal speedups (1% at best).
I tend to agree with Stefan / Michael / Guy Steele... Maybe you don't need much, but the mapreduce style is the minimum requirement to give the language enough "wiggle room" to automatically parallelize stuff. But it DOES require you to restructure your application in a slightly more declarative fashion.
cheers, Toon
On 04/29/2011 04:55 PM, Alexandre Bergel wrote:
Hi Stefan,
I though about your email. I do not understand why automatic parallelization is not the way to go. In my opinion, the computer has much more knowledge about the programmer about where side effects appear and where to cut or split a computation.
Actually, if I want to be provocative, I would say that parallelization cannot be effective without being automatic. For a similar reason that the compiler will always know better than me how to properly allocate registers.
I feel it would be cheaper for me to buy a faster computer than to learn how to program in a multi-core fashion.
Cheers, Alexandre
However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ? Sure, you have to do: n times: [ [ 1 expensiveComputation. ] fork ].
I don't belief in holy grails or silver bullets. Automatic parallelization is something nice for the kids, like Santa Clause or the Easter Bunny...
On 29 Apr 2011, at 16:09, Toon Verwaest wrote:
You shouldn't write "do" loops that start at the beginning and go until the end. You should just say that you want the calculation done and that your intent is that you have visited everything. And then of course you might have dependencies etc... but the idea is generally, don't say how to do it, just declare what you want as a result.
Of course, it doesn't immediately match what we are used to doing: telling the computer how we want things done; but you can't really say that you have to tell the computer more about parallelization. It's exactly the opposite. Well, it is not that easy. You have to include enough information intro the program, and you have to break it down in a way that allows parallelism. For instance, you need to tell the machine that your operators are associative or commutative to enable optimizations and reordering. And there seem to be approaches for instance to infer parallel solutions like prefix-sum algorithms[1] but that is also restricted to certain applications. Nothing general, no holly grail or silver bullet.
Best regards Stefan [1] Prefix Sums and Their Applications. Guy E. Blelloch -- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525
You shouldn't write "do" loops that start at the beginning and go until the end. You should just say that you want the calculation done and that your intent is that you have visited everything. And then of course you might have dependencies etc... but the idea is generally, don't say how to do it, just declare what you want as a result.
Of course, it doesn't immediately match what we are used to doing: telling the computer how we want things done; but you can't really say that you have to tell the computer more about parallelization. It's exactly the opposite. Well, it is not that easy. You have to include enough information intro the program, and you have to break it down in a way that allows parallelism. For instance, you need to tell the machine that your operators are associative or commutative to enable optimizations and reordering. And there seem to be approaches for instance to infer parallel solutions like prefix-sum algorithms[1] but that is also restricted to certain applications. Nothing general, no holly grail or silver bullet.
Best regards Stefan Sure sure. I was just avoiding unnecessary details from the talk ;P
It makes perfect sense to me. Alexandre On 29 Apr 2011, at 10:09, Toon Verwaest wrote:
Actually if you listen to Guy Steele's talk the whole point is to let the developer be even more ignorant than you are now.
You shouldn't write "do" loops that start at the beginning and go until the end. You should just say that you want the calculation done and that your intent is that you have visited everything. And then of course you might have dependencies etc... but the idea is generally, don't say how to do it, just declare what you want as a result.
Of course, it doesn't immediately match what we are used to doing: telling the computer how we want things done; but you can't really say that you have to tell the computer more about parallelization. It's exactly the opposite.
On 04/29/2011 05:05 PM, Alexandre Bergel wrote:
Interesting result. But still, I feel that the computer should be able to do some inference. This could be at runtime, at compile time or during the development. I think than expecting the user to have the knowledge about how to parallelize an application is too much asking.
I will read Charlotte's work.
Alexandre
On 29 Apr 2011, at 09:58, Toon Verwaest wrote:
I have a hunch that Stefan is referring to the PhD thesis of Charlotte Herzeel without giving names. As far as I understood from my discussions with her (and her talks), it generally doesn't really pay off to automatically parallelize on branches. You get minimal speedups (1% at best).
I tend to agree with Stefan / Michael / Guy Steele... Maybe you don't need much, but the mapreduce style is the minimum requirement to give the language enough "wiggle room" to automatically parallelize stuff. But it DOES require you to restructure your application in a slightly more declarative fashion.
cheers, Toon
On 04/29/2011 04:55 PM, Alexandre Bergel wrote:
Hi Stefan,
I though about your email. I do not understand why automatic parallelization is not the way to go. In my opinion, the computer has much more knowledge about the programmer about where side effects appear and where to cut or split a computation.
Actually, if I want to be provocative, I would say that parallelization cannot be effective without being automatic. For a similar reason that the compiler will always know better than me how to properly allocate registers.
I feel it would be cheaper for me to buy a faster computer than to learn how to program in a multi-core fashion.
Cheers, Alexandre
However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ? Sure, you have to do: n times: [ [ 1 expensiveComputation. ] fork ].
I don't belief in holy grails or silver bullets. Automatic parallelization is something nice for the kids, like Santa Clause or the Easter Bunny...
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Hello Alexandre: On 29 Apr 2011, at 16:55, Alexandre Bergel wrote:
I though about your email. I do not understand why automatic parallelization is not the way to go. In my opinion, the computer has much more knowledge about the programmer about where side effects appear and where to cut or split a computation.
Actually, if I want to be provocative, I would say that parallelization cannot be effective without being automatic. For a similar reason that the compiler will always know better than me how to properly allocate registers. First, compilers have always the limitations and heuristics for the common case. The stuff I am most interested in, i.e., interpreters, are an extreme challenge for compilers. Carefully designed and optimized assembler code will always outperform a compiler in that case. But ok, interpreters are not the common case for most compilers...
But still, it is always about what the compiler is allowed to assume and what kind of knowledge is encoded in a program. If you write an inherently sequential program, like an algorithm for huffman decoding, no compiler on the world will stand a chance to automatically parallelize that. However, if you encode you programs in a way, like Guy Steele proposes, that is, making the opportunity for parallelism obvious, than you also have a chance to benefit from that. Thus, solve you problems using data structures that allow parallel execution: get rid of linked lists, abandoned all kind of linear data structures. Use trees! TREES! Trees have always been good for the environment and for humans. And nowadays they are the way to go for green computing ;) And whether you prefer to have you language/VM to do a 'spawn' here or there or whether you put it in explicitly, well, thats a matter of taste or religion... The important thing that matters is that the structure of your problem allows for parallelization.
I feel it would be cheaper for me to buy a faster computer than to learn how to program in a multi-core fashion. Ehm, I assume you haven't bought a computer the last 5 years, otherwise you would have noticed that you can't do that anymore...
Best regards Stefan -- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525
On 29 April 2011 01:03, Stefan Marr <pharo@stefan-marr.de> wrote:
On 29 Apr 2011, at 00:32, Nicolas Cellier wrote:
However, as I understand it, it's entirely up to user to write code exploiting parallel Process explicitly right ?
Sure, you have to do: n times: [ [ 1 expensiveComputation. ] fork ].
I don't belief in holy grails or silver bullets. Automatic parallelization is something nice for the kids, like Santa Clause or the Easter Bunny...
Indeed :) People tend to forget that parallel algorithms are different by nature, and there is no way to automatically convert arbitrary single-threaded algorithm to parallel one, without thinking about rearranging data structures and control flow.
Best regards Stefan
-- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: Â +32 2 629 3525
-- Best regards, Igor Stasenko AKA sig.
One silly idea while reading this thread (not the paper): For single core, the idea makes sense. It may even extend easily to multicore VM (just forget about Smalltalk for a while) by counting message sent per core and taking the max.
But you are here assuming that all the CPU have the same speed (#messages/sec) right? Alexandre
Nicolas
2011/4/29 Alexandre Bergel <alexandre.bergel@me.com>:
+1
Alexandre
On 28 Apr 2011, at 17:35, Michael Haupt wrote:
Hi Alex,
On 29 April 2011 00:08, Alexandre Bergel <alexandre.bergel@me.com> wrote:
I think you're being a bit harsh on stack sampling there. It is exact enough to drive optimisation in some really high-performance VMs. It is also deterministic enough to yield data leading to very good performance results in those VMs. Whether focusing on counting messages instead of taking samples is more beneficial would have to be determined by experiment ...
Yes, 25 pages of experiment :-)
oh, I was not referring to your paper. I was referring to the general applicability of message counting as opposed to sampling. The latter is true-and-tried in many high performance VMs. For the former, an experiment has yielded good results (from what I take from this thread - I still haven't read your paper, sorry, it's on top of the pile) in a constrained setting. All I was saying is that it is not possible to conclude anything for the broader area from the experiments you conducted. But we're probably of the same opinion here.
What you mean with "non-portable" I do not understand.
The information about the execution time contained in your profile cannot be compared with a new profile realized on a different machine, with a different CPU.
That is correct, but the approach itself is portable - may I quote you: "Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable". You weren't talking about the results. Those are obviously specific to the platform, clock frequency, L1/L2/L3 cache and memory sizes, application input (!) and other factors.
Best,
Michael
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
2011/4/29 Alexandre Bergel <alexandre.bergel@me.com>:
One silly idea while reading this thread (not the paper): For single core, the idea makes sense. It may even extend easily to multicore VM (just forget about Smalltalk for a while) by counting message sent per core and taking the max.
But you are here assuming that all the CPU have the same speed (#messages/sec) right?
Alexandre
Sure, an obvious limitation...
Nicolas
2011/4/29 Alexandre Bergel <alexandre.bergel@me.com>:
+1
Alexandre
On 28 Apr 2011, at 17:35, Michael Haupt wrote:
Hi Alex,
On 29 April 2011 00:08, Alexandre Bergel <alexandre.bergel@me.com> wrote:
I think you're being a bit harsh on stack sampling there. It is exact enough to drive optimisation in some really high-performance VMs. It is also deterministic enough to yield data leading to very good performance results in those VMs. Whether focusing on counting messages instead of taking samples is more beneficial would have to be determined by experiment ...
Yes, 25 pages of experiment :-)
oh, I was not referring to your paper. I was referring to the general applicability of message counting as opposed to sampling. The latter is true-and-tried in many high performance VMs. For the former, an experiment has yielded good results (from what I take from this thread - I still haven't read your paper, sorry, it's on top of the pile) in a constrained setting. All I was saying is that it is not possible to conclude anything for the broader area from the experiments you conducted. But we're probably of the same opinion here.
What you mean with "non-portable" I do not understand.
The information about the execution time contained in your profile cannot be compared with a new profile realized on a different machine, with a different CPU.
That is correct, but the approach itself is portable - may I quote you: "Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable". You weren't talking about the results. Those are obviously specific to the platform, clock frequency, L1/L2/L3 cache and memory sizes, application input (!) and other factors.
Best,
Michael
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel  http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel  http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
alex did you read the OOPSLA paper stefan or michael sent around about profiling and the default flaw in research approach? Stef On Apr 29, 2011, at 12:40 AM, Alexandre Bergel wrote:
+1
Alexandre
On 28 Apr 2011, at 17:35, Michael Haupt wrote:
Hi Alex,
On 29 April 2011 00:08, Alexandre Bergel <alexandre.bergel@me.com> wrote:
I think you're being a bit harsh on stack sampling there. It is exact enough to drive optimisation in some really high-performance VMs. It is also deterministic enough to yield data leading to very good performance results in those VMs. Whether focusing on counting messages instead of taking samples is more beneficial would have to be determined by experiment ...
Yes, 25 pages of experiment :-)
oh, I was not referring to your paper. I was referring to the general applicability of message counting as opposed to sampling. The latter is true-and-tried in many high performance VMs. For the former, an experiment has yielded good results (from what I take from this thread - I still haven't read your paper, sorry, it's on top of the pile) in a constrained setting. All I was saying is that it is not possible to conclude anything for the broader area from the experiments you conducted. But we're probably of the same opinion here.
What you mean with "non-portable" I do not understand.
The information about the execution time contained in your profile cannot be compared with a new profile realized on a different machine, with a different CPU.
That is correct, but the approach itself is portable - may I quote you: "Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable". You weren't talking about the results. Those are obviously specific to the platform, clock frequency, L1/L2/L3 cache and memory sizes, application input (!) and other factors.
Best,
Michael
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
I am not sure to which paper you are referring to. But yes, I read the one that we mentioned in the various emails. "Wake Up and Smell the Coffee" is a good one. Actually, there are several papers on a similar topic. The ones that I like very very much are: - "Producing wrong data without doing anything obviously wrong!" - "Evaluating the accuracy of java profilers." The authors of these papers are Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, and Peter F. Sweeney. These guys really rock. They will be at ecoop. Cheers, Alexandre On 29 Apr 2011, at 04:32, Stéphane Ducasse wrote:
alex did you read the OOPSLA paper stefan or michael sent around about profiling and the default flaw in research approach?
Stef
On Apr 29, 2011, at 12:40 AM, Alexandre Bergel wrote:
+1
Alexandre
On 28 Apr 2011, at 17:35, Michael Haupt wrote:
Hi Alex,
On 29 April 2011 00:08, Alexandre Bergel <alexandre.bergel@me.com> wrote:
I think you're being a bit harsh on stack sampling there. It is exact enough to drive optimisation in some really high-performance VMs. It is also deterministic enough to yield data leading to very good performance results in those VMs. Whether focusing on counting messages instead of taking samples is more beneficial would have to be determined by experiment ...
Yes, 25 pages of experiment :-)
oh, I was not referring to your paper. I was referring to the general applicability of message counting as opposed to sampling. The latter is true-and-tried in many high performance VMs. For the former, an experiment has yielded good results (from what I take from this thread - I still haven't read your paper, sorry, it's on top of the pile) in a constrained setting. All I was saying is that it is not possible to conclude anything for the broader area from the experiments you conducted. But we're probably of the same opinion here.
What you mean with "non-portable" I do not understand.
The information about the execution time contained in your profile cannot be compared with a new profile realized on a different machine, with a different CPU.
That is correct, but the approach itself is portable - may I quote you: "Most profilers, including MessageTally, count stack frames at a regular interval. This is doomed to be inexact, non-deterministic and non-portable". You weren't talking about the results. Those are obviously specific to the platform, clock frequency, L1/L2/L3 cache and memory sizes, application input (!) and other factors.
Best,
Michael
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Hi Michael, There is a long discussion in the paper about exactly what you are mentioning here. The assumptions are made for the current version of Pharo: with its naive VM, not state-of-the-Art JIT, naive compiler, simple GC and so on. I agree with you that the result I found may not be valid in Java or .Net. However they are for the current Pharo. And apparently, this is not likely to change anything soon. Alexandre On 28 Apr 2011, at 08:57, Michael Haupt wrote:
Alex,
On 28 April 2011 15:37, Alexandre Bergel <alexandre.bergel@me.com> wrote:
Counting messages is, in the average, closely link to the average execution time.
I believe this is correct only as long as a purely interpreting VM is used, even though quick messages add a tiny bit of uncertainty. But add a JIT compiler and some inlining, and timeToRun and MessageTally are suddenly interesting again.
Not having read your text, I surely cannot say anything remotely conclusive, but the assumption that execution time roughly equals the amount of messages sent seems rather naïve once you leave the cosy well-predictable niche inhabited by pure interpreters.
Best,
Michael
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Hi Alex, On 28 April 2011 16:03, Alexandre Bergel <alexandre.bergel@me.com> wrote:
There is a long discussion in the paper about exactly what you are mentioning here.
wonderful, I'm going to go read it then. :-)
I agree with you that the result I found may not be valid in Java or .Net. However they are for the current Pharo. And apparently, this is not likely to change anything soon.
Not even with increasing support from Cog? Best, Michael
I agree with you that the result I found may not be valid in Java or .Net. However they are for the current Pharo. And apparently, this is not likely to change anything soon.
Not even with increasing support from Cog?
No idea. Together with Eliot we implemented Compteur in Cog. I made some experiments and the results are apparently similar than in a non-jitted VM. If Cog continue to improve, then the assumptions may not be valid anymore. Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Hi: On 28 Apr 2011, at 16:08, Alexandre Bergel wrote:
I agree with you that the result I found may not be valid in Java or .Net. However they are for the current Pharo. And apparently, this is not likely to change anything soon.
Not even with increasing support from Cog?
No idea. Together with Eliot we implemented Compteur in Cog. I made some experiments and the results are apparently similar than in a non-jitted VM.
If Cog continue to improve, then the assumptions may not be valid anymore. As soon as the VM does aggressive method inlining your message sends disappear and you can't count them anymore.
Best regards Stefan -- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525
If Cog continue to improve, then the assumptions may not be valid anymore. As soon as the VM does aggressive method inlining your message sends disappear and you can't count them anymore.
I agree with you, but today it works like this. Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
participants (7)
-
Alexandre Bergel -
Igor Stasenko -
Michael Haupt -
Nicolas Cellier -
Stefan Marr -
Stéphane Ducasse -
Toon Verwaest