Software Development

I've been trying to solve this problem for a very long time now. I finally found the solution and this is one of those times where once you have the answer, you feel pretty stupid. That's a good thing... sorta. It means the answer was extremely simple. On the flip side, it means you missed something obvious.

Ok, here's the problem at hand. Say you have X random points on the circumference of a circle. What I want to do is take X evenly distributed points on the same circumference of the circle, but make sure that the total distance between each of the new points and old points is at a minimum.

Another way to state this is by how much do I need to rotate the evenly spaced points so that the total angular difference between each point and its respective original point is the least possible.

The main purpose was to create evenly spaced points where I move the original points the least possible. I tried all sorts of things. I tried averaging the angles, averaging the (x,y) coordinates of the points, etc. None of them worked. Some looked like they gave close results. To test my answers, I ran an algorithm that basically checked 1000 different angles and picked the one with the least distance.

So what was the answer? Ends up being easy as pie. But a little background on the setup.

1. First, we draw our X points.
2. Then we draw another X points that are evenly spaced starting at angle 0. So divide 360 by X and that's the angle that each of these points will be separated by.
3. Calculate the difference in angle between each pair of points (ie. between point 1 in the original list and point 1 in the evenly spaced list, same for point 2, etc.). Don't adjust for anything. Keep the difference negative if it ends up being negative.
4. Sort the list of differences.

Step #4 is the critical point and is where the solution comes from. In order to understand this, there is a little trick that explains why this solution works. Note that by sorting the points by difference, they are no longer in the original order that they appeared. This is why it wasn't intuitive. But now that I HAVE thought of it, it's so simple I feel stupid.

Suppose you have four points that have negative differences and four points that have positive differences. Now suppose you move the evenly distanced points counterclockwise by 10 degrees. What will happen to the total angular difference?

The answer is NOTHING, except in ONE SPECIAL CASE.

Why nothing? Because in 4 pairs of points, those points will get closer to each other (the points in the pairs that is), while in the other 4 pairs, they will get further away from each other thus canceling each other out.

Here's a simple example. Suppose pair A has a difference of -30 degrees and pair B has a difference of +40 degrees. Then if we move the evenly spaced points by 10 degrees, we now have differences of -20 and +50 degrees. The total difference is still 70 degrees in both cases. Nothing has changed.

But there is ONE case where this is not true. It's where there are more points on one side than the other. Where there are more pairs with negative differences than positive or vice versa. (Also, if there is a negative difference that is less than 10 degrees. That would flip it to the other side and cause the same scenario just described.)

So if we have 2 point pairs that have negative difference and 1 point pair that has positive difference, then moving the evenly spaced points by 10 degrees will mean that TWO point pairs will get closer to each other while only one will get further apart thus causing a decrease in total difference.

A diff = -40 degrees
B diff = -20 degrees
C diff = +50 degrees

Total difference = 40+20+50 = 110 degrees.

Now we move the evenly spaced points clockwise by 10 degrees.

A diff = -30 degrees
B diff = -10 degrees
C diff = +60 degrees

Total difference = 30+10+60 = 100 degrees.

We've now reduced the total angular difference by 10 degrees.

So the key is to rotate the evenly spaced points until there are as many negative differences as there are positive differences and that's easy to do.

Once our differences are sorted, all you do is take the center difference in the sorted list and that's your angular offset for the evenly spaced points. If there are an even number of points, then you take the two center differences and average them and that's your offset.

So that's it. Just sort the angular differences of each pair of points and take the center one. That's your rotational offset.

So simple it hurts.

Here's a picture of what I'm doing. The inside points are the random points. The outside points are the evenly spaced points. The green dot near the center is the average of all the (x,y) coordinates of all the random points. Thought that might be a clue to what direction to rotate, but ended up being a red herring. That angle is represented by the blue line. The pink line represents the above algorithm and you'll see that the back end always ends up being directly between the first and last point. The gray points were calculated using the 1000 offsets.

[click on image for larger version]


edit: Wanted to add that this algorithm works for linear points as well, not just angular values.

I just realized something from responding to new comments on an old blog entry. Neo is the contradiction program. He is the element that disproves the notion of having an Oracle. Now, I know she was called the Oracle and all. But I thought it was just a clever plot device. In this light, it means that the Matrix movie was not about overcoming being controlled, but about being able to predict our own future.

