company_banner

Acceler8 2011 — Accelerate 2012 — и так далее


    Вы участвовали в конкурсе параллельного программирования Acceler8 2011? Тогда этот пост — про вас.
    Вы участвуете в проходящем сейчас конкурсе Аccelerate-2012? Тогда этот пост — для вас.
    Вы принимали участие или только планируете участвовать в любом конкурсе спортивного программирования? А может, собираетесь начать свой первый самостоятельный проект? Тогда Вас, Штирлиц, я попрошу остаться с нами.

    Этот пост — «разбор полетов» прошлогоднего конкурса Intel — Acceler8 2011, выполненный одним из членов жюри. Он прокомментировал ключевые конкурсные моменты, а также дал банальные и очевидные, но до сих пор актуальные советы по участию в подобных соревнованиях и по ведению проектов.

    Итак, поехали!

    Первое, с чем столкнулись организаторы — это искренний интерес участников, живое общение в блогах и форумах. Скажу честно, решения участников, которые много «наследили» в форуме, мы рассматривали с особым пристрастием. У каждого члена жюри были свои любимчики, но на конечный результат соревнования это никак не повлияло, так как у тестовой машины не было предпочтений.

    Задача конкурса


    Ох, каких только нелестных эпитетов выслушали организаторы конкурса по поводу поставленной задачи. Методом проб и ошибок она была приведена к более-менее приемлемому виду. Но после получения первых решений, мы осознали насколько она была богата на различные оптимизации. Основной упор участники (ожидаемо) сделали на вычисление «периодических» матриц и параллелизацию. Но некоторые конкурсанты также сделали теоретические исследования алгоритма, оптимизации выделения памяти и хранения матриц, их заполнения, способов их обхода. В глазах жюри конкурса такой подход к решению задачи прибавлял минимум +100 к карме участника.

    Совет: в мире существуют много способов написания приложений, но наибольшей популярностью пользуется метод северо-западного угла. Это когда курсор ставится в верхний левый угол экрана и начинается набивка кода. Это неправильный метод. Никогда не приступайте к реализации проектов сразу, начните с изысканий на бумаге, разбейте весь проект на интерфейсы-функции-модули. Возможно, вы наткнётесь на сложности и тонкие моменты сразу, что сэкономит вам много человеко-часов позже, перед сдачей проекта.

    Качество кода


    Тут организаторы конкурса прочувствовали истинность народной китайской поговорки «не важно какого цвета кошка, если она ловит мышей». Каких только витиеватых конструкций и выражений не было в коде. Организаторы вспомнили свою юность, когда писали почти так же. Приведу TOP-5 «неловких» мест в проектах:

    5 место (хитрая инициализация указателя в конструкторе): m_memory_pointer((char*)this + 1024)
    4 место (инициализация переменной): static const int min_int = -2147483648;
    3 место: сравнение структуры с указателем. Как это вообще скомпилировалось под Linux?
    2 место: main.c файл на 1900 строк. Парни, серьёзно, как вы в нём ориентируетесь?
    1 место (почти десяток претендентов): несоблюдение формата ввода-вывода.

    Иногда мозг просто взрывался, пытаясь понять, что имели ввиду участники. Отсутствие комментариев только усугубляло общую картину (хотя вру, в паре файлов код терялся среди комментариев). Но что самое поразительное — иногда эти сложные нечитаемые конструкции работали, работали правильно, работали быстрее всех.

    Проблема, с которой могут столкнуться разработчики, если будут писать проекты в таком стиле, — это поддержка и сопровождение кода. Порой, проекты длятся годами, и если в момент завершения проекта разработчики помнят, что они написали, то уже через месяц могут и не разобрать. На наш взгляд, основной причиной невысокого качества кода стала нехватка времени. И даже после того, как организаторы продлили временные рамки конкурса. Рискну предположить, что почти все участники сидели безвылазно за своими компами в выходные перед завершением конкурса.

    Совет: разбейте весь проект на небольшие этапы, и реализуйте по одному этапу каждый день: общая инфраструктура приложения-основной алгоритм-тесты-оптимизации основного алгоритма. Пишите код так, как будто за его красоту и читабельность будет осуществляться пропуск в рай или в ад. Надеюсь, что все в курсе, что теперь правилами хорошего тона при написании резюме программистами считается указывать свой внешний репозиторий? Это делается для того, чтобы потенциальный работодатель мог ознакомится с навыками соискателя работы. Реально, красивый и читабельный код открывает двери так же быстро, как нечитабельный код их закрывает.

    Качество алгоритмов


    Признаюсь, моим фаворитом в прошедшем конкурсе была команда KomsomolskDV. Чувствуется, что парни имеют достаточно богатый опыт участия в подобных соревнованиях. Они подошли к исследованию алгоритма до такой степени педантично, что даже вычислили теоретическое время работы алгоритма в тактах. Если бы все участники провели подобные исследования, то нам бы не пришлось запускать приложения. Достаточно бы было сравнить теоретические времена вычислений.
    Также некоторые участники описали в своих сопроводительных документах ход их мыслей, с чего они начинали, как развивалась их мысль.
    Если представить ход мыслей участников в виде графика (хм, интересно, возможен ли такой график?), то до каких-то базовых улучшений додумались почти все участники. С ростом хитрости и сложности какой-то идеи количество справившихся участников резко падало.

    Если посмотреть на финальную таблицу с результатами, то можно увидеть, что первые пять мест сильно дифференцируются по производительности от других. Знаете почему? Потому, что эти команды придумали чуть более нетривиальные решения, чем остальные участники.

    Совет: Проведите теоретические исследования задач конкурса на бумаге, порисуйте схемы и картинки. Возможно, что вы обнаружите какие-то тонкости или уязвимости алгоритма, делающие его решение много быстрее, что даст вам преимущество перед другими участниками соревнования.

    В заключение хочу сказать, что участники конкурса доставили много весёлых минут организаторам.
    Почти совет: Относитесь к программированию, как серьёзной игре. С одной стороны, всё должно работать, с другой — процесс разработки должен приносить радость.

    Например, почему бы не оставить в комментариях «послание» будущим поколениям?
    Intel
    Company

    Comments 12

      +4
      >Проблема, с которой могут столкнуться разработчики, если будут писать проекты в таком стиле, — это поддержка и сопровождение кода.

      Проблема, с которой сталкиваются организаторы всяких конкурсов, это непонимания различия спортивного программирования и программирования промышленного. В спортивном программировании код всегда будет полон хаков, в нём допустимы всякие goto и сравнение указателей разных типов, в нём можно наплевать на проверку половины ошибок и т.д.

      Ставя условие «написать как можно более быстрый код» — вы в результате получаете именно «как можно более быстрый код». Никто его и не думает сопровождать в будущем, и поэтому он написан так, как написан. И именно поэтому я на собеседованиях уже давно не обращаю внимания на всякие титулы типа «победитель олимпиады по программированию....», поскольку если я начну на них обращать, то они пойдут только в минус соискателю, потому что победа в олимпиаде в 3 случаях из 4-ех означает склонность к хакам и нечитабельному коду, что в реальной жизни огромное зло.

        0
        Насчет постановки задачи. В итоге участники распались на два «лагеря»: те кто пользовался хаками периодичности и те, кто просто писал общее быстрое решение. И было бы интересно сравнить качество кода отдельно по этим лагерям.
          0
          Одинаково некрасиво писали. Другое дело, что были элегантные решения, это да. Но написаны в коде они были уже не так элегантно, как придуманы.
          0
          Требование «быстрого кода» никак не противоречит тому, чтобы писать красиво и читабельно. Я встречал в жизни буквально пару случаев, когда действительно код можно написать было «некрасивым» способом, чтобы он работал.

          Во всех прочих случая — банальная лень программистов оформлять свой код корректно. По крайней мере, прочитав большой объём кода участников, я не нашёл места, которое нельзя было бы написать «красиво».
            0
            Ага, особенно вселяют веру в это вот такие примерчики алгоритма копирования строки:

            strcpy(to, from, count)
            register char *to, *from;
            register count;
            {
                register n = (count + 7) / 8;
                if (!count) return;
                switch (count % 8) {
                case 0: do { *to = *from++;
                case 7:      *to = *from++;
                case 6:      *to = *from++;
                case 5:      *to = *from++;
                case 4:      *to = *from++;
                case 3:      *to = *from++;
                case 2:      *to = *from++;
                case 1:      *to = *from++;
                           } while (--n > 0);
                }
            }
            


            Пример, к стати, с сайта Интела, из видеолекции про оптимизацию. Вот уж всё просто и понятно, правда?
              –2
              Код не самый красивый, да и вообще не понятно, зачем такое написали, если известна длина копировая. Обычный memcpy справился бы лучше. Лекция за какой год?

              PS: Интел очень большой, сотни людей занимаются разными проектами и имеют порой диаметрально противоположные взгляды на какие-то вещи. Моя точка зрения — красивый код почти всегда самый быстрый. Не говоря о том, что он легко читается и поддерживается.
                0
                Лекция за март 2012 по-моему. Код не самый красивый и в лекции так и сказали, что вот пример того, когда производительность важнее красоты.
                Я лично считаю, что производительный код всегда будет достаточно страшным. Достаточно порыться по внутренностям всяких супер-оптимизированных библиотек, чтобы в этом убедиться.

                Еще пример — на форуме Интела на вопрос о том, нужно ли проверять валидность входных параметров и что выводить в случае их невалидности ответили — нет, проверять не надо, всегда будет валидный инпут. Ну вот скажите — где в реальном программировании может быть такой подход?
          0
          В прошлом году задача формально звучала «в данной матрице найти подматрицу с максимальной суммой элементов», фактически это было «найди баг в алгоритме генерации матрицы», т.к. матриц. Что помешало нагенерить матрицы хорошим аппаратным рандомом и за'mmap'ить их потом для выравнивания времени, затраченного на io — непонятно.
            0
            На будущее я бы посоветовал писать в условии задачи какой подход к решению (и какие решения) подразумевают организаторы: в стиле «спортивного программирования» с заточкой на алгоритмы или же промышленный вариант с проработкой реализации.
              0
              Конечно, первые пять мест сильно отличаются, но только не потому что вы написали, а потому
              что организаторы поленились сделать нормальную генерацию матрицы, и задача больше походила на олимпиадную, чем на мастерство распараллеливания. И все участники разделились на тех, кто использовал эту генерацию, и тех, кто честно пытался использовать распараллеливание.

              В этом году генерация нормальная, но условие перемудрили, из-за чего задача становится неинтересной (в плане идеи).
                0
                Ну зря вы так. Первые пять мест действительно постарались. И алгоритм проработали, и распараллелили.

                С генерацией матрицы действительно вышла накладка, тут критика уместна.
                0
                >Ох, каких только нелестных эпитетов выслушали организаторы конкурса по поводу поставленной задачи. Методом проб и ошибок она была приведена к более-менее приемлемому виду.

                Достаточно было послать условие любому красному на топкодере или кодефорсес.

                Only users with full accounts can post comments. Log in, please.