Programming Pimpage Thread

[Terr]

For controlling/automating your web-browser, you might want to take a look at Selenium-RC, since you can use it with multiple web-browsers. I used it at a previous job for automated testing. Basically it allows you to use a language-of-choice to remotely control the web browser through the javascript layer.

Regarding custom programming languages, I've played around a bit with ANTLR for that purpose, but couldn't get my old employer to spring for replacing their regex-driven system with something a bit more secure.

[coder0xff]

I know I said I wouldn't post stuff, but I have to. I wrote a vector normalization algorithm using SSE3 instructions. The vectors are 4-D (can be used as 3 or 2-D). I've never written asm using the FPU, let alone MMX or SSE and while I browsed the instruction set I got some ideas. This works by maximizing the data manipulation of each instruction and works on 4 vectors at one time- written in straight assembler with performance in mind. For comparison, I wrote a C++ func, and also did an SSE version that didn't use my 4-at-once technique but still used some of the optimizations that are common in SSE.

Number of CPU instructions to normalize 4 vectors, including memory moves and such (end to end):
C++ Version: 172 operations
SSE version without 4-at-once technique: 120 operations
My 4-at-once technique: 38 operations

Yes - that's right. I normalize a 4-vector in less than ten operations. Now you know why I had to post this.

While I write this post I realize, what good is all this nonsense without some benchmarks. So to test I just had it normalize 1000000 4-vectors. I'm shocked. These were performed on my Q6600 at 3.2Ghz running on a single core:
C++ Version: 9.241 seconds
SSE version w/o 4-at-once technique: 6.375 seconds
My technique: .052 seconds

I can't wait to actually use it on something. (Are you listening Valve?)

Code: Select all

struct vec4
{
   float x, y, z, w;
   //an SSE3 instruction (haddps) provides the means to remove
   //fadd instructions. To fully utilize the SIMD we must do 4
   //vectors at once. The vectors are normalized in place and
   //lengths is filled with the original lengths.
   inline static void Normalize4Vectors
      (vec4* a, vec4* b, vec4* c, vec4* d, vec4* lengths)
   {
      __asm{
         mov eax, a
         movups xmm0, [eax];//copy a to xmm0
         movaps xmm4, xmm0;//save copy of a to xmm4
         mulps xmm0, xmm0;//xmm0 contains the components of a squared

         mov eax, b
         movups xmm1, [eax];//copy b to xmm1
         movaps xmm5, xmm1;//save copy of b to xmm5
         mulps xmm1, xmm1;//xmm1 contains the components of b squared

         haddps xmm0, xmm1;//xmm0.x = a.x^2 + a.y^2, xmm0.y = a.z^2+a.w^2
         ;//xmm0.z = b.x^2 + b.y^2, xmm0.w = b.z^2+b.w^2

         mov eax, c
         movups xmm1, [eax];//copy c to xmm1
         movaps xmm6, xmm1;//save copy of c to xmm6
         mulps xmm1, xmm1;//xmm1 contains the components of c squared

         mov eax, c
         movups xmm2, [eax];//copy d to xmm2
         movaps xmm7, xmm2;//save copy of d to xmm7
         mulps xmm2, xmm2;//xmm3 contains the components of d squared

         haddps xmm1, xmm2;//xmm2.x = c.x^2 + c.y^2, xmm2.y = c.z^2+c.w^2
         ;//xmm2.z = d.x^2 + d.y^2, xmm2.w = d.z^2+d.w^2

         haddps xmm0, xmm1;//we now have xmm0 filled with the 4 lengths squared
         ;//xmm1.x = a.x^2 + a.y^2 + a.z^2 + a.w^2
         ;//etc

         sqrtps xmm1, xmm0;//square root each
         mov eax, result
         movups [eax], xmm1;//output lengths

         pshufd xmm0, xmm1, 0;//xmm1 filled with a's length-shuffle 0,0,0,0
         divps xmm4, xmm0;//xmm4 contains normalized a
         mov eax, a
         movups [eax], xmm4;//output new a

         pshufd xmm0, xmm1, 0x55;//xmm1 filled with a's length-shuffle 1,1,1,1
         divps xmm5, xmm0;//xmm5 contains normalized b
         mov eax, b
         movups [eax], xmm5;//output new b

         pshufd xmm0, xmm1, 0xAA;//xmm1 filled with a's length-shuffle 2,2,2,2
         divps xmm6, xmm0;//xmm6 contains normalized c
         mov eax, c
         movups [eax], xmm6;//output new c

         pshufd xmm0, xmm1, 0xFF;//xmm1 filled with a's length-shuffle 3,3,3,3
         divps xmm7, xmm0;//xmm7 contains normalized d
         mov eax, d
         movups [eax], xmm7;//output new d
      }
   }
};