From Wikipedia:

Given a description of a computer program, decide whether the program finishes running or continues to run forever. This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.

The halting state isn't what's important. The decision problem can be asked about ANY behaviour. In the Matrix, everyone can be thought of a program. This was a central theme and the scene where Morpheus shows Neo what the Matrix is demonstrates quite clearly that we are people who take in inputs and act according to those impulses.

The entire Matrix movie is about showing how the Halting Problem Proof is flawed. Or rather, what it really means.

There was a point in the movie that always stuck with me. It was the scene where Neo goes in to talk to the Oracle and she says, "Don't worry about the vase." and then Neo knocks it over. The Oracle's response was fantastic. She says,

Ohh, what's really going to bake your noodle later on is, would you still have broken it if I hadn't said anything?

And in one simple sentence, the Wachowski Brothers have completely blown apart the halting problem proof.

The Oracle is saying right then and there that no matter what I tell you, I know your future and can control it. The Halting Problem OTOH forces the Oracle to tell Neo exactly what she thinks he will do causing a contradiction.

If she tells Neo that he IS the one, then he will somehow mess it up. Maybe he'll carry too high a burden and not be able to live up to it. Whatever the case, the Oracle knows that telling him the truth will only cause him to go in the opposite direction. Classic case of the "contradiction" program. So she tells him a lie. That he is NOT the one. He will then do the opposite and will find that he is indeed the one. It's almost as if being the ONE is about determination, not of being chosen. It's a whole new level of depth to the Matrix that I never thought about before.

It all culminated with the ultimate decision problem.

In the one hand you'll have Morpheus' life and in the other hand you'll have your own.

Basically, the Oracle turned the tables on Neo. The entire point of the deceiver program used in the Halting Problem Proof is to make no decisions and wait for the Oracle to do it. The Matrix movie addressed this as well.

Oracle: Sorry, kid. You got the gift, but it looks like you're waiting for something.
Neo: What?
Oracle: Your next life, maybe. Who knows? That's the way these things go.

So instead, she forced Neo to make a decision. Without a decision, there is no Oracle. There is no future.

What's really baking my noodle though is that the Oracle actually told Neo the truth about being the ONE. Forget if he always was the one or became the one. The point is that the Oracle knew that he would be the one. Yet she said no to Neo. How can that be the truth? Well, it's about interpretations. She knew that the "no" she told Neo meant "yes" to her. She also knew that as long as Neo doesn't make his own decision, she has nothing to go on because an Oracle cannot make decisions for others. They can only report it. He's "waiting" on something, on the Oracle or others to make decisions for him. That's the entire point of the theme behind the Matrix movie. It's also the biggest flaw in the Halting Problem Proof. What's funny is that she actually tells Neo what he's waiting for. His next life when he gets killed at the end.

Suppose you altered the Halting Problem in such a way that you can keep an internal translation table as to what the output from the Oracle really means. All of a sudden, the Halting Problem Proof falls apart.

Over the years, I've gotten a lot of complaints that I don't understand the Halting Problem. People have tried to convince me of this or that. I want to state here and now that I'm in agreement with the experts in the field on this. And they agree with me. Everything about the Halting Problem is about interpretation and definitions. It is NOT about computability. It does not mean you cannot predict how a program will behave. At its narrowest interpretation, it means that you cannot always tell something to a program as to how it will behave using the same domain as what that program understands. IOW, if you tell it that it will go left, then you cannot guarantee that it won't go right. But nothing stops you from knowing how it will behave. You can tell it it will go left because you KNOW that it will go right. You've computed its behaviour. You know it. So it's not about computability. It's about what you can tell the program itself. And this should explain why the Oracle told Neo the opposite.

To recap, the vase scene is the Oracle making a decision FOR Neo. This is the classic Halting Problem Proof, but in reverse. It's where the Oracle makes the decision and then the input program acts on it. What I like is that the indeterminate nature of the Halting Problem in the Halting Problem Proof happens regardless if there is a contradiction or not. In this fine example, Neo's action was not of his own. The Oracle had to make something up. If she says something, Neo knocks over the vase. If she says nothing, nothing happens. It's still indeterminate, because none of this is based on Neo's actions. It's all based on the Oracle initiating the chain of events. And the Halting Problem is based on this. The Wachowski Brothers seem to be shouting this fact to the viewers that understand it.

