Newbie questions about Pliant

Newbie questions about Pliant

uInt much slower than Int

uInt performance is much slower than Int performance
Message posted by naasking on 2005/04/09 14:18:40
A simple fibonnacci function demonstrates a drastic performance difference
between using Int and uInt:

function fibo n -> r
  arg Int n r
  if n < 2
    return 1
  else
    return (fibo n-2)   (fibo n-1)

console "out: "   ('convert to string' (fibo 40))   "[lf]"

This version takes 2.77 seconds to complete on my machine. If 'arg Int' 
is replaced by 'arg uInt', the execution time increases to 7.972 seconds.

If the number provided to fibo is increased to 45, to difference is ~30 
seconds vs. ~1 minute 30 seconds

Is there a particular reason for this huge performance difference? Does 
uInt perform extra checks or something?
Message posted by hubert.tonneau on 2005/04/09 14:32:48
Just remplace fibo with 'sample function' and Pliant will display the
code it generates.

You can get an exemple through:
pliant module /pliant/sample/code_generator.pli

Now, about your 'fibo' function, here is the result:

With Int:

  0: i386_push EBP  (Int  ) at 
  1: i386_mov ESP EBP  (Int Int  ) at 
  3: i386_push ESI  (Int  ) at 
  4: i386_push EBX  (Int  ) at 
  5: i386_mov EAX ESI  (Int Int  ) at 
  7: i386_mov ESI EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 3 8
  9: i386_cmp c0 EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 3 8
  12: i386_jump_if 6 => 33  (Int  ) at file:/tmp/foo.pli (internals) 3 8
  18: i386_mov c3 EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 4 5
  23: jump anyway => 61  ( ) at file:/tmp/foo.pli (internals) 4 5
  28: jump anyway => 61  ( ) at file:/tmp/foo.pli (internals) 3 3
  33: i386_mov ESI EAX <= 12  (Int Int  ) at file:/tmp/foo.pli (internals) 6 32
  35: i386_sub c4 EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 32
  38: sample function  (Int Int  file:/tmp/foo.pli (internals) 1 1) at file:/tmp/foo.pli (internals) 6 13
  43: i386_mov EAX EBX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 13
  45: i386_mov ESI EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 56
  47: i386_sub c7 EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 56
  50: sample function  (Int Int  file:/tmp/foo.pli (internals) 1 1) at file:/tmp/foo.pli (internals) 6 37
  55: i386_mov EBX ECX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 35
  57: i386_add EAX ECX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 35
  59: i386_mov ECX EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 35
  61: i386_pop EBX <= 23 <= 28  (Int  ) at 
  62: i386_pop ESI  (Int  ) at 
  63: i386_pop EBP  (Int  ) at 
  64: i386_return 0  (Int  ) at 


With uInt:

  0: i386_push EBP  (Int  ) at 
  1: i386_mov ESP EBP  (Int Int  ) at 
  3: i386_push ESI  (Int  ) at 
  4: i386_push EBX  (Int  ) at 
  5: i386_mov EAX ESI  (Int Int  ) at 
  7: i386_mov c0 EDX  (Int Int  ) at file:/tmp/foo.pli (internals) 3 8
  12: i386_mov ESI EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 3 8
  14: compare_uInt  (uInt uInt Int  /pliant/language/type/number/int.pli (internals) 82 1) at file:/tmp/foo.pli (internals) 3 8
  19: i386_mov 1 EDX  (Int Int  ) at file:/tmp/foo.pli (internals) 3 8
  24: compare apply mode  (Int Int CBool  ) at file:/tmp/foo.pli (internals) 3 8
  29: i386_cmp 0 EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 3 3
  32: i386_jump_if 2 => 53  (Int  ) at file:/tmp/foo.pli (internals) 3 3
  38: i386_mov c3 EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 4 5
  43: jump anyway => 81  ( ) at file:/tmp/foo.pli (internals) 4 5
  48: jump anyway => 81  ( ) at file:/tmp/foo.pli (internals) 3 3
  53: i386_mov ESI EAX <= 32  (Int Int  ) at file:/tmp/foo.pli (internals) 6 32
  55: i386_sub c4 EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 32
  58: sample function  (uInt uInt  file:/tmp/foo.pli (internals) 1 1) at file:/tmp/foo.pli (internals) 6 13
  63: i386_mov EAX EBX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 13
  65: i386_mov ESI EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 56
  67: i386_sub c7 EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 56
  70: sample function  (uInt uInt  file:/tmp/foo.pli (internals) 1 1) at file:/tmp/foo.pli (internals) 6 37
  75: i386_mov EBX ECX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 35
  77: i386_add EAX ECX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 35
  79: i386_mov ECX EAX  (Int Int  ) at file:/tmp/foo.pli (internals) 6 35
  81: i386_pop EBX <= 43 <= 48  (Int  ) at 
  82: i386_pop ESI  (Int  ) at 
  83: i386_pop EBP  (Int  ) at 
  84: i386_return 0  (Int  ) at

