Xl2 compiled to C rather than C++
Henry
Thank you for releasing Xl and in particular Xl2, this is a most
interesting and exciting development. I am a very long-time C++ user
and appreciate the power of generic programming through templates but
the syntax is clunky and I often find myself going off the end of what
is currently possible and end up messing around with the C pre-
processor which is frustrating. I am hoping that Xl2 will prove to be
an effective alternative to C++ templates and provide the programming
flexibility I crave.
I am playing with the code base, compiling the examples and generally
messing around and I notice that compiler.xl compiles to C++ whereas
the examples compile to C. How much work would it be to bootstrap
compiler.xl to compile to C?
The reason I ask is that I am also very interested in dynamic
compilation and having a dynamic run-time and playing with tcc and
libtcc (and gcc compiling shared object files and then loading them)
and wonder if it would be possible to compile Xl2 into such an
environment and use it to compile code to C on the fly and load it
dynamically into the run-time. Have you considers these options?
Have you any suggestions as to where I might start to achieve these
aims?
Thanks again
Henry
Christophe de Dinechin
On 4 mars 2011, at 19:29, Henry wrote:
> Dear Christophe,
>
> Thank you for releasing Xl and in particular Xl2, this is a most
> interesting and exciting development. I am a very long-time C++ user
> and appreciate the power of generic programming through templates but
> the syntax is clunky and I often find myself going off the end of what
> is currently possible and end up messing around with the C pre-
> processor which is frustrating. I am hoping that Xl2 will prove to be
> an effective alternative to C++ templates and provide the programming
> flexibility I crave.
>
> I am playing with the code base, compiling the examples and generally
> messing around and I notice that compiler.xl compiles to C++ whereas
> the examples compile to C. How much work would it be to bootstrap
> compiler.xl to compile to C?
It's part of the long-term plan. Unfortunately, there's still quite a little bit of work. The reason is that compiler.xl is actually built using a bootstrap compiler that only understands a rather simplistic version of XL which is easier to translate directly to C++ concepts. For example, map[integer, text] doesn't instantiate a real XL generic type, but instantiates a C++ std::map.
The bootstrap compiler also does practically no semantics (leaving it to the C++ backend). So there are many errors whenever you try to compile elements of the native compiler with itself. Many of these errors are legitimate, i.e. the code is not valid XL code. But they are also necessary evils because of limitations of the bootstrap compiler.
I am not even entirely sure that it's possible to write code that would be accepted by both the native and bootstrap compilers.
>
> The reason I ask is that I am also very interested in dynamic
> compilation and having a dynamic run-time and playing with tcc and
> libtcc (and gcc compiling shared object files and then loading them)
> and wonder if it would be possible to compile Xl2 into such an
> environment and use it to compile code to C on the fly and load it
> dynamically into the run-time. Have you considers these options?
Yes. The path I have decided to follow is LLVM rather than tcc. XLR was originally intended as the interface between XL2 and LLVM, i.e. something that I could put in the "runtime" directory (in addition to Java and C). In short, the plan is : XL2 generates an XLR file, and XLR converts that to code on the fly.
> Have you any suggestions as to where I might start to achieve these
> aims?
Depends on what you are most interested in.
- If it's to experiment with XL2 and tcc, I would start by checking if it's possible to generate C that tcc is happy with, i.e. add a "tcc" runtime similar to the current C runtime.
- If it's dynamic code generation, I'd look at the dyncompile branch of XLR and see how XL connects to LLVM.
- If you are interested in experimenting with XL2, most of the library remains to be written, starting with simple things like math or I/O libraries.
- If you'd like to make it easier to bootstrap the compiler, you could try transalting some of the native compiler components in a way that they are accepted by the native compiler itself.
Regards
Christophe
Henry
> The bootstrap compiler also does practically no semantics (leaving it to the
> C++ backend). So there are many errors whenever you try to compile elements of
> the native compiler with itself. Many of these errors are legitimate, i.e. the
> code is not valid XL code. But they are also necessary evils because of
> limitations of the bootstrap compiler.
> I am not even entirely sure that it's possible to write code that would be
> accepted by both the native and bootstrap compilers.
>> The reason I ask is that I am also very interested in dynamic
>> compilation and having a dynamic run-time and playing with tcc and
>> libtcc (and gcc compiling shared object files and then loading them)
>> and wonder if it would be possible to compile Xl2 into such an
>> environment and use it to compile code to C on the fly and load it
>> dynamically into the run-time. Have you considers these options?
> Yes. The path I have decided to follow is LLVM rather than tcc. XLR was
> originally intended as the interface between XL2 and LLVM, i.e. something that
> I could put in the "runtime" directory (in addition to Java and C). In short,
> the plan is : XL2 generates an XLR file, and XLR converts that to code on the
> fly.
it's own
right but for my purpose in writing HPC simulation codes I think LLVM
is rather
lacking and translating to C and interfacing to the C world is more
attractive.
My own large simulation code already compiles with Clang/LLVM but the
performance is rather poor compared to using gcc. I have also played
with Cling
from the ROOT people at CERN but unless the speed of Clang/LLVM speeds
up quite
a bit this approach may be problematic. Nevertheless Cling is an
interesting
development, have you been following it?
>> Have you any suggestions as to where I might start to achieve these
>> aims?
> Depends on what you are most interested in.
> - If it's to experiment with XL2 and tcc, I would start by checking if it's
> - similar to the current C runtime.
tcc supports C89 and most of C99 so this should be quite easy, I will
try it
over the weekend.
> - If it's dynamic code generation, I'd look at the dyncompile branch of XLR
I am studying this and look forward to this being integrated into XL2
> - If you are interested in experimenting with XL2, most of the library remains
I would be happy to invest time in this as I did in C++ in the very
early days
before STL etc. But first I need to be sure the framework will help
me achieve
my aims of having a dynamic runtime built on C with efficient
execution and a
statically-typed, generic, extensible language on top. Clearly Xl2
already
fulfils most of these requirements :-)
> - If you'd like to make it easier to bootstrap the compiler, you could try
> - accepted by the native compiler itself.
This would be a challenging task for someone new to the language, I
will look
into it.....
Thanks
Henry
Christophe de Dinechin
On 4 mars 2011, at 22:40, Henry wrote:
> Hi Christophe,
>
>> The bootstrap compiler also does practically no semantics (leaving it to the
>> C++ backend). So there are many errors whenever you try to compile elements of
>> the native compiler with itself. Many of these errors are legitimate, i.e. the
>> code is not valid XL code. But they are also necessary evils because of
>> limitations of the bootstrap compiler.
>
>> I am not even entirely sure that it's possible to write code that would be
>> accepted by both the native and bootstrap compilers.
>
> Do you think another level of bootstrap might be necessary?
I'm afraid so, unfortunately. Although I think this may be done from a single code base with some ad-hoc plugins. I'm delaying that effort until XL2 has a library that is robust enough.
>
>>> The reason I ask is that I am also very interested in dynamic
>>> compilation and having a dynamic run-time and playing with tcc and
>>> libtcc (and gcc compiling shared object files and then loading them)
>>> and wonder if it would be possible to compile Xl2 into such an
>>> environment and use it to compile code to C on the fly and load it
>>> dynamically into the run-time. Have you considers these options?
>
>> Yes. The path I have decided to follow is LLVM rather than tcc. XLR was
>> originally intended as the interface between XL2 and LLVM, i.e. something that
>> I could put in the "runtime" directory (in addition to Java and C). In short,
>> the plan is : XL2 generates an XLR file, and XLR converts that to code on the
>> fly.
>
> I think this is a good approach and XLR an interesting language in
> it's own right but for my purpose in writing HPC simulation codes I think LLVM
> is rather lacking
Interesting. Is this OpenFoam we are talking about?
Where do you see LLVM lacking? Performance only (from what you wrote below)? Or other things? Could you share your experience with tcc and any comparison point with LLVM you may have? I am very interested.
> and translating to C and interfacing to the C world is more
> attractive.
The C runtime of XL2 is probably the most advanced one at this stage. How do you use tcc in an HPC context? Why does the "dynamic" aspect matter?
Would it be sufficient to connect XL2 to tcc for your purpose?
> My own large simulation code already compiles with Clang/LLVM but the
> performance is rather poor compared to using gcc. I have also played
> with Cling from the ROOT people at CERN but unless the speed of Clang/LLVM speeds
> up quite a bit this approach may be problematic. Nevertheless Cling is an
> interesting development, have you been following it?
No, thanks for sharing.
>
>>> Have you any suggestions as to where I might start to achieve these
>>> aims?
>
>> Depends on what you are most interested in.
>
>> - If it's to experiment with XL2 and tcc, I would start by checking if it's
>> - possible to generate C that tcc is happy with, i.e. add a "tcc" runtime
>> - similar to the current C runtime.
>
> tcc supports C89 and most of C99 so this should be quite easy, I will
> try it over the weekend.
Cool!
>
>> - If it's dynamic code generation, I'd look at the dyncompile branch of XLR
>> - and see how XL connects to LLVM.
>
> I am studying this and look forward to this being integrated into XL2
I'm currently focusing on the Taodyne needs for XLR for Taodyne, so this may be deferred a little.
>
>> - If you are interested in experimenting with XL2, most of the library remains
>> - to be written, starting with simple things like math or I/O libraries.
>
> I would be happy to invest time in this as I did in C++ in the very
> early days before STL etc. But first I need to be sure the framework will help
> me achieve my aims of having a dynamic runtime built on C with efficient
> execution and a statically-typed, generic, extensible language on top. Clearly Xl2
> already fulfils most of these requirements :-)
Clearly, you realize that it's work in progress. But I think the basis is there.
>
>> - If you'd like to make it easier to bootstrap the compiler, you could try
>> - transalting some of the native compiler components in a way that they are
>> - accepted by the native compiler itself.
>
> This would be a challenging task for someone new to the language, I will look into it.....
I agree.
Talk to you soon
Christophe
Henry
> I'm afraid so, unfortunately. Although I think this may be done from a single
> code base with some ad-hoc plugins. I'm delaying that effort until XL2 has a
> library that is robust enough.
and the
other bits of STL that you are currently using in the bootstrap
compiler.
> > I think this is a good approach and XLR an interesting language in
> > it's own right but for my purpose in writing HPC simulation codes I think LLVM
> > is rather lacking
>
> Interesting. Is this OpenFoam we are talking about?
looking for
better ways to achieve the same aims. Although C++ is very powerful
and
currently the best choice for CFD development I hope that a better,
more
flexible and extensible generic language will be developed for this
purpose.
> Where do you see LLVM lacking? Performance only (from what you wrote below)?
> Or other things? Could you share your experience with tcc and any comparison
> point with LLVM you may have? I am very interested.
as you
have rightly said in previous posts/blog entries the LLVM project is
still young
and very impressive work is being done particularly on the
optimisation plugins
and it may be that it will get to a point that it will compete with
the current
generation of static compilers. However, I think that using C as the
"assembler" language has some advantages, in particular it looks
simpler to
develop and maintain in your framework and more extensible, for
example to take
advantage of GPUs by using CUDA or OpenCL C extensions. It appears
that it
would be possible to do the equivalent of OpenMP in a much more
convenient and
extensible way.
> The C runtime of XL2 is probably the most advanced one at this stage. How do
> you use tcc in an HPC context?
integrates
the per-processor, compiler, assembler, linker and loader all in one
compact and
efficient package which conveniently supports dynamic compilation.
Also
although it does little optimisation the performance of executable
compiled with
it is often pretty good see e.g.:
http://global.phoronix-test-suite.com/index.php?k=profile&u=staalmannen-231-8340-1312
and given that the C generated by XL2 is simple it is unlikely that
aggressive
optimisation techniques will be beneficial and most optimisation
should be done
in the conversion from XL2 to C. However, for production running it
may prove
useful to use an optimising C compiler like gcc in which case
generating shared
libraries and using dlopen is practical.
> Why does the "dynamic" aspect matter?
generic
language because it would be possible to create the appropriate
instantiations
of the required types on demand rather than attempting to pre-compile
every
combination of types and then look them up at runtime as we currently
do. Also
in CFD it is often necessary to include code which is specific to the
particular
case, e.g. some special boundary condition and it would be convenient
if such
code could be compiled at runtime. We already have this running in C+
+ but it
isn't as convenient as we would like but is quite powerful. And the
other case
for dynamic compilation is to speed-up code development, basically I
want to see
the power of a statically-typed generic language with a runtime and
development
environment to rival the best Lisp environments e.g. SBCL. I do not
see why
this isn't possible or why it has not yet been done.
> Would it be sufficient to connect XL2 to tcc for your purpose?
its
dependency on C++ for portability and maintainability reasons.
> > My own large simulation code already compiles with Clang/LLVM but the
> > performance is rather poor compared to using gcc. I have also played
> > with Cling from the ROOT people at CERN but unless the speed of Clang/LLVM speeds
> > up quite a bit this approach may be problematic. Nevertheless Cling is an
> > interesting development, have you been following it?
>
> No, thanks for sharing.
This is really impressive, a dynamic C++ development and runtime
environment
which does not compromise performance! This project is the proposed
replacement for Cint:
http://root.cern.ch/drupal/content/cint
which I spent a long time working with but came to the conclusion that
it would
never support the complete C++ standard which I require. However,
Cling
supports what Clang does, i.e. the complete standard, more or less.
> > tcc supports C89 and most of C99 so this should be quite easy, I will
> > try it over the weekend.
>
> Cool!
backend C
compiler :-) I will look into linking libtcc to XL2 to support the -
run script
option, i.e. compile XL2 code to executable and execute it completely
in memory.
> I'm currently focusing on the Taodyne needs for XLR for Taodyne, so this may
> be deferred a little.
elaborate?
I have played with several functional languages including Common Lisp,
EuLisp,
Scheme, Haskell and QiII and although all are interesting and I might
choose them
for many purposes none offer what I need for CFD programming, for
which
statically typed generic seems to be the best approach.
> Clearly, you realize that it's work in progress. But I think the basis is there.
this stage is
that it is easier to mould to it to suit the purpose better than one
with a
complete and rigid specification plus it is more fun and more
educational :-)
Best regards
Henry
Christophe de Dinechin
On 5 mars 2011, at 21:31, Henry wrote:
>>> Do you think another level of bootstrap might be necessary?
>
>> I'm afraid so, unfortunately. Although I think this may be done from a single
>> code base with some ad-hoc plugins. I'm delaying that effort until XL2 has a
>> library that is robust enough.
>
> Ahh yes I see, at least a version of map written in Xl2 will be needed
> and the other bits of STL that you are currently using in the bootstrap
> compiler.
Exactly.
>
>>> I think this is a good approach and XLR an interesting language in
>>> it's own right but for my purpose in writing HPC simulation codes I think LLVM
>>> is rather lacking
>>
>> Interesting. Is this OpenFoam we are talking about?
>
> Yes, I have been developing OpenFOAM in C++ since 1989 but always looking for
> better ways to achieve the same aims. Although C++ is very powerful and currently the best choice for CFD development I hope that a better, more flexible and extensible generic language will be developed for this purpose.
I'm glad if XL2 can help. Code performance was a design objective throughout. Here are some of the features that may be of interest to you:
- XL2 has in and out arguments instead of byval and byref. This means that the compiler can optimize how arguments are passed based on machine-dependent information. For example, a "complex" struct can typically fit in registers on x86-64 or Itanium, whereas in C++, the "this" pointer will typically be passed instead. Modern C++ compilers have a feature to promote structure fields to registers, but that only works if the function is inlined and it's a difficult optimization (read: resource consuming). I had some interesting complex number microbenchmarks where XL2 code outperformed C++ code by a wide margin just because of that.
- Expression reduction allows handy notations even when you want to efficiently combine operations. For example, you can write A*B+C to combine two matrix operations. There are techniques in C++ to achieve similar objectives, e.g. expression templates, but they are really gruesome.
- With the right runtimes, it's conceivable to use the XL2 compiler to generate code for other kinds of processors, e.g. GPUs. For example, you could generate code using the OpenGL shading language, or OpenCL code, ... I have not really explored that avenue yet, but it was part of the design objectives.
There are some areas where the XL2 generics are currently lacking relative to C++. One of them is specialization.
>
>> Where do you see LLVM lacking? Performance only (from what you wrote below)?
>> Or other things? Could you share your experience with tcc and any comparison
>> point with LLVM you may have? I am very interested.
>
> Runtime performance of Clang/LLVM is certainly a problem currently but
> as you have rightly said in previous posts/blog entries the LLVM project is
> still young and very impressive work is being done particularly on the
> optimisation plugins and it may be that it will get to a point that it will compete with
> the current generation of static compilers. However, I think that using C as the "assembler" language has some advantages, in particular it looks simpler to
> develop and maintain in your framework and more extensible, for example to take
> advantage of GPUs by using CUDA or OpenCL C extensions. It appears that it
> would be possible to do the equivalent of OpenMP in a much more convenient and
> extensible way.
Yes, that was definitely the idea.
There are a few drawbacks to using C, however. Expressing exception handling or nested functions in standard C is not that easy. GCC has extensions that make it easier, but I've been wary of generating code that only GCC can accept (although it is as close to the "industry standard" C idiom as one can get).
>
>> The C runtime of XL2 is probably the most advanced one at this stage. How do you use tcc in an HPC context?
>
> tcc is interesting for several reasons, the main one being that it
> integrates the per-processor, compiler, assembler, linker and loader all in one
> compact and efficient package which conveniently supports dynamic compilation.
> Also although it does little optimisation the performance of executable
> compiled with it is often pretty good see e.g.:
> http://global.phoronix-test-suite.com/index.php?k=profile&u=staalmannen-231-8340-1312
These results are really counter-intuitive to me. I would have expected clang to fare much better. That may lead me to revisit my decision to use LLVM :-)
> and given that the C generated by XL2 is simple it is unlikely that aggressive optimisation techniques will be beneficial and most optimisation should be done in the conversion from XL2 to C. However, for production running it may prove useful to use an optimising C compiler like gcc in which case
> generating shared libraries and using dlopen is practical.
OK.
>
>> Why does the "dynamic" aspect matter?
>
> I think it is particularly useful in the context of a statically-typed generic language because it would be possible to create the appropriate instantiations of the required types on demand rather than attempting to pre-compile every combination of types and then look them up at runtime as we currently do.
I see. But there's already an on-demand aspect in template instantiation, since you only generate the templates that are required by the program. You can defer code generation until you hit the code, but not semantics. Semantics is probably what will cost you more in that case. To be measured, my intuition may be wrong here.
> Also in CFD it is often necessary to include code which is specific to the particular case, e.g. some special boundary condition and it would be convenient if such code could be compiled at runtime.
This part is not entirely clear to me. By "boundary condition", do you mean a case that occurs all the time but is specialized (e.g. near a border where you have a qualitative change for, say, friction or heat transfers), or a computer-science boundary condition e.g. an error or something that is not supposed to happen.
> We already have this running in C++ but it isn't as convenient as we would like but is quite powerful. And the other case for dynamic compilation is to speed-up code development, basically I want to see the power of a statically-typed generic language with a runtime and development environment to rival the best Lisp environments e.g. SBCL. I do not see why this isn't possible or why it has not yet been done.
It started with resource limitations, i.e. on early machines, it made no sense to waste time in memory with the compiler while you were running the program. This time is long gone, but we never really went beyond that model.
>
>> Would it be sufficient to connect XL2 to tcc for your purpose?
>
> Quite possibly but I would also like to see XL2 release itself from its dependency on C++ for portability and maintainability reasons.
Only the bootstrap phase require C++. The native compiler (nxl) doesn't need C++ to compile. Straight C is sufficient.
>
>>> My own large simulation code already compiles with Clang/LLVM but the
>>> performance is rather poor compared to using gcc. I have also played
>>> with Cling from the ROOT people at CERN but unless the speed of Clang/LLVM speeds
>>> up quite a bit this approach may be problematic. Nevertheless Cling is an
>>> interesting development, have you been following it?
>>
>> No, thanks for sharing.
>
> http://root.cern.ch/drupal/category/package-context/cling
>
> This is really impressive, a dynamic C++ development and runtime environment which does not compromise performance! This project is the proposed replacement for Cint:
>
> http://root.cern.ch/drupal/content/cint
>
> which I spent a long time working with but came to the conclusion that it would never support the complete C++ standard which I require. However, Cling supports what Clang does, i.e. the complete standard, more or less.
Another link to add to my watchlist.
>>> tcc supports C89 and most of C99 so this should be quite easy, I will
>>> try it over the weekend.
>>
>> Cool!
>
> It works no problem, all the TESTS examples compile with tcc as the backend C compiler :-) I will look into linking libtcc to XL2 to support the -run script option, i.e. compile XL2 code to executable and execute it completelyin memory.
That would be really exciting.
>
>> I'm currently focusing on the Taodyne needs for XLR for Taodyne, so this may be deferred a little.
>
> I am interested in what you are using XLR for at Taodyne, could you elaborate?
We use XLR as a dynamic document description language. Think of it as an interactive 3D Postscript. The "concept programming" approach means you can write a slide like this:
slide "This is my nice slide",
* "First bullet point"
* "Second bullet point"
The videos on our web site were generated that way.
> I have played with several functional languages including Common Lisp, EuLisp, Scheme, Haskell and QiII and although all are interesting and I might choose them for many purposes none offer what I need for CFD programming, for which statically typed generic seems to be the best approach.
... although I'm trying to get really close, performance-wise, with XLR.
>
>> Clearly, you realize that it's work in progress. But I think the basis is there.
>
> Absolutely, and the advantage in getting involved in a language at this stage is that it is easier to mould to it to suit the purpose better than one with a complete and rigid specification plus it is more fun and more educational :-)
Welcome aboard.
Christophe
Henry Weller
> throughout. Here are some of the features that may be of interest to you:
> - Expression reduction allows handy notations even when you want to
> - efficiently combine operations. For example, you can write A*B+C to combine
> - two matrix operations.
No this is really interesting! Do you have an example?
> - There are techniques in C++ to achieve similar objectives, e.g. expression
> - templates, but they are really gruesome.
I have played with expression templates but decided against for OpenFOAM partly
because the code base was already rather large by the time the concept had
matured but also it is a maintenance nightmare and the compiler messages are
hideous. Personally I think so kind of pre-processor language would be
preferable to expression templates.
> There are some areas where the XL2 generics are currently lacking relative to
> C++. One of them is specialization.
Do you see any fundamental difficulties here? This is certainly an important
feature of C++.
> There are a few drawbacks to using C, however. Expressing exception handling
Good point. So far I have not used exception handling much because it wasn't in
the language during a substantial part of the development phase of my projects
and difficult to retrofit. Also it is probably better that HPC simulation codes
do not rely on such programming techniques but for interactive code....
> These results are really counter-intuitive to me. I would have expected clang
> to fare much better. That may lead me to revisit my decision to use LLVM :-)
Actually compared to the results we see with OpenFOAM these results show clang
in a pretty good light. At the moment we would expect a clang compiled version
of OpenFOAM to be about a factor of 2 slower than compiled with gcc but we need
to play with the options more to see if we can squeeze more performance out of
it.
>>> Why does the "dynamic" aspect matter?
>> I think it is particularly useful in the context of a statically-typed
>> generic language because it would be possible to create the appropriate
>> instantiations of the required types on demand rather than attempting to
>> pre-compile every combination of types and then look them up at runtime as we
>> currently do.
> I see. But there's already an on-demand aspect in template instantiation,
> since you only generate the templates that are required by the program. You
> can defer code generation until you hit the code, but not semantics. Semantics
> is probably what will cost you more in that case. To be measured, my intuition
> may be wrong here.
We still have to build all the template instances we are going to need for all
types of runs into libraries so that they can be chosen at run-time, I would
like to see the code build itself as required, i.e. I see the overhead of
building the compiler and run-time into the code as small compared to the code
itself which is over 1 million lines. The alternative is building in an
interpreter but this really means developing code in two languages.
>> Also in CFD it is often necessary to include code which is specific to the
>> particular case, e.g. some special boundary condition and it would be
>> convenient if such code could be compiled at runtime.
> This part is not entirely clear to me. By "boundary condition", do you mean a
> case that occurs all the time but is specialized (e.g. near a border where you
> have a qualitative change for, say, friction or heat transfers)
Yes, some kind of specification of properties on the boundary the form of which
is not general and is needed only for the particular case.
> Only the bootstrap phase require C++. The native compiler (nxl) doesn't need
> C++ to compile. Straight C is sufficient.
Sure, but I would like to build the compiler and the code into a single run-time
and currently this would have to be compiled with a C++ compiler.
>> It works no problem, all the TESTS examples compile with tcc as the backend C
>> compiler :-) I will look into linking libtcc to XL2 to support the -run
>> script option, i.e. compile XL2 code to executable and execute it
>> completelyin memory.
> That would be really exciting.
I will keep you posted. The only problem I see is that the XL2 front-end is
currently quite slow for this kind of scripting usage e.g. julia.xl takes ~1s
to compile to C whereas gcc takes 0.062s to compile it and tcc takes 0.007s.
> We use XLR as a dynamic document description language. Think of it as an
> interactive 3D Postscript.
Excellent. We have played with 3D PDF, U3D and more recently PRC and see this
as a very good way to distribute simulation results but we haven't had the time
to take it very far.
> ... although I'm trying to get really close, performance-wise, with XLR.
Do you see XLR as a replacement for XL2?
> Welcome aboard.
Thanks :-)
Henry
Christophe de Dinechin
On 7 mars 2011, at 16:13, Henry Weller wrote:
>> I'm glad if XL2 can help. Code performance was a design objective
>> throughout. Here are some of the features that may be of interest to you:
>
>> - Expression reduction allows handy notations even when you want to
>> - efficiently combine operations. For example, you can write A*B+C to combine
>> - two matrix operations.
>
> No this is really interesting! Do you have an example?
Here is an example: http://xlr.git.sourceforge.net/git/gitweb.cgi?p=xlr/xlr;a=blob;f=xl2/native/TESTS/05.Expressions/multi-reduction.xl. All XL fundamental operators are defined that way (see xl_builtins.xs).
>> There are some areas where the XL2 generics are currently lacking relative to
>> C++. One of them is specialization.
>
> Do you see any fundamental difficulties here? This is certainly an important feature of C++.
No, just lack of time and manpower.
>> There are a few drawbacks to using C, however. Expressing exception handling
>
> Good point. So far I have not used exception handling much because it wasn't in
> the language during a substantial part of the development phase of my projects
> and difficult to retrofit. Also it is probably better that HPC simulation codes
> do not rely on such programming techniques but for interactive code....
I have deferred the implementation so far, because I'd like to allow the error management to be "factored out",i.e. you indicate how you want a given piece of code to report errors. I have not found the right way to do that just yet.
>> These results are really counter-intuitive to me. I would have expected clang
>> to fare much better. That may lead me to revisit my decision to use LLVM :-)
>
> Actually compared to the results we see with OpenFOAM these results show clang in a pretty good light. At the moment we would expect a clang compiled version of OpenFOAM to be about a factor of 2 slower than compiled with gcc but we need to play with the options more to see if we can squeeze more performance out of it.
This is so disappointing. When did you do your experiment?
Here is a recent benchmark: http://www.phoronix.com/scan.php?page=article&item=intel_snb_llvm&num=1. Here, LLVM is far from being as bad as it used to be. It's not stellar either.
> We still have to build all the template instances we are going to need for all
> types of runs into libraries so that they can be chosen at run-time, I would
> like to see the code build itself as required, i.e. I see the overhead of
> building the compiler and run-time into the code as small compared to the code
> itself which is over 1 million lines. The alternative is building in an
> interpreter but this really means developing code in two languages.
I see, this is really a shared library thing. So this is close to my "writeln" case, where I need to instantiate writeln for any kind of argument, and there's no way I'll pre-build them into a shared library.
That makes sense.
> Yes, some kind of specification of properties on the boundary the form of which
> is not general and is needed only for the particular case.
I see.
>> Only the bootstrap phase require C++. The native compiler (nxl) doesn't need
>> C++ to compile. Straight C is sufficient.
>
> Sure, but I would like to build the compiler and the code into a single run-time
> and currently this would have to be compiled with a C++ compiler.
Yes, that is definitely the case today. Until we do the 'yet another bootstrap' phase, I don't see C++ going away entirely when using XL.
>>> It works no problem, all the TESTS examples compile with tcc as the backend C
>>> compiler :-) I will look into linking libtcc to XL2 to support the -run
>>> script option, i.e. compile XL2 code to executable and execute it
>>> completelyin memory.
>
>> That would be really exciting.
>
> I will keep you posted. The only problem I see is that the XL2 front-end is
> currently quite slow for this kind of scripting usage e.g. julia.xl takes ~1s
> to compile to C whereas gcc takes 0.062s to compile it and tcc takes 0.007s.
Yes, that's true. And that's really a design issue, so it's unlikely to be a quick fix. The problem is that the compiler works by rewriting parse trees, so it spends a lot of time looking up the "best tree match", even for simple things like A+B. In A+B*C, you need to first check if there is a form matching A+B*C, then you realize that there is none, so you fall back to B*C followed by A+result.
It's much easier when things are hardcoded and have a fixed size :-)
That being said, the inner symbol lookup code could be optimized quite a bit, e.g by avoiding using C++ maps which are really not suited for that use.
>> We use XLR as a dynamic document description language. Think of it as an
>> interactive 3D Postscript.
>
> Excellent. We have played with 3D PDF, U3D and more recently PRC and see this as a very good way to distribute simulation results but we haven't had the time to take it very far.
The reason I likened it to a 3D postscript and not PDF is that the whole language is there. So you can define functions, do tests, etc.
>
>> ... although I'm trying to get really close, performance-wise, with XLR.
>
> Do you see XLR as a replacement for XL2?
Not in the short term, although it's possible I might one day re-implement XL2 as a library in XLR. Not sure whether this is realistic or not. However, I must say that I'm starting to "like" XLR more and more, in particular because it's very dense. If I can bring its performance to acceptable levels, who knows...
Originally, the idea was that XLR would run only during the compilation phase, just in order to connect XL2 to LLVM. So performance didn't matter that much, it was just a matter of calling a bunch of LLVM primitives and passing simple arguments to them.
Now that we are writing entire real-time interactive programs with it, performance matters much more. I'm starting to feel the need to implement things like real data types (which XLR lacks right now). The "dyncompile" branch is much better than "master" in that respect, but the paint is even fresher than for XL2 (read: it only compiles a dozen tests or so).
Regards
Christophe
Henry Weller
http://xlr.git.sourceforge.net/git/gitweb.cgi?p=xlr/xlr;a=blob;f=xl2/native/TESTS/05.Expressions/multi-reduction.xl. All XL fundamental operators are defined that way (see xl_builtins.xs).
Great, thanks.
>> Actually compared to the results we see with OpenFOAM these results show
>> clang in a pretty good light. At the moment we would expect a clang compiled
>> version of OpenFOAM to be about a factor of 2 slower than compiled with gcc
>> but we need to play with the options more to see if we can squeeze more
>> performance out of it.
> This is so disappointing. When did you do your experiment?
The very latest Clang fails to compile OpenFOAM so we are testing a version from
a couple of months ago. I am just starting some more detailed performance tests
comparing the latest gcc with Clang, I will report back when complete.
> Here is a recent benchmark:
> http://www.phoronix.com/scan.php?page=article&item=intel_snb_llvm&num=1. Here,
> LLVM is far from being as bad as it used to be. It's not stellar either.
Certainly looks better that what we have seen in the past.
> Yes, that's true. And that's really a design issue, so it's unlikely to be a
> quick fix. The problem is that the compiler works by rewriting parse trees, so
> it spends a lot of time looking up the "best tree match", even for simple
> things like A+B. In A+B*C, you need to first check if there is a form matching
> A+B*C, then you realize that there is none, so you fall back to B*C followed
> by A+result.
> It's much easier when things are hardcoded and have a fixed size :-)
> That being said, the inner symbol lookup code could be optimized quite a bit,
> e.g by avoiding using C++ maps which are really not suited for that use.
I have been running some valgrind --tool=callgrind profiling on it and indeed
the bottleneck is in the number of calls and cost of the C++ maps. I guess hash
tables would be more suitable. The containers in OpenFOAM predate STL by quite
a few years and we wrote our map class based on a hash table which seems more
appropriate for most purposes. I understand that a hash table was developed for
STL but not released with it but it will be in the next standard.
>> Do you see XLR as a replacement for XL2?
> Not in the short term, although it's possible I might one day re-implement XL2
> as a library in XLR. Not sure whether this is realistic or not. However, I
> must say that I'm starting to "like" XLR more and more, in particular because
> it's very dense. If I can bring its performance to acceptable levels, who
> knows...
Do you think that it might be suitable for writing HPC simulation codes in? My
feeling is that statically-typed generic is a better approach both in terms of
syntax and performance.
> Now that we are writing entire real-time interactive programs with it,
> performance matters much more. I'm starting to feel the need to implement
> things like real data types (which XLR lacks right now). The "dyncompile"
> branch is much better than "master" in that respect, but the paint is even
> fresher than for XL2 (read: it only compiles a dozen tests or so).
It seems that many of your design goals for XLR are similar to PLOT, a Lisp with
a syntax more like XL and the macros which operate on the AST:
http://users.rcn.com/david-moon/PLOT/page-1.html
http://users.rcn.com/david-moon/PLOT/Moon-ILC09.pdf
Best regards
Henry
Christophe de Dinechin
On 7 mars 2011, at 21:37, Henry Weller wrote:
> I have been running some valgrind --tool=callgrind profiling on it and indeed
> the bottleneck is in the number of calls and cost of the C++ maps. I guess hash
> tables would be more suitable. The containers in OpenFOAM predate STL by quite
> a few years and we wrote our map class based on a hash table which seems more
> appropriate for most purposes. I understand that a hash table was developed for
> STL but not released with it but it will be in the next standard.
While in my experience the STL map is an easy to use disappointment, the issue with tree rewrites is a little more than just the container being used. There's really some work to be done on the algorithm itself.
You may remember that at the beginning of this discussion I talked about the rewrite algorithm for XLR being a simplified version that took the "first fit". That's one of the things that makes it acceptable for interactive use. More importantly, it allows part of the algorithm to be implemented as dynamically generated code.
Another approach I considered, but never implemented, was to optimize for the operators with small number of parameters. Consider an expression like A+B+C+D+E+F. It is highly unlikely that this is a single written form. Yet today, XL2 first looks for the complete expression, then again for the subexpressions. It's expensive, just like the naive implementation of Fibonacci often used to test optimizations.
But just like Fibonacci, you can be much faster if you go bottom up. I.e. you start by assuming it's the standard A+B if you have one. Then you walk one level up, and you lookup combinations of operators, i.e. if you have A+B*C, you recognize it not as a whole tree, but as a combination A+X, where X is the result of the previous operation, specially marked to allow this recognition.
I don't know if the explanation is very clear, but roughly, it would bring the lookup algorithm from O(n^2) down to O(n).
>
>>> Do you see XLR as a replacement for XL2?
>
>> Not in the short term, although it's possible I might one day re-implement XL2
>> as a library in XLR. Not sure whether this is realistic or not. However, I
>> must say that I'm starting to "like" XLR more and more, in particular because
>> it's very dense. If I can bring its performance to acceptable levels, who
>> knows...
>
> Do you think that it might be suitable for writing HPC simulation codes in?
Right now, the answer is no (even if XLR is case sensitive :-). However, the version I'm working on in the dyncompile branch has a much better support for data types and generates much better code.
For example, consider the Fibonacci code in http://xlr.git.sourceforge.net/git/gitweb.cgi?p=xlr/xlr;a=blob;f=xlr/tests/09.Compiler/optimized-fibonacci-loop.xl;hb=dyncompile. There's a million loops which are optimized away because they all compute the same value. And then the generated code for the Fibonacci sequence runs at a speed comparable to GCC at -O2:
ddd@Platipuce[bigmerge] xlr> time ./xlr -O3 f.xl
1836311903
real 0m9.561s
user 0m9.541s
sys 0m0.016s
ddd@Platipuce[bigmerge] xlr> cc -O2 f.c -o a.out
ddd@Platipuce[bigmerge] xlr> time ./a.out
Fib 45=1836311903
real 0m8.534s
user 0m8.525s
sys 0m0.008s
If memory serves me well, I had gotten it close to the -O3 speed at one point, but I disabled some LLVM optimizations for now (they cause problem when you generate code dynamically).
That being said, HPC has many other requirements : data structures, parallelism, ... For instance, how would you see the ideal multicore execution model for HPC? Similar to Erlang? More explicit a la Ada? MPI? OpenMP?
> My feeling is that statically-typed generic is a better approach both in terms of syntax and performance.
Assuming we solve the performance issue, what aspects of syntax and semantics matter the most to you? Here is what I can think about, let me know if there are more:
- Define usable notations for mathematical entities, e.g. complex numbers, matrices, ... For example, write A+B to add two matrices. These should be user-defined.
- Fine-grained control over the machine representation of these notations, e.g. sparse matrices, using GPUs, dispatching workloads over multiple cores, ...
- Visualization of large data sets, e.g. 3D representations, generating movie files, ...
- Readable and maintainable code, e.g. modularization, self-documentation, ... Static typing may fall into this category more than in "performance" (given a smart enough type inference mechanism).
XLR may get there over time. You are certainly more than welcome to share a wish list or samples of pseudo code. They may not turn into real code in the short term, but they will not be forgotten.
>> Now that we are writing entire real-time interactive programs with it,
>> performance matters much more. I'm starting to feel the need to implement
>> things like real data types (which XLR lacks right now). The "dyncompile"
>> branch is much better than "master" in that respect, but the paint is even
>> fresher than for XL2 (read: it only compiles a dozen tests or so).
>
> It seems that many of your design goals for XLR are similar to PLOT, a Lisp with
> a syntax more like XL and the macros which operate on the AST:
>
> http://users.rcn.com/david-moon/PLOT/page-1.html
> http://users.rcn.com/david-moon/PLOT/Moon-ILC09.pdf
I'd say that the design objectives were (at least historically) quite different. But the implementation approach is close.
Another language that inspired XLR is Dr Gräf's Pure programming language.
Regards
Christophe
Henry Weller
very aggressive optimisation options on gcc. We will play a bit more with the
options on Clang to close the gap further but anyway I would say the results
were encouraging.
> You may remember that at the beginning of this discussion I talked about the
> rewrite algorithm for XLR being a simplified version that took the "first
> fit". That's one of the things that makes it acceptable for interactive
> use. More importantly, it allows part of the algorithm to be implemented as
> dynamically generated code.
I guess that this simplification may be rather restrictive.
> Another approach I considered, but never implemented, was to optimize for the
> operators with small number of parameters. Consider an expression like
> A+B+C+D+E+F. It is highly unlikely that this is a single written form. Yet
> today, XL2 first looks for the complete expression, then again for the
> subexpressions. It's expensive, just like the naive implementation of
> Fibonacci often used to test optimizations.
> But just like Fibonacci, you can be much faster if you go bottom up. I.e. you
> start by assuming it's the standard A+B if you have one. Then you walk one
> level up, and you lookup combinations of operators, i.e. if you have A+B*C,
> you recognize it not as a whole tree, but as a combination A+X, where X is the
> result of the previous operation, specially marked to allow this recognition.
> I don't know if the explanation is very clear, but roughly, it would bring the
> lookup algorithm from O(n^2) down to O(n).
Interesting, thanks for the details. I will study the code more closely.
>>>> Do you see XLR as a replacement for XL2?
>> Do you think that it might be suitable for writing HPC simulation codes in?
> Right now, the answer is no (even if XLR is case sensitive :-).
:-)
> However, the version I'm working on in the dyncompile branch has a much better
> support for data types and generates much better code.
Currently I am unable to build XLR, it appears that the Linux build scripts are
a bit behind. I will see if I can get it up and running.
> That being said, HPC has many other requirements : data structures,
> parallelism, ...
Indeed
> For instance, how would you see the ideal multicore execution model for HPC?
> Similar to Erlang? More explicit a la Ada? MPI? OpenMP?
Good question. I would certainly start with a domain-decomposition approach for
the large-scale parallelism, i.e. between node or motherboards in a cluster
machine, using some kind of message-passing the details of which would be
abstracted. However, this form of parallelism is not ideal for multi-core as
the number of cores increases and certainly not appropriate for GPUs and
similar, for these the parallelism needs to be much finer-grained. What I am
looking for is an approach which separates these details from the high-level
solution algorithm so that pluggable back-ends can be optimised for the
different hardware and chosen as required.
>> My feeling is that statically-typed generic is a better approach both in
>> terms of syntax and performance.
> Assuming we solve the performance issue, what aspects of syntax and semantics
> matter the most to you? Here is what I can think about, let me know if there
> are more:
> - Define usable notations for mathematical entities, e.g. complex numbers,
> - matrices, ... For example, write A+B to add two matrices. These should be
> - user-defined.
This is certainly important. C++ is fairly good in this regard but not great;
the biggest problem being that you can't define your own operators or set the
precedence of the operator symbols provided. Nevertheless we can represent the
solution of the Navier-Stokes equation in code as
solve
(
fvm::ddt(rho, U)
+ fvm::div(phi, U)
- fvm::laplacian(mu, U)
==
- fvc::grad(p)
);
I would like to take this kind of representation even further, e.g. as is
possible in Fortress using UTF8 symbols
> - Fine-grained control over the machine representation of these notations,
> - e.g. sparse matrices, using GPUs, dispatching workloads over multiple cores,
> - ...
ABSOLUTELY! This is going to be really important in the future.
> - Visualization of large data sets, e.g. 3D representations, generating movie files, ...
Yes, but these algorithms are not that different to those for simulation so if
we can write a simulation code we can write a post-processor code.
> - Readable and maintainable code, e.g. modularization, self-documentation,
> - ... Static typing may fall into this category more than in "performance"
> - (given a smart enough type inference mechanism).
It seems to me that the most important reason for static typing is for static
function dispatch for efficiency which leads me to generic programming. And if
the generic programming support is good enough then there is no need for virtual
functions, polymorphism and all that complexity, it can all be done with static
types and static dispatch.
I will think further about this list of requirements for a next-generation HPC
programming language and runtime environment.
> XLR may get there over time.
But why XLR? Why not XL2? What is the advantage of XLR? It seems to me that
you were getting close to a really good language with XL2.
> You are certainly more than welcome to share a wish list or samples of pseudo
> code. They may not turn into real code in the short term, but they will not be
> forgotten.
Thanks, I will start fleshing-out my thought on this for discussion.
> Another language that inspired XLR is Dr Gräf's Pure programming language.
Yes, interesting.
Best regards
Henry
Christophe de Dinechin
On 8 mars 2011, at 15:23, Henry Weller wrote:
>> XLR may get there over time.
>
> But why XLR? Why not XL2? What is the advantage of XLR? It seems to me that
> you were getting close to a really good language with XL2.
Before I answer the other parts of your mail, let me answer this one. To me, it's not either XLR or XL2, it's XLR and XL2. XLR is part of what I thought I needed in order to make XL2 dynamic (I write "I thought" because tcc might have gotten me there). XL2 is a language I wish I could use on a daily basis for heavy development.
Now, XL2 is currently a bit on hold because XLR is a) a bit complex to develop, b) turns out to be an interesting language to explore, c) is used by Taodyne in its product (meaning: that's how I plan to earn money).
Also, to be honest, XL2 didn't exactly attract developers as I hoped, so I felt I was harming nobody by slowing development a little. If someone needs it, that's certainly a good motivation for spending a little more time working on it.
But again, if you go to the XLR web site, it shows both XL2 and XLR. Both are alive, both have a reason to be.
Henry Weller
> Before I answer the other parts of your mail, let me answer this one. To me,
> it's not either XLR or XL2, it's XLR and XL2. XLR is part of what I thought I
> needed in order to make XL2 dynamic (I write "I thought" because tcc might
> have gotten me there). XL2 is a language I wish I could use on a daily basis
> for heavy development.
I will have a go myself at making XL2 dynamic with tcc, should be fun :-)
> Now, XL2 is currently a bit on hold because XLR is a) a bit complex to
> develop, b) turns out to be an interesting language to explore, c) is used by
> Taodyne in its product (meaning: that's how I plan to earn money).
Fair enough :-)
> Also, to be honest, XL2 didn't exactly attract developers as I hoped,
Actually I only came across it quite by accident from your posts to the Go
mailing list. I think it could do with a few more links on Wikipedia to the
other language pages, I will put those in.
> so I felt I was harming nobody by slowing development a little. If someone
> needs it, that's certainly a good motivation for spending a little more time
> working on it.
I will certainly play with it with the view of using it seriously if it really
does fulfil the potential and offer the functionality I need. I wonder if we
can find some way to fund this development work.....
Christophe de Dinechin
On 8 mars 2011, at 15:23, Henry Weller wrote:
> Our latest tests show that Clang now is only 15% down on gcc or 20% if we use
> very aggressive optimisation options on gcc. We will play a bit more with the
> options on Clang to close the gap further but anyway I would say the results
> were encouraging.
Good news for me.
>
>> You may remember that at the beginning of this discussion I talked about the
>> rewrite algorithm for XLR being a simplified version that took the "first
>> fit". That's one of the things that makes it acceptable for interactive
>> use. More importantly, it allows part of the algorithm to be implemented as
>> dynamically generated code.
>
> I guess that this simplification may be rather restrictive.
I thought so initially, but actually, it's not been a problem so far. It means you need to write the factorial as
0! -> 1
N! -> N * (N-1)!
because if you put the two statements the other way round, the more general case is found first and you end up with an infinite recursion. But is that really an issue?
>> However, the version I'm working on in the dyncompile branch has a much better
>> support for data types and generates much better code.
>
> Currently I am unable to build XLR, it appears that the Linux build scripts are
> a bit behind. I will see if I can get it up and running.
I know the code builds, because we build it using Qt for the Linux version of Taodyne's product. But it's possible the command-line Makefiles are behind. I will look into this today.
>> - Define usable notations for mathematical entities, e.g. complex numbers,
>> - matrices, ... For example, write A+B to add two matrices. These should be
>> - user-defined.
>
> This is certainly important. C++ is fairly good in this regard but not great;
> the biggest problem being that you can't define your own operators or set the
> precedence of the operator symbols provided. Nevertheless we can represent the
> solution of the Navier-Stokes equation in code as
>
> solve
> (
> fvm::ddt(rho, U)
> + fvm::div(phi, U)
> - fvm::laplacian(mu, U)
> ==
> - fvc::grad(p)
> );
It's been a long time, but what is phi in this notation? Also, how does 'solve' know what variables to solve for?
>
> I would like to take this kind of representation even further, e.g. as is
> possible in Fortress using UTF8 symbols
But then, is it really more readable as:
solve ϱ*dU/dt + U•∇U = -∇p + μ*
Henry Weller
> I thought so initially, but actually, it's not been a problem so far. It means
> you need to write the factorial as
> 0! -> 1
> N! -> N * (N-1)!
> because if you put the two statements the other way round, the more general
> case is found first and you end up with an infinite recursion. But is that
> really an issue?
Not for simple examples such as the factorial but maybe it will be for really
complex algorithms.
>> Currently I am unable to build XLR, it appears that the Linux build scripts are
>> a bit behind. I will see if I can get it up and running.
> I know the code builds, because we build it using Qt for the Linux version of
> Taodyne's product. But it's possible the command-line Makefiles are behind.
I tried the Makefile and noticed the one for Linux is behind that for MacOSX, I
started to upgrade the Makefile for Linux but had a bit of trouble not knowing
exactly how everything should be built.
> I will look into this today.
Thanks
>> solve
>> (
>> fvm::ddt(rho, U)
>> + fvm::div(phi, U)
>> - fvm::laplacian(mu, U)
>> ==
>> - fvc::grad(p)
>> );
> It's been a long time, but what is phi in this notation?
phi is the face-flux which is an alternative representation of the velocity U
needed for the finite-volume approach to discretisation on general computational
meshes.
> Also, how does 'solve' know what variables to solve for?
'fvm' functions return a particular matrix form for which +, - etc. operators are
defined for so 'solve' operates on the resulting complete matrix.
>> I would like to take this kind of representation even further, e.g. as is
>> possible in Fortress using UTF8 symbols
> But then, is it really more readable as:
> solve ϱ*dU/dt + U•∇U = -∇p + μ*
Not much but there is an issue with C++ with respect to operators which this
would resolve, consider the vector expression
vector v = a + b ^ c;
where '^' is the cross-product, this will be evaluated as
vector v = (a + b) ^ c;
not
vector v = a + (b ^ c);
and '^' is not a great symbol for the purpose but there is a suitable one in
UTF8.
> I think it makes sense once we get to the point where we can represent real
> mathematical formulas in our program editors. Before then, I'm not sure it's
> an improvement. What do you think?
It is certainly not the most important issue but being able do define operators
and their precedence is.
>>> - Readable and maintainable code, e.g. modularization, self-documentation,
>>> - ... Static typing may fall into this category more than in "performance"
>>> - (given a smart enough type inference mechanism).
>>
>> It seems to me that the most important reason for static typing is for static
>> function dispatch for efficiency which leads me to generic programming.
> An alternative (used in XLR) is type inference, where the types are dynamic
Are types dynamic only at compile-time or also at run-time?
I have worked on Eu2C which is a "total compiler" of EuLisp to C and uses type
inference extensively to optimise generic (in the CLOS sense) functions but the
types are still dynamic which has a run-time overhead even for very simple
integer operations. This is really why I have gone back to studying
statically-typed generic languages.
> but type equations are resolved by the compiler so that it can optimize for
> the actual types being used. For example, you can write
> min x,y -> if x < y then x else y
> and then have the compiler pick different machine operations depending on the
> actual data types. As a matter of fact, on the dyncompile branch, min 3,4 is
> simplified by the compiler as 3, i.e. it doesn't even generate a function.
Interesting; if all the overhead of dynamic types is stripped away by the
compiler this would be great.
>> And if the generic programming support is good enough then there is no need
>> for virtual functions, polymorphism and all that complexity, it can all be
>> done with static types and static dispatch.
> Polymorphism is still important. I wouldn't write a drawing program without
> being able to write shape.Draw() to draw shapes of any kind, say, picked up
> from a "container of shapes".
Doing this with pure generic functionality would be difficult but there are many
parts of OpenFOAM which currently use virtual functions but needn't if the
generic functionality in C++ were more convenient to use.
> The (unimplemented) plan for XL2 is to have multimethods that are defined as follows:
> procedure Draw(S : any shape)
> function Intersect(S1, S2 : any shape) return any shape
> The "virtuality" is implemented using a generic data type, "any T". A variable
> with "any shape" type can hold a value of any type derived from "shape". When
> it's used as a function parameter, the function becomes "virtual", and this
> can happen on more than one parameter.
Multi-methods is something I miss in C++ but I understand there is a plan to add
them but not in the next standard, the one after :-(
> I know I can implement the "any T" type with the existing generics support,
> not sure about dynamic dispatch but I will try.
If the type information is available at run-time this should be much like it is
in CLOS. It might also be interesting to dig-up the paper that Stroustrup and
his students have written on multi-methods in C++ to see what dispatch algorithm
they have chosen.
Best regards
Henry
Christophe de Dinechin
> started to upgrade the Makefile for Linux but had a bit of trouble not knowing
> exactly how everything should be built.
>
>> I will look into this today.
>
> Thanks
Fixed in commit: commit:eb6176475eb14f67ad35c5dfb21f8ddc8d0dfd99 on the master branch. Very sorry for the inconvenience.
I also pushed the change in the dyncompile branch (commit 0c30f2fd0c752e9e3539a59ba60cfc0371c269b3), but with the latest LLVM, there are a few issues in the test suite. I don't think I ever really tested that branch on Linux.
Regards
Christophe
Henry Weller
> branch. Very sorry for the inconvenience.
No problem, the Makefile now works but I need to upgrade LLVM which I will do
now.
> I also pushed the change in the dyncompile branch (commit
> 0c30f2fd0c752e9e3539a59ba60cfc0371c269b3), but with the latest LLVM, there are
> a few issues in the test suite. I don't think I ever really tested that branch
> on Linux.
For the dyncompile branch I get the same problem as before:
dm(718) make
make[1]: Entering directory `/home/dm2/henry/Other/xlr/xlr'
Dependency obj/linux/debug/basics.cpp.d
Dependency obj/linux/debug/main.cpp.d
Dependency obj/linux/debug/options.cpp.d
Dependency obj/linux/debug/errors.cpp.d
Dependency obj/linux/debug/tree.cpp.d
Dependency obj/linux/debug/hash.cpp.d
Dependency obj/linux/debug/action.cpp.d
Dependency obj/linux/debug/gc.cpp.d
Dependency obj/linux/debug/syntax.cpp.d
Dependency obj/linux/debug/scanner.cpp.d
Dependency obj/linux/debug/parser.cpp.d
Dependency obj/linux/debug/renderer.cpp.d
Dependency obj/linux/debug/context.cpp.d
Dependency obj/linux/debug/runtime.cpp.d
----------- Making debug in /home/dm2/henry/Other/xlr/xlr ------------
make[1]: *** No rule to make target `obj/linux/debug/Makefile.depend', needed by `depend'. Stop.
make[1]: Leaving directory `/home/dm2/henry/Other/xlr/xlr'
make: *** [debug] Error 2
but obj/linux/debug/Makefile.depend does exist
Henry Weller
> 0c30f2fd0c752e9e3539a59ba60cfc0371c269b3), but with the latest LLVM, there are
> a few issues in the test suite. I don't think I ever really tested that branch
> on Linux.
No problem, with the latest LLVM both the master and dyncompile branches of XLR
now compile fine on Linux.
Thanks
Henry
Christophe de Dinechin
On 10 mars 2011, at 12:01, Henry Weller wrote:
> make[1]: Entering directory `/home/dm2/henry/Other/xlr/xlr'
> Dependency obj/linux/debug/basics.cpp.d
> Dependency obj/linux/debug/main.cpp.d
> Dependency obj/linux/debug/options.cpp.d
> Dependency obj/linux/debug/errors.cpp.d
> Dependency obj/linux/debug/tree.cpp.d
> Dependency obj/linux/debug/hash.cpp.d
> Dependency obj/linux/debug/action.cpp.d
> Dependency obj/linux/debug/gc.cpp.d
> Dependency obj/linux/debug/syntax.cpp.d
> Dependency obj/linux/debug/scanner.cpp.d
> Dependency obj/linux/debug/parser.cpp.d
> Dependency obj/linux/debug/renderer.cpp.d
> Dependency obj/linux/debug/context.cpp.d
> Dependency obj/linux/debug/runtime.cpp.d
> ----------- Making debug in /home/dm2/henry/Other/xlr/xlr ------------
> make[1]: *** No rule to make target `obj/linux/debug/Makefile.depend', needed by `depend'. Stop.
> make[1]: Leaving directory `/home/dm2/henry/Other/xlr/xlr'
> make: *** [debug] Error 2
Try rm -rf obj and rebuild. The Makefile structure has changed between master and dyncompile (parallel builds were broken on master). When you switch branches, dyncompile gets confused because the Makefile.depend file is "wrong".
Christophe
Christophe de Dinechin
On 9 mars 2011, at 13:06, Henry Weller wrote:
>>> I guess that this simplification may be rather restrictive.
>
>> I thought so initially, but actually, it's not been a problem so far. It means
>> you need to write the factorial as
>
>> 0! -> 1
>> N! -> N * (N-1)!
>
>> because if you put the two statements the other way round, the more general
>> case is found first and you end up with an infinite recursion. But is that
>> really an issue?
>
> Not for simple examples such as the factorial but maybe it will be for really
> complex algorithms.
In practice, you can always sort the "more specialized" first manually in a single file. The answer is less clear if multiple files are involved. Whether this is a problem or not we don't know yet.
>>> I would like to take this kind of representation even further, e.g. as is
>>> possible in Fortress using UTF8 symbols
>
>> But then, is it really more readable as:
>
>> solve ϱ*dU/dt + U•∇U = -∇p + μ*
>
> Not much but there is an issue with C++ with respect to operators which this
> would resolve, consider the vector expression
>
> vector v = a + b ^ c;
>
> where '^' is the cross-product, this will be evaluated as
>
> vector v = (a + b) ^ c;
>
> not
>
> vector v = a + (b ^ c);
>
> and '^' is not a great symbol for the purpose but there is a suitable one in
> UTF8.
Good point. That makes sense.
>> An alternative (used in XLR) is type inference, where the types are dynamic
>
> Are types dynamic only at compile-time or also at run-time?
Let me start a separate thread on the XLR type system. You asked very interesting questions, some of which I've not completely resolved yet.
> I have worked on Eu2C which is a "total compiler" of EuLisp to C and uses type
> inference extensively to optimise generic (in the CLOS sense) functions but the
> types are still dynamic which has a run-time overhead even for very simple
> integer operations. This is really why I have gone back to studying
> statically-typed generic languages.
That much I can answer : in the XLR case, the whole point of type inference is to completely eliminate dynamic type checks when possible. In the best cases, that leads to code that is indistinguishable from optimized C code.
For instance, consider the following simple test case (f.xl) :
// LLVM built-in opcodes (will be moved in builtins.xl later)
(x:integer * y:integer):integer -> opcode Mul
(x:integer - y:integer):integer -> opcode Sub
// Typical factorial definition
fact 0 -> 1
fact N -> N * fact (N-1)
fact 6
Run this with "./xlr -O3 -tcode f.xl". This shows the generated LLVM code. I added some comments:
// Code generated for the fact 0 definition.
// It returns a native i64, not a boxed entity
define internal i64 @xl_eval_fact1() {
allocas:
ret i64 1
}
// Code generated for the fact N definition
// It takes an i64 argument and return an i64.
define internal i64 @xl_eval_fact(i64) {
allocas:
// Compute N-1 in %1
%1 = sub i64 %0, 1
// Check if N-1 is 0, if so go to label %good
%2 = icmp eq i64 0, %1
br i1 %2, label %good, label %bad
done: ; preds = %bad, %good
%loc.0 = phi i64 [ %5, %good ], [ %4, %bad ]
// Compute N * fact (N-1), all using i64 values, and return the result
%3 = mul i64 %0, %loc.0
ret i64 %3
bad: ; preds = %allocas
// Case when N-1 is not zero: recursive call to this function
%4 = call i64 @xl_eval_fact(i64 %1)
br label %done
good: ; preds = %allocas
// Case when N-1 is zero: call the function for fact 0 (that returns 1).
%5 = call i64 @xl_eval_fact1()
br label %done
}
// Top-level program
define %Tree* @xl_program() {
allocas:
// Perform all computations of fact 6 using only i64 values
%0 = call i64 @xl_eval_fact(i64 6)
// Box the result as an XLR Integer object
%1 = call %Integer* @xl_new_integer(i64 %0)
// Return that Integer
%2 = bitcast %Integer* %1 to %Tree*
ret %Tree* %2
}
Here is what the generated code looks like on MacOSX X86-64:
(gdb) x/30i code
0x101700010: push %rax
// Call generated function for fact N with argument 6
0x101700011: mov $0x6,%edi
0x101700016: mov $0x1017c8010,%rax
0x101700020: callq *%rax
// Move result as input to xl_new_integer
0x101700022: mov %rax,%rdi
0x101700025: mov $0x1000d6b3f,%rax
0x10170002f: pop %rdx
// Tail call to xl_new_integer
0x101700030: jmpq *%rax
// Checking that 0x1000d6b3f is xl_new_integer
(gdb) x/30i 0x1000d6b3f
0x1000d6b3f <_ZN2XL14xl_new_integerEx>: push %rbp
0x1000d6b40 <_ZN2XL14xl_new_integerEx+1>: mov %rsp,%rbp
0x1000d6b43 <_ZN2XL14xl_new_integerEx+4>: push %rbx
The 0x1017c8010 addresss is a small trampoline, I believe used to allow LLVM delayed compilation.
(gdb) x/30i 0x1017c8010
0x1017c8010: mov $0x101700090,%r10
0x1017c801a: jmpq *%r10
The machine code of the actual function is:
0x101700090: push %rbx
// Save N in B
0x101700091: mov %rdi,%rbx
// Compute N-1
0x101700094: mov %rbx,%rdi
0x101700097: dec %rdi
// Multiply by 1 if N-1 is 0
0x10170009a: mov $0x1,%ecx
0x10170009f: je 0x1017000b4
// Otherwise recursive call for fact(N-1)
0x1017000a5: mov $0x1017c8010,%rcx
0x1017000af: callq *%rcx
// Move result of fact (N-1) into rcx for multiplication
0x1017000b1: mov %rax,%rcx
// Multiple N by either 1 or fact(N-1)
0x1017000b4: mov %rbx,%rax
0x1017000b7: imul %rcx,%rax
// Result is in %rax here...
0x1017000bb: pop %rbx
0x1017000bc: retq
So all in all, it's not too bad. There's an extra trampoline and a couple instructions that could be removed, but that's about it.
>
>> but type equations are resolved by the compiler so that it can optimize for
>> the actual types being used. For example, you can write
>
>> min x,y -> if x < y then x else y
>
>> and then have the compiler pick different machine operations depending on the
>> actual data types. As a matter of fact, on the dyncompile branch, min 3,4 is
>> simplified by the compiler as 3, i.e. it doesn't even generate a function.
>
> Interesting; if all the overhead of dynamic types is stripped away by the
> compiler this would be great.
The problem is that there is no guarantee that all the overhead can be removed. It depends on what type information can be deduced from the program. You can also add type information with type declarations, e.g. x:integer.
>> I know I can implement the "any T" type with the existing generics support,
>> not sure about dynamic dispatch but I will try.
>
> If the type information is available at run-time this should be much like it is
> in CLOS.
Yes, that's the idea.
> It might also be interesting to dig-up the paper that Stroustrup and
> his students have written on multi-methods in C++ to see what dispatch algorithm
> they have chosen.
Ideally, I'd like this algorithm to be provided by the library. I'm not entirely sure how to describe this just yet, mostly because it impacts the function call mechanisms which are currently a bit hard-coded.
Regards
Christophe
Henry Weller
> to completely eliminate dynamic type checks when possible. In the best cases,
> that leads to code that is indistinguishable from optimized C code.
> The problem is that there is no guarantee that all the overhead can be
> removed. It depends on what type information can be deduced from the
> program. You can also add type information with type declarations,
> e.g. x:integer.
OK thanks for your patience, now it is all beginning to make sense. However, as
I have found with Eu2C, while type inference as a way to optimise dynamic typing
is very attractive and may be a good approach for many programming problems I am
not convinced that it will allow sufficient optimisation for HPC applications,
not just with respect to CPU usage but also with respect to memory usage if that
is reliant on a garbage collector. For HPC simulation applications my guess is
that XL2 is a better approach and if I had to choose which to invest my time in
it would be that; I suppose I my interests in programming are rather narrow and
extreme.
>> It might also be interesting to dig-up the paper that Stroustrup and
>> his students have written on multi-methods in C++ to see what dispatch algorithm
>> they have chosen.
> Ideally, I'd like this algorithm to be provided by the library. I'm not
> entirely sure how to describe this just yet, mostly because it impacts the
> function call mechanisms which are currently a bit hard-coded.
As far as I can tell XL2 doesn't support functions as function arguments, would
it be possible/realistic/easy to add such support? If so would it also be
possible to add support for anonymous functions?
Best regards
Henry