And finally, the Oracle tells Neo that he is not the one so that he may be the one because she understands that he is the deceiver program. He is the contradiction. It was apparent right from the beginning when Agent Smith captures Neo and Neo does the opposite of everything Smith wants him to do. In fact, he's reluctant to do anything that anyone tells him. NO... WAY! NO... WAY! His almost walking out of the car at the beginning. His refusal to go with the people that knocked on his door until his saw the white rabbit. The Oracle telling him that she'd ask him to sit down, but that he isn't going to anyways. The "No, you're other left" scene. His refusal to listen to Tank telling him that they have to pull the plug on Morpheus. Did the Oracle know about this? Almost certainly.

Some may think that I'm reading too much into this. Perhaps I am. But pieces fit so clearly that I'm incredulous to think that it was mere chance that this message was put into the movie. Messages about fighting on and surviving and control, sure. But the way it was pieced together is no coincidence. Even the spoon bending. It was a metaphor for predicting the future. There is no spoon. Some say this means that the spoon doesn't actually exist because it's in the Matrix. In some ways, this is true. But what it's really about is that everything in the Matrix is a reflection of yourself. It's also a commentary on the Oracle. That things won't happen unless YOU make the decision. No one else will make the decision for you.

She told you exactly what you needed to hear, that's all.

This is probably my favourite line. It debunks what most people think the Halting Problem is about. When you take into account the above quote, it all falls apart. Everything ends up being about what you do with the information you are given. Is it true? Is it false? Does that affect either way if others can determine your actions?

There have been quite a few articles written about Knuth's famous quote warning against premature optimizations, both for and against. In this article, I will not only argue that Knuth was 97% wrong and 3% right, but also that most people who agree with Knuth tend to be 100% wrong. I will also be mentioning different places and strategies that can be done at a very high level to get acceptable performance out of your application. Note that performance isn't something that can be an afterthought. If your application isn't responsive, users won't be inclined to continue using it. If they have to wait an eternity for an operation to complete that they believe should be relatively quick, they will have a negative opinion of not only the software, but of the people responsible for writing it, and correctly so. In today's world of multicores and distributed computing, it's all too easy to write code that unacceptably lacks performance.

Knuth's quote is as follows:

There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance a considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3 %. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified.

So why is this 97% wrong and 3% right?

Read more...

The other day, I was cleaning out some old boxes that I had stored away. In one of them were some computer books, games and magazines. Found same old Amiga games like Secret of Monkey Island and Monkey Island 2 that I had bought at an auction (they were new at the time). Still had all the documentation in it. I also found an old Game Developer magazine from May 1998. Guess what the programming tutorial was? Building an Inline Performance Monitoring System. IOW, how to manually profile your assembly code.

It starts,

Techniques used by today's microprocessors to achieve unprecedented performance have also resulted in unprecedented complexity in the way that assembly routines are optimized. Minimizing the number of instruction execution cycles no longer guarantees the fastest solution. As a developer, you have to consider additional factors, such as cache and translation lookaside buffer (TLB) states, as well as the state of pipelines and execution units. You also have to account for the architectural aspects of the processor, such as support for speculative instruction execution, reordering, and retirement. The alignment of code and data can also make a huge difference.

Aside from multicore, the above paragraph could be written today. It even goes on to say that most games are written in C/C++, but that sometimes you need to go lower and profile your code.

That was 13 years ago. Now consider 13 years before 1998. Could you write the same thing in 1985? Look here if you want to know what was going in 1985 computer-wise. It was the year that Nintendo would take over the console market from the likes of Coleco, Intellivision and Atari after the crash of 1983. Commodore would come out with the Amiga and the C64 was king in the personal computer department until its demise around 1992.

It's 26 years later and you'd think that the days of assembly were over. Remember all the hype about RISC? Please don't misunderstand. RISC has had a profound impact on processor design. But I remember in the early 90's a total PR dominance of the RISC methodology. You were a heretic if you said anything even remotely against it. Everyone was predicting the demise of all current chips that used CISC. For a while, some of these things seemed to come true. The M68K series was eventually abandoned. Apple switched to the PowerPC. But the switch to RISC processors that could be seen at the assembly level were few and far between when it came to personal computers.

