OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 13:00

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 91 ]  На страницу Пред.  1, 2, 3, 4, 5  След.
Автор Сообщение
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 10:48 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Geniepro писал(а):
ЗЫ. Ничего, щас скачаю Clean -- он весьма похож на Хаскелл, только вместо монад у него уникальные типы используются, посмотрю, сколько там израсходуется памяти для этой программки...

Вот ещё бы заставить его реально создавать в памяти список, а то он его оптимизирует и память вообще от размера списка не зависит.
Работает программа, кстати, на порядок быстрее, чем на Хаскелле. Но таки этот Clean хоть и похож на Хаскелл, но отличается, непривычен...
Код:
module Lists

import StdInt
import StdEnum
   
xs :: [Int]
xs = [ 1..100000000 ]

length2 :: [a] -> Int
length2 xs = len xs 0
  where
   len :: [a] !Int -> Int
   len []     n = n
   len [y:ys] n = len ys (n+1)

last :: [a] -> a
last [x]    = x
last [x:xs] = last xs

sum :: [Int] -> Int
sum xs = sum2 xs 0
  where
   sum2 :: [Int] !Int -> Int
   sum2 []     n = n
   sum2 [y:ys] n = sum2 ys (n+y)

Start::(Int, Int, Int)
Start = (length2 xs, last xs, sum xs)
Ужос! :lol:


Последний раз редактировалось Geniepro Среда, 08 Июль, 2009 10:52, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 10:52 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
гм. а там что, библиотечных length и sum нету?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 10:56 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Во! А попробуй ка на нём quick sort ;-) Что-то думается мне что оно там вполне себе будет бегать и в короткой форме.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 10:58 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Geniepro писал(а):
Вот ещё бы заставить его реально создавать в памяти список, а то он его оптимизирует и память вообще от размера списка не зависит.

Наврал. Список в памяти создаётся, на 100 млн эл-тов тратится 100 МБт ОЗУ. Что-то маловато, наверное всё-таки что-то там оптимизируется...

Alexey Veselovsky писал(а):
гм. а там что, библиотечных length и sum нету?
length вроде бы есть, но с полпинка не запустилось, а описания её я не нашёл. Почему компилятор ничего не сказал про last и sum -- не знаю, возможно их и нет...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 11:06 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Доползу до дому с линуксом, попробую пощупать jhc. Вот тут обсуждение интересное насчет производительности http://groups.google.com/group/fa.haske ... eae5ddf12c

Цитата:

on my machine (with 'print' equivalent added to C one to be fair, and
10^9 changed to 1000*1000*1000 just like the C one)

ghc: (-O2)
time ./foo
/foo 2.26s user 0.00s system 99% cpu 2.273 total

gcc:
time ./a.out
/a.out 0.34s user 0.00s system 99% cpu 0.341 total

jhc:
time ./hs.out
/hs.out 0.33s user 0.00s system 96% cpu 0.347 total

Yay! it is good to see my goal of C-equivalent performance starting to
come true :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 12:27 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Текущая версия таки 6.10.3. Уже несколько месяцев как.
Ну вот, я её, оказывается, скачал два месяца назад и забыл вообще... :lol:
Alexey Veselovsky писал(а):
Не менее интересно было бы посмотреть на другие реализации хаскеля. И сравнить. Например тот же jhc посмотреть...
Пытался я как-то сработаться с другими компиляторами, да так и не получилось почему-то. GHC -- всё-таки мейнстрим для Хаскелла...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 12:46 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Alexey Veselovsky писал(а):
Текущая версия таки 6.10.3. Уже несколько месяцев как.
Ну вот, я её, оказывается, скачал два месяца назад и забыл вообще... :lol:
Alexey Veselovsky писал(а):
Не менее интересно было бы посмотреть на другие реализации хаскеля. И сравнить. Например тот же jhc посмотреть...
Пытался я как-то сработаться с другими компиляторами, да так и не получилось почему-то. GHC -- всё-таки мейнстрим для Хаскелла...


Мейнстрим мейнстримом, но 220 мег на жалкие 10 лямонов Int'ов это таки перебор. Либо его надо оптимизировать, либо смотреть на другие компилеры.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 12:52 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Вообще, отсутствие переносимости кода между компиляторами говорит о незрелости языка.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 13:11 

