OberonCore
https://forum.oberoncore.ru/

Способы "копирования" массивов
https://forum.oberoncore.ru/viewtopic.php?f=27&t=2417
Страница 1 из 2

Автор:  Galkov [ Вторник, 02 Март, 2010 13:30 ]
Заголовок сообщения:  Способы "копирования" массивов

Отделено: viewtopic.php?p=43760#p43760

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

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

Автор:  AVC [ Вторник, 02 Март, 2010 13:51 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

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

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

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

Автор:  Galkov [ Вторник, 02 Март, 2010 13:58 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Да кто же судит-то... Самому страшно.
Понятно, что неправильно, а как правильно - непонятно :)

Автор:  AVC [ Вторник, 02 Март, 2010 14:06 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Galkov писал(а):
Понятно, что неправильно, а как правильно - непонятно :)

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

Автор:  Алексей Елин [ Вторник, 02 Март, 2010 21:01 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

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

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

Автор:  AVC [ Вторник, 02 Март, 2010 22:15 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Алексей Елин писал(а):
Именно она чаще всего и используется (например в классе TList Delphi).

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

Автор:  Алексей Елин [ Вторник, 02 Март, 2010 22:23 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

AVC писал(а):
И в моем наброске тоже. :)

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

Автор:  AVC [ Вторник, 02 Март, 2010 22:56 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Алексей Елин писал(а):
Просто при такой стратегии нет необходимости заморачиваться с перестановкой страниц для оптимизации копирования - дороже встанет.

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

Автор:  Galkov [ Вторник, 02 Март, 2010 23:23 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

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

Автор:  Илья Ермаков [ Вторник, 02 Март, 2010 23:32 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Полезна бы прямо на оборудовании структура такая - растущая строка байт. Вот недавно при встрече с Info21 обсуждали. Из разных задач вылезает.

Автор:  Алексей Елин [ Вторник, 02 Март, 2010 23:39 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Galkov писал(а):
Добавьте один байт к 1Г-массиву и покопируйте, вместо "заморачивания".

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

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

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

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

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

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

Автор:  Алексей Елин [ Вторник, 02 Март, 2010 23:53 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Илья Ермаков писал(а):
Полезна бы прямо на оборудовании структура такая - растущая строка байт. Вот недавно при встрече с Info21 обсуждали. Из разных задач вылезает.

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

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

Автор:  AVC [ Среда, 03 Март, 2010 00:36 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Илья Ермаков писал(а):
Полезна бы прямо на оборудовании структура такая - растущая строка байт. Вот недавно при встрече с Info21 обсуждали. Из разных задач вылезает.

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

Автор:  Galkov [ Среда, 03 Март, 2010 02:11 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

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


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

Автор:  Алексей Елин [ Среда, 03 Март, 2010 03:11 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Galkov писал(а):
Вам просто не даст два логических гига под один массив.
В 32-ой виндовой программе выделить 2 гига нельзя, также как и 1 гиг. А вот ваша цитата:
Galkov писал(а):
Добавьте один байт к 1Г-массиву и покопируйте
т.е. ваш 1 гиг ок, а мои 2 - нет?

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

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

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

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

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

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

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

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

Автор:  AVC [ Среда, 03 Март, 2010 09:29 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Ребята, не горячитесь, пожалуйста!
Вы оба рассказали много интересного, за что вам спасибо.
"Ремэпинг" я первоначально даже не рассматривал (наш проц -- без MMU и прочих чудес техники).

Автор:  Илья Ермаков [ Среда, 03 Март, 2010 09:45 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

AVC писал(а):
Илья Ермаков писал(а):
Полезна бы прямо на оборудовании структура такая - растущая строка байт. Вот недавно при встрече с Info21 обсуждали. Из разных задач вылезает.

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


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

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

Автор:  Valery Solovey [ Среда, 03 Март, 2010 14:32 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

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

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

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

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

Автор:  AVC [ Среда, 03 Март, 2010 14:58 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

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

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

Автор:  Илья Ермаков [ Среда, 03 Март, 2010 15:19 ]
Заголовок сообщения:  Re: аналог new ArrayList() (.NET)

Да. У нас в серверных приложениях, как я не раз рассказывал, всюду эти файлы в памяти. Всё на них. Основной контейнер и т.п.

Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/