OberonCore

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

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




Начать новую тему Ответить на тему  [ Сообщений: 35 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Способы "копирования" массивов
СообщениеДобавлено: Вторник, 02 Март, 2010 13:30 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Отделено: viewtopic.php?p=43760#p43760

AVC писал(а):
Но можно реализовать самостоятельно. Примерно так:
Кошмар, вообще-то...

Ведь для любой уважающей себя оси, копирование не делается - тусуют каталоги, и всего делов
В Mt, мне показалось, тоже копирование...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 13:51 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Galkov писал(а):
AVC писал(а):
Но можно реализовать самостоятельно. Примерно так:
Кошмар, вообще-то...

Ведь для любой уважающей себя оси, копирование не делается - тусуют каталоги, и всего делов
В Mt, мне показалось, тоже копирование...

Не судите строго. Я привел первый пришедший в голову алгоритм, исходя из предположения, что требуется массив, размещенный в памяти одним "куском".
Ровно такая же стратегия используется реализациями STL для векторов. Поэтому Скотт Мейерс в своей книге "Эффективное использование STL" и рекомендует пользоваться функцией reserve во избежание многократного перераспределения памяти и копирования (совет 14).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 13:58 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Да кто же судит-то... Самому страшно.
Понятно, что неправильно, а как правильно - непонятно :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 14:06 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Galkov писал(а):
Понятно, что неправильно, а как правильно - непонятно :)

Наверное, для достижения эффективности, реализация должна зависеть от предполагаемого использования.
(Т.е. одной единственной "правильной" реализации просто нет.)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 21:01 

Зарегистрирован: Суббота, 28 Январь, 2006 00:10
Сообщения: 52
Откуда: г. Киров
AVC писал(а):
Наверное, для достижения эффективности, реализация должна зависеть от предполагаемого использования.
(Т.е. одной единственной "правильной" реализации просто нет.)

В принципе, есть достаточно эффективаня для большинства случаев стратегия удвоения размера массива:
http://itblogs.ru/blogs/hitfounder/archive/2009/12/18/57021.aspx
Именно она чаще всего и используется (например в классе TList Delphi).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 22:15 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Алексей Елин писал(а):
Именно она чаще всего и используется (например в классе TList Delphi).

И в моем наброске тоже. :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 22:23 

Зарегистрирован: Суббота, 28 Январь, 2006 00:10
Сообщения: 52
Откуда: г. Киров
AVC писал(а):
И в моем наброске тоже. :)

Ну да, согласен.
Погуглил - .Net делает также. Просто при такой стратегии нет необходимости заморачиваться с перестановкой страниц для оптимизации копирования - дороже встанет.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 22:56 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Алексей Елин писал(а):
Просто при такой стратегии нет необходимости заморачиваться с перестановкой страниц для оптимизации копирования - дороже встанет.

Спасибо за полезную информацию!
Я прежде не задумывался о математическом обосновании "удвоения" массива, просто вставил в код "типовое" решение.
Теперь буду подходить к нему сознательнее. :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 23:23 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Алексей Елин писал(а):
Просто при такой стратегии нет необходимости заморачиваться с перестановкой страниц
Не говорите ерунду, уважаемый.
Добавьте один байт к 1Г-массиву и покопируйте, вместо "заморачивания". Которое, вообще-то говоря, уже давно предоставлено осью.
Ах, это надо делать один раз ??? Мои поздравления, в связи с отсутствием фантазий по постановке задач. А жизнь, вообще-то, богаче любых фантазий...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 23:32 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Полезна бы прямо на оборудовании структура такая - растущая строка байт. Вот недавно при встрече с Info21 обсуждали. Из разных задач вылезает.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 23:39 

Зарегистрирован: Суббота, 28 Январь, 2006 00:10
Сообщения: 52
Откуда: г. Киров
Galkov писал(а):
Добавьте один байт к 1Г-массиву и покопируйте, вместо "заморачивания".

Ну представим что добавил, и что? Менее чем ДВА раз на 1 миллиард операций добавления (считаем что операция 1-о байтная) произошло копирование массива по простейшему условию срванения двух переменных. И в будущем еще на 1 миллиард добавлений никаких копирований не предвидится.

А теперь просмотрим что будет при проверке выхода за границы 4 кб. страницы (архитектура х86) при каждом добавлении:
На 1 миллиард добавлений примерно 256000 пересечений границы страницы. При этом в сореднем 128000 раз придется переназначать маппинг этих же 128000 страниц на логические адреса и того примерно 16000000000 (т.е. 16 миллиардов) записей в таблицу маппинга страниц. И что быстрее?

