Re[55]: Как скрестить ужа и ежа или статическую и утиные тип - Философия программирования

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Denis2005, Вы писали:

VD>>>numbers.Filter(_ < 5).Map(x => x * x)

D>>Ок, вот аналогичный код:
D>>li.FindAll(delegate(int i) { return i < 5; }).ConvertAll<int>(delegate(int i) { return i * i; });

VD>Сомнения в том что Немерле рулит еще остались?

У меня под рукой N нет (и в ближайшее время не предвитится),
поэтому если не трудно запости "бенчарки" этих примеров.
По результатам можно будет определить на сколько он рулит.

VD>Тогда попробуй написать аналогичный код для массива.

int[] arr = new int[] { 5, 4, 1, 3, 9, 8, 6, 7, 2, 0 };
int[] a0 = Array.ConvertAll<int, int>(Array.FindAll(arr, delegate(int i) { return i < 5; }), 
                                                                            delegate(int i) { return i * i; });

Ничего ужасного тут не вижу. В любом случае можно сделать тонкую обертку над Array:

    struct Array<T>
    {
        private T[] _array;

        public Array(T[] array)
        {
            _array = array;
        }

        public Array<T> FindAll(Predicate<T> match)
        {
            return new Array<T>( Array.FindAll(_array, match) );
        }

        public Array<T> ConvertAll(Converter<T, T> converter)
        {
            return new Array<T>(Array.ConvertAll<T, T>(_array, converter));
        }
    }

Array<int> ai = new Array<int>(new int[] { 5, 4, 1, 3, 9, 8, 6, 7, 2, 0 });
ai = ai.FindAll(delegate(int i) { return i < 5; }).ConvertAll(delegate(int i) { return i * i; });

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Denis2005, Вы писали:

Кстати говоря "бенчмарк":

int[] arr = new int[] { 5, 4, 1, 3, 9, 8, 6, 7, 2, 0 };

for (int j = 0; j < 10000000; j++)
{
    int[] a0 = Array.ConvertAll<int, int>(
                    Array.FindAll(arr, delegate(int i) { return i < 5; }),
                    delegate(int i) { return i * i; });
}

~5.9 сек.

Array<int> ai = new Array<int>(new int[] { 5, 4, 1, 3, 9, 8, 6, 7, 2, 0 });
for (int j = 0; j < 10000000; j++)
{
    Array<int> a0 = ai.FindAll(delegate(int i) { return i < 5; }).ConvertAll(delegate(int i) { return i * i; });
}

~6.18 сек.

P.S. Athlon3000+/512Mb(PC2-5300)

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Denis2005, Вы писали:

D>У меня под рукой N нет (и в ближайшее время не предвитится),
D>поэтому если не трудно запости "бенчарки" этих примеров.
D>По результатам можно будет определить на сколько он рулит.

У меня есть один "бенчик" — компилятор самого Немерла. Он как раз написан с огромным объемом использования подобного рода кода.
Вызов фунционалного объекта по скорости равен сорости вызова виртуального метода. Что быстрее интерфейсов и делегатов. Последние вообще довольно тормозны.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Denis2005, Вы писали:

VD>У меня есть один "бенчик" — компилятор самого Немерла. Он как раз написан с огромным объемом использования подобного рода кода.

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

VD>Вызов фунционалного объекта по скорости равен сорости вызова виртуального метода. Что быстрее интерфейсов и делегатов. Последние вообще довольно тормозны.

Насчет делегатов ты конечно прав, а вот насчет интерфейсов погорячился.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Denis2005, Вы писали:

D>Влад, я не думаю, что сделать "бенчмарк", о котором выше шла речь займет у тебе больше минуты.
D>Поэтому запости результаты, а то дискуссия на тему крутизны Nemerle заходит в тупик.

Твой тест будет измерять скорость работы GC. На фоне выделения помяти какие-то там вызовы делегатов просто не будут заметны.

D>Насчет делегатов ты конечно прав, а вот насчет интерфейсов погорячился.

Извини, но я изучил впорос о котором говорю, а вот ты высказываешь свои предположения. Вызов метода интерфейса где-то 2-3 раза медленее нежели виртуального метода. Вот только подобными бэнчмарками это не выявишь. Тут и комплитор может соптимизировать, и предсказание ветвления в процессоре срабатывать начинает.

