1. Java / Говнокод #1351

    +145.9

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    double dotProduct(double vec[]) {
            int k, m, v;
            double rtn;
    
            rtn = 0.0;
            k = vec.length / 4;
            m = vec.length % 4;
    
            v = 0;
            while ((k--) > 0) {
                rtn += vec[v];
                rtn += vec[v + 1];
                rtn += vec[v + 2];
                rtn += vec[v + 3];
                v += 4;
            }
    
            while ((m--) > 0) {
                rtn += vec[v];
                v++;
            }
    
            return rtn;}

    разбираю ocr-апплетик.. нашел вот такой интересный метод.. для лучшего восприятия говнокода, убрал одну переменную(было типа "+=vec1[v]*vec2[v]")

    Запостил: guest, 09 Июля 2009

    Комментарии (21) RSS

    • И где здесь говнокод? Оптимизация по скорости при обращении к памяти, развертка цикла.
      Ответить
    • Tinhol:
      Ага, именно так и стоит в Java делать))). Особенно при обходе массивов
      Ответить
    • Вообще-то не имеет значения из какого языка так делать, хоть из скриптового, массив все равно после компиляции\интерпретации будет представлен непрерывным блоком данных, а цикл превратится в конечном итоге в асеемблерный код с условным переходом назад, сбивающим предвыборку,и учитывая что это, насколько я понимаю, скалярное произведение векторов, то оно будет вызываться неоднократно в циклах, и такая оптимизация очень даже оправдана(можете провести эксперимент, кстати, по быстродействию, и уверен, результаты Вас удивят=) )
      Ответить
    • Mpo:
      Для C/C++ это действительно агрессивная оптимизация - экономия машинных тактов (код то компилируется в машинный). А вот есть ли в этом смысл для Java...
      Может тут и высмеивают простое перенесение "исподвертов" одного языка в другой, хотя выигрыш заранее не известен...
      Ответить
    • Java код тоже компилируется в машинный =) только из байт-кода непосредственно перед исполнением =)
      Ответить
    • Хм... Возможен улучшайзинг.
      /* Программный оверклокинг. Приступим, помолясь. */
      double dotProduct(double vec[]) {
              int k, m, l;
              double rtn;
      
              l = vec.length;
              m = l % 4;
              
              rtn = 0.0;
              for (k = l - m - 1; k >= 0 ; k -= 4)
                  rtn += vec[k] + vec[k - 1] + vec[k - 2] + vec[k - 3];
              /* УТВ: Здесь мы догнали Си... */
      
              switch (m)
              {
                  case 3: rtn += vec[l - 2];
                  case 2: rtn += vec[l - 1];
                  case 1: rtn += vec[l];
              }
              /* УТВ: А здесь уже уверенно обошли Ассемблер! */
       
              return rtn;
      }
      Ответить
    • Mpo:
      #5

      Я JVM не знаю... Может она отлавливает циклы с однотипными действиями внутри байт-кода и, при компиляции налету в машинный, разворачивает в цепь непрерывных действий, передача управления назад вообще не выполняется.
      Ловля таких вещей вполне по силам управляемому коду... Потому я осторожно высказал предположение, что для Java такой подход ничего не даёт.
      Ответить
    • Поправка на ветер:
      switch (m)
      {
         case 3: rtn += vec[l - 3];
         case 2: rtn += vec[l - 2];
         case 1: rtn += vec[l - 1];
      }
      Ответить
    • APE:
      IMHO программы пишутся для человека, а не для машины. Скажите пожалуйста для чего и где нужна эта "оптимизация"?
      Хочется оптимизировать ассемблер - пишите на нём.
      Ответить
    • Tinhol:
      Исходя из контекста - программа написана на Java. Среди многих Java-кодеров (в том числе и среди создателей самой технологии Java)
      такие оптимизации считаются антипаттерном в 99% случаев.

      + современные JIT-компиляторы снабжены оптимизационными фичами.

      ИМХО - писать такой код - издевательство над собой и теми кто будет его читать.
      Ответить
    • Вообще, такая оптимизация имеет место быть, если в теле цикла выполняется какая-то очень короткая операция вроде копирования слова/байта и цикл производит значительное количество итераций. Тогда затраты на организацию цикла (проверка условия выхода, приращение переменной цикла) относительно велики. Чем сложнее тело цикла - тем более ничтожен выигрыш от подобной оптимизации. В данном случае получение заметного эффекта сомнительно.
      Ответить
    • Moxa:
      100к элементов в каждом массиве.. выполняется ничуть не медленнее, чем с такой "оптимизацией", в среднем даже быстрее
      for (int i = 0; i < v1.length; i++) {
                  v1[i] = Double.parseDouble(p.getProperty("v1[" + i + "]"));
                  v2[i] = Double.parseDouble(p.getProperty("v2[" + i + "]"));
              }
              double rtn = 0.0;
      
              for (int i = 0; i < v1.length; i++) {
                  rtn += v1[i] * v2[i];
              }
      Ответить
    • Mpo:
      #9

      Как я упомянул выше, для С/C++ такой подход нормален. Данный код размещён сюда, скорее всего, именно для демострации неправильного применения оптимизации.

      Но разворачивание циклов, указательная арифметика, использование сдвига и прочее - всё это позволяет вам играть в трёхмерные компьютерные игры.

      Программы действительно пишутся для человека, но код создаётся для машины.

      Не сама по себе оптимизация виновата, а то место, в котором её применили.
      Ответить
    • [code=c#]
      class Program
      {
      static void Main(string[] args)
      {
      for (int i = 0; i < 20; ++i)
      {
      DoCheck();
      }
      }
      static double MultiplyFast(double[] v1, double[] v2)
      {
      double res = 0.0;

      long n = v1.Length;
      long m = n - v1.Length % 4;

      while (n != m)
      {
      res += v1[--n];
      }

      while (m != 0)
      {
      res += v1[m - 1] * v2[m - 1];
      res += v1[m - 2] * v2[m - 2];
      res += v1[m - 3] * v2[m - 3];
      res += v1[m - 4] * v2[m - 4];

      m -= 4;
      }

      return res;

      }

      static double MultiplySlow(double[] v1, double[] v2)
      {
      double res = 0.0;
      long size = v1.Length;

      for (long i = 0; i < size; ++i)
      {
      res += (v1[i] * v2[i]);
      }

      return res;

      }
      static void DoCheck()
      {
      const int vectorSize = 10000;
      double[] vector_1 = new double[vectorSize];
      double[] vector_2 = new double[vectorSize];

      Random rand = new Random((int)DateTime.Now.Ticks);

      for (int i = 0; i < vectorSize; ++i)
      {
      vector_1[i] = rand.NextDouble();
      vector_2[i] = rand.NextDouble();
      }

      double res_slow = 0.0;
      long counter = 100000;

      DateTime begin_slow = DateTime.Now;

      while (--counter != 0)
      {
      res_slow += MultiplySlow(vector_1, vector_2);
      }

      DateTime end_slow = DateTime.Now;

      double res_fast = 0.0;
      counter = 100000;

      DateTime begin_fast = DateTime.Now;

      whil
      Ответить
    • double res_fast = 0.0;
      counter = 100000;

      DateTime begin_fast = DateTime.Now;

      while (--counter != 0)
      {
      res_fast += MultiplyFast(vector_1, vector_2);
      }

      DateTime end_fast = DateTime.Now;

      Console.WriteLine(@"Fast result: {0}, SLow result: {1}",
      (long)(end_fast.Ticks - begin_fast.Ticks), (long)(end_slow.Ticks - begin_slow.Ticks));
      }
      }
      }
      Ответить
    • Дает такие результаты

      Fast result: 82345331, SLow result: 100314426
      Fast result: 82970343, SLow result: 92501776
      Fast result: 78595259, SLow result: 87032921
      Fast result: 78751512, SLow result: 85939150
      Fast result: 77970247, SLow result: 90157981
      Fast result: 82657837, SLow result: 85939150
      Fast result: 86876668, SLow result: 91251752
      Fast result: 80782801, SLow result: 93126788
      Fast result: 81095307, SLow result: 92970535
      Fast result: 85001632, SLow result: 90782993
      Fast result: 81251560, SLow result: 89220463
      Fast result: 82189078, SLow result: 88126692
      Fast result: 82814090, SLow result: 92345523
      Fast result: 78595259, SLow result: 87814186
      Fast result: 80001536, SLow result: 87501680
      Fast result: 81876572, SLow result: 89064210
      Fast result: 79845283, SLow result: 89845475
      Fast result: 80939054, SLow result: 87657933
      Fast result: 81564066, SLow result: 88282945
      Fast result: 83595355, SLow result: 88282945

      для до-диеза, для джавы не думаю, что бедет сильно отличаться
      Ответить
    • *за код не бить, это мой первый с# - код =)
      Ответить
    • Mpo:
      #14-#17
      Comparison result: 0,0843373493975904

      Comparison result: 0,0975609756097561

      Comparison result: 0,0987654320987654

      Comparison result: 0,121951219512195

      Comparison result: 0,0864197530864198

      Comparison result: 0,0864197530864198

      Comparison result: 0,0987654320987654

      Comparison result: 0,0975609756097561

      Comparison result: 0,108433734939759

      13 элементов 1.0e7 вызывов (относительное ускорение)
      ------------------------------------------


      Comparison result: 0,120689655172414

      Comparison result: 0,137931034482759

      Comparison result: 0,152542372881356

      Comparison result: 0,152542372881356

      Comparison result: 0,152542372881356

      Comparison result: 0,135593220338983

      Comparison result: 0,137931034482759

      Comparison result: 0,137931034482759

      Comparison result: 0,155172413793103

      10003 элементов на 10000 вызывов

      --------------------------------------------

      Comparison result: 0,103448275862069

      Comparison result: 0,103448275862069

      Comparison result: 0,103448275862069

      Comparison result: 0,11864406779661

      Comparison result: 0,103448275862069

      Comparison result: 0,11864406779661

      Comparison result: 0,103448275862069

      Comparison result: 0,0862068965517241

      Comparison result: 0,103448275862069

      1000003 Элементов на 100 вызывов


      Думаю, что здесь можно признать ускорение на 10%

      В C++ получилось где-то 25% +- трамвайная остановка... Но там я для красоты сделал развёртку на два оператора.
      Ответить
    • Mpo:
      И ещё всем C# .NET программистам пища для размышлений. Как известно в Visual Studio (у меня Professional Edition 2008) можно делать версии с различной оптимизацией на уровнях IL и JIT. Вот результаты Debug неоптимизированного кода в сравнениее с кодом, оптимизированным и на IL, и на машинном уровнях:

      Оптимизированный

      Comparison result: 0,302325581395349

      Comparison result: 0,25

      Comparison result: 0,17948717948718

      Comparison result: 0,205128205128205

      Comparison result: 0,268292682926829

      Comparison result: 0,205128205128205

      Comparison result: 0,225

      Comparison result: 0,24390243902439

      Comparison result: 0,230769230769231

      Comparison result: 0,25

      ----------------------------------------


      Неоптимизированный

      Comparison result: 0,15

      Comparison result: 0,180327868852459

      Comparison result: 0,137931034482759

      Comparison result: 0,135593220338983

      Comparison result: 0,12280701754386

      Comparison result: 0,11864406779661

      Comparison result: 0,120689655172414

      Comparison result: 0,137931034482759

      Comparison result: 0,12280701754386

      Comparison result: 0,120689655172414

      ---------------------------------------------

      Для теста использовались массивы из 100003 элементов,
      число вызывов 1000 раз.


      Как видно прирост производительности для оптимизированной версии в два раза больше.
      Вот и подумаем, нужна ли подобная оптимизация на управляемом коде...
      Ответить
    • Дмитрий:
      Серверный компилятор от Sun HotSpot JVM циклы раскручивает. Поэтому такая оптимизация для это JVM ничего не даст (проверено).
      А для знакомого с такого рода оптимизациями код вполне себе читабелен.
      Да, целочисленное деление там вообще не нужно (для округления до длин, кратных четырём). Можно обойтись битовыми операциями.

      Что-то типа n = a.length & ~3
      Ответить
    • Вообще-то такого рода оптимизация всецело зависит от компилятора.
      Насколько я знаю, современные компиляторы сами развертывают циклы по массивов, причем оптимальнее, чем ручками.
      Если же все-таки в вашем конкретном случае ручная оптимизация оказывается лучше, то ее лучше всего вынести в отдельный класс.

      В идеале я бы сделал две реализации и один интерфейс, чтобы и сохранить более читабельный вариант, и пользоваться более оптимальным в конечном продукте.
      Естественно, в оптимизированном методе при этом должна быть ссылка на неоптимизированный.
      Ответить

    Добавить комментарий