Introducing Newton Scripting language

A place to discuss everything related to Newton Dynamics.

Moderators: Sascha Willems, walaber

Re: Introducing Newton Scripting language

Postby Julio Jerez » Sat Sep 23, 2017 11:37 am

all good and valid point, the only difference with community projects is that some of the cool add on like visual assist, do no recognize there free license. and I can't use VS without it.

is no a problem really it do have VS 2015 update 3 so I can verify there code is better, so far I have not seem any difference, but I am sure they are.
My guess is that they have no done much optimization with code the use intrinsic or high level optimization, so far it seem they focus on porting what he had already which is a bunch of cool peephole heuristics, but heuristic can take the compile only so long.
I like how the discovered that one of the thing VS never did right was conditional moves.
anything other that a = b ? 1 : 2
visual studio failed to reduce to a conditional move when that instruction has been in he CPU for 30 year now.

There reason for that difficulty is quite simple, a conditional move is an instruction the break one of the two or tree assignment instruction. which is that not function can have side effect.
this mean that no instruction can change the argument an the result can no be ambiguous.
this is why many compiler do no use some of the cool CPU intrusions and the have to be use via intrinsic.
Now they do realize that with SSA the phy instruction do allow for sophisticated conditional move,
but it seem they still have trouble with it.

There are really deep and sophisticated optimizations that can be use for parallelization, aliasing, vectorizations, and so on.
there are method like: dominator, dominator frontiers, global value number, conditional propagation an, strip mining and so on that can really, really simply code to a form that no sophisticated can even dream to write. there is no way a programmer can math the optimization that a good SSA code generator can do.
Visual studio still uses really arcane code generator like push registers of the stack before function call, very weak on memory aliasing, so loop has to recalculate the address every time, no loop unroling, no auto vectorization and goes on an on.
Visual studio code generator is so weak that you can actually ready and see where the weaknesses are. yo can't do that with code generated by Clang, Gcc, or even intel compiler. they all use SSA for years.

so maybe is all good after the sort out the bugs.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Introducing Newton Scripting language

Postby JoeJ » Sun Sep 24, 2017 8:58 am

Julio Jerez wrote:Clang, Gcc, or even intel compiler


Would it be practical to use those compilers instead for Windows and (if possible) with Visual Studio?
What would be the limitations - hard to use static libs or something?
User avatar
JoeJ
 
Posts: 1453
Joined: Tue Dec 21, 2010 6:18 pm

Re: Introducing Newton Scripting language

Postby Julio Jerez » Sun Sep 24, 2017 9:26 am

Apparently VS 2017 and 2015 update 3 allows to use other compiler with VS,
but you know that this sounds to good to be true, Microsoft is not going to ever admit that their was the inferior compiler, so what do the do? they do what corporations paid their worker to do, make their produce better by making the competitors bad.
https://blogs.msdn.microsoft.com/vcblog ... -update-1/
To make it easier to develop cross-platform code that works well for both Windows and other platforms, we’ve released an additional compiler toolset for Visual Studio called Clang with Microsoft CodeGen. This compiler uses the open-source Clang parser for C and C++, along with the code generator and optimizer from the Visual C++ compiler.


basically they are using the front end of those compiler to generate intermediate CIL code, then reading that in the visual intrusion intermediate code and producing the optimization with the visual studio optimizer.
The result of this is that no matter what compile front end you use in visual studio, no other compiler will generate faster binary than visual studio front end.

That might be why VS was forced to update their code generator.
They know that if they cannot make so obvious that other compiler code generation was such poor quality as vs studio is, people will compare to the stand along tools and they will make reports, so the has to bring VS up to speed with the others.

That does not solve the problems that I see, the problem that I see is that VS is later to the party, and they come now as of the are the authority in SSA technology, when any one writing a compiler can generate code better than VS, even Luajit beats Visual studio.
The only thing good about visual studio is the editor, nothing else.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Introducing Newton Scripting language