Пожалу самым правильным тестом было бы реализовать функцию сортировки в в разных вариантах которой использовать для сравненеия делегаты, компаратор на базе интерфейса и функциональный объект.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, VladD2, Вы писали:

VD>Твой тест будет измерять скорость работы GC. На фоне выделения помяти какие-то там вызовы делегатов просто не будут заметны.

Хорошо, давай сварганим тест без выделения памяти.

class MyCompare : IComparer<int>
{
    public int Compare(int a, int b)
    {
        return a.CompareTo(b);
    }
}

int[] ar = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int[] tst = new int[ar.Length];
MyCompare cmp = new MyCompare();

for(int i = 0; i < 10000000; i++)
{
    ar.CopyTo(tst, 0);  // {1}
    // Array.Sort(tst, cmp); {2}
    // Array.Sort(tst, delegate(int a, int b) { return a.CompareTo(b); }); {3}
}

Копирование ({1}) ~1.4 сек.
Копирование + сортировка ({1}+{2}) ~10.6
Копирование + сортировка ({1}+{3}) ~11.8

Я думаю не надо быть гением, чтобы сделать соответствующие выводы.

D>>Насчет делегатов ты конечно прав, а вот насчет интерфейсов погорячился.

VD>Извини, но я изучил впорос о котором говорю, а вот ты высказываешь свои предположения. Вызов метода интерфейса где-то 2-3 раза медленее нежели виртуального метода. Вот только подобными бэнчмарками это не выявишь. Тут и комплитор может соптимизировать, и предсказание ветвления в процессоре срабатывать начинает.

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

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Denis2005, Вы писали:

D>Во всяком случае виртуальный вызов не может быть сооптимизирован до прямого и до кучи заинлайнен.

Кстати, именно это и делает HotSpot. Правда к .Net это не имеет отношения...

Здравствуйте, Denis2005, Вы писали:

D>Хорошо, давай сварганим тест без выделения памяти.
D>Копирование ({1}) ~1.4 сек.
D>Копирование + сортировка ({1}+{2}) ~10.6
D>Копирование + сортировка ({1}+{3}) ~11.8

D>Я думаю не надо быть гением, чтобы сделать соответствующие выводы.

И каковы же твои выводы?

Ладно, достал. Убил хрен знает сколько времени чтобы сделать приличный тест.
Результат:

Framework version: 2.0.50727.308
--------------------------------------------------
Test               Sort Fun took: 00:00:02.0639765     Test OK.
Test          Sort Delegate took: 00:00:02.5174177     Test OK.
Test         Sort Interface took: 00:00:02.2520124     Test OK.
Test               Sort Int took: 00:00:01.3553026     Test OK.
Test             Array.Sort took: 00:00:01.2027735     Test OK.
Test  Array.Sort + Delegate took: 00:00:03.2673144     Test OK.
--------------------------------------------------
Test               Sort Fun took: 00:00:02.0579892     Test OK.
Test          Sort Delegate took: 00:00:02.4767103     Test OK.
Test         Sort Interface took: 00:00:02.2513230     Test OK.
Test               Sort Int took: 00:00:01.3561866     Test OK.
Test             Array.Sort took: 00:00:01.2009146     Test OK.
Test  Array.Sort + Delegate took: 00:00:03.2260957     Test OK.

Собственно все как я и говорил, за тем исключением, что похоже в новой версии фрэймворка похоже еще разогнали делегаты.
Если вычисть из тестов время теста Sort Int можно оценить реальное время затраченное на использование компаратора.

Исходник:

using System;
using System.Console;
using Nemerle.Utility;
using System.Diagnostics;