What happened instead was that the Intel processors in the PC became even more popular with the famous "Intel Inside" campaign. The 486 was produced from 1989 to 2006. It's the processor that brought us games like Doom and the numerous derivatives. Not only that, but only about 6 instructions were added to the 486 from the 386. Adding CISC instructions was out of favour. Everyone thought that the existing instructions would become faster and that more complicated CISC instructions would become obsolete. Eventually, such a thing did happen with the Pentium. At least when it came to the underlying architecture (not at the assembly level). It wasn't until the advent of MMX that a substantial amount of new instructions were introduced.

So we have the transition from CISC instructions that take X cycles before the next instruction can execute. The we have the transition to superscalar and pipelined architecture where multiple instructions can be executed at once as well as splitting up each CISC instruction into smaller execution units that can be pipelined. During this transition, almost no new instructions were introduced on the Intel processors used in PC's. And like I said earlier, the M68K was being phased out and the PowerPC was introduced.

What happened next was a complete reversal. MMX, SSE and SSE2 are each completely new instruction sets that don't work on the same registers. Yes, the instructions all do similar things, but all on different sets of registers. MMX operated on 64bits of the floating point registers, but did vector operations on integers (operated on multiple integers at once). SSE did floating point vector operations on a new set of 128bit registers. Intel decided that MMX wasn't the way to go. It would be better to use integer vector operations on the SSE registers which are twice as wide. So that's where SSE2 comes into the picture. SSE2 is essentially MMX on the SSE registers (with other additional instructions added in). Today, there are new AVX, FMA3 and FMA4 instructions sets either in the planning stage or in development.

And these instructions are getting more complex at each new release. We can have instructions that can do CRC calculations. With x64, the general purpose registers are twice as wide and twice as numerous. SSE registers have also double in count. There is talk about expanding them to 256, 512 and even 1024 bits wide in the future.

There is a message to be learned here other than a history lesson. It's that everything old is new again, but with added layers. The first two blocks of code in this article I wrote in October 2008 demonstrates this quite clearly. They both do the same thing. But one is now. The other is from 26 years ago.

Another article I wrote was about video cards and the trend to go back to general computing. I got a lot of heat for that article. Ultimately, any idiot could see what was going to happen. I'm not saying it's not nice to have. But it's not anywhere close to the the silver bullet they were promising.

Back to the Game Developer magazine I found, there is one other article in there that I really wanted to discuss. It's on page 27 titled simply 3D Graphics Hardware. This is a look at what the situation was in 1998. There's a pie chart at the bottom showing the market share of each company.

1. 3Dfx @ 33%
2. Rendition @ 27%
3. NEC (PCX2) @ 27%
4. 3Dlabs (Permedia 2) @ 13%

Funny thing is that nVidia isn't even on the map yet, but just released the RIVA 128 which combines 2D and 3D on the same card. The article mentions this as it has a blurb about each company releasing 3D hardware. They even say, because of what I just paraphrased, "In some ways, this makes nVidia as a more interesting company to watch than 3Dfx, since nVidia is going after both the retail upgrade market, exemplified by PCI-based systems, and the new AGP enabled machines of brand-name PC OEMs such as Gateway 2000." They go on to mention how 3Dfx will have a difficult time transitioning into the combined 2D and 3D market if they were to do so.

Even Game Developer knew at the time that having one card that does both is better than the 3Dfx cards that only did 3D. Today, this seems unimaginable that you needed two cards, one for 2D and one for 3D. But it was indeed so in 1998 and this is what made it possible for 3Dfx to "keep the company ahead of the pack". Everything I've mentioned here is in the article.

I won't go into why 3Dfx went away. But we do know that having one card instead of two is better if it accomplishes the same thing. With this, we can see how the future unfolds by looking at the past.

Stage 1
With processors, we had single instructions at a time.
With 3D, general purpose code was too slow.

Stage 2
Processors implement superscalar and pipelined architectures.
3D hardware use a pipeline and multiple texture units.

Stage 3
Processors implement more vector instructions and multiple cores.
3D hardware uses a multitude of cores to implement general purpose programming.

