![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
henry_flower) wrote2018-01-12 09:40 pm
Top Reasons Nondeterministic Algorithms Lose Business
'A few years ago [~1991] the Computer Science Department at Carnegie-Mellon University regularly ran a small programming contest for its incoming graduate students.
[...] in one particular year it was very simple. Contestants had to read a file of numbers and print the average. There were only two rules:
- The program had to run as fast as possible.
- The program had to be written in Pascal or C.
The rival programs were grouped together and submitted in batches by a faculty member. Students could submit as many entries as they wished; this encouraged the use of nondeterministic probabilistic algorithms (algorithms that would guess at certain characteristics of the data set and use the guess to obtain faster performance). The golden rule was that the program which ran in the shortest amount of time won the contest. [...]
The data file contained about 10,000 numbers, so assuming it took a millisecond just to read and process each number (about par for the systems at the time), the fastest possible program would take about 10 seconds.
The actual results were very surprising. The fastest program, as reported by the operating system, took -3 seconds. That's right--the winner ran in a negative amount of time! The next fastest apparently took just a few milliseconds, while the entry in third place came in just under the expected 10 seconds. Obviously, some devious programming had taken place, but what and how? A detailed scrutiny of the winning programs eventually supplied the answer.
The program that apparently ran backwards in time had taken advantage of the operating system. The programmer knew where the process control block was stored relative to the base of the stack. He crafted a pointer to access the process control block and overwrote the "CPU-time-used" field with a very high value. The operating system wasn't expecting CPU times that large, and it misinterpreted the very large positive number as a negative number under the two's complement scheme.
The runner-up, whose program took just a few milliseconds, had been equally cunning in a different way. He had used the rules of the competition rather than exotic coding. He submitted 2 different entries. One entry read the numbers, calculated the answer in the normal way, and wrote the result to a file; the second entry spent most of its time asleep, but woke up briefly every few seconds and checked it the answer file existed. When it did, it printed it out. The second process only took a few milliseconds of total CPU time. Since contestants were allowed to submit multiple entries, the smaller time counted and put him in second place,
The programmer whose entry came in third, taking slightly less than the calculated minimum time, had the most elaborate scheme, He had worked out the optimized machine code instructions to solve the problem, and stored the instructions as an array of integers in his program. It was easy to overwrite a return address on the stack (as Bob Morris, Jr. later did with the Internet worm of 1988) and cause the program to jump into and start executing this array. These instructions solved the problem honestly in record time.
There was an uproar among the faculty when these stratagems were uncovered. Some of the staff were in favor of severely reprimanding the winners. A younger group of professors proposed instead awarding them an extra prize in recognition of their ingenuity. In the end, a compromise was reached. No prizes were awarded, no punishments were handed down, and the results stuck. Sadly, the contest was a casualty of the strong feelings, and this incident marked the final year it was held.'
(From Expert C Programming by Peter van der Linden.)
no subject
А то известное явление; я первый год после вуза работал, у нас на заводе выпускали "вторую очередь АСУ" - там просто захардкодили все распечатки, и распечатали для комиссии. Все довольны. Как говорила моя тамошняя начальница, "программа разработана, но еще не написана."
no subject
напевно.
там професура розлютилася результатами тому, що вони спеціяльно поклали у файл не рендомно сгенеровані числа, а щось підпадаюче під паттерн, сподіваючись на цікаві ідеї від майбутніх phd, а вийшло так, що той паттерн намагалися шукати лише лохи.
> "программа разработана, но еще не написана."
ггг
no subject
Вот буквально вчера с сыном обсуждали пользование книгами при сдаче экзамена.
Он говорит: у нас так на экзамене по Security было. Я спрашиваю: потому что, если ты хорошо успеваешь по этому предмету, то хакнешь на экзамене учебник прямо из воздуха и все спишешь? Он говорит, нет, я сразу хакну базу оценок. Что значит смотреть в корень! Молодежь, свежие мозги, мы им в подметки не годимся.
no subject
Не поділяю вашого оптимізму. Коли сцяний MS Word або Google Chrome жере гігабайти пам’яті, то це означає, що програму та цільову систему написано дуже погано, гірше просто вже нікуди.
no subject
no subject
Ага, называется стахановский метод. Надо посмотреть, что там за студент - наверняка из бывших соцстран...
no subject
він не знав, яку з версій запустять першою (може навіть їх пускали паралельно), тому чекав у циклі на готові результати, замість того, щоб просто зразу 1 раз прочитати потрібний файл.
тобто, йому пощастило що 1шу версію запустили перед 2гою. якщо би ні, то через 10 сек ніякого сенсу чекати на кешований результат не було б.
no subject