For many years competitive programming have follow the old "sequantial" style, where a program is just an ordered sequence of instructions executed in a deterministic way, one after the other.
In the present, processors have reach the maximum clock speed (a least the current technology leaders no longer focuses on faster, but multi-core processors). There is a funny upper bound: Lets suppose that a processor cycle takes the same time that light takes to travel from one side of the processor to the other (square processor), then to achieve 3Ghz the processor (square side) should be smaller than 30 cm, not very tight, but enough to worry. There is also the (theoretical) physical limit of 12nm for the manufacturing process, most advanced processors today are built with 22nm technology (very close too). Today, the industry tries to overcome the processing speed limits with concurrent, multi-threaded programs. "Functional" languages are becoming popular because it's "scalability".
The question is, does competitive programming should keep the old format, or maybe in a not too far future, parallel programs would become the standard?
Right now write a multi-threaded algorithm is by far more painful than the good old sequential way, there are a lot of approaches, different languages provides different frameworks, libraries, or just doesn't.
Maybe competitive programming could enable some multi-threading capabilities, but that would be unfair with older (or not so well supported languages). Java is 2 or 3 times slower than C++, what if we could use 2 threads in Java?.
The ideal would be that our programs could be coded in a sequential manner, and compiled/executed in a multi-threaded one, sadly the technology of today imposes a barrier; writing parallel programs requires a change (often introducing additional complexity) in the sintaxis, or the use of some obscure frameworks ...
We all hope that competitive programming would stay as a pilar of tomorrow technology and development and not as a divergent branch. As happened with Formula 1 which is becoming less and less important to common cars development(taken from here), or bodybuilding (drugs, pills, steroids...) in the case of physical health (fitness).
Parallelism has been the future of programming for 30 years already.
Maybe admit that programming contests are for traditional algorithms. And I see nothing wrong with that. Just like we don't have much threading, we don't have a lot of database stuff either.
I don't agree with comparing traditional algorithms with formula 1 or bodybuilding. Because unlike formula and bodybuilding, traditional algorithms are still the core of programming. You won't learn threads without some good sequential algorithms first. And there will always be real world problems that are better solved at least partially with some sequential stuff.
Besides, I have used threads to my advantage in GCJ constantly. So there are opportunities for this in the contest world. I think the main reason threads can't be worked into online judges is that if you use two threads, you are using two cores. That's double the processing needs. Worse, thread support is not very portable/standard in many languages. Waiting for C++0x to take over. With time all contest sites shall figure out that they should use google's model (submit output instead of source code). But until this happens, it would be very hard to do it.
"The ideal would be that our programs could be coded in a sequential manner, and compiled/executed in a multi-threaded one"
Isn't that already what happens in codeforces and topcoder? Your program receives a single test case, the server runs many cases simultaneously.
Multi-threading is more like constant optimization, while we focus more on complexity in traditional algorithm contests. Of course, there are specified contests and problems for parallelism as well.
In contests that running programs on local machine lick GCJ and FHC, splitting test cases into many threads is a widely-known, tricky and useful technology. There are also some online judges supporting multi-threading. However, cpu time is measured instead of real time in them. So using multi-threading will do nothing but make you program "cost more time".
So after 11 years of tech development, what is the answer?
That's exactly what I'm thinking about when I'm in the bathroom.
bitmask operation is a weird limited 64 parallelism, start solving bitmask problem.
CP focus on finding algorithm with the best the time and space complexity (or at least in reasonable time to pass). Using multi-threading to speed up program is useful nowadays, but CP will make it even better, right?
Suppose you find an algorithm with O(nm) time complexity, and it's pretty slow with single thread. You then decide to raise up to 100 threads, and the program is pretty okay now. But someone else could do it in O(nlogm), and using 1 thread could be enough to handle. And in reality, this should will save you or some companies to minimize the cost of the hardware.
Actually, I don't know which future will be for CP. Maybe it will be what you predict. Then CP will be like "You need to run this program in x seconds, with the limitation of y threads". If that is not the case, then you could use "infinity" threads for parallel calculations to achieve any time limit you want. Then you can see, y threads is something like constant optimization, so why don't we scale it to only 1 thread for simplicity?
To conclude, instead of thinking about applying modern programming ways in CP, let's ask yourself "what is the main point of CP?".
Algorithms of O(nm) are widely parallelizable and can be extended to tens of thousands of threads on the GPU, while O(nlogm) are always sequential and single-threaded. . In this case, you may want to reconsider which one will save more hardware costs. Especially when high-level programming languages running on GPUs have been developed: https://github.com/HigherOrderCO/Bend
Zero explicit parallel annotations will not bring more learning costs and coding costs, but CP needs to reconsider whether writing an algorithm with lower parallel difficulty would be better.
Some NlogN algorithms can still be parallelized by using threads (eg divide and conquer algorithms like merge sort).
Yes, the idea of divide and conquer makes parallel features more prominent