[Zipfinator]

I have no idea what that block of text is trying to explain... The benchmarks are impressive though, I think...

[coder0xff]

I actually read the benchmarks wrong, but they are still pretty much the same (I increased it by 10x for better accuracy too).

Normalizing a vector is a very important operation in physics and graphics. It involves addition, multiplication, division, and square root. The faster you can do it the better. This assembler (it's a way of writing machine code) I've written is 177 times faster then what C++ has to offer.

Graphics cards IIRC and prolly physics cards have a vector normalization instruction - which makes even my 38 instructions unnecessarily long (on top of that GPUs are massively parallel). CPUs dont have it though - yet. I'm sure it's right around the corner.

[Zipfinator]

Those benchmarks are even more impressive! I'm still not exactly sure what they mean but if you say the faster they are the better then your method seems pretty good. How do you not have a job yet?

[Gary]

Ugh, I am just starting C++ coding for Source, how can you people do this O_o

And you even know assembly Coder? That must be fun to code in.

[Shr3d]

I will hopefully have a basic grasp on C++ by the end of April coder0xff, any professional development sites/resources you can recommend (sorry if this is a bit off topic) for someone with beginner-intermediate knowledge? I have got hold of the coding bible by the Gang of Four if that makes any difference.

[zombie@computer]

cplusplus.com?

[coder0xff]

Well, if you wanna learn C++ I suggest C++ for dummies. That's what I read (years and years ago). But there are newer things you might be interested in like Visual C# or even C++/CLI (what this was written for) which Microsoft Press publishes books for. My favorite book of all time though is Code Complete - though it may not be the most useful thing for beginners.

Assembly was actually the second thing I learned. I starting learning QBasic when I was 10 and tried C++ a few years later but couldn't seem to wrap my head around pointers and classes. So I tried learning assembly and it turned out to be a great way to bring everything I failed to comprehend in C++ neatly together. It is fun to code in, especially when it rewards you (almost every time) with amazing performance. But that's not inherent of assembler - you have to know how to use that proximity to the hardware to squeeze out every bit of speed.

[Shr3d]

cplusplus.com?

I was thinking more something along the lines of a way to explain C++ to someone who's never learned a programming language before (much less an object orientated one). I guess the dummies book is a good start also Currently I'm reading Introduction to Programming with C++ by Y. Daniel Liang.

[Terr]

I have no idea what that block of text is trying to explain... The benchmarks are impressive though, I think...

Normalizing a vector... means taking an given arrow in 3D space, and shortening it to a length of 1 without changing the direction it points in. The block of text is a crazy low-level way of doing the algebra.

[PhoeniX1992]

I have no idea what that block of text is trying to explain... The benchmarks are impressive though, I think...

Normalizing a vector... means taking an given arrow in 3D space, and shortening it to a length of 1 without changing the direction it points in. The block of text is a crazy low-level way of doing the algebra.

Normalizing a vector... Is that like what I learned in physics class? De-constructing a vector into an x and y component on an x and y axis?

Like, if all vectors are lined up on an x and y axis, it's much more easier to calculate the resulting force.

Like (paint ftw)

[Unreal_Me]

Say for example that the diagram you drew has these values:
Fx = 8
Fy = 8
F = 11.3

Normalizing the vector would turn it into
Fx = .71
Fy = .71
Fy = 1

The length of the vector is 1, but the angle remains the same.
And his also does 3D and 4D(howthefuck?) vectors
AFAIK it makes vector arithmetic 9001 times easier

[vcool]

Normalizing a vector is setting it's length to 1. It's still pointing in whatever direction it was pointing at.

[Terr]

Unreal_Me: There are several areas of programming and theory it makes sense to think of vectors in N-dimensions. For example, consider a system monitoring some health metrics while 20 people in a group exercise:

• Heart rate
• Respiration rate
• Difficulty level

Imagine it graphed as a cube, with each axis being one of these things.
Over time, the 3D "point" where a single person is will move to different places in the cube, and between any two times we can describe the transition as a 3D vector.

Now suppose we add another metric, like "Oxygen absorption".

All of a sudden we can't put it on paper or in a computer screen, we've got a 4D plot. But we can still use a 4D vector to describe any movement between two states.

We can re-use that geometric math to describe things like: "Going from time X to Y, we saw three main kinds of person in our study based on how the participants bodies reacted. Some of them started needing a lot more oxygen with a little change in breathing rate, while others just started breathing faster with a raised heartrate", etc.)