As you can see (if you understand assembly language), the key difference is
that in the second case, we call an external 'compare_uInt' function instead
of turning it to inline assembly.

  14: compare_uInt  (uInt uInt Int  /pliant/language/type/number/int.pli (internals) 82 1) at file:/tmp/foo.pli (internals) 3 8

Pliant code generator would need quite a lot of improvements !
Message posted by naasking on 2005/04/09 15:02:09
I figured it would be something like this. But since Int and uInt are
identical on any given machine (at least, of identical size), why are they 
treated differently by the optimizer?

As an aside, since you mentioned the optimizer, the underyling machinery of
pliant is till written in C is it not? I recall an effort for a native pliant
compiler:

http://fig.org/gord/cross-pliant.html

This would enable all of pliant to be written in pliant itself would it not? Is
there some reason this avenue is not pursued? Is the C foundation just
good enough?
Message posted by hubert.tonneau on 2005/04/09 16:04:28
> I figured it would be something like this. But since Int and uInt are
> identical on any given machine (at least, of identical size), why are they 
> treated differently by the optimizer?

They should.

> As an aside, since you mentioned the optimizer, the underyling machinery of
> pliant is till written in C is it not? I recall an effort for a native pliant
> compiler:
>
> http://fig.org/gord/cross-pliant.html
>
> This would enable all of pliant to be written in pliant itself would it not? Is
> there some reason this avenue is not pursued? Is the C foundation just
> good enough?

Most of Pliant is written in Pliant.
A small bootstrap part is still written in C.
Turning it to a cross compiler would be nice from the consistency point of view,
but would not change that much the overall picture since most people that are
willing to dig in Pliant machinery source code already know C.

The more serious problem to solve is code generator quality, and it is more
an algorithm issue (how to properly assign temporary variables to registers)
than a write it in C or Pliant issue.

What would be nice would be to be abble to use GCC optimising effort, but here
we fall on GCC poor design. GCC is thought as a compiler plus linker model,
and it's not flexible because it implies static compiling which is sadely
outdated and leads to bloated distributions.
Now, it has a second design flow which is that the object file format (what
is exchange between the compiler and the linker) is binary instead of beeing
ascii, so it's a nightmare to interface.

As a result, Pliant still relies on it's internal code generator (also the
GCC interface basically works with GCC 2.95) but I have not enough ressources
at the moment to work seriously on optimisation issues.
Another problem is that I will have to make a 64 bits port at some point, and
I will face serious problems here because Pliant assumes that Int is the same
as Address, so Pliant Int will be 64 bits on a 64 bits plateform as opposed
to C, and the Pliant prototype to the external (kernel and C libraries
interfaces) are not precise enough so plenty of small changes on prototypes
will be riquired.

In very fiew words, I'm concentrating my effort at the moment on turning Pliant
to a complete system, including a consistent user interface, rather than
concentrating on the language side, which I find basically ok except the small
performance penality due to subobtimal code generator optimiser.
Also I can understand people beeing interested solely by Pliant as a language
rather than a full application framework not be happy with that.
Message posted by naasking on 2005/04/09 21:47:04
>Most of Pliant is written in Pliant.
>A small bootstrap part is still written in C.
>Turning it to a cross compiler would be nice from the consistency point of view,
>but would not change that much the overall picture since most people that are
>willing to dig in Pliant machinery source code already know C.

