Неперемещаемые динамические массивы

[SeZuka]

Возможно ли сделать чтобы при изменении размера динамического массива с помощью SetLength, сам он не перемещался в памяти, т.е. указатель оставался неизменным?

[Mirage]

Нет, т.к. для увеличения размера может не хватить свободного места до следующего занятого куска.
Хотя от менеджера памяти зависит.

[debi12345]

Он вызывает LIBC/CRT "REALLOC" - там надо и смотреть.

[sign]

Закладываясь на постоянство указателя в памяти, вы закладываете мину в свою программу.

[SeZuka]

Закладываясь на постоянство указателя в памяти, вы закладываете мину в свою программу.

Уже наступил на эту мину, потому и спросил. Пока временно решил проблему выделением большего куска памяти сразу, без дальнейшего увеличения.

[zub]

>>Закладываясь на постоянство указателя в памяти, вы закладываете мину в свою программу.
Тут можно уточнить - "начиная писать программу вы закладываете мину в свою программу"))

SeZuka
динамический массив на то и придуман чтоб уйти от указателей. не храните адрес элемента, храните его индекс и всё будет ОК

[SeZuka]

не храните адрес элемента, храните его индекс и всё будет ОК

как один из вариантов решения, но это сильно усложняет конструкцию, см. далее

Оригинальный код с указателями:

Код: Выделить всё

var
  Strings: array of PChar; // массив с указателями на начало строки в хранилище
  Storage: array of Byte; // хранилище строк
  s: String;
  i: Integer;
  ...
begin
  ...
  s := Strings[i]; // получение строки по ее номеру
  ...

Код с индексами:

Код: Выделить всё

var
  Strings: array of Integer; // массив с индексами на начало строки в хранилище
  Storage: array of Byte; // хранилище строк
  s: String;
  i: Integer;
  ...
begin
  ...
  s := PChar(@Storage[Strings[i]]); // получение строки по ее номеру
  ...

Согласитесь Strings[i] куда понятней и проще чем PChar(@Storage[Strings[i]])

[zub]

ну извиняйте)) такова жизнь. либо обеспечить неперераспределение участка памяти (потеряв "динамичность" массива), либо обращаться к элементам массива общепринятыми безопасными способами

[Mirage]

s := Storage[i] подойдет?
Где Storage - класс, у которого есть default array property, выдающий строку по индексу.
Причем он же может как считать адрес по второму методу, так и по первому, автоматом производя фикс-ап указателей при изменении размера.
Единственное что, уже выданные строки могут стать невалидными при изменении размера. Хотя это проблема всех вариантов.

Я так понял, что данные строк почему-то хранятся в каком-то куске памяти, вместо того, чтобы просто управляться менеджером памяти.
В этом случае, у этого самого Storage возникает нетривиальная логика, которая до этого выполнялась менеджером памяти, и которую логично инкапсулировать в классе.

[SeZuka]

Я так понял, что данные строк почему-то хранятся в каком-то куске памяти, вместо того, чтобы просто управляться менеджером памяти.

Суть задачи: работа ведется с тысячами строк получаемых из файла, сначала создается массив строк в памяти, параллельно сортируясь по алфавиту, затем по ним ведется поиск, затем преобразования, ну и вывод в файл. Создание массива с сортировкой занимает примерно треть от всего объема алгоритма. Так вот заменив всего одну строчку отвечающую за копирование строки в массив:

Код: Выделить всё

  Strings[i] := StrNew(PChar(S));

на пару строк дополнительного кода:

Код: Выделить всё

   Strings[i] := @Storage[StoragePos];
  CopyMemory(Strings[i], PChar(S), Length(S)+1);
  Inc(StoragePos, Length(S)+1);

с индексами это выглядит так:

Код: Выделить всё

   Strings[i] := StoragePos;
  CopyMemory(@Storage[StoragePos], PChar(S), Length(S)+1);
  Inc(StoragePos, Length(S)+1);