I'm afraid to say that the verdict is not one of simplicity. RISC did not win out at the assembly level. If there ever was a trend to go that way, it's been hidden away in the hardware. Market insiders have said for a long time that hardware manufacturers are waiting for developers to tell them what they need out of the hardware. That's not exactly true. They're waiting for the market to break a certain way. And it's not breaking because it's a catch-22 this time around.

In the past, it was always about speed. Stage one and two are all about that. Stage 1 can go faster by having more cycles per second. Stage 2 can go faster by pipelining and superscalar architecture where you can operate on more than one instruction at a time. Obviously, the next stage was multicore, but that was never new. It's always been around. What I'm saying is that the hardware companies are putting in what they already knew.

So what's the next stage? Stage 4?

Re-simplification. We can look back at stage 2 for some hints. One would be hard pressed to think that Stage 2 was about making it simple. And they'd be right. While the instruction set did not simplify, the idea of RISC was alive and well. So don't expect any actual simplification for the user this time around either. But expect to see different technologies coalesce into a more consistent overall design.

The first hint of this is software ray tracers. I fully expect that in the future, custom hardware will be handled by general purpose hardware. I also expect that code that is done in 3D or custom hardware today will eventually have to be redone in software. So dust off your software renderers that you wrote back in the 90's. You're gonna need them. No more dumping the tasks to hardware and waiting for the results.

Then you know what Stage 5 will be? The re-introduction of specific hardware that can implement common tasks. Pluggable devices for specific functionality will make a comeback. I expect this to be especially lucrative in the mobile market. Turn your mobile device into anything you want it to be.

I could be wrong of course and I expect that the hardware industry will play its waiting game a little longer. What does this mean for right now? More of the same for a while yet.

The real bottleneck is and always has been sequential code on multiple cores. Will developers change their ways? History answers that quite clearly. NO! Even when developers think they've changed, it's only because old has become new again. What I envision is that the only way for hardware to be able to properly split up parallel code is if the developer states up front what can be split up. Like I said, they won't do that. So I fully expect a trend toward modularization that looks similar what we're doing now, with the exception that you need to specify inter-module dependencies. You know what that is, right? So do I. It's already begun. Those that see it will survive. Those that don't will disappear. Now you know why hardware companies are cautious, lest they become another 3Dfx. This time, it's not up to them. It's up to the developers. At the same time, they could miss it if they act too late.

Stage 4 is nothing more than Stage 2 on top of Stage 3.

Both hardware and software are needed to make it work.

And it's unavoidable.

The new release version 1.2 is at the same location.

http://sourceforge.net/projects/csskiplist/

New features in this release are some new containers. Yeah, there's a astounding amount of containers now. But they're all related. It's basically just selecting what options you want.

- Multi or Unique (Duplicates allowed or not)
- Auto or not (Auto means that you can use random access in logn time)
- Set, Map or Access (Access is where the key is within the element itself).
- Single or Double linked list.

So 2*2*3*2 = 24 containers. As you can see, you just pick the options you want and that decides what container to use. There are also the Indexed type skip lists that operate much like a vector, but in logarithmic time.

The new containers are Access type containers where you can have the key inside the element itself. This means you don't have to create a dummy element as you would normally. Or alternatively, you don't need to duplicate the key thus saving memory.

The Access containers are also available as delegate containers for the composite list where elements can be ordered in many different ways. This is actually the only way to have a key within a delegate container.

struct A
{
  int ID;
  int x,y;
  A(int ID, int x, int y) : ID(ID), x(x), y(y) {}
};

struct GetID
{
  int operator()(const A &a) const {return ID;}
};

AutoAccessSkipList<int,A,GetID> mylist;

void func()
{
  mylist.insert(A(10,10,20));
  mylist.insert(A(20,20,20));
  mylist.insert(A(30,30,50));

  AutoAccessSkipList<int,A,GetID>::iterator i = mylist.find(20);  // Find item with ID = 20.

  mylist[2].x = 50;  // Change element at index 2 (third element).
  mylist(10).y = 50; // Change element with ID = 10.
}

If the key type isn't an unsigned int, you can use mylist[key] as well.

I also changed a few methods. remove() in Indexed type skiplists has been changed to erase_value(). And remove_if() has been changed to erase_if(). destroy_if() has also been added.