Postby Julio Jerez » Thu Oct 05, 2017 3:17 pm

here is a comparison between visual studion 2015 x64 with all optization on of tshi funtions
Code: Select all
int fact(int n)
{
   if (n <= 1)
      return 1;
   else
      return n * fact(n - 1);
}

; Line 7
$LN6:
   push   rbx
   sub   rsp, 32               ; 00000020H
   mov   ebx, ecx
   cmp   ecx, 1
   jg   SHORT $LN2@fact
   mov   eax, 1
   add   rsp, 32               ; 00000020H
   pop   rbx
   ret   0
$LN2@fact:
   dec   ecx
   call   ?fact@@YAHH@Z            ; fact
   imul   eax, ebx
   add   rsp, 32               ; 00000020H
   pop   rbx
   ret   0


her eis what newton optimizing c0mpler does


Code: Select all
    function fact (n)
      if n <= 1 then
        return 1
      else
        return n * fact(n-1)
      end
    end

function luaType fact (luaType n)
label_1:
   push int r4
   argument luaType r0
   luaType r4 = luaType r0
   luaType r0 = luaType r4 <= constInt 1
   if (luaType r0 != constInt 0) goto label_3 else goto label_2
label_2:
   luaType r0 = constInt 1
   goto label_0
label_3:
   luaType r0 = luaType r4 - constInt 1
   luaType r0 = call fact (luaType r0)
   luaType r0 = luaType r4 * luaType r0
label_0:
   pop int r4
   ret luaType r0


as you can see the newton script still generate better assembly and is no even using advanced optimization transformations.
This is because MS still rely heavily on peephole passes while everybody else focus on general transform passes.
It will take MS abut 4 to 5 years VS 2020 or something to get up the level of other compilers. so I do no put my hope high.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Introducing Newton Scripting language

Postby Julio Jerez » Mon Oct 09, 2017 3:36 pm

here is another example of how poor in the VS2015 code generator, this is a trivial fibonacii function
Code: Select all
int fibonacciIterative(int n)
{
   int a = 0;
   int b = 1;
   for (int i = 1; i < n; i++) {
      int c = a + b;
      a = b;
      b = c;
   }
   return a;
}


visual studios with all it tricks still nee to use 5 register, even when ether code transform detect that the iterator is in eh inner loop and do no the can replace by a def instruction saving one register
their assemble uses five register eax, ecx, edx, r8 and r9

Code: Select all
?fibonacciIterative@@YAHH@Z PROC         ; fibonacciIterative, COMDAT
   xor   edx, edx
   mov   r8d, 1
   cmp   ecx, r8d
   jle   SHORT $LN10@fibonacciI
   lea   r9d, DWORD PTR [rcx-1]
$LL4@fibonacciI:
   lea   ecx, DWORD PTR [r8+rdx]
   mov   edx, r8d
   mov   r8d, ecx
   sub   r9, 1
   jne   SHORT $LL4@fibonacciI
$LN10@fibonacciI:
   mov   eax, edx
   ret   0


here is the code generating by the newton optimizer, it use also for register, by that because I still do no have the code transform pass that will replace the iterator test.

Code: Select all
function luaType fibonacciIterative (luaType n)
label_1:
   argument luaType r0
   luaType r1 = luaType r0
   int r0 = constInt 0
   int r3 = constInt 1
   int r4 = constInt 1
label_2:
   if (int r4 >= luaType r1) goto label_0 else goto label_3
label_3:
   luaType r2 = luaType r0 + luaType r3
   int r4 = int r4 + constInt 1
   int r0 = luaType r3
   int r3 = luaType r2
   goto label_2
label_0:
   ret luaType r0


it is rather embarrassing that VS 2015 is such simple code is producing worse code that a simple script code generation that still do no have loop optimization and strength reductions. once that added the newton strict will be far better doe that visual studio 2015 can generate, and that my
disappointment with the corporations that has take ever body for fool year after year after years.
Visual studio has not improved in more than 20 years yet MS keeps telling us that it has.

