OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Воскресенье, 17 Ноябрь, 2019 07:21

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




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

Зарегистрирован: Воскресенье, 08 Март, 2009 17:54
Сообщения: 372
Alexey Veselovsky писал(а):
Ну, этта... Я не знаю какую чёрную магию использует gcc и msvc, но в плюсах std::vector<int> vec(10000000) -- отжирает ровно 38 мегабайт ОЗУ, как ему и положено.

Если мне неизменяют мои слабые познания С++, внутреннее представление std::vector<...> - массив, а не список, от сюда и результат.


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

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Algo писал(а):
Alexey Veselovsky писал(а):
Ну, этта... Я не знаю какую чёрную магию использует gcc и msvc, но в плюсах std::vector<int> vec(10000000) -- отжирает ровно 38 мегабайт ОЗУ, как ему и положено.

Если мне неизменяют мои слабые познания С++, внутреннее представление std::vector<...> - массив, а не список, от сюда и результат.


Дык про массивы и шла речь:
Илья Ермаков писал(а):
А касательно массивов здоровых - всё равно задействуются служебные структуры и потери по страницам у ОС...


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

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

Ну опять же, как я Вам уже отмечал, никто Вас не вынуждает ограничиваться только списками...
Код:
import Data.Array.Unboxed

arr :: UArray Int Int
arr = listArray (1, 10000000) [1..]

main = do
    print $ arr ! 9999999

    putChar =<< getChar
82 МБ в памяти. Тип Int на самом деле, похоже хранится как указатель на значение в куче, поэтому массив занимает не 40 МБт, а 80...


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

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

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


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

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


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

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


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

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Alexey Veselovsky писал(а):
Вот моё:
Что-то я недопонял -- Ваш список не содержит в себе значения, а только ссылку на следующий элемент -- почему на него тратится столько же памяти, как и на мой?

Аа! Это видимо потому же почему и в плюсах -- стандартный аллокатор аллоцирует минимум 8 байт под элемент. Т.о. у нас получается место зарезервировано для себя и ещё для вон того парня, которого на самом деле нет.

Возможно в BB используется ещё более крупный кусок по умолчанию. Mожно поэкспериментировать ;-)


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

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Илья Ермаков писал(а):
А касательно массивов здоровых - всё равно задействуются служебные структуры и потери по страницам у ОС...
Речь, вероятно, о том, что при огромных массивах всё равно будут промахи в кеше и переключения контекстов всяких в ОС...


А толку? Это же ж не влияет на размер массива. А про быстродействие тут никто и не говорил. Только про размер. Про память.


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

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

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


Кстати, а попробуйте забить оный список случайными числами. Посмотрим, сумеет ли он это оптимизировать/пожать.


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

Зарегистрирован: Воскресенье, 08 Март, 2009 17:54
Сообщения: 372
Alexey Veselovsky писал(а):
Дык про массивы и шла речь:
Илья Ермаков писал(а):
А касательно массивов здоровых - всё равно задействуются служебные структуры и потери по страницам у ОС...

В основном то речь шла о списках, элементы которых отностительно небольшие.
Служебная информация в этом случае составляет большой процент.
С большими массивами такого быть не должно.
Посмотрел на результат распределения 10 млн. integer в D7. Ни каких сюрпризов.
Поискал в сети, похоже, что служебная информация занимает 4 байта, плюс, блоки выравниваются на границу 4 байта.
Ни каких увеличений в разы.
Скорее уж это не магия С++ или D7, а особенности BB.


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

Зарегистрирован: Воскресенье, 08 Март, 2009 17:54
Сообщения: 372
Geniepro писал(а):
Algo писал(а):
В императиве обсуждать было бы просто не чего.
А по-вашему в императиве нет проблем? Ну-ну... :lol:

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

Да я и не собираюсь так уж экстраполировать. Но всё равно, ситуация показательная:
1. Пример ТРИВИАЛЬНЫЙ.
2. Первое, интуитивное его решение на MAINSTREAM компиляторе не слабо засветившегося ФП языка, выдаёт ошибку.
3. Для ликвидации ошибки требуется глубокие знания языка и модификация решения в МЕНЕЕ простую форму.

Вывод: это острый камушек в огород ФП.
А на "кривую рожу" императива "пенять" не надо, ибо известно, что импратив - зло, но придёт светлое царствие ФП, простое и безпроблемное :)


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

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


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Algo писал(а):
...
2. Первое, интуитивное его решение на MAINSTREAM компиляторе не слабо засветившегося ФП языка, выдаёт ошибку.
3. Для ликвидации ошибки требуется глубокие знания языка и модификация решения в МЕНЕЕ простую форму.
Ну есть и более простая форма, и вообще нужно изучать стандартную библиотеку -- со стандартной функицией length никаких проблем нет! :lol:


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

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

Как так? даже для списка из нескольких элементов?


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

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

Как так? даже для списка из нескольких элементов?


Даже для списка из двух элементов заданых явно. Т.е. [1,2]
Для списка из одного элемента проблем нет ;-)
Видать что-то они там совсем жестко наоптимизировали. Надыть будет багрепорт накатать.


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

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


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

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


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Ужасно, ужасно всё это. Я вот попробовал на интерпретаторе YHC -- 100 тыс элементов проканало, на миллионе интерпретатор упал -- памяти, говорит, не хватает, нужно 32 кБт, а доступно только 30. И это на двух гигах ОЗУ... :lol:


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

Зарегистрирован: Воскресенье, 08 Март, 2009 17:54
Сообщения: 372
Geniepro писал(а):
Algo писал(а):
...
2. Первое, интуитивное его решение на MAINSTREAM компиляторе не слабо засветившегося ФП языка, выдаёт ошибку.
3. Для ликвидации ошибки требуется глубокие знания языка и модификация решения в МЕНЕЕ простую форму.
Ну есть и более простая форма, и вообще нужно изучать стандартную библиотеку -- со стандартной функицией length никаких проблем нет! :lol:

Получается, что программист должен
1) обязательно знать про указанную особенность компилятора
2) знать про хвостовую рекурсию и форсирование вычислений
3) знать стандартную библиотеку
4) в случае аналогичного, но сложного примера "увидеть" потенциальную проблему.

Очень, очень просто!
Как не сделать ошибку? Просто нужно всё знать и понимать и не делать ошибок!

Прокол это, локальный, но прокол. И это надо признать.


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9155
Откуда: Россия, Орёл
Alexey Veselovsky писал(а):
Создание массива INTEGER'ов на 10 млн. элементов хавает 57 мегабайт.


Я-то думал, и правда так. Проверил. Алексей, что-то Вы путаете.
Вложение:
bbmem.PNG
bbmem.PNG [ 50.17 КБ | Просмотров: 4222 ]


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

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


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

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


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

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