module Program
{
  Main() : void
  {
    WriteLine("Framework version: " + Environment.Version.ToString());

    def run(test, msg) : void
    {
      def calcCheckSum(ary) { ary.Fold(0 : long, _ + _) }
        def ary = array(10_000_000) : array[int];
        def r = Random(123);
        
      for (mutable i = 0; i < ary.Length; i++)
            ary[i] = r.Next(0, 1000000);

          def etalon = calcCheckSum(ary);
          def timer = Stopwatch.StartNew();
          
      test(ary);

      Write("Test {1,22} took: {0}", timer.Elapsed, msg);

          Trace.Assert(etalon == calcCheckSum(ary));
          _ = ary.Fold(0, fun(x, acc) { Trace.Assert(x >= acc); x });
      WriteLine("     Test OK.");
    }

    def runAll()
    {
      WriteLine("--------------------------------------------------");

      run(ary => ary.Sort(_ > _),                   "Sort Fun");
      run(ary => ary.SortDelegate(_ > _),           "Sort Delegate");
      run(ary => ary.SortInterface(Utils.CmpInt()), "Sort Interface");
      run(ary => ary.SortInt(),                     "Sort Int");
      run(ary => Array.Sort(ary),                   "Array.Sort");
      run(ary => Array.Sort(ary, _ - _),            "Array.Sort + Delegate");
    }

    runAll();
    runAll();
  }
}

public module Utils
{
  public Sort[T](this ary : array[T]) : void
    where T : IComparable[T]
  {
    Sort(ary, 0, ary.Length - 1, (x, y) => x.CompareTo(y) > 0);
  }
  
  public Sort[T](this ary : array[T], left : int, right : int) : void    
    where T : IComparable[T]
  {
    Sort(ary, left, right, (x, y) => x.CompareTo(y) > 0);
  }

  public Sort[T](this ary : array[T], isGreat : T * T -> bool) : void
  {
      Sort(ary, 0, ary.Length - 1, isGreat);
  }

  public Sort[T](
      this ary : array[T],
          left : int,
         right : int,
       isGreat : T * T -> bool
  )
    : void    
  {
    mutable i = left;
    mutable j = right;
    def center = ary[(left + right) / 2];

    while (i <= j)
    {
        while (isGreat(center, ary[i]))
            i++;
        while (isGreat(ary[j], center))
            j--;

        when (i <= j)
        {
          ary[i] <-> ary[j];
          i++;
          j--;
        }
    }

    when (left < j)
        Sort(ary, left, j, isGreat);
    when (right > i)
        Sort(ary, i, right, isGreat);
  }

  public delegate Cmp[T](x : T, y : T) : bool;
  
  public SortDelegate[T](this ary : array[T], isGreat : Cmp[T]) : void
  {
      SortDelegate(ary, 0, ary.Length - 1, isGreat);
  }

  public SortDelegate[T](
      this ary : array[T],
          left : int,
         right : int,
       isGreat : Cmp[T]
  )
    : void    
  {
    mutable i = left;
      mutable j = right;
      def center = ary[(left + right) / 2];

      while (i <= j)
      {
          while (isGreat(center, ary[i]))
              i++;
          while (isGreat(ary[j], center))
              j--;

          when (i <= j)
          {
            ary[i] <-> ary[j];
              i++;
              j--;
          }
      }

      when (left < j)
          SortDelegate(ary, left, j, isGreat);
      when (right > i)
          SortDelegate(ary, i, right, isGreat);
  }

  public interface ICmp[T] { Cmp(x : T, y : T) : bool; }
  public class CmpInt : ICmp[int] { public Cmp(x : int, y : int) : bool { x > y } }

  public SortInterface[T](this ary : array[T], isGreat : ICmp[T]) : void
  {
      SortInterface(ary, 0, ary.Length - 1, isGreat);
  }

  public SortInterface[T](
      this ary : array[T],
          left : int,
         right : int,
       isGreat : ICmp[T]
  )
    : void    
  {
    mutable i = left;
      mutable j = right;
      def center = ary[(left + right) / 2];

      while (i <= j)
      {
          while (isGreat.Cmp(center, ary[i]))
              i++;
          while (isGreat.Cmp(ary[j], center))
              j--;

          when (i <= j)
          {
            ary[i] <-> ary[j];
              i++;
              j--;
          }
      }

      when (left < j)
          SortInterface(ary, left, j, isGreat);
      when (right > i)
          SortInterface(ary, i, right, isGreat);
  }

  public SortInt(this ary : array[int]) : void
  {
    SortInt(ary, 0, ary.Length - 1);
  }

  public SortInt(
      this ary : array[int],
          left : int,
         right : int
  )
    : void    
  {
    mutable i = left;
    mutable j = right;
    def center = ary[(left + right) / 2];

    while (i <= j)
    {
        while (center > ary[i])
            i++;
        while (ary[j] > center)
            j--;

        when (i <= j)
        {
          ary[i] <-> ary[j];
          i++;
          j--;
        }
    }

    when (left < j)
        SortInt(ary, left, j);
    when (right > i)
        SortInt(ary, i, right);
  }
}

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, Andrei N.Sobchuck, Вы писали:

