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) |
Алексей Елин писал(а): Ну представим что добавил, и что? Много чего Например, ось Вам просто не даст два логических гига под один массив.Но я вижу полное отсутстсвие фантазии даже про оперирование с одним массивом... Не говоря уже про два, три, и т.д.. Дельфи (вообще-то, речь идет о его модуле 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/ |