for fun later I will add the loop transformation and you will see that the newton script is in fact better.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Introducing Newton Scripting language

Postby Schmackbolzen » Tue Oct 10, 2017 5:36 am

I think your information is outdated. Microsoft does use SSA now. You can see it e.g. in their newest slides: https://msdnshared.blob.core.windows.ne ... _share.pdf slide 12. Keep in mind that 15.5 is not out yet (currently vs2017 5.4), so we will have to wait for the promised numbers.

Also there is a nice blog entry with the changes for vs 2015 update 3: https://blogs.msdn.microsoft.com/vcblog ... optimizer/ . As far as I remember that's where they started using SSA.

So it will be interesting to see where they are heading.

As for your example: It would be helpful to see how gcc and llvm handle the code. Then one can judge what is currently possible and how bad the MS compiler really is.
Schmackbolzen
 
Posts: 26
Joined: Mon Feb 16, 2015 5:37 pm

Re: Introducing Newton Scripting language

Postby Julio Jerez » Tue Oct 10, 2017 8:59 am

no sure about version, but this the version that I have
Microsoft Visual Studio Professional 2015
Version 14.0.25431.01 Update 3
Microsoft .NET Framework
Version 4.7.02046


The comment I am baking as base of what they say on that Blog, all the say there is *, and will not get studio anywhere near the code generation quality that other compiler like intel, gcc, clang and the old wacon were generation year, and year ago.

if you read the blog you will see that all they are doing is porting their bag of heuristic optimization to the new method. they are not using the more sophisticated optimization technique that are offered by SSA.

you can see that in the code in the intrusion that use the Lea instruction to perform adds, rather than using add r, r
this is the only thing that keep visual studio competitive.
for example but use lea instead of add the can get another cpu addressing unit to do the operation while the arithmetic unit does some other. the problem is that this trick can only get eth compile so far, and many other compiler are implementation then as well.

to put it simply if I, with few passes, can generate code that use fewer registers, and better IR that what the best visual studio can generate, I do not put my hopes high.

I will have to see some real progress other that those peepwhole code transformation base of pattern matching.

I will add a couple of optimization plus some pattern matching and I bet you can generate code that is form 50 to double what visual studio can.

would it be funny that a and interpreter language can be competitive with a native compiler, oh wait a minute, that's why people keep comparing Java and csharp to visual studio.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Introducing Newton Scripting language

Postby Julio Jerez » Tue Oct 10, 2017 2:20 pm

notice that the criticism I am making is very bias.
I am only comparing the optimization passes that I have against, no way I can produce general code that is better that Microsoft since the have some many years ahead.
my criticism is about on the lied that Microsoft has said about the visual studio when the claim that the newer version can generate better binary, when in fact they has no added any of the global optimization like vale numbering, dominance frontiers, etc, instead what the added were some local optimization like check if a move can be replaced with a conditional move and stuff like that.
stuff that can potential made the overall code even slower.

Microsoft code generator is specially mediocre when using SSE intrinsic. The code is pretty much a on for one translation, with very little optimization.
Its not wonder that lot of people say the SSE code some time runs slower that the non SSE part,
and that can't be possible unless the code generator is very does not a good job. so what you gain from vectorization, you lose in bad optimization.

has you ever wonder how it is that after 30 years Visual Studio still can't do trivial optimization
loop unrolling or auto vectorization when every competitor does. at least in some limited ways.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Introducing Newton Scripting language

Postby zak » Wed Oct 11, 2017 6:20 am

Does this mean that Windows or Office may be faster if compiled with a more efficient compiler, or does Microsoft compile Windows with a different compiler than VC?
zak
 
Posts: 87
Joined: Mon Dec 06, 2004 9:30 am

Re: Introducing Newton Scripting language

Postby Julio Jerez » Wed Oct 11, 2017 2:32 pm

I suppose the use their own compiler. It is not lie that compiler is garbage.
It is the deceiving tactic and the lies the have kept for so many tears.