Galkov писал(а):
Которое, вообще-то говоря, уже давно предоставлено осью.

Это вряд ли что то ускорит, скорее затормозит в результате SysCall-а через кольца защиты

Galkov писал(а):
Ах, это надо делать один раз ??? Мои поздравления, в связи с отсутствием фантазий по постановке задач. А жизнь, вообще-то, богаче любых фантазий...

Приведите пример где в ЖИЗНИ всречается преведенная вами версия List-а?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Вторник, 02 Март, 2010 23:53 

Зарегистрирован: Суббота, 28 Январь, 2006 00:10
Сообщения: 52
Откуда: г. Киров
Илья Ермаков писал(а):
Полезна бы прямо на оборудовании структура такая - растущая строка байт. Вот недавно при встрече с Info21 обсуждали. Из разных задач вылезает.

В голове вырисовывается лишь 2-х уровневая схема с дискрипторама наподобии 16-разрядной x86 архитекруры помноженной на страничную адресацию.
Тогда указатель будет состоять из фиксированного дискриптора и смещения в нем. Дискриптор может содержать (ссылаться на) собственную таблицу страниц памяти, которые могут добавляться по мере необходимости без необходимости "переставлять" ранее выделенные участки. Тогда вроде будет эффективно.

Есть ли еще какие идеи?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Среда, 03 Март, 2010 00:36 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Илья Ермаков писал(а):
Полезна бы прямо на оборудовании структура такая - растущая строка байт. Вот недавно при встрече с Info21 обсуждали. Из разных задач вылезает.

А можно немного подробнее?
Например, обязательна ли непрерывность области памяти для строки?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Среда, 03 Март, 2010 02:11 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Алексей Елин писал(а):
Ну представим что добавил, и что?
Много чего :wink: Например, ось Вам просто не даст два логических гига под один массив.
Но я вижу полное отсутстсвие фантазии даже про оперирование с одним массивом... Не говоря уже про два, три, и т.д..
Дельфи (вообще-то, речь идет о его модуле system) дураки сочиняли, наверное... А ведь они делают релокацию не только при увеличении строки, но и при уменьшении. Зачем-то.
Просто делают, не спрашивая, где в ЖИЗНИ это может пригодится.
Ты смотри, сами про ЖИЗНЬ догадались.
Сложно объяснять простые вещи, однако... :(


Алексей Елин писал(а):
А теперь просмотрим что будет при проверке выхода за границы 4 кб. страницы
Посмотрите.
Например, как это сделано в том же Дельфи. И найдите кого другого, кто быстрее со строками работает.
На практике, а не из некоторых якобы "рассуждений"
Вообще-то, никто не говорил, что "удвоение размеров" - глупость. Говорилось, что копирование при этом даже 4К - не эффективно.
Ремэпинг - быстрее, несмотря на страшные переходы на нулевое кольцо


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Среда, 03 Март, 2010 03:11 

Зарегистрирован: Суббота, 28 Январь, 2006 00:10
Сообщения: 52
Откуда: г. Киров
Galkov писал(а):
Вам просто не даст два логических гига под один массив.
В 32-ой виндовой программе выделить 2 гига нельзя, также как и 1 гиг. А вот ваша цитата:
Galkov писал(а):
Добавьте один байт к 1Г-массиву и покопируйте
т.е. ваш 1 гиг ок, а мои 2 - нет?

Galkov писал(а):
Но я вижу полное отсутстсвие фантазии даже про оперирование с одним массивом... Не говоря уже про два, три, и т.д..
Откуда взялось два, три и т.д. массивов. Вы вообще про что? про фантазии? Тогда наверно это не та тема. А я лишь про эффективность статегии удвоения.

Galkov писал(а):
Дельфи (вообще-то, речь идет о его модуле system) дураки сочиняли, наверное... А ведь они делают релокацию не только при увеличении строки, но и при уменьшении. Зачем-то.
Откуда всплылО уменьшение? За какие уши притянуто? Речь шла о добавлении элементов.

Galkov писал(а):
Просто делают, не спрашивая, где в ЖИЗНИ это может пригодится.
Ты смотри, сами про ЖИЗНЬ догадались.
Ха-ха. Написали какой то фигни (это я про создателей дельфи), даже не думая "Зачем это в ЖИЗНИ может пригодится." Вы хоть сами себя читаете?

Galkov писал(а):
Сложно объяснять простые вещи, однако... :(
Опять не понимаю про что вы?

Galkov писал(а):
Посмотрите. Например, как это сделано в том же Дельфи. И найдите кого другого, кто быстрее со строками работает. На практике, а не из некоторых якобы "рассуждений"
Представляете, я знаю ТОЧНО как это в дельфи работает. И да, я смотрел, много раз :) Дак вот - они КОПИРУЮТ если нет свободных страниц сразу после текущего блока памяти. А в реальной программе их (свободных страниц в конце блока) обычно нет.

И это я вас просил привести пример кто "быстрее работает". Не передергивайте. Я таких не знаю, хотя занимался этим вопросом. Если приведете - я буду признателен.

Galkov писал(а):
Вообще-то, никто не говорил, что "удвоение размеров" - глупость.
Ну спасибо хоть на этом.

Galkov писал(а):
Говорилось, что копирование при этом даже 4К - не эффективно.
Ремэпинг - быстрее, несмотря на страшные переходы на нулевое кольцо
При удвоении массива на каждый элемент в среднем приходится 1-но копирование (а максимум 2). Это очень мало.
И просто ремепинг в средах со сборкой мусора (.Net, Java, CP) делать нельзя. Почему? Да потому что указатель после ремапинга будет другой. Дальше объяснять?


Последний раз редактировалось Алексей Елин Четверг, 04 Март, 2010 20:58, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Среда, 03 Март, 2010 09:29 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Ребята, не горячитесь, пожалуйста!
Вы оба рассказали много интересного, за что вам спасибо.
"Ремэпинг" я первоначально даже не рассматривал (наш проц -- без MMU и прочих чудес техники).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Среда, 03 Март, 2010 09:45 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
AVC писал(а):
Илья Ермаков писал(а):
Полезна бы прямо на оборудовании структура такая - растущая строка байт. Вот недавно при встрече с Info21 обсуждали. Из разных задач вылезает.

А можно немного подробнее?
Например, обязательна ли непрерывность области памяти для строки?


Это должен быть аппаратный Files.File :) Как он там виртуалиться будет - дело техническое. Скорее всего, наращиванием или изъятием страниц.

(В структуре Эльбрусов такую поддержку вполне легко представить.)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Среда, 03 Март, 2010 14:32 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
AVC писал(а):
А можно немного подробнее?
Например, обязательна ли непрерывность области памяти для строки?
Я тоже думал над этим вопросом некоторое время назад (почитывая Дейкстру). Основное удобство непрерывной памяти массива для человека заключено в удобстве обращения к элементам. Есть адрес базы массива (начало), есть размер элемента. Обращение к нужному элементу производится с помощью операции "база + размер * порядковый_номер_ячейки". Если слежение за индексами массива сделать аппаратным, то необходимость в непрерывной области исчезает (или проблема хотя бы уменьшается).

А вообще, мысль была избавиться от сквозной адресации памяти вообще. Это атавизм, тянущийся с самого первого компьютера. Думаю, уже второй или третий компьютер использовали структуры данных, превыщающих размер одной ячейки, и классическая память перестала быть прозрачной в использовании.

Удобнее, чтобы контроллер памяти работал не со значениями адресов, а с переменными. Например, получить значение переменной prog1.var1 или записать значение в переменную prog4.var2[14]. Естественно, prog4.var2 должна иметь тип массив.

А введение в контроллер памяти переменных вида prog3.ptr6 незаметно избавит от необходимости сборки мусора. И вообще, введение указателей в контроллер памяти (а не в процессор, как это сделали в x86) может сократить объём данных, гоняемых между ОЗУ и процессором.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Среда, 03 Март, 2010 14:58 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Илья Ермаков писал(а):
Это должен быть аппаратный Files.File :) Как он там виртуалиться будет - дело техническое. Скорее всего, наращиванием или изъятием страниц.

Т.е. это должен быть файл (последовательность), который не пишется на диск (вероятно, временный файл для накопления и обработки каких-то данных "на лету")?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: аналог new ArrayList() (.NET)
СообщениеДобавлено: Среда, 03 Март, 2010 15:19 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Да. У нас в серверных приложениях, как я не раз рассказывал, всюду эти файлы в памяти. Всё на них. Основной контейнер и т.п.


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

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


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

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


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

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