Indeed, but it would make pliant applicable in areas for which it is currently
unsuitable (ie. operating system kernels).

>The more serious problem to solve is code generator quality, and it is more
>an algorithm issue (how to properly assign temporary variables to registers)
>than a write it in C or Pliant issue.

I'm not sure if you're aware of it, but there are packages that help in writing
platform-independent JITC, and which might assist you in this regard:

http://www.gnu.org/software/lightning/
http://www.southern-storm.com.au/libjit.html

>What would be nice would be to be abble to use GCC optimising effort, but here
>we fall on GCC poor design. GCC is thought as a compiler plus linker model,
>and it's not flexible because it implies static compiling which is sadely
>outdated and leads to bloated distributions.
>Now, it has a second design flow which is that the object file format (what
>is exchange between the compiler and the linker) is binary instead of beeing
>ascii, so it's a nightmare to interface.

Well, as an idea, how about compiling pliant to Register Transfer Language(RTL), 
GCC's platform-independent, low-level 'assembler-like' intermediate language.

http://en.wikipedia.org/wiki/Register_Transfer_Language

That would gain you GCC optimizations in addition to complete platform 
independence (well, to the extent that GCC is supported on a platform).
Message posted by naasking on 2005/04/09 21:47:30
>In very fiew words, I'm concentrating my effort at the moment on turning Pliant
>to a complete system, including a consistent user interface, rather than
>concentrating on the language side, which I find basically ok except the small
>performance penality due to subobtimal code generator optimiser.

Well, one could make the argument that completing the language will attract
enough outside interest to help you in your efforts... But you have to spend
your efforts where you feel it's most deserved. :-)
Message posted by naasking on 2005/04/09 22:25:32
Also just found this, which looks promising:

Low-Level Virtual Machine
http://llvm.cs.uiuc.edu/

Unfortunately written in C  , but is being praised quite widely as excellent
software.
Message posted by hubert.tonneau on 2005/04/10 07:39:38
> Well, one could make the argument that completing the language will attract
> enough outside interest to help you in your efforts... But you have to spend
> your efforts where you feel it's most deserved. :-)

Not really.
Marketing is better.
If you compare Python and Pliant, you soon understand that from a technical
point of view, Python should be discarded in favor of Pliant, but it does not
append.

> Low-Level Virtual Machine

A virtual machine is not the way to go: Pliant has a language has even more low
level capability than C. I mean you can add through a library some new data
type that for exemple would make great use of SSE, and the corresponding
optimising rules, what you can't do with C.

The problem to solve is: do we have a tool that takes the object file produced
by GCC and it's related assembler, and outputs it as a complete (no missing
information) and stable (not changing with every GCC release) ascii file.

The other possibility would be to interface a write a library that enables
to open the binary object file or the ELF DLLs. This is probably the way to
go in facts.

The bonus would probably to be abble to enter GCC at code generator neutral
language, so get maximum flexibility, rather than entering at C parser level,
but this is even more work.

On the code generator side, the top priority, except correcting the small
bug you pointed out about 'uInt' is to start using SSE2 (register based
floatting point) instructions instead of the i387 (stack based) ones that
are not optimised at all in Pliant code generator because I'm assuming any
modern processor is using registers rather than a stack.
Message posted by naasking on 2005/04/10 13:18:53
>Marketing is better.
>If you compare Python and Pliant, you soon understand that from a technical
>point of view, Python should be discarded in favor of Pliant, but it does not
>append.

I agree, but you can't market a language that is lacking in features. Python
provides programmers with certain features which you can't get in Pliant just
yet, so the barrier to entry is higher. The feature-completeness of the 
language makes for good self-marketing though. If programmers are impressed
with the featureset, they'll market it themselves.

>A virtual machine is not the way to go: Pliant has a language has even more
>low level capability than C. I mean you can add through a library some new
>data type that for exemple would make great use of SSE, and the corresponding
>optimising rules, what you can't do with C.

LLVM provides this too. I read into LLVM quite a bit last night and I'm 
seriously impressed with the quality of work that's gone into it. LLVM is
essentially a compiler framework that permits JITC, ahead of time compiling,
and sophisticated static analysis of all generated code all from a common
interface. Their stated goal is essentially to become the "next generation 
gcc". Check out some of their publications:

http://llvm.cs.uiuc.edu/pubs/

For instance, they used LLVM to write a framework to ensure memory safety
without runtime checks or garbage collection.

http://llvm.cs.uiuc.edu/pubs/2003-05-05-LCTES03-CodeSafety.html

If pliant were to target the LLVM bytecode, it could leverage all these
optimizations and simultaneously achieve platform independence. Sounds pretty 
good to me. :-)
Message posted by naasking on 2005/04/10 13:22:20
Given your statement that Pliant targets primarily register architectures,
targeting LLVM would be simpler I believe, since it uses an SSA
architecture with an "infinite register space"; it then performs its own
register optimizations and allocations for each architecture. Sorry, for going
all fan-boy, but it honestly looks like a compiler architecture done right.
Using it as a foundation would enable you to avoid thinking about optimization
and architecture dependencies and focus instead on the language-level and up,
which is where you've stated you want to be anwyay.

By the way, I noticed that trying to preview a message that is too long, kicks
me back to the note screen without any warning. I'm using konqueror as my web
browser; is it just my problem, or do the pliant forums intentionally lose posts
if they're too long? ie. do I have to manually cut and paste into two separate
notes (as I've been doing)?
Message posted by hubert.tonneau on 2005/04/10 14:33:02
> I agree, but you can't market a language that is lacking in features. Python
> provides programmers with certain features which you can't get in Pliant just
> yet

Portability, due to using bytecode instead of native code generation.
It has a serious efficiency drawback, so it runs poorly everywhere whereas
Pliant runs fairly nicely but requires i386 instruction set (*).
What else ?

> I read into LLVM quite a bit last night and I'm 
> seriously impressed with the quality of work that's gone into it.

If you look at /pliant/language/optimizer/gcc.pli,
it contains everything to switch from Pliant built in code generator to GCC.
The main functions are:
  generate_c_listing
which is translating Pliant instructions set to a C source code,
and
  load_compiled_code
which is responsible for parsing the assembly output.

You could try to adapt it to newer GCC or even LLVM. I can help through
providing Pliant side informations.
Now what makes me septical is that Python would get much more benefits to
switching to a serious code generator, and they have so much more ressources,
so if they can't carry it, I tend to believe it might not be that straight
forward.

I also tend to believe that what I need is more a state of the art registers
assigment algorithm.

From the various tests I could do on real computing intensive tests,
I concluded that Pliant code generator leads roughly to a 30% more execution
time compared to C. This is something I can cope with.
Also I can reduce it to nearly nothing through activating Pliant GCC interface,
I tend not to do it on production servers because it makes debugging harder,
and reliability is more important for me.
Also, the application level algorithms improvements I could achieve thanks
to Pliant very efficient profiler tend to be more than 30%, even if it does
not discard the possible 30% extra improvement at code generation level.

Now, the serious problems in software interface are in details, so when you start
everything is fine, and when you are close to the end, you start to discover
the real problems, and you already invested quite a lot of time, and end with
two projets to debug instead of one, so if LLVM is huge, I'll tend to avoid
it whatever it's quality are.
It does not mean that it's a bad choice, just that I cannot gamble because
I'm too old for that. When I was 15 or 20 years old I could have done that,
but now I have a very strict roadmap so I tend to favor predictible actions.

So if you point me out articles about registers assignment algorithms,
I will be personaly more interested because what I have to invest in order
to decide if it's truely usable for Pliant real situation is much lighter
than interfacing a real project.

On the other hand, the long term right solution might be LLVM, but we need
a guy that has time to invest in pure investigation. Welcome to contributors.


(*) It remains to be seen if Python native PowerPCC is more efficient than
    Pliant with an i386 emulation layer. I have no numbers here.


> By the way, I noticed that trying to preview a message that is too long, kicks
> me back to the note screen without any warning.

These are browser issues. Netscape 4 is ok in this area. Neither Mozilla nor
Firefox is. Konqueror is buggy in events handling.

You know what, my current task is building the Pliant browser because I need
a predictable user interface and HTML + CCS + DOM + SVG + Javascript + Java
is not a dinosorus, and it's still facing most of the issues the wrong way
round.