Зарегистрирован: Воскресенье, 08 Март, 2009 17:54
Сообщения: 372
Сам факт наличия проблем с таким тривиальным примером и достаточно длинное обсуждение, ИМХО, очень наглядно демонстрируют возможности ФП, и не случшей стороны.
В императиве обсуждать было бы просто не чего.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 13:22 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Algo писал(а):
Сам факт наличия проблем с таким тривиальным примером и достаточно длинное обсуждение, ИМХО, очень наглядно демонстрируют возможности ФП, и не случшей стороны.
В императиве обсуждать было бы просто не чего.


Проблемы не у ФП вообще, а конкретно у ghc.
Хотите проблем в императиве? Пожалуйста: создание односвязного списка (пустого, т.е. каждый элемент не содержит ничего кроме ссылки на последующий) с 10 млн. элементами в BB хавает 176 Мегабайт памяти. Создание массива INTEGER'ов на 10 млн. элементов хавает 57 мегабайт.

PS. Прошу вынести обсуждения странностей BB в отдельную ветку, тут не нужно это обсуждать, тут тихое мирное обсуждение проблем ghc и альтернатив ему, и поиск путей их решения.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 13:37 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Вообще, отсутствие переносимости кода между компиляторами говорит о незрелости языка.
Сам Хаскелл-98 и его библиотеки поддерживаются-то всеми трансляторами. Конкретно GHC является фактически лабораторией, в которой исследуются системы типов. Поэтому в GHC много расширений языка, которые, естественно, не поддерживаются другими трансляторами.
Скоро будут сам язык пересматривать, стандарт Haskell-2010 принимать. В него, как я понимаю, войдёт и обширная библиотека Haskell Platform.
Ну так любой язык время от времени пересматривается.
Вы хотите сказать, что С++ тоже незрелый язык, учитывая что нет двух полностью совместимых трансляторов для него?
А как ситуация с оберонами? Вот есть реализации того же CP -- Блэкбокс и GPCP (для .NET и JVM) -- насколько переносимы программы между ними?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 13:39 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Algo писал(а):
В императиве обсуждать было бы просто не чего.
А по-вашему в императиве нет проблем? Ну-ну... :lol:

И, кстати, экстраполировать странность одной из реализаций одного из языков на всю парадигму -- мягко говоря некорректно...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 13:49 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Сам Хаскелл-98 и его библиотеки поддерживаются-то всеми трансляторами. Конкретно GHC является фактически лабораторией, в которой исследуются системы типов. Поэтому в GHC много расширений языка, которые, естественно, не поддерживаются другими трансляторами.
Скоро будут сам язык пересматривать, стандарт Haskell-2010 принимать. В него, как я понимаю, войдёт и обширная библиотека Haskell Platform.

Ну вот и отлично. Собственно я лишь озвучил мнение самих хаскелистов относительно того же jhc и стандарта -- говорят в Haskell 98 слишком мало всего. Бедновато-с.

Geniepro писал(а):
Ну так любой язык время от времени пересматривается.
Вы хотите сказать, что С++ тоже незрелый язык, учитывая что нет двух полностью совместимых трансляторов для него?

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

Geniepro писал(а):
А как ситуация с оберонами? Вот есть реализации того же CP -- Блэкбокс и GPCP (для .NET и JVM) -- насколько переносимы программы между ними?

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

В общем, попробую поставить/собрать jhc И прогнать на нем тот пример со списком. Хотя, думается мне, он в том примере список честно создавать заленится ;-)

PS. Кстати, а как идет сборка у ghc? Оно в качестве бэкенда таки использует gcc, или же напрямую пишет бинарь? А то у меня такое ощущение что там собака порылась не на уровне хаскеля а где-то на уровне менеджера памяти, ибо std::list<int> lst(10000000) в точности также сжирает порядка 229 мег ОЗУ. Зато вот std::vector<int> vec(10000000) честно сжирает 38 мег, как ему и положено. Попробую мелкомягким компилятором сейчас, чтобы удостовериться что это не из за неких фенечек std::list'a так происходит.

PPS. Проверил. На мелкомягком компиляторе та же ситуация. Видимо аллокатор тут не причем. Таков сам по себе std::list.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 14:05 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
PS. Кстати, а как идет сборка у ghc? Оно в качестве бэкенда таки использует gcc, или же напрямую пишет бинарь?
В GHC можно указывать, как генерировать код -- через Си или через ассемблер. В разных тестах то один способ выдаёт более быстрый код, то другой...

