mukel's blog

By mukel, 11 years ago, In English

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).

  • Vote: I like it
  • +26
  • Vote: I do not like it

»
11 years ago, # |
Rev. 2   Vote: I like it +47 Vote: I do not like it

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.

»
11 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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".

»
3 months ago, # |
  Vote: I like it +16 Vote: I do not like it

So after 11 years of tech development, what is the answer?