То есть заменив тысячи выделений маленьких кусочков памяти под каждую строку, на один большой кусок где строки лежат друг за другом, получили уменьшение времени работы всего алгоритма в разы! Причем именно всего алгоритма, а не строки с копированием, само копирование ускорилось в десятки раз. Собственно основной тормоз здесь - это выделение памяти.

В этом случае, у этого самого Storage возникает нетривиальная логика, которая до этого выполнялась менеджером памяти, и которую логично инкапсулировать в классе.

Нет тут никакой нетривиальной логики, есть указатель на начало свободной памяти, при копировании очередной строки он просто перемещается на ее конец (см. код), и если очередная строка выходит за пределы, то просто увеличивается размер Storage, при помощи SetLength, вот и все.

[Vapaamies]

Создание массива с сортировкой занимает примерно треть от всего объема алгоритма.

И правильно, ибо нефиг. Двоичные деревья именно для этого и придумали.

То есть заменив тысячи выделений маленьких кусочков памяти под каждую строку, на один большой кусок где строки лежат друг за другом, получили уменьшение времени работы всего алгоритма в разы!

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

[Mirage]

Странно это. Какой менеджер памяти используется?
Для FastMM, например, выделить тысячи кусков памяти для строк не проблема.
Тут либо менеджер памяти сильно тормозит, либо алгоритм больше ничего не делает, кроме выделения памяти.

Память можно вообще не выделять, а замапить файл в память. В этом случае, кусок с данными будет иметь один и тот же адрес.
Останется только пройтись и построить массив Strings[].

Если же маппинг файла не подходит, то остается подход с созданием специализированного менеджера памяти. Который, собственно, и применяется по всей видимости. Просто автор этого не осознает.
Но нетривиальная логика у такого менеджера таки имеется, т.к. без оной решение не работает, о чем, собственно, топик.
Надо отслеживать изменения расположения данных и учитывать это, производя корректировку указателей.
Можно, кстати, хранить относительные указатели, тогда при выдаче строки можно просто сложить адрес массива-хранилища и относительный указатель.

Но спрятать это все за интерфейсом очень стоит, т.к. это например позволяет начать с тривиальной реализации, с очень большим массивом фиксированного размера. А потом оптимизировать реализацию хранилища, не трогая основной код. Если понадобится.

[debi12345]

Хм... А когда происходит ресайзинг массива (инвалидирующий шифты от начала массива )? В отдельном треде пареллельно работе алгоритма ?

[Kemet]

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

[SeZuka]

Двоичные деревья именно для этого и придумали.

Ну а я по вашему методом пузырька что ли сортирую? 10 операций сравнения для 1000 строк и строка стоит в нужном месте.

Странно это. Какой менеджер памяти используется?

Стандартный. FastMM не пробовал.

либо алгоритм больше ничего не делает, кроме выделения памяти

Алгоритм создает словарь для текста, затем для этого же текста выводит в файл уже коды из словаря.

Память можно вообще не выделять, а замапить файл в память.

Была такая мысль, но так как еще имеется предварительное преобразование регистра текста, пока от нее отказались.

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

Решение было написано менее чем за 5 минут, просто прилетела мысль и захотелось попробовать, из плюсов сильно порадовала скорость работы, из минусов - на больших объемах рушились данные, как выяснилось из-за ресайза хранилища, указатели на строки оставались, а сами строки перемещались в памяти. Почему собственно и создал топик, думал может есть какое-нибудь "волшебное" слово типа fixed или static для динамических массивов.

Можно, кстати, хранить относительные указатели, тогда при выдаче строки можно просто сложить адрес массива-хранилища и относительный указатель.

Так это тоже самое что и индексы, на которые кстати все и переделал.

Хм... А когда происходит ресайзинг массива (инвалидирующий шифты от начала массива )? В отдельном треде пареллельно работе алгоритма ?

Все в одном треде. Перед копированием строки проверяется, влезет ли она в остаток хранилища, если нет, то хранилище расширяется.