Не знаю, как конкретно в памяти выглядят хаскельные списки, но сомневаюсь, что там используется std::list -- компилятора С++ там в стандартной поставке нет, отдельно добавлять нужно.

Задал вопрос по этой теме на ru_lambda, там ответили, что в списке целых тратится по 16 байт -- тогда должно быть 160 МБт. Так же припомнили, что в той же Java тратится по 12 байт на каждый объект (заголовок объекта), так что возможно и в хаскелле чуть ли не до 28 (ну пусть до 22) байт может дойти...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 14:11 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Самое смешное что банальный крестовый:
for (int i=0; i<10000000; ++i) new int;

Зохавывает 151 MiB ОЗУ.

Нифига не понимаю.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 14:33 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Такс. С плюсами разобрался.
new int хавает память:
1) указатель на начало выделенного куска памяти, указатель на конец куска памяти (чтобы манагер памяти знал какие куски у него уже выделены а какие нет). -- итого 4+4 = 8
2) Аллокатор по умолчанию (а при new int используется именно он) выделяет память не меньше 8ми байт (что логично). Итого имеем +8 байт.

16*10000000 = 152,59 MiB. Ч.т.д.

У оберонов видимо то же + затраты на сборщик мусора + невозможность подсунуть (не залазя глубоко в потроха) другой аллокатор.

В ghc видимо аналогично. И тут всплывает целесообразность использования в качестве внутренней структуры данных для последовательностей, именно списков...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 14:38 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Код:
MODULE Test123;

TYPE Item = INTEGER;
       List = RECORD item : Item; next : POINTER TO List END;

PROCEDURE  Do*;
VAR i: INTEGER;
      p, l, n: POINTER TO List;
BEGIN
  n := NIL;
   FOR i:=1 TO 10000000 DO
      NEW(p);
      p.item := i;
      p.next := n;
      n := p
   END;
   l := p
END Do;

END Test123.

^Q Test123.Do
160 МБт. Что я сделал не так?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 14:51 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Alexey Veselovsky писал(а):
Проблемы не у ФП вообще, а конкретно у ghc.
Хотите проблем в императиве? Пожалуйста: создание односвязного списка (пустого, т.е. каждый элемент не содержит ничего кроме ссылки на последующий) с 10 млн. элементами в BB хавает 176 Мегабайт памяти. Создание массива INTEGER'ов на 10 млн. элементов хавает 57 мегабайт.


Ну, у любого диспетчера памяти есть накладные расходы на служебные структуры - мы как-то редко считаем их, правда... А касательно массивов здоровых - всё равно задействуются служебные структуры и потери по страницам у ОС...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 14:59 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Цитата:
160 МБт. Что я сделал не так?


Вот моё:
Код:
MODULE PointerExample;

   IMPORT StdLog;

   TYPE   
      list = RECORD
         next : POINTER TO list;
      END;
         
   PROCEDURE Test*;
   VAR
      first : POINTER TO list;
      current : POINTER TO list;
      i : INTEGER;
   BEGIN
      NEW (first);
      current := first;
      i := 1;
      WHILE (i < 10000000) DO
           NEW(current.next);
           current := current.next;
           INC(i);
      END;
   END Test;   
END PointerExample.


При тестах следует учитывать что BB не возвращает в систему память. Совсем. Т.е. если мы запустили BB, что-то в нем поделали (оно откушало скажем N мег. озу), собрщик мусора потом всё это собрал, а потом мы запускаем наш тест, то мы увидим в виндовозном таскмане что тест скушал на M мег. озу, а M-N, где M истинное значение прожорливости теста.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 15:01 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Илья Ермаков писал(а):
Alexey Veselovsky писал(а):
Проблемы не у ФП вообще, а конкретно у ghc.
Хотите проблем в императиве? Пожалуйста: создание односвязного списка (пустого, т.е. каждый элемент не содержит ничего кроме ссылки на последующий) с 10 млн. элементами в BB хавает 176 Мегабайт памяти. Создание массива INTEGER'ов на 10 млн. элементов хавает 57 мегабайт.


Ну, у любого диспетчера памяти есть накладные расходы на служебные структуры - мы как-то редко считаем их, правда... А касательно массивов здоровых - всё равно задействуются служебные структуры и потери по страницам у ОС...


Ну, этта... Я не знаю какую чёрную магию использует gcc и msvc, но в плюсах std::vector<int> vec(10000000) -- отжирает ровно 38 мегабайт ОЗУ, как ему и положено.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 91 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB