Today I started playing as Zerg against Terran on medium difficulty. And I've found a very interesting strategy which the AI doesn't react to well against.
First, send your initial drones to the mineral field, and create up to 10 drones and those will go to the mineral field.
Now, build a second Overlord (send the Overlords somewhere "safe" either the corner of the map or over your hatchery).
Good - build 2 more drones, and send them mining. You want a continuous stream of income!
Your next drones, make them relay somewhere safe, and build a Spawning Pool and an Extractor. The Spawning Pool allows you to get Zerglings, the Extractor you need for Vespene Gas.
Get 3 Drones working on each of your geysers. If you have 2, build 6 Drones, and another Extractor.
By now, the Spawning Pool must be built; build a Queen and upgrade your Hatchery to a Hive. Your income ought to be stable enough by now to forget about resources for a bit (your units should be 13 Drones on minerals, 6 Drones maximum on Vespene gas, and one Queen).
Here's the bad news - all this time spent building up for resources left us a bit vulnerable. Quickly, build some Zerglings (you may want to build them earlier). 2 suffice! These two will venture and explore the map.
While you take in the bad news, build a Lair and an Evolution Chamber. When building units, build 2 Roach and 1 Drone or 1 Roach 1, Drone and 1 Overlord. The Zerglings are useless against Terran, we want Roaches to have a bit of defence, and we want the Zerglings to reveal the Terran base.
As you build units, make your Queen build Creep Tumors all over the place. Preferably towards a choke point. At the choke-point, build Spine Crawlers. Expect to lose your Spine Crawlers. Also - research Burrowing at the Hive.
Quick Recap: By now you should have a Hive, discovered the Terran base, or the location of their army (avoid it if you can). Have a few (3 maybe?) roaches, plenty of defence, and your upgrade to Burrow is being worked on. Ideally, you know where the Terran base is thanks to your Zerglings. We know that the Terran are overpowering us.
Quickly, get the Roaches out of your base in a spot outside of the Terran field of interest (that is - where they most likely won't be...) - ideally near the entrance of their base. Burrow the roaches.
At the base, build (as soon as possible) a Hydralisk Den and build hydralisks.
Expect to be attacked. When the Terrans attack - they will have sent their entire army. Their base is now empty. You have units waiting there...
Attack the base with your units. If you can do enough damage - the Terrans will retreat and your base will be in good shape (minimal damage - except for the loss of the Queen and some Spine Crawlers. If you manage to take out some SCVs, Supply Depots, etc. in the Terran base; they are done for. While they head back to their base you have time to inflict quite a bit of damage.
You can sacrifice your Roaches. By now, you should have plenty of Hydralisks. With the enemy back at their base, bring the Hydralisks to their entrance, and Burrow. Rebuild your minimal defences and try to get an expansion going. With an expansion, the number of Hydralisks built will easily double.
Repeat the tactic of squatting in front of the Terran base and attack when your cheap defences get attacked. Be sure to have a few Hydralisks and Spine Crawlers to keep thing from wanting to stay and get past the cheap defences. Doing a lot of damage to their base also has the same effect!
And now, it's rinse-wash-repeat.
To recap: the overall strategy is to Burrow near the entrance of the base and to go in and destroy when the offence (also acting as defence against medium Terran difficulty) as busy destroying a cheap entrance to your base that can easily be rebuilt. Without stopping, keep on sending reinforcements to your crew waiting to ambush the enemy. Once they leave their base, keep your new units with you as defence. Once they reach your base and start attacking, inflict as much damage as possible.
Happily - this works very well. However, don't expect to win the first time. The AI does make the mistake of leaving its base undefended - but that doesn't mean it is completely stupid. The building must be done as fast as possible. Go too slow and the first wave from the Terrans will destroy your base.
Sunday, September 12, 2010
Is the "New Digg" that bad?
<rant>
Each time a new version of iTunes comes out; people line up to complain about the UI. There's something about change that people fear and don't like.
Now that I've spent a bit more time with the "New Digg" - let me say it isn't that bad. You can still submit links. That erases most of the arguments that I had against it. The crux of Digg is finding new stuff.
For the auto-submission? I think it's a good thing. Normally - if I wanted to submit something I wrote, I'd log into Digg, submit it, and see it remain ranked with 1 Digg (mine). Now, what I do gets auto-submitted, and automatically gets a single Digg (mine, again).
For the enhanced algorithm? Using multiple sources, but weighing the number of Diggs as having more of an effect. Good idea, actually. Ok, sit back and let's see how this works out: you want to find new stuff. Stuff that a lot of people like. Do you want a closed community of Diggers or a bigger community of people who may in the future be lured to Digg? At the end of the day - I don't think this will make much of a difference.
For those quoting http://www.alexa.com/siteinfo/digg.com, let me say that is a considerable dip (in the month of August 2010, pageviews and time on site have nearly halved!). Is this the end of the world? Let's dig deeper. Page views probably went down since articles don't seem change as often. Can't complain there. That would also describe why the time on the site went down. And would explain why the reach has remained somewhat constant. I call the evidence inconclusive that Digg shed most of it's users.
Lastly, for those complaining about not seeing how many Diggs a comment, just click your profile icon.
Yes, Digg did shed some users - there are the emotional bunch that have trouble whenever the iTunes UI changes...
Here's the only downside. I lost my entire history. Either it's in the process of being ported, or lost forever. From reading the comments on Digg, I see things are probably being tweaked.
Like any new machine; Digg will take some time. Play around with it, and you might even find that going forward it's going to be much better. It looks more like a problem with deployment rather than a problem with the system. If they slowly deployed it to certain users rather than the whole - things might have gone more smoothly. A bit more communication, and maybe Reddit wouldn't have flooded the front page (if deployment of the new version took considerable time and people were complaining about real issues at the time - notifying the users might have been better).
But all in all. It's not that bad. And to say this, I forced myself to spend a bit of time to use it (rather than my previous version of this post that was completely inaccurate - a bit of research goes a long way - although let's say I still did no research for the fun of it!)...
Edit1: Mashable has a nicely researched piece at http://mashable.com/2010/09/15/what-digg-must-do-to-survive/
</rant>
For the auto-submission? I think it's a good thing. Normally - if I wanted to submit something I wrote, I'd log into Digg, submit it, and see it remain ranked with 1 Digg (mine). Now, what I do gets auto-submitted, and automatically gets a single Digg (mine, again).
For the enhanced algorithm? Using multiple sources, but weighing the number of Diggs as having more of an effect. Good idea, actually. Ok, sit back and let's see how this works out: you want to find new stuff. Stuff that a lot of people like. Do you want a closed community of Diggers or a bigger community of people who may in the future be lured to Digg? At the end of the day - I don't think this will make much of a difference.
For those quoting http://www.alexa.com/siteinfo/digg.com, let me say that is a considerable dip (in the month of August 2010, pageviews and time on site have nearly halved!). Is this the end of the world? Let's dig deeper. Page views probably went down since articles don't seem change as often. Can't complain there. That would also describe why the time on the site went down. And would explain why the reach has remained somewhat constant. I call the evidence inconclusive that Digg shed most of it's users.
Lastly, for those complaining about not seeing how many Diggs a comment, just click your profile icon.
Yes, Digg did shed some users - there are the emotional bunch that have trouble whenever the iTunes UI changes...
Here's the only downside. I lost my entire history. Either it's in the process of being ported, or lost forever. From reading the comments on Digg, I see things are probably being tweaked.
Like any new machine; Digg will take some time. Play around with it, and you might even find that going forward it's going to be much better. It looks more like a problem with deployment rather than a problem with the system. If they slowly deployed it to certain users rather than the whole - things might have gone more smoothly. A bit more communication, and maybe Reddit wouldn't have flooded the front page (if deployment of the new version took considerable time and people were complaining about real issues at the time - notifying the users might have been better).
But all in all. It's not that bad. And to say this, I forced myself to spend a bit of time to use it (rather than my previous version of this post that was completely inaccurate - a bit of research goes a long way - although let's say I still did no research for the fun of it!)...
Edit1: Mashable has a nicely researched piece at http://mashable.com/2010/09/15/what-digg-must-do-to-survive/
</rant>
Case for Objective-C++
Forget Objective-C. I mean it. For iOS development, the ideal language is Objective-C++.
I expect plenty of pitch-fork bearing purists who tend to align themselves with the crowd of goto is bad, and overloaded operators are bad to not like what I'm about to suggest. But; as with goto and overloaded operators, like certain medicines, too much can be fatal. I believe programmers can make reasonable decisions to the use of these constructs.
With Objective-C 2.0 came properties. These allowed for easy integration with key-value coding; but there's one problem with it - all properties are public. All methods are public as well. I believe this is bad programming style.
Here's a key to my solution; simple and elegant:
Consider how this code nicely takes an an Objective-C object and wraps it in a smart-pointer. Ensuring that objects get retained and released becomes much more trivial - and a lot less typing. No need to define a parameter, synthesize, and double-check that it exists in the dealloc. Why? Objective-C++ automagically calls the destructor for C++ objects.
Using this is quite simple: Auto<NSString*> m_something; creates your string. Assign an auto-release string to it (or use the noRetain method) and off you go forgetting about this object. Assign a new string? The old one gets automatically released. Need to call a method? [m_something() UTF8String]; is a good example.
The good thing? minimal overhead - the compiler should inline out most, if not all, of the Auto object. What you're left with are the retains and releases that you'd have normally put in.
A note of caution: only use this object in places where you'd normally ensure an object gets a retain or release. Do not enthusiastically put it everywhere. Recall: good things in great quantities might not be that good. They can even be fatal!
On the up-side, if you want properties, you'll need to actually write the methods behind to translate from the C++ wrapper. This is good, you'll see, since it makes it harder to make objects publicly accessible, always a good design decision.
Before I wrap up this post; for private methods, I suggest using C static functions in your implementation files. Can't get more private than that!
For protected functions - useful with polymorphism - I'd avoid them. Once a function is declared, it can easily be reflected and used. No matter how hidden/private it is (unfortunately). I believe that this poses interesting software design constraints though.
I expect plenty of pitch-fork bearing purists who tend to align themselves with the crowd of goto is bad, and overloaded operators are bad to not like what I'm about to suggest. But; as with goto and overloaded operators, like certain medicines, too much can be fatal. I believe programmers can make reasonable decisions to the use of these constructs.
With Objective-C 2.0 came properties. These allowed for easy integration with key-value coding; but there's one problem with it - all properties are public. All methods are public as well. I believe this is bad programming style.
Here's a key to my solution; simple and elegant:
template<class T>
class Auto
{
private:
T m_o;
public:
inline T operator=(T in_o)
{
if (in_o) [in_o retain];
if (m_o) [m_o release];
m_o = in_o;
return m_o;
}
inline T noRetain(T in_o)
{
if (m_o) [m_o release];
m_o = in_o;
return m_o;
}
inline T operator()() const
{
return m_o;
}
inline Auto(T in_o = NULL)
: m_o(NULL)
{ (*this) = in_o; }
inline Auto(const TNS<T> &in_cpy)
: m_o(NULL)
{
(*this) = in_cpy();
}
inline ~Auto()
{
if (m_o) [m_o release];
}
};
Consider how this code nicely takes an an Objective-C object and wraps it in a smart-pointer. Ensuring that objects get retained and released becomes much more trivial - and a lot less typing. No need to define a parameter, synthesize, and double-check that it exists in the dealloc. Why? Objective-C++ automagically calls the destructor for C++ objects.
Using this is quite simple: Auto<NSString*> m_something; creates your string. Assign an auto-release string to it (or use the noRetain method) and off you go forgetting about this object. Assign a new string? The old one gets automatically released. Need to call a method? [m_something() UTF8String]; is a good example.
The good thing? minimal overhead - the compiler should inline out most, if not all, of the Auto object. What you're left with are the retains and releases that you'd have normally put in.
A note of caution: only use this object in places where you'd normally ensure an object gets a retain or release. Do not enthusiastically put it everywhere. Recall: good things in great quantities might not be that good. They can even be fatal!
On the up-side, if you want properties, you'll need to actually write the methods behind to translate from the C++ wrapper. This is good, you'll see, since it makes it harder to make objects publicly accessible, always a good design decision.
Before I wrap up this post; for private methods, I suggest using C static functions in your implementation files. Can't get more private than that!
For protected functions - useful with polymorphism - I'd avoid them. Once a function is declared, it can easily be reflected and used. No matter how hidden/private it is (unfortunately). I believe that this poses interesting software design constraints though.
Sunday, August 8, 2010
Parallel Processing Predictions: Part II
Last we left off, I stuck to my theory that applications would remain sequential - and that parallelization would be done implicitly through interaction with the OS. I gave a hint to my thinking by specifying that there is a delay between creation of an object, and it's actual use.
Previous Work First, Amdahl's Law [Wikipedia has a good write-up on it]. You can't go faster than the slowest serial portion of your code. DrDobb's has an article on beating Amdahl's law[DrDobb's Article]. I disagree - speeding up the execution on a single processor still means your are bound by the serial portions of your code.
For your reference - I consider SIMDizing[Intel has a good intro to get the idea] to be parallelizing code; as well as reordering instructions to maximize the use of the underlying execution units[Apple's write-up is a bit dated, but I like it.].
So - you must be laughing. I should explain in this post a miraculous way to make all of today's code parallel. Well, most of today's code parallel -- as long as the OS incorporates these changes.
I will give credit to Intel's Thread Building Blocks and distant relative CILK. I shouldn't forget Grand Central Dispatch - if only for it's ability to do task-scheduling with a view of the entire system load.
Aren't these great solutions? Oh yes. Brilliant. Tackling issues of data locality and efficiently doing work across multiple cores. Essential given the future is parallel.
Then what's the problem? If they optimally express the intentions of the programmer, none what-so-ever. For me, just keeping track of what is running, and can be run is not a "good thing".
Inspiration: When I think of implicit parallel programming, I think OpenGL. Even though drawing requests are done in sequence. For example, you can draw plenty of geometry - but that geometry is just cached in a buffer and drawn when the GPU has time. So while the code is doing whatever logic it needs to do, OpenGL is working in the background getting stuff done. And it's not only the video-card that's running, but part of the API. States need not take effect until they are actually needed.
The other thing I'd like to point out is the intelligence of compilers - more exactly, how much optimizations they can do. I'm not suggesting the Octopiler or something similar.
I'm suggesting devising APIs that are designed from the ground up to do work in parallel. But also increasing the integration of the compiler within the process (I'm sure someone else thought of this, there are brilliant people in CS departments around the world. I'm thinking aloud since I enjoy it. It also helps me coherently determine how my code should evolve.)
To avoid the simplicity that is a graphics API, let's consider another object. Let's say an object that does set manipulations. We have intersections, unions, enumerations, and all the wonderful related dangers to parallelizing these operations. A quick google search will lead to results of people writing codes using atomic operations, and making mistakes using atomic operations. So, in this part I'll document how this API would be presented to the end-user and how it could be implemented.
First, I can feel the temptation to say that all objects are immutable - that all mutations happen over copies. However, that is - how to say this - cheating. Our goal is to not change existing code as much as possible.
The API: The end-user of the API can do whatever they're used to doing with scalar code. It's the API itself that must do the miracles.
The Inner Workings: Finally, the moment of truth, how would it work? Let's assume that we are building on Grand Central Dispatch; with cache coherency methods similar to those of Thread Building Blocks (hybridized - these would do a great team for the next few years).
The general strategy is that the API has a series of sequential tasks. These tasks can run in parallel (even later) until the user actually makes a request for data. This leaves us with a few cases - the major ones are Immutable and Mutable.
Ok, Immutable objects are the easiest. We will add a state to the objects: "Pending". An Immutable object is in a "Pending" state if it hasn't completed initialization. We will also add a sequential list of tasks that can run asynchronously.
The entire API's logic is run on this asynchronous task list. Each task is sequentially numbered by the sequential portion of the API.
The easiest methods are those that return a new object. That might be a list, or something else. As long it's all part of the same API; it doesn't matter. This new object, Immutable or not, is not really an object, but more like an IOU. It holds the ID of the task and is put into a "pending" state. The same is true for existing objects stored within the data structure.
The next easiest method is functions that return basic data types. These could be defined to return a special wrapping object; so they'd behave like their object counter-parts. I'd suggest making the compiler hide these gory details, and use decent heuristics to determine if the overhead of creating an object is worth it.
But back to those returning basic data types. We'd get an ID of a task; but would stall the execution of the sequential code until the data was received.
Wouldn't we always be stalling? Here's the beauty of the solution - we know what work we must do sequentially. We can also do dependency checks. If one operation doesn't depend on another, it can be scheduled to run in parallel. Even; individual tasks could be made to run in parallel (like the intersection of two sets).
Next are the Mutable objects. Surprisingly, these aren't that different. Really.
What I've just done is outline how to parallelize a sequential application by properly engineering the backend libraries. This parallelization is completely transparent to the end-user of the API.
This basic solution might be enough to divorce an application's serial logic from the immensely parallel nature of the underlying computational hardware.
Previous Work First, Amdahl's Law [Wikipedia has a good write-up on it]. You can't go faster than the slowest serial portion of your code. DrDobb's has an article on beating Amdahl's law[DrDobb's Article]. I disagree - speeding up the execution on a single processor still means your are bound by the serial portions of your code.
For your reference - I consider SIMDizing[Intel has a good intro to get the idea] to be parallelizing code; as well as reordering instructions to maximize the use of the underlying execution units[Apple's write-up is a bit dated, but I like it.].
So - you must be laughing. I should explain in this post a miraculous way to make all of today's code parallel. Well, most of today's code parallel -- as long as the OS incorporates these changes.
I will give credit to Intel's Thread Building Blocks and distant relative CILK. I shouldn't forget Grand Central Dispatch - if only for it's ability to do task-scheduling with a view of the entire system load.
Aren't these great solutions? Oh yes. Brilliant. Tackling issues of data locality and efficiently doing work across multiple cores. Essential given the future is parallel.
Then what's the problem? If they optimally express the intentions of the programmer, none what-so-ever. For me, just keeping track of what is running, and can be run is not a "good thing".
Inspiration: When I think of implicit parallel programming, I think OpenGL. Even though drawing requests are done in sequence. For example, you can draw plenty of geometry - but that geometry is just cached in a buffer and drawn when the GPU has time. So while the code is doing whatever logic it needs to do, OpenGL is working in the background getting stuff done. And it's not only the video-card that's running, but part of the API. States need not take effect until they are actually needed.
The other thing I'd like to point out is the intelligence of compilers - more exactly, how much optimizations they can do. I'm not suggesting the Octopiler or something similar.
I'm suggesting devising APIs that are designed from the ground up to do work in parallel. But also increasing the integration of the compiler within the process (I'm sure someone else thought of this, there are brilliant people in CS departments around the world. I'm thinking aloud since I enjoy it. It also helps me coherently determine how my code should evolve.)
To avoid the simplicity that is a graphics API, let's consider another object. Let's say an object that does set manipulations. We have intersections, unions, enumerations, and all the wonderful related dangers to parallelizing these operations. A quick google search will lead to results of people writing codes using atomic operations, and making mistakes using atomic operations. So, in this part I'll document how this API would be presented to the end-user and how it could be implemented.
First, I can feel the temptation to say that all objects are immutable - that all mutations happen over copies. However, that is - how to say this - cheating. Our goal is to not change existing code as much as possible.
The API: The end-user of the API can do whatever they're used to doing with scalar code. It's the API itself that must do the miracles.
The Inner Workings: Finally, the moment of truth, how would it work? Let's assume that we are building on Grand Central Dispatch; with cache coherency methods similar to those of Thread Building Blocks (hybridized - these would do a great team for the next few years).
The general strategy is that the API has a series of sequential tasks. These tasks can run in parallel (even later) until the user actually makes a request for data. This leaves us with a few cases - the major ones are Immutable and Mutable.
Ok, Immutable objects are the easiest. We will add a state to the objects: "Pending". An Immutable object is in a "Pending" state if it hasn't completed initialization. We will also add a sequential list of tasks that can run asynchronously.
The entire API's logic is run on this asynchronous task list. Each task is sequentially numbered by the sequential portion of the API.
The easiest methods are those that return a new object. That might be a list, or something else. As long it's all part of the same API; it doesn't matter. This new object, Immutable or not, is not really an object, but more like an IOU. It holds the ID of the task and is put into a "pending" state. The same is true for existing objects stored within the data structure.
The next easiest method is functions that return basic data types. These could be defined to return a special wrapping object; so they'd behave like their object counter-parts. I'd suggest making the compiler hide these gory details, and use decent heuristics to determine if the overhead of creating an object is worth it.
But back to those returning basic data types. We'd get an ID of a task; but would stall the execution of the sequential code until the data was received.
Wouldn't we always be stalling? Here's the beauty of the solution - we know what work we must do sequentially. We can also do dependency checks. If one operation doesn't depend on another, it can be scheduled to run in parallel. Even; individual tasks could be made to run in parallel (like the intersection of two sets).
Next are the Mutable objects. Surprisingly, these aren't that different. Really.
What I've just done is outline how to parallelize a sequential application by properly engineering the backend libraries. This parallelization is completely transparent to the end-user of the API.
This basic solution might be enough to divorce an application's serial logic from the immensely parallel nature of the underlying computational hardware.
Sunday, August 1, 2010
Parallel Processing Predictions: Part I
I've been thinking of parallel processing as of late. I've coded a task scheduler with a few swappable algorithms in the backend to test performance; seen my programs degrade in performance as the number of cores increase; and literally learn everything the "oops I made a mistake" way.
So, standing upon my pile of errors; I'm going to attempt to predict what will happen (some of it very long term). Some of it we already know - hardware will make a massive shift. Others; well - let's see if I'm right about any in the next decade.
No Change For Most: 99% of applications will remain sequential in nature and never directly deal with threads. This sounds crazy; I know given this massive push towards multi-core - but it's an unshakable conclusion in my mind.
Rather, libraries will be parallel and asynchronous - making "DIY" algorithms an even sillier affair. As a simple example: consider comparing two strings. There is a time since the request to compare the strings is sent, and when the value is actually used. If we use something like Grand Central where the threads are already spawned and just need to be used, then we're talking low-overhead implicit parallelization.
Essentially, libraries will present a sequential interface. User-land code will not need to know about parallelism - but will take advantage of the hardware when the programmer leverages the underlying frameworks.
Right about now, some people probably want to remind me that the GUI runs in the main thread whereas heavy processing is normally put into a secondary thread with mutexes to coordinate the two. I'll recall olde code that actually split up the processing so that the GUI event-pump could run. Even, olde code that would, at explicit times, yield execution to the GUI. Just yield when data is available to update the GUI, much less messy than having locks in obscure places. Normally, for such things, I have one lock that synchronizes events from the GUI on the separate thread with my work thread. The more sequential my code, the easier it is to work with.
Procedural Over Functional: Again, the Haskell fans will most likely disagree. Actually, I'd rather code parallel code in Haskell at times... But; let's not get distracted - I believe procedural code will maintain it's reign. The reason is simplicity. Everyone understands a TO-DO list, a sequence of instructions, manuals, etc. No manual I know asks you to trace to the desired result to get to the start of the solution (sometimes I feel like I'm rigging code to have side-effects to get it to run in functional languages).
Even if languages like Haskell are "better"; the rich and parallel underlying libraries of the system will make the entire thing moot.
Software Diets: Back-end system libraries will overthrow software complexity. That is, the OS will provide so much functionality that an application will simply have to connect the pieces. Some specialization might be needed; but very little.
This availability of features in the OS will change the software landscape. Software that does not properly integrate into the OS (that will have a global strategy for multiprocessing, with libraries optimized for that strategy) will slow down.
Think of it this way: the OS and it's libraries will shift together. And as hardware changes, so will the OS-provided libraries. Software using it's own libraries will need to adapt; but those using the OS-provided libraries won't.
This raises problems for multi-platform toolkits as I figure that certain functionality will be radically different on different OSes, even though they accomplish a similar thing.
Hardware Rollercoaster: See the disconnect between the user-land software and the hardware? Well, that means the underlying hardware can change more drastically. If the OS is the only one that needs to know about the specifics of the hardware and the user-land software just needs to focus on the algorithm; then people shouldn't even notice the insanity that is going on underneath the hood.
This implies that something akin to the LLVM project would be used to compile to a machine-independant level and complete compilation on the final hardware.
More Open-Source: Not the year of Linux; but the year of the open-source libraries. The added complexity of the underlying libraries will mean that they are more costly to develop. I'm not advocating using the spare time of developers to advance a corporations heavy work; but rather problems will be shared among OS vendors. Open-source is just a way to save money by reducing the amount of redundant work among companies.
If I had to wager, I'd say a BSD-style license - so each vendor can advertise having an upper-hand when marketing to consumers.
In the end... We aren't headed towards great doom when it comes to multi-core. Yes, people are panicking now as they realize all the caveats, however we've known for quite a while that 10% of the code is responsible for 90% of the execution time. That 10% of the code, in most cases, should be part of the OS and supporting library.
Final Ramblings: I referred to Apple's technology since I'm more familiar with it. I'm sure Microsoft is doing something similar - and that the .NET runtime might be better suited to the type of parallelism that I'm describing.
Now that I've predicted that nothing much will change for your average programmer; I'm going to do a part 2 - and detail exactly how I see the underlying libraries and hardware shifting. In part 3 - I'll explore how the development environment could change.
These predictions aren't final. As I learn more and read more of the results from the scientific community, my predictions may be refined over time. I won't delete these pages; but admit my mistakes and document how I erred.
One last thing. As a reader, you must have noticed the lack of references in this document. I don't trust texts without references. Neither should you. This part essentially puts forward the theory that user applications will just, in the worst case, need a recompile and keep on running using all the available hardware.
All this despite the move to multicore.
So, standing upon my pile of errors; I'm going to attempt to predict what will happen (some of it very long term). Some of it we already know - hardware will make a massive shift. Others; well - let's see if I'm right about any in the next decade.
No Change For Most: 99% of applications will remain sequential in nature and never directly deal with threads. This sounds crazy; I know given this massive push towards multi-core - but it's an unshakable conclusion in my mind.
Rather, libraries will be parallel and asynchronous - making "DIY" algorithms an even sillier affair. As a simple example: consider comparing two strings. There is a time since the request to compare the strings is sent, and when the value is actually used. If we use something like Grand Central where the threads are already spawned and just need to be used, then we're talking low-overhead implicit parallelization.
Essentially, libraries will present a sequential interface. User-land code will not need to know about parallelism - but will take advantage of the hardware when the programmer leverages the underlying frameworks.
Right about now, some people probably want to remind me that the GUI runs in the main thread whereas heavy processing is normally put into a secondary thread with mutexes to coordinate the two. I'll recall olde code that actually split up the processing so that the GUI event-pump could run. Even, olde code that would, at explicit times, yield execution to the GUI. Just yield when data is available to update the GUI, much less messy than having locks in obscure places. Normally, for such things, I have one lock that synchronizes events from the GUI on the separate thread with my work thread. The more sequential my code, the easier it is to work with.
Procedural Over Functional: Again, the Haskell fans will most likely disagree. Actually, I'd rather code parallel code in Haskell at times... But; let's not get distracted - I believe procedural code will maintain it's reign. The reason is simplicity. Everyone understands a TO-DO list, a sequence of instructions, manuals, etc. No manual I know asks you to trace to the desired result to get to the start of the solution (sometimes I feel like I'm rigging code to have side-effects to get it to run in functional languages).
Even if languages like Haskell are "better"; the rich and parallel underlying libraries of the system will make the entire thing moot.
Software Diets: Back-end system libraries will overthrow software complexity. That is, the OS will provide so much functionality that an application will simply have to connect the pieces. Some specialization might be needed; but very little.
This availability of features in the OS will change the software landscape. Software that does not properly integrate into the OS (that will have a global strategy for multiprocessing, with libraries optimized for that strategy) will slow down.
Think of it this way: the OS and it's libraries will shift together. And as hardware changes, so will the OS-provided libraries. Software using it's own libraries will need to adapt; but those using the OS-provided libraries won't.
This raises problems for multi-platform toolkits as I figure that certain functionality will be radically different on different OSes, even though they accomplish a similar thing.
Hardware Rollercoaster: See the disconnect between the user-land software and the hardware? Well, that means the underlying hardware can change more drastically. If the OS is the only one that needs to know about the specifics of the hardware and the user-land software just needs to focus on the algorithm; then people shouldn't even notice the insanity that is going on underneath the hood.
This implies that something akin to the LLVM project would be used to compile to a machine-independant level and complete compilation on the final hardware.
More Open-Source: Not the year of Linux; but the year of the open-source libraries. The added complexity of the underlying libraries will mean that they are more costly to develop. I'm not advocating using the spare time of developers to advance a corporations heavy work; but rather problems will be shared among OS vendors. Open-source is just a way to save money by reducing the amount of redundant work among companies.
If I had to wager, I'd say a BSD-style license - so each vendor can advertise having an upper-hand when marketing to consumers.
In the end... We aren't headed towards great doom when it comes to multi-core. Yes, people are panicking now as they realize all the caveats, however we've known for quite a while that 10% of the code is responsible for 90% of the execution time. That 10% of the code, in most cases, should be part of the OS and supporting library.
Final Ramblings: I referred to Apple's technology since I'm more familiar with it. I'm sure Microsoft is doing something similar - and that the .NET runtime might be better suited to the type of parallelism that I'm describing.
Now that I've predicted that nothing much will change for your average programmer; I'm going to do a part 2 - and detail exactly how I see the underlying libraries and hardware shifting. In part 3 - I'll explore how the development environment could change.
These predictions aren't final. As I learn more and read more of the results from the scientific community, my predictions may be refined over time. I won't delete these pages; but admit my mistakes and document how I erred.
One last thing. As a reader, you must have noticed the lack of references in this document. I don't trust texts without references. Neither should you. This part essentially puts forward the theory that user applications will just, in the worst case, need a recompile and keep on running using all the available hardware.
All this despite the move to multicore.
Monday, July 26, 2010
The wonders of NSString
This post is much less of a rant, and more of a regurgitation of how to use NSString as a way to solidify it in my memory and provide a useful way to look it up (I think it'll get buried and I'll forget about this post, making it a form of future e-waste. Where e-waste is knowledge that accumulates, but serves no purpose in the present except take up space.).
So... the lowly NSString. Where shall I begin? Maybe with the simple idea that whatever text processing I needed to do, NSString (and supporting objects) always seems to provide a means to do it (sometimes thanks to methods added after-the-fact to the NSString object). And also that getting a C string is almost never needed unless interacting with a C library (the standard C library shouldn't be needed).
NSString is very similar (for historical reasons) to Java's String object. Both can not be changed after being created, changes are rather require the creation of a new object (In such cases - NSAutoReleasePool is your friend if you find yourself doing innumerable string manipulations):
That's the beginning. Ok; time for some fun! Let's say there are plenty of string constants that need to be internationalized? The simplest solution is to write the following for strings:
Can we do more with NSString? Of course! splitting, loading a string from a file, and all sorts of other operations can be done.
I'll just note a few objects that can be useful rather than give a complete tutorial on them (the Apple docs are very good).
NSCharacterSet defines a set of unicode characters. This object provides a quick way to get all white-space, all punctuation, and even all newline character sets. Very useful when parsing files or breaking up strings.
NSScanner provides a nice way to scan any arbitrary file. It is much more flexible than the standard C/C++ file operations in that it returns the data (String, float, etc. - even delimited to an NSCharacterSet) and a boolean specifying whether the data was obtained. This makes parsing more complex files... easier. (I don't doubt that it can be done in C/C++ - just that assuming the structure might vary rather than be fixed is a nice one. eg. optional floating-point number would be read as 0 in C++ if memory serves.)
NSXMLParser is nice - but I'm not really a fan of XML. Let's say that there are neater ways to represent data than XML. XML is nice for being standard - but the tags are just too much for me. But it's there and works great!
NSString can also do everything that the standard C library does. Just that I don't worry about memory buffer sizes. I'm not familiar enough with the C++ String class to comment on it.
And for speed, CFString allows quick access to the underlying data:
Unfortunately, this is true of most modern APIs - and for all objects. That is; the objects can do so much. It's no longer a question of knowing how to do something - but knowing the magic keyword that will return the proper function in a search result.
OK, a mini-rant,
<rant>
Programmers now work at such a high-level. And that high-level will allow us to keep on coding as normal while everything transparently becomes parallel (something I've been thinking a lot about recently - the challenge may appear great; but in retrospect abstraction makes it easier. As a hint - we parallelize like the CPU does with instructions. Branches are our undoing - yes I'm captain obvious. I think QT Concurrent is the closest to what I'm thinking - but there is a way to provide a sequential API with parallel underpinnings. It already in the form of OpenGL. The real trick - which I'm almost done tinkering with - is how to get modules that don't know about each other communicating in a relevant way in parallel.).
</rant>
So... the lowly NSString. Where shall I begin? Maybe with the simple idea that whatever text processing I needed to do, NSString (and supporting objects) always seems to provide a means to do it (sometimes thanks to methods added after-the-fact to the NSString object). And also that getting a C string is almost never needed unless interacting with a C library (the standard C library shouldn't be needed).
NSString is very similar (for historical reasons) to Java's String object. Both can not be changed after being created, changes are rather require the creation of a new object (In such cases - NSAutoReleasePool is your friend if you find yourself doing innumerable string manipulations):
NSAutoreleasePool *p
= [[NSAutoreleasePool alloc] init];
//Do plenty of string operations using
//[NSString string*] methods.
[p release];
= [[NSAutoreleasePool alloc] init];
//Do plenty of string operations using
//[NSString string*] methods.
[p release];
That's the beginning. Ok; time for some fun! Let's say there are plenty of string constants that need to be internationalized? The simplest solution is to write the following for strings:
NSString *s = NSLocalizedString(@"Hello", @"Greeting String");
If you've set up your translation files correctly (get them using genstrings), then "Hello" is the word to get in the current language, and "Greeting String" is a hint to the translator.
Can we do more with NSString? Of course! splitting, loading a string from a file, and all sorts of other operations can be done.
I'll just note a few objects that can be useful rather than give a complete tutorial on them (the Apple docs are very good).
NSCharacterSet defines a set of unicode characters. This object provides a quick way to get all white-space, all punctuation, and even all newline character sets. Very useful when parsing files or breaking up strings.
NSScanner provides a nice way to scan any arbitrary file. It is much more flexible than the standard C/C++ file operations in that it returns the data (String, float, etc. - even delimited to an NSCharacterSet) and a boolean specifying whether the data was obtained. This makes parsing more complex files... easier. (I don't doubt that it can be done in C/C++ - just that assuming the structure might vary rather than be fixed is a nice one. eg. optional floating-point number would be read as 0 in C++ if memory serves.)
NSXMLParser is nice - but I'm not really a fan of XML. Let's say that there are neater ways to represent data than XML. XML is nice for being standard - but the tags are just too much for me. But it's there and works great!
NSString can also do everything that the standard C library does. Just that I don't worry about memory buffer sizes. I'm not familiar enough with the C++ String class to comment on it.
And for speed, CFString allows quick access to the underlying data:
//Direct cast -
//toll-free-bridge as Apple calls it.
CFStringRef r = (CFStringRef)@"NSString";
CFStringLineBuffer b; //... inline buffer used to iterate...
So yes - this has devolved into a rant. It's conclusion: look at what NSString does. It does a lot more than what you think. Especially thanks to categories that allow for any programmer to give NSString more functionality (that's how it can render text to views - and how external libraries could use it - to render strings to textures, etc.).
//toll-free-bridge as Apple calls it.
CFStringRef r = (CFStringRef)@"NSString";
CFStringLineBuffer b; //... inline buffer used to iterate...
Unfortunately, this is true of most modern APIs - and for all objects. That is; the objects can do so much. It's no longer a question of knowing how to do something - but knowing the magic keyword that will return the proper function in a search result.
OK, a mini-rant,
<rant>
Programmers now work at such a high-level. And that high-level will allow us to keep on coding as normal while everything transparently becomes parallel (something I've been thinking a lot about recently - the challenge may appear great; but in retrospect abstraction makes it easier. As a hint - we parallelize like the CPU does with instructions. Branches are our undoing - yes I'm captain obvious. I think QT Concurrent is the closest to what I'm thinking - but there is a way to provide a sequential API with parallel underpinnings. It already in the form of OpenGL. The real trick - which I'm almost done tinkering with - is how to get modules that don't know about each other communicating in a relevant way in parallel.).
</rant>
Saturday, July 17, 2010
iPhone 4 Ranting
<rant>
Note: as usual - no research, just a personal opinion. I like the opinions page in newspapers by the way! If there's a massive flaw in what's said below; just leave a comment.
So today; we have the results. Owners of the first batch of the devices (as per the Apple standard, there's a problem with them) can easily get a full refund, or get a free case. Which, I believe, to be a good result.
For those complaining about the delivery: if they were to admit fault in the product, they'd probably open themselves to more trouble than it's worth. The delivery ensures people get a working device or a refund (good for the customer) while minimizing the impact of the negative consequences due to the device malfunctioning (good for Apple). It's win-win if it all plays through as expected (unless if some die-hard person/fanatic desperately wants the device to work without a case and survive a death-grip: where the death-grip hasn't been replicated by everyone).
So... now, what's more interesting than the actual response from Apple? the comments on various forums. I'll classify them into the following categories:
- Emotional: I don't know how I could get emotional over an Apple product. Some are infatuated, some are angry. It's a device - if I want to play with my emotions, give me a good story!
- Quick Point: Some use it as a bargaining chip to advocate the Android platform / open source / etc. Of course, that platform hasn't been without it's own issues - and certain vendors do lock it down. Shouldn't people just walk into a store, try out the machines, and see which one best matches how they expect to use it? And if it doesn't work - return it? In the store of some wireless provider, I'd rather muck with menus/devices rather than compare feature-sets. Yes - some have a lot of features; but when accidentally pressing other buttons is possible, it gets annoying. Feature-sets and statistics can be equally rigged I believe.
- Realists: Actually work out the numbers of the statistics thrown out at the event and question their validity. The result is that things probably aren't as rosy as the statistics intuitively say.
There might have more; but that's enough for now.
I'm waiting until the dust settles until even considering that device. Actually, I'm more interested in an iPad.
On a side-note: people completely driven by emotion scare me. It's not funny how people's emotions play such a role in who gets elected here...
</rant>
Note: as usual - no research, just a personal opinion. I like the opinions page in newspapers by the way! If there's a massive flaw in what's said below; just leave a comment.
So today; we have the results. Owners of the first batch of the devices (as per the Apple standard, there's a problem with them) can easily get a full refund, or get a free case. Which, I believe, to be a good result.
For those complaining about the delivery: if they were to admit fault in the product, they'd probably open themselves to more trouble than it's worth. The delivery ensures people get a working device or a refund (good for the customer) while minimizing the impact of the negative consequences due to the device malfunctioning (good for Apple). It's win-win if it all plays through as expected (unless if some die-hard person/fanatic desperately wants the device to work without a case and survive a death-grip: where the death-grip hasn't been replicated by everyone).
So... now, what's more interesting than the actual response from Apple? the comments on various forums. I'll classify them into the following categories:
- Emotional: I don't know how I could get emotional over an Apple product. Some are infatuated, some are angry. It's a device - if I want to play with my emotions, give me a good story!
- Quick Point: Some use it as a bargaining chip to advocate the Android platform / open source / etc. Of course, that platform hasn't been without it's own issues - and certain vendors do lock it down. Shouldn't people just walk into a store, try out the machines, and see which one best matches how they expect to use it? And if it doesn't work - return it? In the store of some wireless provider, I'd rather muck with menus/devices rather than compare feature-sets. Yes - some have a lot of features; but when accidentally pressing other buttons is possible, it gets annoying. Feature-sets and statistics can be equally rigged I believe.
- Realists: Actually work out the numbers of the statistics thrown out at the event and question their validity. The result is that things probably aren't as rosy as the statistics intuitively say.
There might have more; but that's enough for now.
I'm waiting until the dust settles until even considering that device. Actually, I'm more interested in an iPad.
On a side-note: people completely driven by emotion scare me. It's not funny how people's emotions play such a role in who gets elected here...
</rant>
Subscribe to:
Posts (Atom)