I has been delving with compiler optimization and parsing cine the early 90.'s
back then Single static assignment, flow graph, and nominator analysis was kind of a secret.

the only decent book was the Dragon of compiler, which for today standards is quite obsoleted.
we use sync tact trees, and brute force logic equations for aliveness, used defined, reaching definitions, dead code, and so on.
today there compiler optimization has advanced a lot, and those method are only taught as fundamentals but Microsoft kept using them and lien.
if is was not for LLVM and how competive all other compilers are, I bet you they would simple keep going with the obsoleted code generator.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Introducing Newton Scripting language

Postby Julio Jerez » Tue Nov 07, 2017 9:54 am

here si a real case of why GCC and Clam are far better compile that Visual studio all version.

This is a loop that is piece of code about 10 time slower in VS than it is in GCC when use in a look

Code: Select all
   x = x > high ? x : high;
   x = x < low ? x : low;


visual studion 2.15 x64 update 3 produces

Code: Select all
00007FF7187350DB  comiss      xmm0,xmm1 
00007FF7187350DE  ja          dgDanzigSolver::Solve+323h (07FF7187350E3h) 
00007FF7187350E0  movaps      xmm0,xmm1 
            x = x < low ? x : low;
00007FF7187350E3  comiss      xmm0,xmm3 
00007FF7187350E6  jb          dgDanzigSolver::Solve+32Bh (07FF7187350EBh) 
00007FF7187350E8  movaps      xmm0,xmm3 


any version of clang or gcc generates
Code: Select all
maxss   %xmm0, %xmm1
minss   %xmm1, %xmm2
movass  %xmm2, %xmm0



the reason why vs studio is so slow is that the code breaks branch prediction, so each time
the code do on loop if the prediction is wrong the code flushed the pipe, and the is almost guarantee to happen in each loop so the code reduces to one instruction per cycle or less while clang and GCC keep the pipe loaded with all the decode code.

using intrinsic doe not help because the make visual studios generate much less quality code.
That why I am not too exited about this move of VS studio to SSA, they are no really doing the high level optimization they are just porting the crappy peehole bag of trick that are no doing the job with moderm cpus.

when using intrinsic then visual studio generates a really repugnant code

Code: Select all
         union data {
            dgFloat32 m_single;
            __m128 m_sse;
         };
         data xxx;
         xxx.m_sse = _mm_max_ss (_mm_min_ss (*(__m128*) &x, *(__m128*)&low), *(__m128*)&high);


the output is this

Code: Select all
            x = dgClampFloat (x, low, high);
00007FF758674E6B  movss       dword ptr [rsp+10h],xmm1 
00007FF758674E71  movss       dword ptr [rsp+20h],xmm0 
00007FF758674E77  movss       xmm0,dword ptr [rax+rbx] 
00007FF758674EA3  minss       xmm1,dword ptr [rsp+10h] 
00007FF758674EA9  maxss       xmm1,dword ptr [rsp+20h] 


is actually move the values to memory, when it already had the in register, the doe sthe comaprison form memory, I am afraid Visual studio is not even close to any modern compiler.


I mean to give an idea of how horrendous visual studio is when using intrinsic, look at this code
Code: Select all
            dgScalar x ((r + row[j] * m_x0[j]) * m_invDiag[j]);
// here after calculation x In register xmm0, it save it to a memory location
00D44A86  movss       dword ptr [x],xmm0 
            
            //if (x > high) {
            //   x = high;
            //} else if (x < low) {
            //   x = low;
            //} else {
            //   r += m_r0[j];
            //   accelNorm1 += r * r;
            //}

            x = x.GetMin(low).GetMax(high);
//here it imediallly load the value form memory, committing perhaps the worse cache
// offence read after right that cost hundreds of cycles. and id does the same for viable low and high
00D44A8B  movaps      xmm0,xmmword ptr [x] 
00D44A8F  minss       xmm0,dword ptr [low] 
00D44A94  maxss       xmm0,dword ptr [high] 
            //x = x > high ? x : high;
            //x = x < low ? x : low;
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Introducing Newton Scripting language

Postby JernejL » Wed Nov 08, 2017 3:36 am

that looks pretty crappy, i guess we could also expect a performance boost if compiling newton with gcc - compared to gcc?
Help improving the Newton Game Dynamics WIKI
User avatar
JernejL
 
Posts: 1578
Joined: Mon Dec 06, 2004 2:00 pm
Location: Slovenia

Re: Introducing Newton Scripting language

Postby Schmackbolzen » Wed Nov 08, 2017 7:30 am

I agree that this is weird. I tested with VS2017 15.4 and it behaves the same. But if you use std::max and std::min it chooses the right instructions. Maybe they had other priorities. Lets see how well 15.5 will do. The preview is already out.

Have you ever tested with newton how well gcc with mingw-w64 does against the visual studio build on windows? Is there a huge performance benefit? I only could find an article which states that threading works better with vs2017 so they stayed with it.
Schmackbolzen
 
Posts: 26
Joined: Mon Feb 16, 2015 5:37 pm

Re: Introducing Newton Scripting language

Postby Julio Jerez » Wed Nov 08, 2017 11:35 am

I agree that this is weird. I tested with VS2017 15.4 and it behaves the same. But if you use std::max and std::min

probably so, this is what I said about all the peephole nonsense that Microsoft uses in their compiler.
My guess is that std::max and std::min in recognized by the front end and it issue intemidiate code that is already predicated is such way that is generates only one basic block instead of two and a phi functions. It is all BS.
They are use the right method but that are using it to port the old syntax tree and pattern matching methods and they have to use more for flow graphs that pattern patching in order to get global optimization. Basically Visual studio is only good optimizing basic block.


no I have not tested newton wih GCC is a long time.
I know that last time I test on Linux and OSX using Clang it was far faster than visual studio.

the assembly part on Visual studio is code from newton, the Clang assembly was from a different project that integrate Clang to visual studio. but I can't compile newton since I do not have license to create a project.
what I did paste was that I pasted a snipe of the code and collect the assembly

In general any compile should be able to predicate any instruction of the form,
Code: Select all
x = x > a ? b : c;


but visual studio despite what they claim, I have never seen it doing it unless when b and c are constant. There is a lot of exaggeration in the ms blog about visual studio code generation.

I have all version of visual studio professional all the way donw to VS 2002
and till these day I have not seen a bit of sustatial difference between 2015 and 2001,

They cliam VS 2017 will supprt diffrent compilers, in partiucaul clang, but read that carefully.
teh are no really suprting clang optimizer, they are taking the front end and runing the intemidiate code trught vusial stidion optimizer,

so in essence that are going to make visual studion faster by making Clang slower.
to see real difference you will have to use somthing like Mingw or use a real plugging that integrate the external tool like Intel compiler.

I will probably purchase Visual studio 2017 next month but I am bracing myself for a boat load of bug just like they said about VS2005 and it took 11 years to fix the bugs.
basically visual studio 2015 is a patch of visual studio 2005 with lot of bug fixes.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Introducing Newton Scripting language

Postby Schmackbolzen » Mon Dec 11, 2017 12:47 pm

Edited: Made a mistake, sorry!
The newest version (15.5.1) does still not recognize it correctly.

I only can say that at least the IDE is since VS2013 shaping up to be really good and for me it looks like VS2017 is getting even better. As for the compiler, benchmarks will tell. We will see whether they can beat gcc or clang someday. Also I think as long as you don't create large commercial projects you can just use the community edition for free.
Regarding the VS clang support: Yeah I read that when it was announced and found it also weird. It's not a real support of the compiler.
Last edited by Schmackbolzen on Mon Dec 11, 2017 3:26 pm, edited 1 time in total.
Schmackbolzen
 
Posts: 26
Joined: Mon Feb 16, 2015 5:37 pm

PreviousNext

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 24 guests

cron