ANS>Кстати, именно это и делает HotSpot. Правда к .Net это не имеет отношения...

Если метод действительно виртуальный, то ХотСпот ничего поделать не сможет.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, Denis2005, Вы писали:

АХ>>+1. Да еще и неэффективно, т.к. сначала создается массив а потом он же копируется в List<int>

D>Конечно можно обойтись и без лишних "танцев":

D>

D>int[] a0 = Array.FindAll(new int[] { 5, 4, 1, 3, 9, 8, 6, 7, 2, 0 }, delegate(int i) { return i < 5; });
D>

Конечно:

def a0 = [5,4,1,3,9,8,6,7,2,0].Filter(_<5);

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

VladD2 wrote:
> ANS>Кстати, именно это и делает HotSpot. Правда к .Net это не имеет
> отношения...
> Если метод действительно виртуальный, то ХотСпот ничего поделать не сможет.
Только вот это бывает достаточно редко на практике — большинство вызовов
мономорфны. HotSpot в седьмой JDK будет получать информацию от
escape-анализатора, которая поможет ему выделять места, где просто не
может быть виртуальных вызовов.

Заодно, escape-анализатор еще позволяет располагать переменные на стеке
и убирать ненужную синхронизацию.

Posted via RSDN NNTP Server 2.0

Здравствуйте, Cyberax, Вы писали:

C>Только вот это бывает достаточно редко на практике — большинство вызовов
C>мономорфны.

Это не наш случай. Это всего лишь уравнивает шансы Явы и дотнета.

C> HotSpot в седьмой JDK будет получать информацию от
C>escape-анализатора, которая поможет ему выделять места, где просто не
C>может быть виртуальных вызовов.

Не факт что это поможет подавлять виртуальность. И, кстати, почему в 7-й? Вроде бы в прошлый раз они обещали что escape-анализ войдет в слудующую версию, а тогда текущей была 1.5.
Ну, да, в любом случае это дико интересно. Если Сан это сделает и это даст соотвествующий эффект, то — это будет прорыв!

C>Заодно, escape-анализатор еще позволяет располагать переменные на стеке
C>и убирать ненужную синхронизацию.

Это не "заодно", это как раз его основ его предназначение.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, VladD2, Вы писали:

VD>Это не наш случай. Это всего лишь уравнивает шансы Явы и дотнета.

Интересно, с каких это пор ручная оптимизация лучше автоматической?

Здравствуйте, Andrei N.Sobchuck, Вы писали:

VD>>Это не наш случай. Это всего лишь уравнивает шансы Явы и дотнета.

ANS>Интересно, с каких это пор ручная оптимизация лучше автоматической?

К чему эта фраза?

... << RSDN@Home 1.2.0 alpha rev. 637>>

VD>>>Это не наш случай. Это всего лишь уравнивает шансы Явы и дотнета.

ANS>>Интересно, с каких это пор ручная оптимизация лучше автоматической?

VD>К чему эта фраза?

всегда virtual vs. расставлять virtual руками. Или ты не об этом говорил, когда писал о шансах?

Здравствуйте, Andrei N.Sobchuck, Вы писали:

ANS>всегда virtual vs. расставлять virtual руками. Или ты не об этом говорил, когда писал о шансах?

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

А вот в Яве пока что получается, что многие расставляют где не попадя final, что намного хуже, так как это как раз портит дизайн.

В прочем, это очередной уход от темы. Главное, что замечаение Киберакса не подходит к данному случаю. Функциональный объект принципиально обязан быть истенно виртуальным, так как функции получают ссылку на абстрактный класс (считай интерфейс) и деспетчиризация проходит принципиально динамически.

ЗЫ

Мысли вслух...

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

Возможно такой перенос надо совмещать с инлайнингом ФВП. Тогда проблема распухания будет менее важна и упростится перенос кода. Ведь код лямбд просто будет работать в исходном собвстенном контексте.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, VladD2, Вы писали:

C>> HotSpot в седьмой JDK будет получать информацию от
C>>escape-анализатора, которая поможет ему выделять места, где просто не
C>>может быть виртуальных вызовов.
VD>Не факт что это поможет подавлять виртуальность. И, кстати, почему в 7-й? Вроде бы в прошлый раз они обещали что escape-анализ войдет в слудующую версию, а тогда текущей была 1.5.
На днях 1.6 уже вышла — так что следующая будет как раз семерка.

VD>Ну, да, в любом случае это дико интересно. Если Сан это сделает и это даст соотвествующий эффект, то — это будет прорыв!
Java на глазах улучшается — http://rsdn.ru/Forum/?mid=2267562

Пока лень было в код JVM лезть, но как только время будет — полажу по исходникам.

VladD2 wrote:
> В прочем, это очередной уход от темы. Главное, что замечаение Киберакса
> не подходит к данному случаю. Функциональный объект принципиально обязан
> быть истенно виртуальным, так как функции получают ссылку на абстрактный
> класс (считай интерфейс) и деспетчиризация проходит принципиально
> динамически.
Однако, оптимизатор в первый проход может за-inline'ить код
функционального объекта, а потом обнаружить, что в этом коде на самом
деле нет полиморфных вызовов.

Точнее говоря, оптимизатору вообще на важно, что код находится в
функциональном объекте — он работает с деревьями SSA и ищет "закрытые
участки". То есть, например, Array.sort будет помечен именно как такой
участок — а значит его можно инлайнить и убирать виртуальность.

> Тут если и оптимизировать что-то, то надо избавляться от самого вызова
> перенося код лямбд в код функций высшего порядка (ФВП), согдавая их
> специализированные версии. Что очень не просто и может приводить к
> распуханию кода.
Вот как раз тут HotSpot и рулит, он позволит оптимизировать только самые
узкие места. А их обычно не так много, так что распуханием кода можно
пренебречь.

> Возможно такой перенос надо совмещать с инлайнингом ФВП. Тогда проблема
> распухания будет менее важна и упростится перенос кода. Ведь код лямбд
> просто будет работать в исходном собвстенном контексте.
Угу

Я это прочел уже после того, как ответ написал.

Posted via RSDN NNTP Server 2.0

Здравствуйте, Kisloid, Вы писали:

K>Здравствуйте, konsoletyper, Вы писали:

K>>LR(1)-парсеры не распознают не то что весь класс КС-грамматик, они распознают даже далеко не весь класс однозначных КС-грамматик.

K>LR-grammars generate exactly the DCFLs
K>The family of LR(1)-languages is exactly the family of deterministic languages.

Нет, тут надо разобраться

Цитата с твоей первой ссылки

- deterministic CFLs (accepted by deterministic PDAs)
syntax of many programming languages
LR-grammars generate exactly the DCFLs

Так вот, deterministic PDAs, то есть детерминированные магазинные (стековые) автоматы, действительно эквивалентны LR-грамматикам. Но дело в том, что языки, распознаваемые deterministic PDA, представляют собой лишь подмножество КС-языков. Все КС-языки распознаются с помощью non-deterministic PDA. Более того, как говорилось выше, deterministic PDAs не распознают даже все языки, порожденные однозначными КС-грамматиками.
Язык, порожденный вот такой вот однозначной грамматикой S -> 0S0 | 1S1 | eps, не разпознается детерминированным PDA.

... << RSDN@Home 1.1.4 beta 7 rev. 447>>

	От:	Denis2005
	Дата:	28.01.07 11:27
	Оценка:

	От:	Denis2005
	Дата:	28.01.07 11:39
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	28.01.07 11:49
Оценка:

	От:	Denis2005
	Дата:	28.01.07 12:05
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	28.01.07 15:20
Оценка:	+1

От:	Andrei N.Sobchuck	www.smalltalk.ru
Дата:	28.01.07 16:34
Оценка:	+1

	От:	Андрей Хропов
	Дата:	28.01.07 23:03
	Оценка:

	От:	Cyberax
	Дата:	29.01.07 02:37
	Оценка:

	От:	Cyberax
	Дата:	30.01.07 00:14
	Оценка:

	От:	Cyberax
	Дата:	30.01.07 00:16
	Оценка:	+1

	От:	_DAle_
	Дата:	30.01.07 00:17
	Оценка:	7 (2) +1